Signature (logic)

Formally, a (single-sorted) signature can be defined as a 4-tuple ${\displaystyle \sigma =\left(S_{\operatorname {func} },S_{\operatorname {rel} },S_{\operatorname {const} },\operatorname {ar} \right),}$ where ${\displaystyle S_{\operatorname {func} }}$ and ${\displaystyle S_{\operatorname {rel} }}$ are disjoint sets not containing any other basic logical symbols, called respectively


and a function ${\displaystyle \operatorname {ar} :S_{\operatorname {func} }\cup S_{\operatorname {rel} }\to \mathbb {N} }$ which assigns a natural number called arity to every function or relation symbol. A function or relation symbol is called ${\displaystyle n}$-ary if its arity is ${\displaystyle n.}$ Some authors define a nullary (${\displaystyle 0}$-ary) function symbol as constant symbol, otherwise constant symbols are defined separately.


A signature with no function symbols is called a relational signature, and a signature with no relation symbols is called an algebraic signature.^[1] A finite signature is a signature such that ${\displaystyle S_{\operatorname {func} }}$ and ${\displaystyle S_{\operatorname {rel} }}$ are finite. More generally, the cardinality of a signature ${\displaystyle \sigma =\left(S_{\operatorname {func} },S_{\operatorname {rel} },S_{\operatorname {const} },\operatorname {ar} \right)}$ is defined as ${\displaystyle |\sigma |=\left|S_{\operatorname {func} }\right|+\left|S_{\operatorname {rel} }\right|+\left|S_{\operatorname {const} }\right|.}$


The language of a signature is the set of all well formed sentences built from the symbols in that signature together with the symbols in the logical system.

Use of signatures in logic and algebra[edit]

In the context of first-order logic, the symbols in a signature are also known as the non-logical symbols, because together with the logical symbols they form the underlying alphabet over which two formal languages are inductively defined: The set of terms over the signature and the set of (well-formed) formulas over the signature.


In a structure, an interpretation ties the function and relation symbols to mathematical objects that justify their names: The interpretation of an ${\displaystyle n}$-ary function symbol ${\displaystyle f}$ in a structure ${\displaystyle \mathbf {A} }$ with domain ${\displaystyle A}$ is a function ${\displaystyle f^{\mathbf {A} }:A^{n}\to A,}$ and the interpretation of an ${\displaystyle n}$-ary relation symbol is a relation ${\displaystyle R^{\mathbf {A} }\subseteq A^{n}.}$ Here ${\displaystyle A^{n}=A\times A\times \cdots \times A}$ denotes the ${\displaystyle n}$-fold cartesian product of the domain ${\displaystyle A}$ with itself, and so ${\displaystyle f}$ is in fact an ${\displaystyle n}$-ary function, and ${\displaystyle R}$ an ${\displaystyle n}$-ary relation.