Definition:Signature (Logic)

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\LL$ be a formal language.

A choice of vocabulary for $\LL$ is called a signature for $\LL$.


Signature for Predicate Logic

Let $\LL_1$ be the language of predicate logic.


Then a signature for $\LL_1$ is an explicit choice of the alphabet of $\LL_1$.

That is to say, it amounts to choosing, for each $n \in \N$:

A collection $\FF_n$ of $n$-ary function symbols
A collection $\PP_n$ of $n$-ary relation symbols

It is often conceptually enlightening to explicitly address the $0$-ary function symbols separately, as constant symbols.


Also known as

Some sources refer to a signature as a lexicon.

Others call it a language, particularly in the field of model theory.

However, this is easy to conflate with the generic formal language, and therefore discouraged on $\mathsf{Pr} \infty \mathsf{fWiki}$.


Also see