This entry lists some of the more common examples used in model theory and some of their properties.
One of the few interesting properties that can be stated in the language of pure identity theory is that of being infinite.
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.
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.
(There are no theories whose models are exactly sets of cardinality N if N is an infinite subset of the integers.)
The theory of a countable number of independent unary relations is complete, but has no atomic models.
The equivalence relation ~ should not be confused with the identity symbol '=': if x=y then x~y, but the converse is not necessarily true.
Theories of equivalence relations are not all that difficult or interesting, but often give easy examples or counterexamples for various statements.
If T is a theory in some language, we define a new theory 2T by adding a new binary relation to the language, and adding axioms stating that it is an equivalence relation, such that there are an infinite number of equivalence classes all of which are models of T. It is possible to iterate this construction transfinitely: given an ordinal α, define a new theory by adding an equivalence relation Eβ for each β<α, together with axioms stating that whenever β<γ then each Eγ equivalence class is the union of infinitely many Eβ equivalence classes, and each E0 equivalence class is a model of T. Informally, one can visualize models of this theory as infinitely branching trees of height α with models of T attached to all leaves.
The signature of orders has no constants or functions, and one binary relation symbols ≤.
We define x ≥ y, x < y, x > y as abbreviations for y ≤ x, x ≤ y ∧¬y ≤ x, y < x, Some first-order properties of orders: The theory DLO of dense linear orders without endpoints (i.e. no smallest or largest element) is complete, ω-categorical, but not categorical for any uncountable cardinal.
There are three other very similar theories: the theory of dense linear orders with a: Being well ordered ("any non-empty subset has a minimal element") is not a first-order property; the usual definition involves quantifying over all subsets.
Lattices can be considered either as special sorts of partially ordered sets, with a signature consisting of one binary relation symbol ≤, or as algebraic structures with a signature consisting of two binary operations ∧ and ∨.
For two binary operations the axioms for a lattice are: For one relation ≤ the axioms are: First-order properties include: Heyting algebras can be defined as lattices with certain extra first-order properties.
The signature of graphs has no constants or functions, and one binary relation symbol R, where R(x,y) is read as "there is an edge from x to y".
In other words, the values of these invariants classify the possible completions of the theory of Boolean algebras.
So the possible complete theories are: The signature of group theory has one constant 1 (the identity), one function of arity 1 (the inverse) whose value on t is denoted by t−1, and one function of arity 2, which is usually omitted from terms.
The class of structures satisfying such a theory has the property of being closed under substructure.
The theory ACFp has a universal domain property, in the sense that every structure N satisfying the universal axioms of ACFp is a substructure of a sufficiently large algebraically closed field
For technical reasons to do with quantifier elimination, it is sometimes more convenient to force the constant field to be perfect by adding a new symbol r to the signature with the axioms The theory of the natural numbers with a successor function has signature consisting of a constant 0 and a unary function S ("successor": S(x) is interpreted as x+1), and has axioms: The last axiom (induction) can be replaced by the axioms The theory of the natural numbers with a successor function is complete and decidable, and is κ-categorical for uncountable κ but not for countable κ. Presburger arithmetic is the theory of the natural numbers under addition, with signature consisting of a constant 0, a unary function S, and a binary function +.
This is no longer true for most of the following theories; they can usually encode both multiplication and addition of natural numbers, and this gives them enough power to encode themselves, which implies that Gödel's incompleteness theorem applies and the theories can no longer be both complete and recursively enumerable (unless they are inconsistent).
Axioms: IΣn is first-order Peano arithmetic with induction restricted to Σn formulas (for n = 0, 1, 2, ...).
Exponential function arithmetic (EFA) is IΣ0 with an axiom stating that xy exists for all x and y (with the usual properties).
For the real numbers, the situation is slightly different: The case that includes just addition and multiplication cannot encode the integers, and hence Gödel's incompleteness theorem does not apply.
The usual signature of set theory has one binary relation ∈, no constants, and no functions.