Signatures

A signature determines the set of symbols which can be used in first-order formulas.

Example In the article on logic a situation is described where people can be barbers and can shave one another. This can be modelled by a unary prediacte that describes whether someone is a barber and a binary predicate which describes who shaves who. A good naming convention would be to say that $B$ stands for the "is barber" predicate and $S$ for the "shaves" relation. The signature would then consist of these two symbols.

Example In a situation where one wants to speak about the natural numbers (arithmetic), it is important to be able to speak about addition and multiplication. It may come in handy to have available concrete numbers such as $0$ and $1$ as well as the "less than" relation. The signature would consist of binary function symbols $\text{add}$ and $\text{mult}$, symbols $\text{zero}$ and $\text{one}$ for constants, and one binary relation symbol $\text{Lt}$.

Sorted signatures, which are alluded to in the next example, is a topic on its own.

Example In a situation where one has a list of names of persons and birthdays for them, a binary relation "born on" could be used to model it. Unlike in the previous example, the elements in the first position of the binary relation are different from the elements in the second position: names vs. dates. The signature would then consists of a single symbol $B$ for the "born on" relation and one would further specify that there is a sort for the first component and another sort for the second component.

Formal definition

A signature $\mathcal S$ consists of a set $S$ of symbols together with a function $\Sigma \colon S \to \mathbf N \cup \mathbf N \times \{1\}$.

The elements of $S$ are called symbols and are classified as follows:

• A symbol $f$ with $\Sigma(f) = \langle n, 1\rangle$ for $n > 0$ is a function symbol. The set of these symbols is denoted $\mathcal F_\Sigma$ or simply $\mathcal F$.
• A symbol $R$ with $\Sigma(R) = n$ for $n > 0$ is a relation symbol. The set of these symbols is denoted $\mathcal R_\Sigma$ or simply $\mathcal R$.
• A symbol $c$ with $\Sigma(c) = \langle 0,1\rangle$ is a constant symbol (symbol for a constant). The set of these symbols is denoted $\mathcal C_\Sigma$ or simply $\mathcal C$.
• A symbol $b$ with $\Sigma(b) = 0$ is a boolean symbol (symbol for a boolean value). The set of these symbols is denoted $\mathcal B_\Sigma$ or simply $\mathcal B$.

In general, signatures with $\mathcal B \neq \emptyset$ are ignored.

Clearly, the set $S$ can be deduced from $\Sigma$. So, in principle, it is enough to work with $\Sigma$ only or one identifies $\mathcal S$ and $\Sigma$.

Example The first and the second example above give rise to different signatures. In the first example, an appropriate choice is: \begin{align} S & = \{B, S\} \end{align} and \begin{align} \Sigma = \{B \mapsto 1, S \mapsto 2\} \enspace. \end{align} In the second example, an appropriate choice is: \begin{align} S & = \{\text{zero}, \text{one}, \text{add}, \text{mult}, \text{Lt}\} \end{align} and \begin{align} \Sigma = \{\text{zero} \mapsto \langle 0,1\rangle, \text{one} \mapsto \langle 0,1\rangle, \text{add} \mapsto \langle 2,1\rangle, \text{mult} \mapsto \langle 2,1\rangle, \text{Lt} \mapsto 2\} \enspace. \end{align}

Simplified notation

The formal specification of a signature using a function $\Sigma$ is often clumsy. A simpler notation is introduced in the following.

Example Here is a simple way of writing the above signature for working with the natural numbers: \begin{align} \mathcal S = \{\text{zero}, \text{one}, \text{add}/\!/2, \text{mult}/\!/2, \text{Lt}/2\} \enspace. \end{align}

So symbols listed without any decoration are constant symbols, symbols listed in the form $f/\!/n$ are function symbols of arity $n$, and symbols listed in the form $R/n$ are relation symbols of arity $n$.

Mathematical symbols in signatures

In mathematics, symbols such as $0$, $1$, $+$, and $\cdot$ are used and are typically interpreted in a fixed fashion in a given context. When one is concerned with the natural numbers, then $0$ stands for the natural number $0$ and $+$ stands for the addition of natural numbers.

It is good to distinguish between the above symbols from mathematics from the symbols used in mathematical logic. We simply add a dot on top.

Example Another signature for working with the natural numbers: $$\Sigma = \{\dot 0, \dot 1, \dot{+}/\!/2, \dot{\cdot}/\!/2, {\dot <}/2\}\enspace.$$

Classification of signatures

In algebra, in many cases relations do not play any role. Signatures with $\mathcal R = \emptyset$ are called algebraic signatures.

Example The signatures $\{\text{mult}/\!/2\}$ and $\{\text{one}, \text{inv}/\!/1, \text{mult}/\!/2\}$ are algebraic signatures for working with groups. The first one can also be used for groupoids and monoids.

In other contexts, function symbols do not play any role. Signatures with $\mathcal F = \emptyset$ are called relational signatures.

Example The signature $\{\text{Edge}/2\}$ is a good relation for working with graphs. When, for instance, a source and a target are specified, then $\{\text{src}, \text{tgt}, \text{Edge}/2\}$ would be a good signature. Both are relational signatures.

If one wants to have short symbols, one could work with $\{E/2\}$ and $\{s, t, E/2\}$ as well.

Commonly used signatures

There is a list of commonly used signatures.