List of first-order theories


In first-order 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.

Preliminaries

For every natural mathematical structure there is a signature σ listing the constants, functions, and relations of the theory together with their arities, 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:
  1. List or describe a set of sentences in the language Lσ, called the axioms of the theory.
  2. Give a set of σ-structures, and define a theory to be the set of sentences in Lσ holding in all these models. For example, the "theory of finite fields" consists of all sentences in the language of fields that are true in all finite fields.
An Lσ theory may:
The signature of the pure identity theory is empty, with no functions, constants, or relations.
Pure identity theory has no 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:
  • ∃x1 ∃x2 ¬x1 = x2,    ∃x1 ∃x2 ∃x3 ¬x1 = x2 ∧ ¬x1 = x3 ∧ ¬x2 = x3,...
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 σ or to ¬σ for some finite subset N of the non-negative integers, where σ 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. The complete theories are the theories of sets of cardinality n for some finite n, and the theory of infinite sets.
One special case of this is the inconsistent theory defined by the axiom ∃x ¬x = x. It is a perfectly good theory with many good properties: it is complete, decidable, finitely axiomatizable, and so on. The only problem is that it has no models at all. By Gödel's completeness theorem, it is the only theory with no models. It is not the same as the theory of the empty set : the theory of the empty set has exactly one model, which has no elements.

Unary relations

A set of unary relations Pi for i in some set I is called independent if for every two disjoint finite subsets A and B of I there is some element x such that Pi is true for i in A and false for i in B. Independence can be expressed by a set of first-order statements.
The theory of a countable number of independent unary relations is complete, but has no atomic models. It is also an example of a theory that is superstable but not totally transcendental.

Equivalence relations

The signature of equivalence relations has one binary infix relation symbol ~, no constants, and no functions. Equivalence relations satisfy the axioms:
  • Reflexive ∀x ''x~x'';
  • Symmetric ∀x ∀y ''x~y'' → y~''x;
  • Transitive: ∀x'' ∀y ∀z → x~''z.
Some first-order properties of equivalence relations are:
The theory of an equivalence relation with exactly 2 infinite equivalence classes is an easy example of a theory which is ω-categorical but not categorical for any larger cardinal.
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.
The following constructions are sometimes used to produce examples of theories with certain spectra; in fact by applying them to a small number of explicit theories T one gets examples of complete countable theories with all possible uncountable spectra. 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.

Orders

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:
  • Transitive: ∀x ∀y ∀z '' ∧ → x'' ≤ z
  • Reflexive: ∀x ''x ≤ x''
  • Antisymmetric: ∀x ∀y '' ∧ → x'' = y
  • Partial: Transitive ∧ Reflexive ∧ Antisymmetric;
  • Linear : Partial ∧ ∀x ∀y '' ∨
  • Dense : ∀x'' ∀z '' → ∃y '' ∧
  • There is a smallest element: ∃x'' ∀y ''
  • There is a largest element: ∃x ∀y ''
  • Every element has an immediate successor: ∀x ∃y ∀z '' ↔
The theory DLO of dense linear orders without endpoints 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:
  • Smallest but no largest element;
  • Largest but no smallest element;
  • Largest and smallest element.
Being well ordered 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 ∨. The two approaches can be related by defining a ≤ b to mean a∧b = a.
For two binary operations the axioms for a lattice are:
For one relation ≤ the axioms are:
  • Axioms stating ≤ is a partial order, as above.
First-order properties include:
Heyting algebras can be defined as lattices with certain extra first-order properties.
Completeness is not a first-order property of lattices.

Graphs

The signature of graphs has no constants or functions, and one binary relation symbol R, where R is read as "there is an edge from x to y".
The axioms for the theory of graphs are
  • Symmetric: ∀x ∀y ''R→ R''
  • Anti-reflexive: ∀x ¬R
The theory of random graphs has the following extra axioms for each positive integer n:
  • For any two disjoint finite sets of size n, there is a point joined to all points of the first set and to no points of the second set.
The theory of random graphs is ω categorical, complete, and decidable, and its countable model is called the Rado graph. A statement in the language of graphs is true in this theory if and only if the probability that an n-vertex random graph models the statement tends to 1 in the limit as n goes to infinity.