Introduction to Model theory Zoé Chatzidakis – CNRS (Paris 7) Notes for Luminy, November 2001

These notes aim at giving the basic definitions and results from model theory. My intention in writing them, is that they should provide the reader with many examples, even with some proofs, and contain most of the definitions. Differences in vocabulary can be quite an obstacle to mutual understanding, and having the terminology written up somewhere should prove helpful. An index is included at the end.

People interested in reading more should consult standard model theory books. For instance: C.C. Chang, H.J. Keisler, Model Theory, North-Holland Publishing Company, Amsterdam 1973; W. Hodges, A shorter model theory, Cambridge University Press, 1997.

The notes are organised as follows. Chapter 1 gives the very basic definitions of languages, structures and satisfaction. Chapter 2 gives more definitions and some important theorems, such as the compactness theorem. Section 3 introduces ultraproducts and their properties. In section 4, we give a short proof of the decidability of the theory of the field of real numbers.

1. Languages, structures, satisfaction

(1.1) Languages. A language is a collection L, finite or infinite, of symbols. These symbols are of three kinds:

– function symbols

– relation symbols

– constant symbols

To each function symbol f is associated a number n(f) ∈ ℕ^{>0}, and to each relation symbol R a number n(R) ∈ ℕ. The numbers n(f) and n(R) are called the arities of the function f, resp., the relation R.

(1.2) L-structures. We fix a language L = {f_{i}, R_{j}, c_{k} | i ∈ I, j ∈ J, k ∈ K}, where the f_{i}’s are function symbols, the R_{j}’s are relation symbols, and the c_{k}’s are constant symbols.

An L-structure M is then given by

– A set M, called the universe of M,

– For each function symbol f ∈ L, a function f^{M} : M^{n(f)} → M, called the interpretation of f in M,

– For each relation symbol R ∈ M, a subset R^{M} of M^{n(R)}, called the interpretation of R in M,

– For each constant symbol c ∈ L, an element c^{M} ∈ M, called the interpretation of c in M. The structure M is then denoted by

M = (M, f_{i}^{M}, R_{j}^{M}, c_{k}^{M} | i ∈ I, j ∈ J, k ∈ K).

In fact, most of the time the superscript M disappears, and the structure and its universe are denoted by the same letter. This is when no confusion is possible, for instance when there is only one type of structure on M.

(1.3) Substructures. Let M be an L-structure. An L-substructure of M, or simply a substructure of M if not confusion is likely, is an L-structure N, with universe contained in the universe of M, and such that the interpretations of the symbols of L in N are restrictions of the interpretation of these symbols in M, i.e.:

– If f is a function symbol of L, then the interpretation of f in N is the restriction of f^{M} to N^{n(f)},

– If R is a relation symbol of L, then R^{N} = R^{M} ∩ N^{n(R)},

– If c is a constant symbol of L, then c^{M} = c^{N}.

Hence a subset of M is the universe of a substructure of M if and only if it contains all the (elements interpreting the) constants of L, and is closed under the (interpretation in M of the) functions of L. Note that if the language has no constant symbol, then the empty set is the universe of a substructure of M. Convention. If M and N are L-structures, the notation M ⊆ N will indicate that M is an L-substructure of N.

(1.4) Examples of languages, structures, and substructures. The concrete structures considered in model theory all come from standard algebraic examples, and so the examples given below will be very familiar to you. Example 1 - The language of groups. The language of groups, L_{G}, is the language {·,^{−1}, 1}, where · is a 2-ary function symbol, ^{−1} is a unary function symbol, and 1 is a constant symbol.

Any group G has a natural L_{G}-structure, obtained by interpreting · as the group multiplication, ^{−1} as the group inverse, and 1 as the unit element of the group.

A substructure of the group G is then a subset containing 1, closed under multiplication and inverse: it is simply a subgroup of G.

This is a good place to remark that the notion of substructure is sensitive to the language. While the inverse function and the identity element of the group G are retrievable (definable) from the group multiplication of G, the notion of “substructure” heavily depends on them. For instance, a {·, e}-substructure of G is simply a submonoid of G containing e, while a {·}-substructure of G can be empty. Example 2 - The language of graphs. The language consists of a binary relation symbol, E. Graphs which have at most one edge between two vertices are the {E}-structures: simply interpret E(x, y) if and only there is an edge going from x to y. Graphs in which there can be several edges between two vertices need a more sophisticated language, see below in (2.15). Example 3 - The language of rings. The language of rings, L_{R}, is the language {+, −, ·, 0, 1}, where +, − and · are binary functions, 0 and 1 are constants.

A (unitary) ring S has a natural L_{R}-structure, obtained by interpreting +, −, · as the usual ring operations of addition, subtraction and multiplication, 0 as the identity element of +, and 1 as the unit element of S.

A substructure of the L_{R}-structure S is then simply a subring of S. Note that it will in particular contain the subring of S generated by 1, i.e., a copy of ℤ or of ℤ/pℤ.

When one deals with fields, it is sometimes convenient to add a symbol for the multiplicative inverse (denoted ^{−1}). By convention 0^{−1} = 0.

Example 4 - The language of ordered groups, of ordered rings.

One simply adds to L_{G}, resp. L_{R}, a binary relation symbol, ≤.

(1.5) Morphisms, embeddings, isomorphisms, automorphisms. Let M and N be two L-structures. A map s : M → N is an (L)-morphism if for all relation symbol R ∈ L, function symbol f ∈ L, and tuples ā, b̄ in M, we have:

if ā ∈ R, then s(ā) ∈ R; s(f(b̄)) = f(s(b̄)).

An embedding is an injective morphism s : M → N, which satisfies in addition for all relation R ∈ L and tuple ā in M, that

ā ∈ R ⟺ s(ā) ∈ R.

An isomorphism between M and N is a bijective morphism, whose inverse is also a morphism. Finally, an automorphism of M is an isomorphism M → M.

(1.6) Terms. We can start using the symbols of L to express properties of a given Lstructure. In addition to the symbols of L, we will consider a set of symbols (which we suppose disjoint from L), called the set of logical symbols. It consists of

– logical connectives ∧, ∨, ¬, and sometimes also (for convenience) → and ↔,

– parentheses ( and ),

– a (binary relation) symbol = for equality,

– infinitely many variable symbols, usually denoted x, y, x_{i}, etc …

– the quantifiers ∀ (for all) and ∃ (there exists).

Fix a language L. An L-formula will then be a string of symbols from L and logical symbols, obeying certain rules. We start by defining L-terms (or simply, terms). Roughly speaking, terms are expressions obtained from constants and variables by applying functions. In any L-structure M, a term t will then define uniquely a function from a certain cartesian power of M to M. Terms are defined by induction, as follows:

– a variable x, or a constant c, are terms.

– if t_{1}, …, t_{n} are terms, and f is an n-ary function, then f(t_{1}, …, t_{n}) is a term. Given a term t(x_{1}, …, x_{m}), the notation indicating that the variables occurring in t

are among x_{1}, …, x_{m}, and an L-structure M, we get a function F_{t} : M^{m} → M. Again this function is defined by induction on the complexity of the term:

– if c is a a constant symbol, then F_{c} : M^{0} → M is the function ∅ ↦ c^{M},

– if x is a variable, then F_{x} : M → M is the identity,

– if t_{1}, …, t_{n} are terms in the variables x_{1}, …, x_{m} and f is an n-ary function symbol, then F_{f(t_{1},...,t_{n})} : (x_{1}, …, x_{m}) ↦ f(F_{t_{1}}(x̄), …, F_{t_{n}}(x̄)) (x̄ = (x_{1}, …, x_{m})).

(1.7) Formulas. We are now ready to define formulas. Again they are defined by induction. An atomic formula is a formula of the form t_{1}(x̄) = t_{2}(x̄) or R(t_{1}(x̄), …, t_{n}(x̄)), where x̄ = (x_{1}, …, x_{m}) is a tuple of variables, t_{1}, …, t_{n} are terms (of the language L, in the variables x̄), and R is an n-ary relation symbol of L. The set of quantifier-free formulas is the set of Boolean combinations of atomic formulas, i.e., is the closure of the set of atomic formulas under the operations of ∧ (and), ∨ (or) and ¬ (negation, or not). So, if φ_{1}(x̄), φ_{2}(x̄) are quantifier-free formulas, so are (φ_{1}(x̄)∧φ_{2}(x̄)), (φ_{1}(x̄) ∨ φ_{2}(x̄)), and (¬φ_{1}(x̄)). One often uses (φ_{1} → φ_{2}) as an abbreviation for ((¬φ_{1}) ∨ φ_{2}), and (φ_{1} ↔ φ_{2}) as an abbreviation for ((φ_{1} → φ_{2}) ∧ (φ_{2} → φ_{1})). A formula ψ is then a string of symbols of the form

Q_{1}x_{1}Q_{2}x_{2} … Q_{m}x_{m} φ(x_{1}, …, x_{n})  (1)

where φ(x̄) is a quantifier-free formula, with variables among x̄ = (x_{1}, …, x_{n}), and Q_{1}, …, Q_{m} are quantifiers, i.e., belong to {∀, ∃}. We may assume m ≤ n. Important: the variables x_{1}, …, x_{n} are supposed distinct: ∀x_{1}∃x_{1} … is not allowed. If m ≤ n, the variables x_{m+1}, …, x_{n} are called the free variables of the formula ψ. One usually writes ψ(x_{m+1}, …, x_{n}) to indicate that the free variables of ψ are among (x_{m+1}, …, x_{n}). The variables x_{1}, …, x_{m} are called the bound variables of ψ. If n = m, then ψ has no free variables and is called a sentence.

If all quantifiers Q_{1}, …, Q_{m} are ∃, then ψ is called an existential formula; if they are all ∀, then ψ is called a universal formula. One can define a hierarchy of complexity of formulas, by counting the number of alternances of quantifiers in the string Q_{1}, …, Q_{n}. Let us simply say that a Π_{2}-formula, also called a ∀∃-formula, is one in which Q_{1} … Q_{n} is a block of ∀ followed by a block of ∃, that a Σ_{2}-formula, also called a ∃∀-formula, is one in which Q_{1} … Q_{n} is a block of ∃ followed by a block of ∀. In these definitions, either block is allowed to be empty, so that an existential formula is both a Π_{2} and a Σ_{2}-formula. Let us also mention that a positive formula is one of the form Q_{1}x_{1} … Q_{m}x_{m}φ(x_{1}, …, x_{n}), where φ(x̄) is a finite disjunction of finite conjunctions of atomic formulas.

