0
$\begingroup$

So I was just given the definition of a signature:

A signature is a pair $\Sigma = (\Omega, \Pi)$ where $\Omega$ is a set of operation symbols $\omega$, each equipped with an arity $\alpha(\omega)\in\mathbb{N}$ and $\Pi$ is a set of relation symbols $\pi$, each equipped with an arity $\alpha(\pi)\in\mathbb{N}$.

And I saw the term "first order signature" after this without any previous context. Can anyone tell me what is a "first order signature"? Thanks a lot.

  • 2
    Probably "first-order" is used there to emphasize that the operations and relations are not higher-order, i.e. they are defined on powers of the carrier, not on powersets (and iterations thereof), i.e. they operate on elements of the carrier, not subsets.2012-11-02

2 Answers 2

2

In set theory, there is only one nonlogical symbol, the set membership relation $\in$. In Peano arithmetic, there are several nonlogical symbols: the addition symbol $+$, the multiplication symbol $\cdot$, and the order relation $<$. Each formal theory in first-order logic has a specific set of nonlogical symbols that is uses. This collection is called the signature of the theory. It can have function symbols (like the addition symbol in Peano arithmetic) as well as relation symbols (like the order relation symbol). In general, each function symbol can have its own arity, and each relation symbol can have its own arity. The "first order" term in "first order signature" usually just means the author is working in first-order logic, where every signature is a "first order signature".

0

Bill Dubuque's comment provides the answer.

Say an operation or function is first-order if it maps objects in the relevant domain to objects. (Some operations are higher-order, e.g. mapping functions to functions, e.g. the operation that takes a function to its inverse).

Say a relation is first-order if it relates objects in the domain. (Some relations are higher-order, e.g. relating functions to functions, e.g. the relation two functions have if they form a Galois connection.)

To say that a signature is first-order means that all the operation (function) symbols are symbols for first-order functions, and the relational symbols are all symbols for first-order relations.