Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Bill Dubuque Nov 2 '12 at 16:59
add comment

2 Answers

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".

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.