(1.8) Warning. I lied, this is not the usual definition of a formula. A formula as in (1) is said to be in prenex form. The set of formulas in prenex form is not closed under Boolean operations. One has however a notion of “logical equivalence”, under which for instance the formulas Q_{1}x_{1}Q_{2}x_{2} … Q_{m}x_{m} φ(x_{1}, …, x_{m}, x_{m+1}, …, x_{n}) and Q_{1}y_{1}Q_{2}y_{2} … Q_{m}y_{m} φ(y_{1}, …, y_{m}, x_{m+1}, …, x_{n}) are logically equivalent. Then it is quite easy to see that a Boolean combination of formulas in prenex form is logically equivalent to a formula in prenex form. E.g,

(Q_{1}x_{1} … Q_{m}x_{m} φ_{1}(x_{1}, …, x_{n})) ∧ (Q′_{1}x_{1} … Q′_{m}x_{m} φ_{2}(x_{1}, …, x_{n}))

is logically equivalent to

Q_{1}x_{1}Q′_{1}y_{1} … Q_{m}x_{m}Q′_{m}y_{m}(φ_{1}(x_{1}, …, x_{n}) ∧ φ_{2}(y_{1}, …, y_{m}, x_{m+1}, …, x_{n})).

If one wants to be economical about the number of quantifiers, one notes that in general ∀x φ_{1}(x, …) ∧ ∀x φ_{2}(x, …) is logically equivalent to ∀x (φ_{1}(x, …) ∧ φ_{2}(x, …)), and ∃x φ_{1}(x, …) ∨ ∃x φ_{2}(x, …) is logically equivalent to ∃x (φ_{1}(x, …) ∨ φ_{2}(x, …)). For negations, one uses the logical equivalence of ¬(Q_{1}x_{1} … Q_{m}x_{m} φ(x_{1}, …, x_{n})) with Q′_{1}x_{1} … Q′_{m}x_{m} ¬(φ(x_{1}, …, x_{n})), where Q′_{i} = ∃ if Q_{i} = ∀, Q′_{i} = ∀ if Q_{i} = ∃. Thus the negation of a Π_{2}-formula is a Σ_{2}-formula, etc.

Logical equivalence can also be used to rewrite Boolean combinations, and one can show that any quantifier-free formula φ(x̄) is logically equivalent to one of the form ⋁_{i} ⋀_{j} φ_{i,j}(x̄), where the φ_{i,j} are atomic formulas or negations of atomic formulas.

(1.9) Comments and examples. The definitions given above are completely formal. When considering concrete examples, they get very much simplified, to agree with current usage. The first thing to note is that the formula (¬(x = y) is abbreviated by x ≠ y.

Example 1. L_{G} = {·,^{−1}, 1}. A term is built up from 1, ·, ^{−1}. and some variables. E.g., ·(1,^{−1}(·(x_{1},^{−1}(x_{1})))) is a term, in the variable x_{1}. If we work in an arbitrary L_{G}- structure, i.e., not necessarily a group, this expression cannot be simplified. If we work in a group, then we will first of all switch to the usual notation of xy instead of ·(x, y) and x^{−1} instead of ^{−1}(x); then allow ourselves to use the associativity of the group law to get rid of extraneous parentheses. The term above then becomes 1(x_{1}x_{1}^{−1})^{−1}, which can be further simplified to 1 (now using the defining properties of ^{−1} and of 1). From now on, we will assume that our L_{G}-structures are groups.

A term in the variables x_{1}, …, x_{n} is then simply a word in the symbols x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}. One can do a further reduction: replace occurrences of the formula w_{1}(x̄) = w_{2}(x̄) by w_{1}(x̄)(w_{2}(x̄))^{−1} = 1. An atomic formula will then be a finite disjunction of finite conjunctions of equations w(x̄) = 1 and inequations w(x̄) ≠ 1. The following formula is a Π_{2}-formula:

∀x̄ ∃ȳ(w_{1}(x̄, ȳ, z̄) = 1 ∧ w_{2}(x̄, z̄) ≠ 1),

where w_{1}(x̄, ȳ, z̄) is a word in the elements of the tuple (x̄, ȳ, z̄) and their inverses, and w_{2}(x̄, z̄) is a word in the elements of (x̄, z̄) and their inverses. The free variables of this formula are the elements of the tuple z̄, while the elements of (x̄, ȳ) are the bound variables of the formula.

In case all structures considered are free groups, containing two non-commuting elements a, b, then a quantifier-free formula can be written as finite disjunction of formulas of the form

w(x̄, a, b) = 1 ∧ w′(x̄, a, b) ≠ 1

for some words w, w′.

Example 2. The language of graphs {E}. The only terms are variables (since there are no function or constant symbols). Thus an atomic formula is of the form E(x, y) or (x = y). An example of formula in this language is e.g.,

∃y_{1}, …, y_{m}( ⋀_{i=1}^{m−1} E(y_{i}, y_{i+1}) ∧ E(x_{1}, y_{1}) ∧ E(y_{n}, x_{2}) ∧ ⋀_{1≤i<j≤m} y_{i} ≠ y_{j}).

Note the use of x ≠ y instead of ¬(x = y). The free variables of this formula are x_{1}, x_{2}.

Example 3. L_{R} = {+, −, ·, 0, 1}. Again, terms as defined formally, are extremely ugly. But, in case all L_{R}-structures considered are rings, they can be rewritten in a more natural fashion. From now on, all L_{R}-structures are commutative rings.

If n ∈ ℕ^{>1} the term 1 + 1 + ⋯ + 1 (n times) will simply be denoted by n. Similarly x + x + ⋯ + x (n times) is denoted by nx, and x · . . . · x (n times) by x^{n}. An arbitrary term will then be of the form f(x_{1}, …, x_{n}), where f(X_{1}, …, X_{n}) ∈ ℤ[X_{1}, …, X_{n}].

Quantifier-free formulas are finite disjunctions of finite conjunctions of equations and inequations.

If one adds ≤ to the language, and assumes that our structures are ordered rings, then quantifier-free formulas can be rewritten as finite conjunctions of finite disjunctions of formulas of the form

f(x̄) = 0, g(x̄) > 0,  (2)

where f, g are polynomials over ℤ. Here, x < y stands for x ≤ y ∧ ¬(x ≠ y), and one uses the equivalences x ≠ 0 ⟺ x < 0 ∨ x > 0, x > 0 ⟺ (−x) < 0.

(1.10) Satisfaction. Let M be an L-structure, φ(x̄) an L-formula, where x̄ = (x_{1}, …, x_{n}) is a tuple of variables occurring freely in φ, and ā = (a_{1}, …, a_{n}) an n-tuple of elements of M. We wish to define the notion M satisfies φ(ā), (or ā satisfies φ in M, or φ(ā) holds in M, is true in M), denoted by

M ⊧ φ(ā).

(The negation of M ⊧ φ(ā) is denoted by M |̸= φ(ā).) This is done by induction on the complexity of the formulas:

– If φ(x̄) is the formula t_{1}(x̄) = t_{2}(x̄), where t_{1}, t_{2} are L-terms in the variable x̄, then

M ⊧ t_{1}(ā) = t_{2}(ā) if and only if F_{t_{1}}(ā) = F_{t_{2}}(ā).

– If φ(x̄) is the formula R(t_{1}(x̄), …, t_{m}(x̄)), where t_{1}, …, t_{m} are terms and R is an m-ary relation, then

M ⊧ R(t_{1}(ā), …, t_{m}(ā)) if and only if (F_{t_{1}}(ā), …, F_{t_{m}}(ā)) ∈ R^{M}.

– If φ(x̄) = φ_{1}(x̄) ∨ φ_{2}(x̄), then

M ⊧ φ(ā) if and only if M ⊧ φ_{1}(ā) or M ⊧ φ_{2}(ā).

– If φ(x̄) = φ_{1}(x̄) ∧ φ_{2}(x̄), then

M ⊧ φ(ā) if and only if M ⊧ φ_{1}(ā) and M ⊧ φ_{2}(ā).

– If φ(x̄) = ¬φ_{1}(x̄), then

M ⊧ φ(ā) if and only if M |̸= φ_{1}(ā).

– If φ(x̄) = ∃y ψ(x̄, y), where the free variables of ψ are among x̄, y, then

M ⊧ φ(ā) if and only if there is b ∈ M such that M ⊧ ψ(ā, b).

– if φ(x̄) = ∀y ψ(x̄, y), then

M ⊧ φ(ā) if and only if M ⊧ ¬(∃y ¬ψ(ā, y))
if and only if for all b in M, M ⊧ φ(ā, b).

(1.11) Parameters, definable sets. Let M be an L-structure, φ(x̄, ȳ) a formula (x̄ an n-tuple of variables, ȳ an m-tuple of variables), and ā ∈ M^{n}. Then the set {b̄ ∈ M^{m} | M ⊧ φ(ā, b̄)} is called a definable set. We also say that it is defined over ā by the formula φ(ā, ȳ), or that it is ā-definable. The tuple ā is a parameter of the formula φ(ā, ȳ).

Let M be an L-structure. The set of M-definable subsets of M^{n} is clearly closed under unions, intersections and complements (corresponding to the use of the logical connectives ∨, ∧ and ¬). If S ⊆ M^{n+1} is defined by the formula φ(x̄, ā), x̄ = (x_{1}, …, x_{n+1}), and π : M^{n+1} → M is the projection on the first n coordinates, then π(S) is defined by the formula ∃x_{n+1} φ(x̄, ā), and the complement of π(S) by the formula ∀x_{n+1} ¬φ(x̄).

(1.12) The examples, revisited. (1) L_{G} = {·,^{−1}, 1). Consider the formula φ(x, y) : xy = yx. Let G be a group (endowed with its natural L_{G}-structure), and g ∈ G. Then the formula φ(x, g) defines in G the centraliser of g in G, while the formula ψ(y) = ∀x φ(x, y) will define the centre of G. The sentence ∀x, y (xy = yx) will only be satisfied if G is abelian.

Other examples of definable subsets of a group G are: The conjugacy class of an element g (by ∃y y^{−1}gy = x); the set of commutators (∃y, z (y^{−1}z^{−1}yz = x)); the set of squares (∃y (y^{2} = x)), or more generaly of n-th powers (∃y y^{n} = x); the set of elements of order ≤ n (x^{n} = 1).

