First order theory

In mathematical logic, a first-order theory is given by a set of axioms in some language. This entry lists some of the more common examples used in model theory and some of their properties.

For every natural mathematical structure there is a signature σ listing the constants, functions, and relations of the theory together with their valences, so that the object is naturally a σ-structure. Given a signature σ there is a unique first-order language L_σ that can be used to capture the first-order expressible facts about the σ-structure.

There are two common ways to specify theories:

An L_σ theory may:

The signature of the pure identity theory is empty, with no functions, constants, or relations.

Pure identity theory has no (non-logical) axioms. It is decidable.

One of the few interesting properties that can be stated in the language of pure identity theory is that of being infinite. This is given by an infinite set of axioms stating there are at least 2 elements, there are at least 3 elements, and so on:

These axioms define the theory of an infinite set.

The opposite property of being finite cannot be stated in first-order logic for any theory that has arbitrarily large finite models: in fact any such theory has infinite models by the compactness theorem. In general if a property can be stated by a finite number of sentences of first-order logic then the opposite property can also be stated in first-order logic, but if a property needs an infinite number of sentences then its opposite property cannot be stated in first-order logic.

Any statement of pure identity theory is equivalent to either σ(N) or to ¬σ(N) for some finite subset N of the non-negative integers, where σ(N) is the statement that the number of elements is in N. It is even possible to describe all possible theories in this language as follows. Any theory is either the theory of all sets of cardinality in N for some finite subset N of the non-negative integers, or the theory of all sets whose cardinality is not in N, for some finite or infinite subset N of the non-negative integers. (There are no theories whose models are exactly sets of cardinality N if N is an infinite subset of the integers.) The complete theories are the theories of sets of cardinality n for some finite n, and the theory of infinite sets.

...
Wikipedia