Signature (logic)

In mathematical logic, a signature specifies the non-logical symbols of a formal language. In universal algebra, it lists the operations that define an algebraic structure. Model theory uses signatures for both of these purposes, though they are seldom made explicit in more philosophical discussions of logic.

Formally, a single-sorted signature is a 4-tuple consisting of a set of function symbols, a set of relation symbols, a set of constant symbols, and an arity function. This arity function assigns a natural number to each function or relation symbol, indicating how many arguments it takes. A symbol with arity \(n\) is called \(n\)-ary. Some authors treat nullary (0-ary) function symbols as constant symbols, while others list constants separately. A signature with no function symbols is relational, and one with no relation symbols is algebraic. A finite signature has finite sets of function and relation symbols. The cardinality of a signature is the total number of symbols in its three sets. The language of a signature consists of all well-formed sentences built from its symbols plus the logical symbols.

In universal algebra, the term "type" or "similarity type" is often used instead of "signature." In model theory, a signature is frequently called a vocabulary or is identified with the first-order language \(L\) it supplies with non-logical symbols. However, the language \(L\) always has infinite cardinality—if the signature is finite, the language's cardinality is \(\aleph_0\). Because the formal definition is cumbersome in practice, specific signatures are often given informally, such as "the standard signature for abelian groups is \(\sigma = (+,-,0)\), where \(-\) is a unary operator." Sometimes an algebraic signature is treated simply as a list of arities.