Are usually not definable: the commutator subgroup; the set of torsion elements; the subgroup generated by the squares.

(2) L = {E}. The formula φ(x_{1}, x_{2}) = ∃y_{1}, …, y_{m}(⋀_{i=1}^{m−1} E(y_{i}, y_{i+1}) ∧ E(x_{1}, y_{1}) ∧ E(y_{n}, x_{2}) ∧ ⋀_{1≤i<j≤m} y_{i} ≠ y_{j}) will define in a graph Γ the set of pairs (x_{1}, x_{2}) for which there is a path of length exactly m + 1 going from x_{1} to x_{2}.

Other examples of definable sets: the set of elements connected by an edge to at least two distinct elements (∃y_{1}, y_{2} (y_{1} ≠ y_{2} ∧ E(x, y_{1}) ∧ E(x, y_{2}))); the set of elements at distance ≤ n of a given element a (∃y_{1}, …, y_{n−1} (⋀_{i=1}^{n−2} E(y_{i}, y_{i+1})∧E(a, y_{1})∧E(y_{n−1}, x)).

Are usually not definable: the connected component of an element a (unless all of its elements are at bounded distance of a); the set of pairs contained in a loop.

(3) L_{R} = {+, −, ·, 0, 1} is the language of rings. In the ring ℂ, quantifier-free formulas with parameters in ℂ will finite conjunctions of formulas of the form f(x̄) = 0, g(x̄) ≠ 0, where f and g are polynomials over ℂ. Thus, the subsets of ℂ^{n} which are defined by quantifier-free formulas are the usual constructible sets (i.e., Boolean combinations of algebraic sets).

If one adjoins to the language a symbol ≤, and considers the natural L_{R}∪{≤}-stucture on ℝ, then the quantifier-free formulas with parameters in ℝ will be finite disjunctions of finite conjunctions of formulas of the form f(x̄) = 0, g(x̄) > 0, where the polynomials f(x̄), g(x̄) have their coefficients in ℝ. The set defined by these formulas are the usual semi-algebraic sets.

2. Theories, and some big theorems

In this section we will introduce many definitions and important concepts. We will also mention the very important Compactness theorem, one of the crucial tools of model theorists.

(2.1) Theories, models of theories, etc.. Let L be a language. A L-theory (or simply, a theory), is a set of sentences of the language L. A model of a theory T is an L-structure M which satisfies all sentences of T, denoted by M ⊧ T. The class of all models of T is denoted Mod(T). If K is a class of L-structures, then T h(K) denotes the set of all sentences true in all elements of K, and T h({M}) is denote by T h(M).

A theory T is consistent iff it has a model. If φ is a sentence which holds in all models of T, this is denoted by T ⊧ φ. Two L-structures M and N are elementarily equivalent, denoted M ≡ N, iff they satisfy the same sentences, iff T h(M) = T h(N). A theory is complete iff given a sentence φ, either T ⊧ φ or T ⊧ ¬φ. Equivalently, if any two models of T are elementarily equivalent. (Observe that if M is an L-structure, then necessarily T h(M) is complete).

Elementary equivalence is an equivalence relation between L-structures. Two isomorphic L-structures are clearly elementarily equivalent, however the converse only holds for finite L-structures. A famous theorem (of Shelah) states that two structures are elementarily equivalent if and only if they have isomorphic ultrapowers, see definition in Section 3.

(2.2) Elementary substructures, extensions, embeddings, etc. Let M ⊆ N be Lstructures. We say that M is an elementary substructure of N, or that N is an elementary extension of M, denoted by M ≺ N, iff for any formula φ(x̄) and tuple ā from M,

M ⊧ φ(ā) ⟺ N ⊧ φ(ā).

A map f : M → N is an elementary embedding iff it is an embedding, and if f(M) ≺ N. In other words, if for any formula φ(x̄) and tuple ā from M, M ⊧ φ(ā) if and only N ⊧ φ(f(ā)).

Using induction on the complexity of formulas, one can show

Tarski’s test. Let M be a substructure of N. Then M ≺ N if and only if, for every formula φ(x̄, y) and tuple ā in M, if N ⊧ ∃y φ(ā, y), then there exists b ∈ M such that N ⊧ φ(ā, b).

Note that while the element b is in M, the satisfaction is taken in N.

(2.3) Some useful facts. (1) If M_{1} ≺ M_{2} and M_{2} ≺ M_{3}, then M_{1} ≺ M_{3}.

(2) If M_{1} ⊆ M_{2} ⊆ M_{3}, M_{1} ≺ M_{3} and M_{2} ≺ M_{3}, then M_{1} ≺ M_{2}.

(3) Let M_{n}, n ∈ ℕ, be a chain of L-structures (i.e., M_{n} ⊆ M_{n+1} for all n). Then M_{ω} = ⋃_{n∈ℕ} M_{n} has a unique L-structure which makes the M_{n}’s substructures of M_{ω}: the interpretation of the constants is the obvious one, R^{M_{ω}} = ⋃_{n∈ℕ} R^{M_{n}}, and f^{M_{ω}} = ∪_{n∈ℕ}f^{M_{n}}, for R a relation symbol, and f a function symbol.

Assume that M_{n} ≺ M_{n+1} for each n ∈ ℕ. Then M_{n} ≺ M_{ω} for each n ∈ ℕ.

(2.4) Elimination of quantifiers. Formulas with more than two alternances of quantifiers are fairly awkward, and usually difficult to decide the truth of. One therefore tries to “eliminate quantifiers”. Definition. A theory T eliminates quantifiers if for any formula φ(x̄) there is a quantifierfree formula ψ(x̄) which is equivalent to φ(x̄) modulo T, i.e., is such that

T ⊧ ∀x̄(φ(x̄) ↔ ψ(x̄)).

Note that the set of free variables in φ and ψ are the same. Thus if φ is a sentence, so is ψ. (If the language has no constant symbol, then one allows ψ to be either ⊤ (true) or ⊥ (false); if the language contains a constant symbol c, then one can use instead the formulas c = c or c ≠ c). Definition. A theory T is model complete iff it is consistent and whenever M ⊆ N are models of T, then M ≺ N. Remarks. Clearly, a theory which eliminates quantifiers is also model complete. An important result concerning model complete theories is the following: A consistent theory T is model complete if and only, for any formula φ(x̄), there is an existential formula ψ(x̄) such that

T ⊧ ∀x̄(φ(x̄) ↔ ψ(x̄)).

Note that this is equivalent to every formula being equivalent modulo T to a universal formula: if ¬φ(x̄) is equivalent modulo T to the existential formula ψ(x̄), then φ(x̄) is equivalent modulo T to the universal formula ¬ψ(x̄).

One can show that a theory T is model complete, if whenever M ⊆ N are models of T, then M is existentially closed in N, i.e., if φ(x̄) is an existential formula, and ā a tuple in M such that N ⊧ φ(ā), then N ⊧ φ(ā).

(2.5) Examples. (1) The theory of algebraically closed fields, denoted ACF, is axiomatised by the axioms for fields, plus, for each n > 1, the axiom ∀x_{1}, …, x_{n}∃y (y^{n} +x_{1}y^{n−1} +⋯+ x_{n} = 0). ACF eliminates quantifiers, see (2.14).

(2) Consider the field of real numbers, first with its natural L_{R}-structure, then as an L_{R} ∪ {≤}-structure. Let T_{0} be its theory in L_{R}, T_{1} its theory in L_{R} ∪ {≤}. Then one can show that T_{0} is model complete, but does not eliminate quantifiers (in L_{R}), while T_{1} eliminates quantifiers. The quantifier one cannot eliminate in L_{R} is the existential quantifier of ∃y(y^{2} = x). This can be seen as follows: consider the substructure ℚ(\sqrt{2}) of ℝ. As a field (i.e., as an L_{R}-structure), it has an automorphism sending \sqrt{2} to −\sqrt{2}. This automorphism however does not respect the ordering. See chapter 4 for a proof of quantifier-elimination.

(2.6) Soundness and completeness theorem. Given a set of sentences, there is a notion of proof, i.e., which statements are deducible from the given statements using some formal rules of deduction, such as modus ponens (from A and A → B deduce B), and some substitution rules (from a sentence of the form φ(c) where c is a constant, deduce ∃x φ(x)). A proof can be thought of therefore as a finite sequence of sentences, each being obtained from the previous ones by applying some deduction rules. The first result, the soundness theorem, tells us that our notion of satisfaction is well-defined: If a theory T has a model, then one cannot derive a contradiction from T, i.e., one cannot prove from T the sentence ∀x(x ≠ x).

Gödel’s completeness theorem then states the converse: If from a given theory T, one cannot derive the sentence ∀x(x ≠ x), then the theory T has a model.

Another way of stating this result is by saying that the set of sentences deducible from a given theory T is exactly the set of sentences true in all models of T, i.e., in the notation introduced above, that it coincides with T h(Mod(T)).

(2.7) Decidability. A theory T is decidable, if there is an algorithm allowing to decide whether a sentence φ holds in all models of T or not. (Here, the difficulty lies in being able to tell when φ does not hold in all models of T). If one can enumerate a theory T and one knows (somehow) that T is complete, then T is decidable: given a sentence φ, start enumerating the proofs from T; eventually you reach a proof of either φ or ¬φ.

How does one prove that a theory T is decidable? One tries to find a nice set of sentences Σ contained in T, and show that any other sentence is equivalent, modulo Σ, to a sentence which one can decide. For instance, by the results of quantifier elimination for algebraically closed fields given above, one shows that the theory ACF of algebraically closed fields is decidable: the set of axioms of ACF is clearly enumerable, any sentence is equivalent to a quantifier-free sentence, and there are very few of those. So, given a sentence φ, one starts enumerating all the proofs from ACF. Eventually one will reach a proof of (φ ↔ ψ) where ψ is some quantifier-free sentence. Then, one again enumerates proofs to decide whether ψ is equivalent to ⊤, ⊥, or whether it implies a finite disjunction of sentences of the form p = 0 or p ≠ 0. The procedure will eventually terminate and say whether φ holds in all algebraically closed fields or not.

Similarly for the theory ORCF of real closed fields (axioms for ordered fields, any odd degree polynomial has a root, and every positive element has a square root). From which it follows that the theory of real closed fields in the language of rings is also decidable, since the ordering can be defined by “the non-negative elements are the squares”.

How does one prove that a theory is undecidable? Usually one tries to code the ring (ℤ, +, −.·, 0, 1) in some model of the theory. Or to show that any finite graph is codable in some model of the theory.

(2.8) Compactness theorem. Let T be a set of sentences in a language L. If every finite subset of T has a model, then T has a model.

We will present later a proof of this theorem using ultraproducts. Note that it is also a consequence of the completeness theorem, since any proof involves only finitely many elements of T. It also has for consequence the first half of the next theorem.

(2.9) Löwenheim-Skolem Theorems. Let L be a language. T a theory, and let M be an infinite model of T.

(1) Let κ be an infinite cardinal, κ ≥ |M| + |L|. Then M has an elementary extension N with |N| = κ.

(2) Let X be a subset of M. Then M has an elementary substructure N containing X, with |N| ≤ |X| + |L| + ℵ_{0}.

(2.10) Comments. These results allow us to use large models with good properties. For instance, assume that we have a set Σ(x_{1}, …, x_{n}) of formulas in the variables (x_{1}, …, x_{n}), and that we know that every finite fragment of Σ(x_{1}, …, x_{n}) is satisfiable in some model M of T, i.e., there is a tuple ā of M which satisfies all formulas of this finite fragment. Then there is a model N of T containing a tuple b̄ which satisfies simultaneously all formulas of Σ(x̄).

Using other techniques, one can show that if ā and b̄ are tuples of an L-structure M, which satisfy the same formulas in M, then M has an elementary extension M^{∗}, in which there is an automorphism which sends ā to b̄.

(2.11) Application of the compactness theorem. Let T be a theory in a language L, and Δ a set of formulas in the (free) variables (x_{1}, …, x_{n}), closed under finite disjunctions. Let Σ(x_{1}, …, x_{n}) be a set of formulas in the free variables (x_{1}, …, x_{n}), such that every finite fragment of Σ(x_{1}, …, x_{n}) is satisfiable in a model of T. The following conditions are equivalent:

(1) There is a subset Γ(x̄) of Δ such that, if c̄ = (c_{1}, …, c_{n}) are new constant symbols,

then

T ∪ Γ(c̄) ⊧ Σ(c̄), T ∪ Σ(c̄) ⊧ Γ(c̄).

(2) For all models M and N of T, and n-tuples ā in M and b̄ in N, if N ⊧ Σ(b̄) and ā satisfies (in M) all formulas of Δ that are satisfied by b̄ (in N), then M ⊧ Σ(ā).

Remark. If the set Σ(x̄) is finite, then so is Γ(x̄). Hence, taking φ(x̄) to be the conjunction of the formulas of Σ(x̄), one obtains that φ(x̄) is equivalent, modulo T, to a finite conjunction of formulas of Δ.

(2.12) Preservation theorems. This has for consequences several preservation theorems. One direction is trivial, the other one not.

Let T be a theory in a language L.

(1) The following conditions are equivalent:

(a) Whenever M ⊆ N are L-structures, and M ⊧ T, then N ⊧ T.

(b) T has an axiomatisation given by existential sentences.

(2) The following conditions are equivalent:

(a) Whenever M ⊆ N are L-structures, and N ⊧ T, then M ⊧ T.

(b) T has an axiomatisation given by universal sentences.

(3) The following conditions are equivalent:

(a) Whenever M_{n}, n ∈ ℕ, is a chain of models of T, then ⋃_{n∈ℕ} M_{n} is a model of T.

(b) T has an axiomatisation given by ∀∃ sentences.

(4) The following conditions are equivalent:

(a) Whenever M is a model of T, and f : M → N is an morphism, then f(M) ⊧ T.

(b) T has an axiomatisation given by positive sentences.

Note that (3) implies that a model complete theory has an axiomatisation given by ∀∃ sentences.

(2.13) Craig’s interpolation theorem. Let L_{1} and L_{2} be two languages. Let φ be a sentence of L_{1} and ψ a sentence of L_{2}. If φ ⊧ ψ, then there is a sentence θ of L_{1} ∩ L_{2} such that φ ⊧ θ and θ ⊧ ψ.

A somewhat different interpolation theorem is given by Robinson: Let L_{1} and L_{2} be two languages, and L_{0} = L_{1} ∩ L_{2}. Assume that T_{1} and T_{2} are theories in L_{1} and L_{2} respectively, such that T_{0} = T_{1} ∩ T_{2} is complete. Then T_{1} ∪ T_{2} is consistent.

(2.14) Application of the Löwenheim-Skolem theorem to the theory of algebraically closed fields. This will allow us to show that the theory of algebraically closed fields (denoted ACF) eliminates quantifiers. From that we will deduce that the completions of ACF (i.e., the complete theories extending ACF) are obtained by specifying the characteristic. This will actually be obvious from the proof.

Notation. Let M be an L-structure, and ā an n-tuple in M. We denote by tp_{M}(ā) the set of formulas satisfied by ā in M.

Theorem. Let T = ACF be the theory of algebraically closed fields. Then T eliminates quantifiers. Moreover, any two models of T of the same characteristic are elementarily equivalent.

Proof. By (2.11), it suffices to show that if M and N are algebraically closed, and if ā and b̄ are n-tuples from M and N respectively, which satisfy the same quantifier-free formulas, then they satisfy the same formulas, i.e., tp_{M}(ā) = tp_{N}(b̄).

First note that if ā and b̄ satisfy the same formulas, then the fields M and N have the same characteristic. Indeed, if char(M) = p > 0, then ā satisfies (the sentence) p = 0 (where p is an abbreviation for the term 1 + 1 + ⋯ + 1 p times). Hence the prime subfield of M is isomorphic to the prime subfield of N, and we will denote this field by k. By assumption ā and b̄ satisfy the same quantifier-free formulas, and this implies that there is a field-isomorphism f : k(ā) → k(b̄) sending ā to b̄.

Let κ be a cardinal, κ > |M|, |N|. By Löwenheim-Skolem, M has an elementary extension M^{∗} of cardinality κ, and N has an elementary extension N^{∗} of cardinality κ. Select transcendence bases X of M^{∗} over k(ā) and Y of N^{∗} over k(b̄). Then |X| = |Y | = κ, so that there is a bijection g : X → Y. Then f ∪g extends to an isomorphism h : M^{∗} → N^{∗}. As isomorphisms preserve formulas, this implies that tp_{M^{∗}}(ā) = tp_{N^{∗}}(b̄). As M ≺ M^{∗} and N ≺ N^{∗}, this shows that tp_{M}(ā) = tp_{N}(b̄).

Moreover the proof shows that any two algebraically closed fields of the same characteristic are elementarily equivalent, as they have isomorphic elementary extensions.

We will see later an important consequence of this, the Lefshetz principle.

(2.15) Many-sorted structures. Many-sorted structures are like ordinary structures, except that there are now several universes, usually disjoint (but not always), with associated sorts. The language will have sorts, relation symbols will have attached to them, not only an arity, but also a tuple of sorts, and similarly for functions. Formulas are built in the usual way, the only restriction being that variables now have a sort attached to them. In case one has finitely many sorts, say n, one can reduce to the usual case, by adding for instance to the language n new unary relation symbols R_{1}, …, R_{n}, with intended interpretation the universes of the sorts.

A formal definition is a bit awkward, and we will rather give four natural examples. Most classical results hold in many-sorted logic, with sometimes the appropriate adaptation. In particular, the compactness theorem holds. Example 1. Let G be a finitely generated group, say by a_{1}, …, a_{n}. We consider the language with two sorts: one sort is the group sort, the other one is the “length” sort. The language is:

– {·,^{−1}, 1, a_{1}, …, a_{n}}, applied to the group sort. Here we have added to the language of groups n new constant symbols for the elements a_{1}, …, a_{n} (we denote, abusively maybe, the constant and the element by the same symbol).

– Any structure you want on the length sort. E.g., a constant symbol 0, and a binary relation ≤. Maybe also a symbol for addition and subtraction.

– A binary function symbol d, with domain the group sort squared, and range the length sort.

The two-sorted structure we have in mind is the structure

G = ((G, ·,^{−1}, 1, a_{1}, …, a_{n}), (ℕ, +, 0, ≤), d),

where (G, ·,^{−1}, 1, a_{1}, …, a_{n}) is our group with the distinguished elements a_{1}, …, a_{n}, (ℕ, +, 0, ≤) is the non-negative integers with their natural addition, subtraction and ordering, and d : G^{2} → ℕ is the distance function (on the Cayley graph of G with respect to the set {a_{1}, …, a_{n}} of generators). Note that for each n, to be at distance ≤ n is expressible by a first order formula. But there is no formula expressing that every element is at finite distance from 1, unless G is finite.

Note also that an elementary extension of (G, ℕ, d) will be a two-sorted structure (G^{∗}, ℕ^{∗}, d^{∗}), in which the distance function will still be onto, and satisfy certain ultrametric inequalities; but its range will (in general) be a non-standard model of the integers, so that distance between two elements of G^{∗} may be infinite. One can also replace ℕ by any additive ordered subgroup of the reals, but the map d will then not be onto. We will come back to this example in asymptotic cones. Example 2. Consider the field ℚ_{p}, and its valuation v : ℚ_{p} → ℤ, residue map ℤ_{p} → 𝔽_{p}. it is customary to view this valued field as a 3-sorted structure Q_{p}: the sorts are the field sort, the value group sort, and the residue field sort. We have two sets of field operations, one for the field sort, and one for the residue field sort. We also have the language of ordered groups for the residue sort, together with a distinguished constant ∞. Finally, we have the valuation map ℚ_{p} → ℤ ∪ {∞}, and the residue map π : ℤ_{p} → 𝔽_{p} (if one wants this map to be defined on the whole field sort, one assigns the elements of ℚ_{p} \ ℤ_{p} to 0, for instance). Example 3. Let K be a field, and fix an integer m > 0. Consider the polynomial ring R = K[X_{1}, …, X_{m}]. We will define an ω-sorted structure (indexed by the integers) on R. For d ∈ ℕ, the elements of sort d are the polynomials of total degree ≤ d, and we denote the corresponding set by R_{d}. We add an addition, subtraction and multiplication, in the natural way. Then + for instance will send R_{d} × R_{e} to R_{sup{d,e}}, while · will send R_{d} × R_{e} to R_{d+e}.

Elementary statements about the ω-sorted structure R are expressible by ordinary L_{R}-formulas in the field K: as all variables have a sort, quantification over polynomials of degree ≤ d is achieved by quantifying over their coefficients, i.e., over N-tuples for a certain N computable from m, d.

A similar construction can be done for K[V], for V an algebraic set defined over K.

Example 4. The 2-sorted language used for graphs in which there can be several edges between two vertices, is simply the language with two sorts, the vertice sort, and the edge sort. It has three unary function symbols, σ, τ and ¯ . The domains of σ and τ are the edge sort, and their range the vertice sort. The domain and range of ¯ is the edge sort.

A graph will be given by (V, E, σ, τ, ¯ ), where V is the set of vertices, E is the set of edges, σ : E → V assigns to an edge e its starting point σ(e), and τ : V → E assigns to an edge e its endpoint τ(e). The map ¯ reverses the direction of edges. Hence we have ¯ē = e for every edge e, and σ(ē) = τ(e), τ(ē) = σ(e).

One can put additional structure on the graph, for instance by colouring the edges. This is done by adding unary predicates on the edge sort. Bipartitite graphs can be treated in a similar manner.

(2.16) Additional remarks on quantifier-elimination. So, what does one do if a theory T in a language L does not eliminate quantifiers? One possibility is to form the Skolemization of T: for each formula φ(x_{1}, …, x_{n}) one adds a new n-ary relation symbol R_{φ}, and adds to T an axiom saying that R_{φ} defines precisely the set of n-tuples satisfying φ. The resulting theory eliminates quantifiers. However, this does not bring any information about our theory T.

The hope is that one does not need to add much to the language to obtain quantifierelimination. For instance we saw that to get elimination of quantifiers of the theory ORCF of real closed fields, it is enough to add the ordering to L_{R}.

Another interesting example is the theory of the field of p-adic numbers ℚ_{p}, now viewed as an ordinary L_{R}-structure. A beautiful result of Macintyre states that it is enough to add to the language a unary predicate P_{n} for each n > 1, as well as the inverse function ^{−1}. The interpretation of the predicates P_{n} in ℚ_{p} is the set of non-zero n-th powers, i.e.,

ℚ_{p} ⊧ ∀x (P_{n}(x) ↔ (x ≠ 0 ∧ ∃y y^{n} = x)).

Observe that the elements of positive valuation are then definable: v(x) > 0 ⟺ P_{2}(1 + px^{2}). The first-order theory of the expansion of ℚ_{p} to this enlarged language then eliminates quantifiers. This allows one to give a good description of the definable sets.

(2.17) Diagrams. Diagrams are meant to give a logical formulation of the following properties: the structure N contains a copy of the structure M; there is a morphism f : M → N; there is an elementary embedding f : M → N.

Definitions. Let M be an L-structure, A ⊆ M. We let L(A) be the language obtained by adding to the language new symbols of constants c_{a} for each a ∈ A. If ā is a tuple of elements of A, we let c̄ā denote the tuple of constants corresponding to the elements of the tuple ā. L(A) is then a bona fide language, but may be much larger than L. Note that M becomes naturally an L(A)-structure, when one interprets the constant c_{a} by a, for a ∈ A. This structure is usually denoted by (M, c_{a})_{a∈A}, or (M, a)_{a∈A} (i.e., we denote the constant and the element by the same symbol).

(1) The quantifier-free diagram of A in M, Δ(A), is the set of all quantifier-free sentences φ(c̄ā) ∈ L(A) which hold in the L(A)-structure M (i.e., such that M ⊧ φ(ā)).

(2) The positive diagram of A in M, Δ^{+}(A), is the set of all positive quantifier-free sentences φ(c̄ā) ∈ L(A) which hold in the L(A)-structure M.

(3) The elementary diagram of A in M, Diag(A), is the set of all sentences φ(c̄ā) ∈ L(A) which hold in the L(A)-structure M.

(4) Let L′ be a language containing L. An expansion of the L-structure M to L′ is an L′-structure M′, with same universe as M, and such that the interpretation of the symbols of L in M and in M′ coincide. M is then called a reduct of M′ to L. For instance, (M, c_{a})_{a∈A} is an expansion of M to L(A).

Facts. Let M and N be two L-structures. The following are immediate consequences of the definition:

(1) N can be expanded to an L(M)-structure which is a model of Δ(M) if and only if there is an embedding f : M → N.

(2) N can be expanded to an L(M)-structure which is a model of Δ^{+}(M) if and only there is a morphism f : M → N.

(3) N can be expanded to an L(M)-structure which is a model of Diag(M) if and only if there is an elementary embedding f : M → N. Note also that if T is an L-theory, then

(5) T is model complete if and only if, for every model M of T, T ∪ Δ(M) is complete (in L(M)).

(6) T eliminates quantifiers if and only if, for every M ⊧ T and subset A of M, T ∪Δ(A) is complete (in L(A)).

(2.18) Questions and hopes on free groups. Sela has shown that the theory T of all non-abelian free groups (in the language L_{G}) is complete, and moreover, that every formula is equivalent, modulo T, to a Boolean combination of ∀∃-formulas. From what I understand, he does not yet have an axiomatisation of the theory T, nor does he knows whether it is decidable.

One of the outstanding open questions for model theorists, is whether the theory T is stable. Stability is a certain combinatorial property of a theory, which allows one to use a huge machinery to study models and possible interactions between definable subsets. One definition of stability is the following: we say that a formula φ(x̄, ȳ) is stable (for T) if there is exists an integer n such that in a model M of T, any two sequences of tuples (ā_{i}) and (b̄_{j}) indexed by some initial segment of ℕ, and satisfying

M ⊧ φ(ā_{i}, b̄_{j}) ⟺ i < j,

have length ≤ n. The (complete) theory T is stable iff all formulas are stable. Stability forbids in particular the existence of an infinite (definable) linear ordering in models of T.

It is believed that the theory T of non-abelian free groups is stable. One question is to understand better the sets definable in free groups. An arbitrary Boolean combination of ∀∃-definable sets is quite an intractable object. The hope is that the complication originates from certain definable sets. I.e., that there are a few families of ∀∃-definable sets, such that if one adds suitable relation symbols for these definable sets, then one can eliminate quantifiers to a lower level. Ideally to existential formulas, but one shouldn’t be too optimistic.

There are also questions related to induced structure. For instance, let g ≠ 1, and consider the stabiliser C(g) of g in the free group F. We know that C(g) is isomorphic to the abelian group ℤ. One question is: what is the structure induced by F on C(g)? If one knows that T is stable, this reduces to the following: let D ⊂ F^{m} be definable (without parameters). Describe D ∩ C(g)^{m}. Is it definable in the structure (C(g), ·,^{−1}, 1)? (Maybe the answer to this question is trivially no, but one can ask analogous questions for any definable subset of F^{n}). If it were, then the induced structure would be very simple: indeed the theory of ℤ in the language of groups enlarged by adding unary predicates S_{n} for each of the subgroups nℤ of ℤ, n > 1, eliminates quantifiers.

Here we are using the following property of a stable theory: let M be a model of a stable theory T, let S be a 0-definable subset of M^{n}, and let D be an M-definable subset of M^{mn}. Then D ∩ S^{m} is definable with parameters from S. (Warning: the formula may change).

3. Ultraproducts, Łos theorem In this section we will introduce an important tool: ultraproducts. They are at the

centre of many applications, within and outside model theory.

(3.1) Filters and ultrafilters. Let I be a set. A filter on I is a subset F of P(I) (the set of subsets of I), satisfying the following properties:

(1) I ∈ F, ∅ ∉ F.

(2) If U ∈ F and V ⊇ U, then V ∈ F.

(3) If U, V ∈ F, then U ∩ V ∈ F. A ultrafilter on I is a filter on I which is maximal for inclusion. Equivalently, it is

filter F such that for any U ∈ P(I), either U ∈ F or I \ U ∈ F.

(3.2) Remarks. (1) Note that condition (1) forbids that both U and I \ U belong to the same filter on I.

(2) Using Zorn’s lemma (and therefore the axiom of choice), every filter on I is contained in a ultrafilter.

(3) If G ⊂ P(I) has the finite intersection property (i.e., the intersection of finitely many elements of G is never empty), then G is contained in a filter. The filter generated by G is then the set of elements of P(I) containing some finite intersection of elements of G.

(3.3) Principal and non-principal ultrafilters, Fréchet filter. Let I be a set. A ultrafilter F on I is principal if there is i ∈ I such that {i} ∈ F (and then we will have: U ∈ F ⟺ i ∈ U). A ultrafilter is non-principal if it is not principal. Note that if I is finite, then every ultrafilter on I is principal.

Let I be infinite. The Fréchet filter on I is the filter F_{0} consisting of all cofinite subsets of I. A ultrafilter F on I is then non-principal if and only if contains the Fréchet filter on I. Note that if S ⊆ I is infinite, then F_{0} ∪{S} has the finite intersection property, so that it is contained in a ultrafilter.

(3.4) Cartesian products of L-structures. Fix a language L. Let I be an index set, and (M_{i}), i ∈ I, a family of L-structures. We define the L-structure M = ∏_{i∈I} M_{i} as follows:

— The universe of M is simply the cartesian product of the M_{i}’s, i.e., the set of sequences (a_{i})_{i∈I} such that a_{i} ∈ M_{i} for each i ∈ I.

— If c is a constant symbol of L, then c^{M} = (c^{M_{i}})_{i∈I}.

— If R is an n-ary relation symbol, then R^{M} = ∏_{i∈I} R^{M_{i}}.

— If f is an n-ary function symbol and ((a_{1,i})_{i}, …, (a_{n,i})_{i}) ∈ M^{n}, then

f^{M}((a_{1,i})_{i}, …, (a_{n,i})_{i}) = (f^{M_{i}}(a_{1,i}, …, a_{n,i}))_{i∈I}.

(3.5) Reduced products of L-structures. Let I be a set, F a filter on I, and (M_{i}), i ∈ I, a family of L-structures. The reduced product of the M_{i}’s over F, denoted by ∏_{i∈I} M_{i}/F, is the L-structure defined as follows:

— The universe of ∏_{i∈I} M_{i}/F is the quotient of ∏_{i∈I} M_{i} by the equivalence relation ≡_{F} defined by

(a_{i})_{i} ≡_{F} (b_{i})_{i} ⟺ {i ∈ I | a_{i} = b_{i}} ∈ F.

We denote by (a_{i})_{F} the equivalence class of the element (a_{i})_{i} for this equivalence relation. The structure on ∏_{i∈I} M_{i}/F is then simply the “quotient structure”, i.e.,

— The interpretation of c is (c^{M_{i}})_{F}, for c a constant symbol of L.

— If R is an n-ary relation symbol, and if a_{1}, …, a_{n} ∈ ∏_{i∈I} M_{i}/F are represented by (a_{1,i})_{i}, …, (a_{n,i})_{i} ∈ ∏_{i∈I} M_{i}, then we set

∏_{i∈I} M_{i}/F ⊧ R(a_{1}, …, a_{n}) ⟺ {i ∈ I | (a_{1,i}, …, a_{n,i}) ∈ R^{M_{i}}} ∈ F.

— If f is an n-ary function symbol and if a_{1}, …, a_{n} ∈ ∏_{i∈I} M_{i}/F are represented by (a_{1,i})_{i}, …, (a_{n,i})_{i} ∈ ∏_{i∈I} M_{i}, then we set

f^{M}(a_{1}, …, a_{n}) = (f^{M_{i}}(a_{1,i}, …, a_{n,i}))_{F}.

The properties of filters guarantee that the quotient structure is well-defined. Note that the quotient map : ∏_{i∈I} M_{i} → ∏_{i∈I} M_{i}/F, (a_{i})_{i} ↦ (a_{i})_{F}, is a morphism of L-structures. Definitions. If all structures M_{i} are equal to a structure M, then we write M^{I}/F instead of ∏_{i} M_{i}/F, and the structure is called a reduced power of M. If the filter F is an ultrafilter, then ∏_{i} M_{i}/F is called the ultraproduct of the M_{i}’s (with respect to F), and M^{I}/F the ultrapower of M (with respect to F).

(3.6) Łos Theorem. Let I be a set, F a ultrafilter on I, and (M_{i}), i ∈ I, a family of L-structures. Let φ(x_{1}, …, x_{n}) be an L-formula, and let a_{1}, …, a_{n} ∈ ∏_{i∈I} M_{i}/F be represented by (a_{1,i})_{i}, …, (a_{n,i})_{i} ∈ ∏_{i∈I} M_{i}. Then

∏_{i∈I} M_{i}/F ⊧ φ(a_{1}, …, a_{n}) ⟺ {i ∈ I | M_{i} ⊧ φ(a_{1,i}, …, a_{n,i})} ∈ F.

(3.7) Corollary. Let I be a set, F an ultrafilter on I, and M an L-structure. Then the natural map M → M^{I}/F, a ↦ (a)_{F}, is an elementary embedding. (Here (a)_{F} is the equivalence class of the sequence with all terms equal to a).

(3.8) Remarks and comments. Let I be an infinite index set, and F a ultrafilter on I.

(1) If F is principal, say {j} ∈ F, then ∏_{i∈I} M_{i}/F ≃ M_{j} for any family of L-structures M_{i}, i ∈ I.

(2) Suppose that the M_{i}’s are fields, with maybe additional structure (e.g., an ordering, new functions, etc.). Consider the ideal M of ∏_{i} M_{i} generated by all elements (a_{i})_{i} such that {i ∈ I | a_{i} = 0} ∈ F. Then M is a maximal ideal of ∏_{i} M_{i}, and quotienting by the equivalence relation ≡_{F} is equivalent to quotienting by the maximal ideal M. The strength of Łos theorem is to tell you that the elementary properties of the M_{i}’s, including the ones depending on the additional structure, are preserved. E.g., that ℝ^{I}/F is a real closed field.

(3.9) Shelah’s isomorphism theorem. Let M and N be two L-structures. Then M ≡ N if and only if there is a ultrafilter F on a set I such that M^{I}/F ≃ N^{I}/F.

Note the following immediate consequence: if M ≡ N, then there is M^{∗} in which both M and N embed elementarily.

(3.10) Application 1: proof of the compactness theorem. Let T be a theory in a language L, and assume that every finite subset s of T has a model M_{s}. Then T has a model.

Proof. If T is finite, there is nothing to prove, so we will assume that T is infinite. Let I be the set of all finite subsets of T. For every φ ∈ T, let S(φ) = {s ∈ I | φ ∈ s}. Then the family G = {S(φ) | φ ∈ T } has the finite intersection property, and therefore is contained in a ultrafilter F. We claim that ∏_{s∈I} M_{s}/F is a model of T: let φ ∈ T. Then, by assumption, {s ∈ I | M_{s} ⊧ φ} contains S(φ), and therefore belongs to F. By Łos’s theorem, ∏_{s∈I} M_{s}/F ⊧ φ.

(3.11) Application 2: Lefshetz principle. Let φ be a sentence of the language L_{R}. The following conditions are equivalent:

(1) ℂ ⊧ φ.

(2) If K is an algebraically closed field of characteristic 0, then K ⊧ φ.

(3) There is an integer n, such that if p is a prime number > n, then 𝔽̃_{p} ⊧ φ.

(4) There is an integer n, such that if p is a prime number > n and K is an algebraically closed field of characteristic p, then K ⊧ φ.

Proof. The equivalences of (1) and (2), and of (3) and (4) are clear, by (2.14). Assume (2). Then ACF∪{p ≠ 0 | p a prime } ⊧ φ. By compactness, there are finitely many prime numbers p_{1}, …, p_{m} such that ACF∪{p_{1} ≠ 0, …, p_{m} ≠ 0} ⊧ φ. Take n > sup{p_{1}, …, p_{m}}. This shows that (2) implies (3).

Assume (3), and let F be a non-principal ultrafilter on the set P of primes. For each prime p, choose an algebraically closed field K_{p} of characteristic p. By assumption, {p ∈ P | K_{p} ⊧ φ} ∈ F, and therefore ∏_{p∈P} K_{p}/F ⊧ φ. For each p, the set {q ∈ P | q ≠ p} is also in the ultrafilter. By Łos’s Theorem, ∏_{p∈P} K_{p}/F is an algebraically closed field of characteristic 0, and therefore shows (2).

(3.12) Application 3: Orderable groups. Let G be a group, and assume that every finitely generated subgroup of G is orderable. Then G is orderable. Proof. Let I be the set of finite subsets of G. For each s ∈ I, let G_{s} be the subgroup of G generated by s, and fix an ordering ≤ on G_{s}. Let F be a ultrafilter on I containing all sets S(g) = {s ∈ I | g ∈ s} for g ∈ G, and consider the L_{G} ∪ {≤}-structure

(G^{∗}, ·,^{−1}, 1, ≤) = ∏_{s∈I}(G_{s}, ·,^{−1}, 1, ≤)/F.

Then G^{∗} is an ordered group, by Łos theorem. We embed G in G^{∗} in the following fashion: for g ∈ G, we set

f(g) = (g_{s})_{F}, where g_{s} = \{ \begin{matrix}g & if g ∈ G_{s} , \\ 1 & otherwise. \end{matrix}

One checks that f is a group embedding, and f(G) is therefore an ordered group.

(3.13) Types. Let M be an L-structure, A ⊆ M, and b̄ ∈ M^{m}. The type of b̄ over A, denoted by tp(b̄/A) (or tp_{M}(b̄/A)), is the set of all formulas φ(ā, ȳ) satisfied by b̄ in M, where ā is a finite tuple of elements of A.

One has the following result: if b̄, c̄ realise the same type over A in M, i.e., if tp(b̄/A) = tp(c̄/A), then there is an elementary extension M^{∗} of M, and an automorphism of M^{∗}, which fixes the elements of A and sends b̄ to c̄.

More generally, an n-type over a subset A of M is a set Σ(ȳ) of formulas φ(ā, ȳ) in the n-tuple ȳ of variables and with ā ∈ A, which is finitely realisable in M, i.e., is such that if s ⊂ Σ is finite, then there is b̄ ∈ M^{n} satisfying all the formulas of s.

(3.14) Application 4: ω_{1}-saturation. Let I be a countable set, F a non-principal ultrafilter on I, and (M_{i}), i ∈ I, a family of L-structures, where |L| ≤ ℵ_{0}. Let A ⊂ M^{∗} = ∏_{i∈I} M_{i}/F be countable, and let Σ(ȳ) be a type over A. Then Σ(ȳ) is realised in M^{∗}, i.e., there is b̄ ∈ M^{∗} which satisfies all the formulas of Σ(ȳ).

Another way of stating this property is to say that if (S_{n}), n ∈ ℕ, is a countable family of definable subsets of M^{∗}^{m} with the finite intersection property, then ⋂_{n} S_{n} ≠ ∅.

(3.15) A constructions of ℝ. We will present a construction allowing one to construct ℝ, coming from non-standard analysis. Let L = {+, −, ≤, 0) be the language of abelian ordered groups, and endow ℝ with its natural L-structure.

We fix a non-principal ultrafilter F on I = ℕ. Assume that for each i we are given an L-substructure Γ_{i} of ℝ (i.e., an additive subgroup of ℝ with the induced ordering).

Consider the ordered groups Γ^{∗} = ∏_{i∈I} Γ_{i}/F and ℝ^{∗} = ℝ^{I}/F. We have a natural embedding Γ^{∗} → ℝ^{∗} induced by each of the inclusions Γ_{i} ⊆ ℝ. Note that ℝ^{∗} also has a ring structure, and therefore contains a copy of (the ring) ℤ. Define

R^{fin} = {g ∈ ℝ^{∗} | ∃c ∈ ℕ − c ≤ g ≤ c}
μ = {g ∈ ℝ^{∗} | ∀c ∈ ℕ − 1 ≤ cg ≤ 1}
Γ^{fin} = Γ^{∗} ∩ R^{fin} μ_{Γ} = Γ^{∗} ∩ μ.

Then R^{fin} is the convex hull of ℤ in ℝ^{∗}. Both Γ^{fin} and μ_{Γ} are convex subgroups of Γ^{∗}. Hence, Γ_{F} = Γ^{fin}/μ_{Γ} is an ordered abelian group, which is clearly archimedean. There are three possibilities for this group: one possibility is that it is trivial: this is the case for instance if each Γ_{i} = iℤ. The second possibility is that it is discrete, i.e., has a smallest positive element. It is then isomorphic to ℤ. The third case is when Γ_{F} has no smallest positive element. It is then isomorphic to a dense additive subgroup of ℝ (because it is archimedean), and we claim that it equals ℝ. It suffices to show that Γ_{F} is complete. Let (a_{n})_{n∈ℕ} and (b_{n})_{n∈ℕ} be sequences of elements of Γ_{F} such that a_{n} < b_{m} for all n, m. Lift these sequences to sequences (a′_{n})_{n∈ℕ} and (b′_{n})_{n∈ℕ} in Γ^{fin}. Then a′_{n} < b′_{m} for all m, n. By ω_{1}-saturation of Γ^{∗} (see (3.14)), there is an element c′ ∈ Γ^{fin} such that a′_{n} < c′ < b′_{m} for all m, n. The image c of c′ in Γ_{F} then satisfies a_{n} ≤ c ≤ b_{m} for all n, m, and this shows the completeness of Γ_{F}.

The third case occurs in particular when the groups Γ_{i} are of the form r_{i}ℤ, where r_{i} ∈ ℝ, and (r_{i})_{F} ∈ μ. Or if they are dense in ℝ.

This construction is used in non-standard analysis, with all Γ_{i} equal to ℝ. The structure R^{fin} is then a valuation ring, with maximal ideal μ (if a ∈ R^{fin}, a ∉ μ, then there is c ∈ ℕ such that 1/c < |a| < c, so that 1/a also belongs to R^{fin}). The elements of μ are called infinitesimal, and the ring homorphism R^{fin} → ℝ = R^{fin}/μ is called the standard part.

Comments. One can do the same construction replacing 1 by an arbitrary element a ∈ ℝ^{∗}. Then one defines Γ^{fin,a} to be the intersection of Γ^{∗} with the convex hull of aℤ in ℝ^{∗}, and μ_{Γ,a} to be the elements of Γ^{∗}, whose archimedean class is smaller than the archimedean class of a. Then again one obtains an archimedean ordered group, which is either trivial, or isomorphic to ℤ, or to ℝ. The two constructions are really similar: if a is represented by the sequence (a_{i})_{i}, the first construction applied to the ordered groups Γ′_{i} = a_{i}Γ_{i} gives the same group.

(3.16) The theorem of Ax and Kochen. Consider the field 𝔽_{p}((t)) of power series over 𝔽_{p}. This is a valued field (where v(t) = 1), with value group ℤ and residue field 𝔽_{p}. The theorem of Ax and Kochen states that if F is a non-principal ultraproduct on the set p of primes, then there is an isomorphism of valued fields between the fields ∏_{p∈P} ℚ_{p}/F and ∏_{p∈P} 𝔽_{p}((t))/F.

This implies in particular that, given a sentence φ which holds in all but finitely many of the ℚ_{p}’s [resp., in all but finitely many of the 𝔽_{p}((t))′s], the sentence φ will hold in all but finitely many of the 𝔽_{p}((t))’s [resp., all but finitely many of the ℚ_{p}’s].

(3.17) Ultraproducts of many-sorted structures. The ultraproduct construction carries over to many-sorted structures without any trouble. If s is a sort, then the universe of sort s of the ultraproduct will simply be the ultraproduct of the universes of sort s. Functions between tuples of sorts and relations will be defined similarly. Maybe this is better seen with examples.

Example 1. See Example 1 of (2.15) for the notation. Let I be an index set, F a ultrafilter on I, and G_{i}, i ∈ I, a family of 2-sorted structures, where G_{i} = ((G_{i}, ·,^{−1}, 1), (Γ_{i}, +, 0, ≤ ), d_{i}).

Then G^{∗} = ∏_{i∈I} G_{i}/F will be the 2-sorted structure

(∏_{i∈I}(G_{i}, ·,^{−1}, 1)/F, ∏_{i∈I}(Γ_{i}, +, 0, ≤)/F, d^{∗})

where

d^{∗}((g_{i})_{F}, (h_{i})_{F}) = (d(g_{i}, h_{i}))_{F}.

Example 2. Let P be the set of primes, F a ultrafilter on P, and consider the 3-sorted structures Q_{p} introduced in the example 2 of (2.15).

Then ∏_{p} Q_{p}/F = (∏_{p} ℚ_{p}/F, ∏_{p} 𝔽_{p}/F, (ℤ ∪ {∞})^{P} /F, v^{∗}, π^{∗}), where ∏_{p} ℚ_{p}/F and ∏_{p} 𝔽_{p}/F have their natural field structure, ℤ^{P} /F the structure of an ordered group, with a distinguished constant ∞, and the maps v^{∗} and π^{∗} are defined by: v^{∗}((a_{p})_{F}) = (v(a_{p}))_{F}, π^{∗}((a_{p})_{F}) = (v(a_{p}))_{F}. Example 3. Let I be an index set, F a ultrafilter on I, K_{i}, i ∈ I, a family of fields, and for each i, R_{i} = (R_{n,i}) the ω-sorted structure defined in (2.15).

Then R^{∗} = ∏_{i∈I} R_{i}/F is the ω-sorted structure, with universe of sort n R_{n}^{∗} = ∏_{i∈I} R_{n,i}/F. The addition an multiplication are defined naturally. Observe that R^{∗} is simply the ω-sorted structure associated to the polynomial ring in X_{1}, …, X_{m} over K^{∗} = ∏_{i∈I} K_{i}/F. Example 4 - Asymptotic cones. We start with a family of 2-sorted structures X_{i} = ((X_{i}, x_{i}, ⋯), (Γ_{i}, +, −, ≤, 0), d_{i}), where (X_{i}, d_{i}) is a metric space with a distinguished point x_{i} (i ∈ I). The values of d_{i} are in the subgroup Γ_{i} of ℝ. We allow X_{i} to have extra structure, for instance a group structure. Fix a non-principal ultrafilter F on I. Consider

∏_{i∈I} X_{i}/F = (X^{∗}, Γ^{∗}, d^{∗}),

where (X^{∗}, x^{∗}, ⋯) = ∏_{i∈I}(X_{i}, x_{i}, ⋯)/F, Γ^{∗} = ∏_{i∈I} Γ_{i}/F and d^{∗}((y_{i})_{F}, (z_{i})_{F}) = (d_{i}(y_{i}, z_{i}))_{F}. We consider the ordered subgroup Γ^{fin} and μ_{Γ} defined in (3.15), set

X^{fin} = {y ∈ X^{∗} | d^{∗}(x^{∗}, y) ∈ Γ^{fin}},

and quotient X^{fin} by the equivalence relation

E(y, z) ⟺ d^{∗}(y, z) ∈ μ_{Γ}

to obtain a set X_{F}. We call the map X^{fin} → X_{F} the standard part, and denote it st. Then d^{∗} induces a map d_{F} : X_{F} → Γ_{F} = Γ^{fin}/μ_{Γ} ⊆ R^{fin}/μ = ℝ. Observe that the structure (X_{F}, ℝ, d_{F}), being a quotient of the substructure (X^{fin}, Γ^{fin}, d^{∗}) of (X^{∗}, Γ^{∗}, d^{∗}), will satisfy all quantifier free formulas (maybe with parameters) satisfied by (X^{∗}, Γ^{∗}, d^{∗}). In particular, the map d_{F} will satisfy the axioms of a distance, so that (X, d_{F}) is a metric space. If each (X_{i}, d_{i}) is δ_{i}-hyperbolic, then (X_{F}, d_{F}) will be (δ_{i})_{F}-hyperbolic. If for every i, and y, z ∈ X_{i}, there is a distance preserving embedding [0, d(y, z)] ∩ Γ_{i} → X_{i} which sends 0 to x and d(y, z) to y, the same will be true for (X_{F}, d_{F}). We will give the proof, as this shows how flexible ultraproducts are: one can add structure a posteriori. Let a, b ∈ X_{F}, be represented by (a_{i})_{u}, (b_{i})_{i} ∈ ∏_{i} X_{i} respectively. For each i, fix f_{i} : [0, d_{i}(a_{i}, b_{i})] ∩ Γ_{i} → X_{i} which is distance preserving and sends 0 to a_{i}, d_{i}(a_{i}, b_{i}) to b_{i}. Then consider f^{∗} : [0, d^{∗}((a_{i})_{F}, (b_{i})_{F}) ∩ Γ^{∗} → X^{∗} defined by f^{∗}((γ_{i})_{F}) = (f(γ_{i}))_{F} for (γ_{i})_{F} ∈ [0, d^{∗}((a_{i})_{F}, (b_{i})_{F}) ∩ Γ^{∗}. This map is distance preserving. Hence, as (a_{i})_{F}, (b_{i})_{F} ∈ X^{fin}, we may pass to the quotient, and get a map f_{F}, distance preserving, and sending some segment [0, γ] of Γ_{F} to X_{F}, and with f_{F}(0) = a, f(γ) = b.

If for each i, there is a group G_{i} acting on X_{i}, then the ultraproduct G^{∗} = ∏_{i∈I} G_{i}/F will also act on X^{∗}. But, unless there is an integer N such that for all i ∈ I, g ∈ G_{i} and y ∈ X_{i}, one has d_{i}(y, gy) ≤ Nd_{i}(x_{i}, y), the group G^{∗} will not act on X^{fin}.

If however all groups G_{i} are equal to some group G, and for every g ∈ G, there is N = N(g) such that for all i ∈ I and y ∈ X_{i}, d_{i}(y, gy) ≤ N(g)d_{i}(x_{i}, y), then G will act on X^{fin} and also on X_{F}.

Assume now that each X_{i} is in fact a group (G, ·,^{−1}, 1, a_{1}, …, a_{n}), with x_{i} = 1, and that d_{i} : G^{2} → ℝ equals (1/m_{i})d, where d is the distance on the Cayley graph of G with respect to the set {a_{1}, …, a_{n}} of generators of G (we set d(x, y) = d(1, yx^{−1}), so that d is invariant under right multiplication). If the element N = (m_{i})_{F} is infinite, then the image of d_{F} will be all of ℝ, provided of course our group G is infinite.

The equivalence relation E will correspond to being in the same left-coset of the subgroup G(0) = {g ∈ X^{fin} | d^{∗}(1, g) ∈ μ} of X^{fin}. Also, both G(0) and X^{fin} are convex subgroups of X^{∗}, but G(0) is not necessarily normal in X^{fin}, so that X_{F} does not necessarily have a group structure. However, the group X^{fin} acts (transitively) on X_{F}.

4. Real closed fields In this section we will study the theory ORCF of real closed fields, and show that it

is complete, decidable, eliminates quantifiers, etc. We will also mention o-minimality and some quite striking results obtained in the past decade.

(4.1) The theory ORCF. This is the theory in the language L = L_{R} ∪ {≤}, which says the following:

(1) ≤ is an ordering, axioms for ordered fields,

(2) every polynomial in one variable of odd order has a root,

(3) every non-negative element is a square.

A model of ORCF is called a real closed ordered field. If one replaces axioms (1) and (3) by the following axioms: (1’) axioms for fields of characteristic 0 (3’) an axiom expressing that the formula φ(x, y) = ∃z (z^{2} = y − x) defines an ordering ≤

on the field then one obtains a theory of the language L_{R}, denoted RCF, the models of which are called real closed fields. Note that every real closed field expands in a unique fashion to a model of ORCF, as the order is definable. We can also replace the scheme of axioms (2) and (3) by the axiom expressing the

sign change property: if P (X) ∈ F [X], and a < b ∈ F are such that P (a)P (b) < 0, then there is c such that a < c < b and P (c) = 0.

Clearly this axiom implies both (2) and (3).

(4.2) Well-known facts. To tell the truth, I don’t know how well-known these facts are. The first two are easy. Fact 1. Let F be a real closed field, and F_{0} the smallest subfield of F. Then the ordered field F_{0} is isomorphic to the ordered field ℚ. Fact 2. Let F be a real closed field, F_{0} a subfield of F, and assume that F_{0} is relatively algebraically closed in F. Then F_{0} is real closed. Fact 3. Let F be an ordered field. Then F is contained in a ordered real closed field F′ which is algebraic over F. Moreover, if F′′ is another algebraic extension of F which is a model of ORCF, then the ordered fields F′′ and F′ are isomorphic over F.

Thus the field F′ (or F′′) will be called the real closure of the ordered field F. The proof of this result is quite difficult, and involves Sturm’s algorithm.

(4.3) Tarski’s theorem. The theory ORCF eliminates quantifiers Proof. It suffices, by induction, to show that a formula of the form ∃y φ(x̄, y), where φ(x̄, y) is quantifier-free, is equivalent modulo ORCF, to a quantifier-free formula, Let F_{1} and F_{2} be two ordered real closed fields, let ā and b̄ be tuples in F_{1}, F_{2}, respectively, of the same length, and assume that they satisfy the same quantifier-free formulas. Assume also that F_{2} ⊧ ∃y φ(b̄, y), and let d ∈ F_{2} be such that F_{2} ⊧ φ(b̄, d). We will show that F_{1} ⊧ ∃y φ(ā, y).

Our assumption that ā and b̄ implies that there is an L-isomorphism f from the ordered subfield ℚ(ā) of F_{1} to the ordered subfield ℚ(b̄) of F_{2}, which sends ā to b̄. By facts 2 and 4, this isomorphism f extends to an isomorphism f : A_{1} → A_{2}, where A_{1} is the relative algebraic closure of ℚ(ā) in F_{1} (and hence its real closure), and A_{2} is the relative algebraic closure of ℚ(b̄) in F_{2}.

We will now work a little on the formula φ(x̄, y). We know that it is a finite disjunction of conjunction of formulas of the form

P (x̄, y) = 0,  P (x̄, y) > 0,  (1)

where P is polynomial with integral coefficients. Since (b̄, d) will necessarily satisfy one of the disjuncts of φ, we may assume that φ(x̄, y) is a conjunction of formulas of the form given in (1). Moreover, we may assume that there is only one equation: one uses the fact that in an ordered field, x_{1} = x_{2} = ⋯ = x_{n} = 0 is equivalent to x_{1}^{2} + x_{2}^{2} + ⋯ + x_{n}^{2} = 0. Hence, we may assume that the formula φ(x̄, y) is of the form

P (x̄, y) = 0 ∧ ⋀_{i=1}^{n} Q_{i}(x̄, y) > 0,

for some polynomials P and Q_{1}, …, Q_{n} with integral coefficients. If P is not the 0 polynomial, then d is algebraic over ℚ(b̄) and therefore belongs to A_{2}. Hence, as f is an isomorphism of ordered fields, f^{−1}(d) satisfies φ(ā, y), so that F_{1} ⊧ ∃y φ(ā, y).

This reasoning works equally well if d ∈ A_{2} (adding to φ(b̄, y) the equation P′(b̄, y) = 0, where P (b̄, Y) is the minimal polynomial of d over ℚ(b̄), so that we may assume that d ∉ A_{2} and that P is the 0 polynomial. Then our formula is a conjunctions of inequalities, and none of the polynomials Q_{i} is the 0 polynomial.

We consider the set of solutions of the equation ∏_{i=1}^{n} Q_{i}(b̄, y) = 0, and enumerate it as β_{1} < β_{2} < ⋯ < β_{m}. Then β_{1}, …, β_{m} ∈ A_{2}, and so d is in one of the open intervals (−∞, β_{1}), (β_{1}, β_{2}), …, (β_{m}, +∞). Observe that when restricted to any of these open intervals, the functions defined by the Q_{i}(b̄, y) do not change sign or take the 0-value. Also, f^{−1}(β_{1}) < f^{−1}(β_{2}) < ⋯ < f^{−1}(β_{m}) enumerate the roots of ∏_{i=1}^{n} Q_{i}(ā, y) = 0, and each of the corresponding intervals (−∞, f^{−1}(β_{1})), (f^{−1}(β_{1}), f^{−1}(β_{2})), …, (f^{−1}(β_{m}), +∞) of A_{1} is non-empty. We choose c ∈ A_{1} such that c < f^{−1}(β_{i}) ⟺ d < β_{i}. Then one checks that Q_{i}(ā, c) and Q_{i}(b̄, d) have the same sign for i = 1, …, n and are non-zero, so that c satisfies φ(ā, y) in A_{1} and also in F_{1}.

We have therefore shown that the formula ∃yφ(x̄, y) and the set Δ of quantifier-free L-formulas in x̄ satisfy the criterion given in (2.11). Hence, the formula ∃y φ(x̄, y) is equivalent modulo ORCF to a quantifier-free formula ψ(x̄). This implies that ∀y ¬φ(x̄, y) is equivalent modulo ORCF to the quantifier-free formula ¬ψ(x̄). Applying an easy induction argument (i.e., eliminating quantifiers one at a time) gives that ORCF eliminates quantifiers.

(4.4) Completeness of ORCF and decidability. The quantifier-free L-sentences are fairly simple: the only terms without variables are the terms of the form 1 + 1 + ⋯ + 1 and −(1 + 1 + ⋯ + 1). Therefore the quantifier-free sentences we have to decide are of the form n < m, n = m, for n, m ∈ ℤ. This is clearly decidable and shows that the theory ORCF is complete (every model of ORCF contains a copy of the ordered field ℚ). Since the axioms for ORCF are enumerable, the theory ORCF is decidable. Similarly for RCF. This gives Theorem (Tarski). The theories RCF and ORCF are complete and decidable.

(4.5) O-minimality. Let L be a language containing a binary relation ≤. An L-structure M is o-minimal iff the relation ≤ defines an ordering, and every M-definable subset of M is a finite union of points and of open intervals with their endpoints in M ∪ {−∞, +∞}.

Thus the real closed field (ℝ, +, −, ·, ≤, 0, 1) is o-minimal: this is essentially immediate using the quantifier-elimination of ORCF.

O-minimality is a very strong property. it is preserved under elementary equivalence, i.e., an L-structure elementarily equivalent to an o-minimal one, is also o-minimal. Thus we will talk of an o-minimal theory, meaning that its models are o-minimal. O-minimality allows one to prove cell-decomposition theorems, which describe definable sets in terms of “basic cells”. One of the very exciting developments of the past decade was the discovery of several o-minimal expansions of the ordered field of reals. A result rather simple to state is: (Wilkie). The theory of the field of real numbers with exponentiation, (ℝ, +, −, ·, exp, ≤, 0, 1), is model complete and o-minimal. Macintyre and Wilkie also showed that, assuming Schanuel’s conjecture, the theory of the field of real numbers with exponentiation, is decidable.

Symbols

⊧ (1.10) ≡ (2.1) ≺ (2.2)

A

ACF, algebraically closed field (2.5), (2.14) Ax and Kochen theorem (3.16) automorphism (1.5) atomic formula (1.7)

B

Boolean combination (1.7) bound variable (1.7)

C

chain of L-structures (2.3) Compactness theorem (2.8), (3.10) complete (2.1) completeness theorem (2.6) completion of a theory (2.14) consistent (2.1)

D

decidable (2.7) Δ(A), Δ^{+}(A), Diag(A) (2.17) definable sets (1.11) diagrams (2.17)

E

elementarily equivalent (2.1) elementary embedding (2.2) elementary extension (2.2) elementary substructure (2.2) elimination of quantifiers (2.4) embedding (1.5) equivalence modulo T (2.5) existential formula (1.7) existentially closed (2.4) expansion (2.17)

F filter (3.1) finite intersection property (3.2) finitely realisable (3.13) formulas (1.7) free variables (1.7) Fréchet filter (3.3)

G groups (language of) (1.4)

I Interpolation theorems (2.13) isomorphism (1.5)

L L(A) (2.17) language (1.1) Lefshetz principle (3.11) logical connectives (1.6) logical equivalence (1.8) Łos theorem (3.6) Löwenheim-Skolem (2.9)

M many-sorted structures (2.15) model (of a theory) (2.1) model complete (2.4) Mod(T) (2.1) morphisms (1.5)

O ω_{1}-saturation (3.14) o-minimality (4.5)

P

parameters (1.11) positive formula (1.7) prenex (1.8) preservation theorems (2.12) principal ultrafilter (3.3) products of L-structures (3.4)

Q

quantifier-free formula (1.7)

R

RCF, real closed field (4.1) real closure (4.2) reduct (2.17) reduced power of a L-structure (3.5) reduced product of L-structures (3.5) rings (language of) (1.4)

S

satisfaction (1.10) sentence (1.7) Shelah’s isomorphism theorem (3.9) Soundness theorem (2.6) stable formula, theory (2.18) substructure (L-) (1.3) structure (L-) (1.2)

T

Tarski’s test (for ≺) (2.2) terms (L-) (1.6) theory (L-) (2.1) T h(K), T h(M) (2.1) tp_{M}(ā), tp(ā/A) (2.14),(3.13) types (2.14),(3.13)

U

ultrafilter (3.1) ultraproduct, ultrapower (3.5) universal formula (1.7) universe (1.2)