In mathematical logic, a firstorder 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.
Contents 
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 firstorder language L_{σ} that can be used to capture the firstorder expressible facts about the σstructure.
There are two common ways to specify theories:
A L_{σ} theory may:
The signature of the pure identity theory is empty, with no functions, constants, or relations.
Pure identity theory has no (nonlogical) 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 firstorder 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 firstorder logic then the opposite property can also be stated in firstorder logic, but if a property needs an infinite number of sentences then its opposite property cannot be stated in firstorder logic.
Any statement of pure identity theory is equivalent to either σ(N) or to ¬σ(N) for some finite subset N of the nonnegative 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 nonnegative integers, or the theory of all sets whose cardinality is not in N, for some finite or infinite subset N of the nonnegative 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.
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 (for any given language) with no models.
A set of unary relations P_{i} 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 P_{i}(x) is true for i in A and false for i in B. Independence can be expressed by a set of firstorder 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.
The signature of equivalence relations has one binary infix relation symbol ~, no constants, and no functions. Equivalence relations satisfy the axioms:
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 2^{T} 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 E_{0} 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 ≤. (It is of course possible to use ≥, < or > instead as the basic relation, with the obvious minor changes to the axioms.) We define x≥y, x<y, x>y as abbreviations for y≤x, x≤y ∧¬y≤x, y<x,
Some firstorder properties of orders:
The theory DLO of dense linear orders with no endpoints (i.e. no smallest or largest element) is complete, ωcategorical, but not categorical for any uncountable cardinal. There are 3 other very similar theories: the theory of dense linear orders with a:
Being well ordered ("any nonempty subset has a minimal element") is not a firstorder 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:
Commutative laws:  
Associative laws:  
Absorption laws: 
For one relation ≤ the axioms are:
First order properties include:
Completeness is not a first order property of lattice.
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".
The axioms for the theory of graphs are
The theory of random graphs has the following extra axioms for each positive integer n:
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 it is true with probability 1 for a random graph on a countable number of points.
There are several different signatures and conventions used for Boolean algebras:
The axioms are:
Tarski proved that the theory of Boolean algebras is decidable.
We write x ≤ y as an abbreviation for x ∧ y = x, and atom(x) as an abbreviation for ¬x = 0 ∧ ∀y y≤x → y = 0 ∨ y = x, read as "x is an atom", in other words a nonzero element with nothing between it and 0. Here are some firstorder properties of Boolean algebras:
The theory of atomless Boolean algebras is ωcategorical and complete.
For any Boolean algebra B, there are several invariants defined as follows.
Then two Boolean algebras are elementarily equivalent if and only if their invariants l, m, and n are the same. 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. For any integer n. t^{n} is an abbreviation for the obvious term for the nth power of t.
Groups are defined by the axioms
Some properties of groups that can be defined in the firstorder language of groups are:
The theory of Abelian groups is decidable. The theory of Infinite divisible torsionfree abelian groups is complete, as is the theory of Infinite abelian groups of exponent p (for p prime).
The theory of finite groups is the set of firstorder statements in the language of groups that are true in all finite groups (there are plenty of infinite models of this theory). It is not completely trivial to find any such statement that is not true for all groups: one example is "given two elements of order 2, either they are conjugate or there is a nontrivial element commuting with both of them".
The properties of being finite, or free, or simple, or torsion are not firstorder. More precisely, the firstorder theory of all groups with one of these properties has models that do not have this property.
The signature of (unital) rings has 2 constants 0 and 1, two binary functions + and ×, and, optionally, one unary inverse functions − ^{1}.
Rings Axioms: Addition makes the ring into an abelian group, multiplication is associative and has an identity 1, and multiplication is left and right distributive.
Commutative rings The axioms for rings plus ∀x ∀y xy=yx.
Fields The axioms for commutative rings plus ∀x ∃y xy=1 and ¬ 1=0. Many of the examples given here have only universal, or algebraic axioms. The class of structures satisfying such a theory has the property of being closed under substructure. For example, a subset of a group closed under the group actions of multiplication and inverse is again a group. Since the signature of fields does not usually include multiplicative and additive inverse, the axioms for inverses are not universal, and therefore a substructure of a field closed under addition and multiplication is not always a field. This can be remedied by adding unary inverse functions to the language.
For any positive integer n the property that all equations of degree n have a root can be expressed by a single firstorder sentence:
Perfect fields The axioms for fields, plus axioms for each prime number p stating that if p 1 = 0 (ie the field has characteristic p), then every field element has a pth root.
Algebraically closed fields of characteristic p The axioms for fields, plus for every positive n the axiom that all polynomials of degree n have a root, plus axioms fixing the characteristic. The classical examples of complete theories. Categorical in all uncountable cardinals. The theory ACF_{p} has a universal domain property, in the sense that every structure N satisfying the universal axioms of ACF_{p} is a substructure of a sufficiently large algebraically closed field , and additionally any two such embeddings N → M induce an automorphism of M.
Finite fields. The theory of finite fields is the set of all firstorder statements that are true in all finite fields. Significant examples of such statements can, for example, be given by applying the ChevalleyWarning theorem, over the prime fields. The name is a little misleading as the theory has plenty of infinite models. Ax proved that the theory is decidable.
Formally real fields These are fields with the axiom
Real closed fields Axioms:
The theory of real closed fields is decidable (Tarski) and therefore complete.
padic fields: Ax & Kochen (1965) showed that the theory of padic fields is decidable and gave a set of axioms for it.
Axioms for various systems of geometry usually use a typed language, with the different types corresponding to different geometric objects such as points, lines, circles, planes, and so on. The signature will often consist of binary incidence relations between objects of different types; for example, the relation that a point lies on a line. The signature may have more complicated relations; for example ordered geometry might have a ternary "betweenness" relation for 3 points, which says whether one lies between two others, or a "congruence" relation between 2 pairs of points.
Some examples of axiomatized systems of geometry include ordered geometry, absolute geometry, affine geometry, Euclidean geometry, projective geometry, and hyperbolic geometry. For each of these geometries there are many different and inequivalent systems of axioms for various dimensions. Some of these axiom systems include "completeness" axioms that are not first order.
As a typical example, the axioms for projective geometry use 2 types, points and lines, and a binary incidence relation between points and lines. If point and line variables are indicated by small and capital letter, and a incident to A is written as aA, then one set of axioms is
Euclid did not state all the axioms for Euclidean geometry explicitly, and the first complete list was given by Hilbert in Hilbert's axioms. This is not a first order axiomatization as one of Hilbert's axioms is a second order completeness axiom. Tarski's axioms are a first order axiomatization of Euclidean geometry. Tarski showed this axiom system is complete and decidable by relating it to the complete and decidable theory of real closed fields.
The signature is that of fields (0, 1, +, , ×) together with a unary function ∂, the derivation. The axioms are those for fields together with
For this theory one can add the condition that the characteristic is p, a prime or zero, to get the theory DF_{p} of differential fields of characteristic p (and similarly with the other theories below).
If K is a differential field then the field of constants The theory of differentially perfect fields is the theory of differential fields together with the condition that the field of constants is perfect; in other words for each prime p it has the axiom:
(There is little point in demanding that the whole field should be perfect field, because in nonzero characteristic this implies the differential is 0.) 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 +. It is complete and decidable. The axioms are
Many of the first order theories described above can be extended to complete recursively enumerable consistent theories. 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).
The signature of a theory of arithmetic has:
Some authors take the signature to contain a constant 1 instead of the function S, then define S in the obvious way as St = 1 + t.
Robinson arithmetic (also called Q). Axioms (1) and (2) govern the distinguished element 0. (3) assures that S is an injection. Axioms (4) and (5) are the standard recursive definition of addition; (6) and (7) do the same for multiplication. Robinson arithmetic can be thought of as Peano arithmetic without induction. Q is a weak theory for which Gödel's incompleteness theorem holds. Axioms:
IΣ_{n} is first order Peano arithmetic with induction restricted to Σ_{n} formulas (for n = 0, 1, 2, ...). The theory IΣ_{0} is often denoted by IΔ_{0}. This is a series of more and more powerful fragments of Peano arithmetic. The case n=1 has about the same strength as primitive recursive arithmetic (PRA). Exponential function arithmetic (EFA) is IΣ_{0} with an axiom stating that x^{y} exists for all x and y (with the usual properties).
First order Peano arithmetic, PA. The "standard" theory of arithmetic. The axioms are the axioms of Robinson arithmetic above, together with the axiom scheme of induction:
Kurt Gödel's 1931 paper proved that PA is incomplete, and has no consistent recursively enumerable completions.
Complete arithmetic (also known as true arithmetic) is the theory of the standard model of arithmetic, the natural numbers N. It is complete but does not have a recursively enumerable set of axioms.
Secondorder arithmetic can refer to a first order theory (in spite of the name) with two types of variables, thought of as varying over integers and subsets of the integers. (There is also a theory of arithmetic in second order logic that is called second order arithmetic. It has only one model, unlike the corresponding theory in first order logic, which is incomplete.) The signature will typically be the signature 0, S, +, × of arithmetic, together with a membership relation ∈ between integers and subsets (though there are numerous minor variations). The axioms are those of Robinson arithmetic, together with axiom schemes of induction and comprehension.
There are many different subtheories of second order arithmetic that differ in which formulas are allowed in the induction and comprehension schemes. In order of increasing strength, five of the most common systems are
These are defined in detail in the articles on second order arithmetic and reverse mathematics.
The usual signature of set theory has one binary relation ∈, no constants, and no functions. Some of the theories below are "class theories" which have two sorts of object, sets and classes. There are three common ways of handling this in firstorder logic:
Some first order set theories include:
Some extra first order axioms that can be added to one of these (usually ZF) include:
