Signature (Logic)

logic

Definition

Signature

A signature is a tuple $(\mathcal{F},\mathcal{P})$ consisting of a set of function symbols $\mathcal{F}$ and a set of predicate symbols $\mathcal{P}$. Each symbol is associated with a non-negative integer called its arity.

The signature defines the non-logical symbols of a first-order language.

Components

Function Symbols

The set $\mathcal{F}$ contains symbols used to represent functions within the universe.

• A symbol $f/n\in \mathcal{F}$ represents a function mapping $n$ elements to a single element.
• Constants: Functions with arity 0 ($f/0\in \mathcal{F}$) are called constants.

Predicate Symbols

The set $\mathcal{P}$ contains symbols used to represent relations or properties.

• A symbol $P/n\in \mathcal{P}$ represents an $n$-ary relation.
• Propositions: Predicates with arity 0 ($P/0\in \mathcal{P}$) are called propositions, effectively reducing the logic to propositional logic for these symbols.

Arity Notation

It is common to denote the arity of a symbol $S$ as $S/n$, where $n$ is the number of arguments the symbol accepts.

Example

The signature for an ordered ring might be defined as:

$$\Sigma =(\{+/2,\cdot /2,0/0,1/0\},\{</2\})$$

where:

• $+$, $\cdot$ are binary functions.
• $0$, $1$ are constants (arity 0 functions).
• $<$ is a binary predicate.