Copyright\begin{matrix}c \\ ◯ \end{matrix}1982–1998 by Stephen G. Simpson

Math 563: Model Theory

Stephen G. Simpson

May 2, 1998

Department of Mathematics The Pennsylvania State University

University Park, State College PA 16802

   simpson@math.psu.edu
www.math.psu.edu/simpson/courses/math563/

Note: Chapters 12 and 13 are not finished.

2

Contents

1 Sentences and models 7 1.1 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Truth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Models and theories . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Complete theories 13 2.1 Definitions and examples . . . . . . . . . . . . . . . . . . . . . 13 2.2 Vaught’s test . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Applications of Vaught’s test . . . . . . . . . . . . . . . . . . . 16

3 The compactness theorem 21 3.1 Proof of the compactness theorem . . . . . . . . . . . . . . . . 21 3.2 Some applications to field theory . . . . . . . . . . . . . . . . 23 3.3 The Löwenheim-Skolem-Tarski theorem . . . . . . . . . . . . . 24

4 Decidability 27 4.1 Recursively axiomatizable theories . . . . . . . . . . . . . . . . 27 4.2 Decidable theories . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3 Decidable models . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Elementary extensions 35 5.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . 35 5.2 Existence of elementary extensions . . . . . . . . . . . . . . . 38 5.3 Elementary monomorphisms . . . . . . . . . . . . . . . . . . . 40 6 Algebraically closed fields 43

6.1 Simple field extensions . . . . . . . . . . . . . . . . . . . . . . 43 6.2 Algebraic closure . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.3 Completeness and model completeness . . . . . . . . . . . . . 49 6.4 Hilbert’s Nullstellensatz . . . . . . . . . . . . . . . . . . . . . 52

7 Saturated models 55 7.1 Element types . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.2 Saturated models . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.3 Existence of saturated models . . . . . . . . . . . . . . . . . . 60 7.4 Preservation theorems . . . . . . . . . . . . . . . . . . . . . . 63

8 Elimination of quantifiers 71 8.1 The model completion of a theory . . . . . . . . . . . . . . . . 71 8.2 Substructure completeness . . . . . . . . . . . . . . . . . . . . 73 8.3 The role of simple extensions . . . . . . . . . . . . . . . . . . . 76

9 Real closed ordered fields 79 9.1 Ordered fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 9.2 Uniqueness of real closure . . . . . . . . . . . . . . . . . . . . 83 9.3 Quantifier elimination for RCOF . . . . . . . . . . . . . . . . . 86 9.4 The solution of Hilbert’s 17th problem . . . . . . . . . . . . . 89

10 Prime models (countable case) 93 10.1 The omitting types theorem . . . . . . . . . . . . . . . . . . . 93 10.2 Prime models . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 10.3 The number of countable models . . . . . . . . . . . . . . . . 101 10.4 Decidable prime models . . . . . . . . . . . . . . . . . . . . . 104

11 Differentially closed fields of characteristic 0 109 11.1 Simple extensions . . . . . . . . . . . . . . . . . . . . . . . . . 109 11.2 Differentially closed fields . . . . . . . . . . . . . . . . . . . . 115 11.3 Differential closure (countable case) . . . . . . . . . . . . . . . 117 11.4 Ritt’s Nullstellensatz . . . . . . . . . . . . . . . . . . . . . . . 120

12 Totally transcendental theories 125 12.1 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 12.2 Rank of an element type . . . . . . . . . . . . . . . . . . . . . 125 12.3 Indiscernibles . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

12.4 Existence of saturated models . . . . . . . . . . . . . . . . . . 125

13 Prime models (uncountable case) 127 13.1 Strongly atomic models . . . . . . . . . . . . . . . . . . . . . . 127 13.2 Normal sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 13.3 Uniqueness and characterization of prime models . . . . . . . 127 6 CONTENTS

Chapter 1

Sentences and models

1.1 Symbols

1.

We assume the availability of a large supply of nonlogical symbols of the following kinds:

1. n-ary relation symbols \underline{R}( , …, ), n ≥ 1;

2. n-ary operation symbols \underline{o}( , …, ), n ≥ 1;

3. constant symbols \underline{c}. These collections of symbols are assumed to be disjoint.

2.

We make use of the following logical symbols:

1. propositional connectives ¬ (negation), ∧, ∨ (conjunction, disjunction), →, ↔ (implication, biimplication);

2. quantifiers ∀, ∃ (universal, existential);

3. equality =;

4. variables v_{0}, v_{1}, …, v_{n}, . . .. Note that = is a logical symbol although syntactically it behaves as a

binary relation symbol.

1.2 Formulas

1.

The notion of a term is defined inductively as follows. A constant symbol is a term. A variable is a term. If t_{1}, …, t_{n} are terms and \underline{o} is an n-ary operation symbol, then \underline{o}(t_{1}, …, t_{n}) is a term.

2.

The notion of atomic formula is defined as follows. If t_{1} and t_{2} are terms, then t_{1} = t_{2} is an atomic formula. If t_{1}, …, t_{n} are terms and \underline{R} is an n-ary relation symbol, then \underline{R}(t_{1}, …, t_{n}) is an atomic formula.

3.

The notion of a formula is defined inductively as follows. An atomic formula is a formula. If φ and ψ are formulas then so are ¬φ, φ ∧ ψ, φ ∨ ψ, φ → ψ, φ ↔ ψ. If φ is a formula and v is a variable, then ∀vφ and ∃vφ are formulas.

We assume familiarity with the concept of a free variable, i.e. one not bound by a quantifier. We assume unique readability of formulas.

4.

If S is a set of formulas and/or terms, the signature of S is the set of all nonlogical symbols occurring in it. This is sometimes called in the literature the similarity type of S. Note that = never bolongs to the signature since it is a logical symbol. We write sig(S) = signature of S.

5.

A sentence is a formula with no free variables.

Examples: The formula ∀x∃y(x+y = 0) is a sentence. Here + is a binary operation symbol, 0 is a constant symbol, and = is a logical symbol. The formula x + y = y + x is not a sentence.

If we write x, y, … in the same formula, we tacitly assume that x, y, … are distinct variables.

Examples, continued: The formula ∀x(∃y(y · y = x) ∨ ∃z(z · z = −x)) is a sentence. It is “logically equivalent” to the sentence ∀x∃y(y · y = x ∨ y · y = −x) but these two sentences are not identical. We asume that the student has some previous acquaintance with the syntactical and semantical notions of logical equivalence. These notions will be defined later.

1.3 Structures

1.

A structure is an ordered pair A = (|A|, Φ) where |A| is a nonempty set, called the universe of A, and Φ is a function whose domain is a set of nonlogical symbols. The domain of Φ is called the signature of A. To each n-ary relation symbol \underline{R} ∈ sig(A) we assume that Φ assigns an n-ary relation

R ⊆ |A|^{n} = \underbrace{|A| × ⋯ × |A|}_{n times} .

To each n-ary operation symbol \underline{o} ∈ sig(A) we assume that Φ assigns an n-ary operation

o : |A|^{n} → |A| .

To each constant symbol \underline{c} ∈ sig(A) we assume that Φ assigns an individual constant c ∈ |A|.

Example: the structure of the reals

R = (|R|, +, −, ·, 0, 1, <)

where |R| = ℝ. We cannot include ÷ because it is not an operation on |R| (because not everywhere defined). Here the universe is |R| = ℝ = (−∞, ∞); +, · are binary operations; − is a unary operation; 0, 1 are constants; < is a binary relation.

1.4 Truth

1.

Given a structure A and a sentence σ such that sig(σ) ⊆ sig(A), we assume known the meaning of

A ⊧ σ (A satisfies σ, σ is true in A) .

For example, R ⊧ ∀x∃y(y · y = x ∨ y · y = −x) expresses the fact that every real number or its negative is a square. Note that the structure

Z = (ℤ, +, ·, −, 0, 1, <) ,

where |Z| = ℤ = {…, −2, −1, 0, 1, 2, … }, has the same signature as R but satisfies the negation of the above sentence.

In general, A ⊧ σ means that σ is true in A when the variables are interpreted as ranging over |A|, the other symbols in σ being given their obvious interpretation.

Another example:

Z ⊧ ∀x(x > 0 → ∃y_{1}∃y_{2}∃y_{3}∃y_{4}(x = y_{1}^{2} + y_{2}^{2} + y_{3}^{2} + y_{4}^{2}))

and this expresses the fact that every positive integer is the sum of four squares.

1.5 Models and theories

1.

Let S be a set of sentences. A model of S is a structure M such that M ⊧ σ for all σ ∈ S, and sig(M) = sig(S).

For example, a group can be described as a model G = (|G|, ·,^{−1} , 1) of the axioms of group theory:

∀x∀y∀z((x · y) · z = x · (y · z))
∀x(x · 1 = 1 · x = x)
∀x(x · x^{−1} = x^{−1} · x = 1)

2.

The class of all models of S is denoted Mod(S). A sentence τ is said to be a logical consequence^{1} of S (written S ⊧ τ) if sig(τ) ⊆ sig(S), and M ⊧ τ for all M ∈ Mod(S).

A theory is a set T of sentences which is consistent and closed under logical consequence; in other words, T has at least one model, and τ ∈ T whenever τ is a sentence such that sig(τ) ⊆ sig(T) and M ⊧ τ for all M ∈ Mod(T).

For example, the theory of groups is the set of all logical consequences of the axioms of group theory. These axioms have many nonobvious logical consequences, e.g. the Jacobi identity

((x, y), z^{x}) · ((y, z), x^{y}) · ((z, x), y^{z}) = 1

where we use abbreviations (x, y) = x^{−1} · y^{−1} · x · y and x^{y} = y^{−1} · x · y.

3.

A model class is a nonempty class of structures all having the same signature. An elementary model class is a model class of the form Mod(S) where S is a consistent set of sentences. There are lots of nonelementary model classes, e.g. the class of finite groups.

If K is a model class, we write Th(K) for the theory of K, i.e. the set of sentences σ such that sig(σ) ⊆ sig(K) and M ⊧ σ for all M ∈ K. Note that Th(K) is a theory and for any theory T we have T = Th(Mod(T)). There is a natural 1-1 correspondence between theories and elementary model classes.

4.

If T is a theory and S ⊆ T, we say that S is a set of axioms for T if T = Th(Mod(S)). If there exists a finite set of axioms for T, we say that T is finitely axiomatizable.

For example, the theory of groups is finitely axiomatizable (a finite set of axioms for it is displayed above). We shall see later that the theory of fields of characteristic 0 is not finitely axiomatizable.

1Note: This definition is somewhat unusual because, for instance, ∀x(x < 0 ∨ x = 0 ∨ x > 0) is not a logical consequence of ∀x∀y(x < y ∨ x = y ∨ x > y), owing to the restriction on signature.

12 CHAPTER 1. SENTENCES AND MODELS

Complete theories

2.1 Definitions and examples

1.

A theory T is complete if for all sentences σ, either σ ∈ T or ¬σ ∈ T, provided sig(σ) ⊆ sig(T).

Examples: The theory of groups is not complete. The theory of fields of characteristic 0 is not complete (e.g. ∃x(x · x = 1 + 1) is true in ℝ, false in ℚ). We shall see later that the theory of algebraically closed fields of characteristic 0 is complete.

2.

Two structures A and B are elementarily equivalent (written A ≡ B) if they have the same signature and satisfy the same sentences. In other words, Th(A) = Th(B).

3.

Proposition. For a theory T the following are equivalent.

1. T is complete;

2. all models of T are elementarily equivalent; 3. T = Th(A) for some structure A.

Proof. Trivial.

4.

Exercise. Prove that the theory of dense linear ordreings without end points is complete. Use the method of elimination of quantifiers, described below.

axioms for linear orderings:

∀x∀y∀z(x < y ∧ y < z → x < z)

∀x∀y(x < y → ¬y < x)
∀x∀y(x < y ∨ x = y ∨ y < x)

dense : ∀x∀y(x < y → ∃z(x < z < y)) without end points : ∀x∃y∃z(y < x < z) .

5.

We use the following notational convention: φ(x_{1}, …, x_{n}) denotes a formula φ whose free variables are among x_{1}, …, x_{n}.

A theory T is said to admit elimination of quantifiers if for all formulas φ(x_{1}, …, x_{n}), n ≥ 1, there exists a quantifier free formula φ∗(x_{1}, …, x_{n}) such that

T ⊧ ∀x_{1} … ∀x_{n}(φ(x_{1}, …, x_{n}) ↔ φ∗(x_{1}, …, x_{n})) .

For the above exercise, show that the theory of dense linear orderings without end points admits elimination of quantifiers. (Do this by induction on the number of quantifiers, working from the inside out.) Once this has been done, completeness follows easily.

Historically, the method of elimination of quantifiers came very early. It is also the most versatile method for showing that algebraic theories are complete and/or decidable. The drawback is that the method is syntactical. We shall develop various model-theoretic methods for proving the same results.

2.2. VAUGHT’S TEST 15

2.2 Vaught’s test

Vaught’s test is another method for establishing completeness of theories. It is less versatile than quantifier elimination, but much easier to use.

1.

Two structures A and B are said to be isomorphic (written A ≅ B) if sig(A) = sig(B) and there exists an isomorphic map of A onto B, i.e. i : |A| → |B| such that

1. i is one-one and onto;

2. R^{A}(a_{1}, …, a_{n}) if and only if R^{B}(a_{1}, …, a_{n});

3. i(o^{A}(a_{1}, ..., a_{n})) = o^{B}(i(a_{1}), …, i(a_{n}));

4. i(c^{A}) = c^{B}. Note that isomorphic structures are “essentially identical”. In particular they satisfy the same sentences, i.e. A ≅ B implies A ≡ B.

2.

The cardinality or power of a structure A is the cardinality of its universe. For instance, we say that A is countable if and only if |A| is countable, etc. The power of A is denoted ∥A∥ or card(A).

3.

A theory T is said to be κ-categorical if (i) T has at least one model of power κ; (ii) any two such models are isomorphic.

4.

Theorem (Vaught’s test for completeness). Let T be a countable theory such that

(i) T has no finite models;

(ii) for some infinite cardinal κ, T is κ-categorical.

Then T is complete.

We shall prove this later as an application of the Löwenheim-Skolem-Tarski theorem. For now we content ourselves with giving various examples of how the theorem is used to prove completeness of specific theories.

2.3 Applications of Vaught’s test

1.

We can use Vaught’s test to show that the theory of dense linear orderings without end points is complete.

Clearly the theory has no finite models. We shall show that the theory is ℵ_{0}-categorical. Let A = (|A|, <^{A}) and and B = (|B|, <^{B}) be countable dense linear orderings without end points. To show A ≅ B we use a back-and-forth argument. Let |A| = {a_{n} : n ∈ ω}, |B| = {b_{n} : n ∈ ω}. The construction of an isomorphism proceeds in stages. At each stage we have constructed a finite partial isomorphism of A onto B. Stage 2n. Pick the least k so that a_{k} = a′ is not in the domain of the partial isomorphism so far. Find an element b′ ∈ |B| satisfying finitely many inequalities so that we can extend the partial isomorphism by adding to it the ordered pair (a′, b′). Stage 2n+1. Proceed as in stage 2n replacing a’s by b’s and vice versa. In this way we build up an isomorphism of A onto B.

2.

We use Vaught’s test to show that the theory of nontrivial torsion free divisible Abelian groups is complete.

Abelian groups:

∀x∀y∀z((x + y) + z = x + (y + z))
∀x∀y(x + y = y + x)
∀x(x + 0 = x)
∀x(x + (−x) = 0)

An Abelian group is said to be divisible if it satisfies

∀x∃y(ny = x)

for n = 1, 2, 3, . . .. This is an infinite set of axioms. Note that ny is an abbreviation for

\underbrace{y + ⋯ + y}_{n times} .

An Abelian group is said to be torsion free if it satisfies

∀x(nx = 0 → x = 0)

for n = 1, 2, . . .. This is again an infinite set of axioms.

An Abelian group is nontrivial if it contains a nonzero element. Clearly any nontrivial torsion free Abelian group is infinite. Thus our theory has no finite models. To prove completeness, we shall apply Vaught’s test by showing that our theory is κ-categorical for any uncountable cardinal κ.

An example of a torsion free divisible Abelian group is the additive group of the rationals (ℚ, +, −, 0). More generally, if V is any vector space over the field of rational numbers, then the additive group of V is torsion free and divisible.

Fact: Any torsion free divisible Abelian group is of this form.

Proof. Let A = (|A|, +, −, 0) be a torsion free divisible Abelian group. For a ∈ |A| and r ∈ ℚ we want to define ra. Let r = m/n, m, n ∈ ℤ, n > 0. Define

ra = some b with ma = nb .

We need to show that ra is well defined. So suppose ma = nb_{1} = nb_{2}. Then n(b_{1} − b_{2}) = 0. hence b_{1} − b_{2} = 0 by torsion freeness of A. The vector space axioms

(r_{1} + r_{2})a = r_{1}a + r_{2}a
r(a_{1} + a_{2}) = ra_{1} + ra_{2}
1a = a
(−r)a = −ra

are easily verified. Thus A is the additive group of a vector space over ℚ.

We shall need the following facts from the theory of vector spaces. (1) Any vector space V over a field F has a basis, i.e. a set U ⊆ V such that every element of V is uniquely expressible in the form

r_{1}u_{1} + ⋯ + r_{n}u_{n} , r_{i} ∈ F ,

where the u_{i} are distinct elements of U, 1 ≤ i ≤ n. (Proof: use Zorn’s lemma.) (2) Any two bases of V over F have the same cardinality, the dimension of V. (3) If V_{1} and V_{2} are vector spaces over F of the same dimension, then they are isomorphic over F.

Let A and B be torsion free divisible Abelian groups of power κ where κ is uncountable. As vector spaces over ℚ they have bases U_{A} and U_{B} respectively. Put λ = card(U_{A}). Since every element of |A| is of the form r_{1}u_{1} + ⋯ + r_{n}u_{n}, r_{i} ∈ ℚ, u_{i} ∈ U_{A}, we have |A| ≤ λ · ℵ_{0}. From this we easily deduce card(U_{A}) = λ = κ. Similarly card(U_{B}) = κ. So by fact (3), A ≅ B. This shows that our theory is κ-categorical. Hence by Vaught’s test it is complete.

A corollary of the result we have just proved is that the Abelian groups (ℚ, +, −, 0) and (ℝ, +, −, 0) are elementarily equivalent. Here ℚ = rationals, ℝ = reals.

3.

Remark. The theory of nontrivial torsion free divisible Abelian groups is not ℵ_{0} categorical, since there are countable vector spaces over ℚ of dimensions 1, 2, 3, . . .. The theory of dense linear orderings without end points is not κ-categorical, κ > ℵ_{0}.

4.

Remark. Let T_{p} be the theory of algebraically closed fields of characterstic p, where p is a prime or p = 0. We shall see later that Vaught’s test can be used to show that T_{p} is complete. Namely, T_{p} is κ-categorical for all κ > ℵ_{0}.

The field axioms are as follows:

axioms for a commutative ring:

∀x∀y∀z((x + y) + z = x + (y + z)) ∀x∀y(x + y = y + x) ∀x(x + 0 = x) ∀x(x + (−x) = 0) ∀x∀y∀z((x · y) · z = x · (y · z)) ∀x∀y(x · y = y · x) ∀x∀y∀z(x · (y + z) = x · y + x · z) 0 ≠ 1

field axiom: ∀x(x ≠ 0 → ∃y(x · y = 1)

If we weaken the last axiom to

∀x∀y((x ≠ 0 ∧ y ≠ 0) → x · y ≠ 0)

we get the axioms for a domain (usually called integral domain). A field (or domain) is said to be of characteristic p if p is the least n such that

n = \underbrace{1 + ⋯ + 1}_{n times} = 0 .

Here p will have to be a prime number (since m · n = 0 implies m = 0 or n = 0). If there is no such p, then we say that the field is of characteristic 0. For example ℚ, ℝ, ℂ, ℤ are of characteristic 0.

A field F = (|F|, +, −, 0, ·, 1) is said to be algebraically closed if it satisfies

∀x_{0}∀x_{1} … ∀x_{n}(x_{n} ≠ 0 → ∃y(x_{n}y^{n} + ⋯ + x_{1}y + x_{0} = 0))

for n = 1, 2, 3, . . .. For example, the fundamental theorem of algebra asserts that the complex field C = (ℂ, +, −, 0, ·, 1) is algebraically closed.

5.

Remark. A difficult theorem of Morley says that if a theory T is countable and κ-categorical for some uncountable cardinal κ, then it is κ-categorical for all uncountable cardinals κ. This shows that the class of theories to which Vaught’s test applies is rather limited. Many important complete theories are not κ-categorical for any κ. This limitation of Vaught’s test will be partly overcome by means of saturated models. (See theorem 7.3.6 below.)

The compactness theorem

In this chapter and in chapter 4 it will be convenient to assume that formulae have been defined in terms of ¬, ∨, ∃ only; then ∧, →, ↔, ∀ can be introduced by definition as usual.

3.1 Proof of the compactness theorem

1.

A set S of sentences is said to be consistent if it has a model. The following theorem is due to Gödel 1929 in the countable case and Malcev 1936 in the uncountable case.

2.

Theorem (compactness theorem). If every finite subset of S is consistent, then S is consistent.

Proof. We give a proof by transfinite induction in the style of Henkin 1949. Assume that S is finitely consistent, i.e. every finite subset of S has a model. Let κ = max(ℵ_{0}, card(S)). Thus κ is a cardinal; we identify cardinals with initial ordinals. Let \{\underline{c}_{γ} : γ < κ\} be new constant symbols, and put W = sig(S) ∪ \{\underline{c}_{γ} : γ < κ\}. Let \{σ_{γ} : γ < κ\} be an enumeration of all sentences σ with sig(σ) ⊆ W. Fix a variable x and let {φ_{γ}(x) : γ < κ} be an enumeration of all formulas φ with only free variable x and sig(φ) ⊆ W. By induction on γ define finitely consistent sets of sentences S_{γ}, γ ≤ κ, and a function h : κ → κ as follows.

Stage 0: S_{0} = S.

Stage 2γ + 1: Let h(γ) be the least β such that \underline{c}_{β} does not occur in S_{2γ} or in φ_{γ}(x). Define

S_{2γ+1} = S_{2γ} ∪ \{(∃xφ_{γ}(x)) → φ_{γ}(\underline{c}_{h(γ)})\} .

The sentence (∃xφ_{γ}(x)) → φ_{γ}(\underline{c}_{h(γ)}) is called a Henkin sentence. We claim that S_{2γ+1} is finitely consistent (assuming S_{2γ} was). Let M be a model of some finite subset of S_{2γ+1}. We want to expand M to a model of those sentences plus the Henkin sentence. First, interpret in |M| arbitrarily the nonlogical symbols in φ_{γ}(x) which are not interpreted in M. Call the resulting structure M′. Let M′′ be the result of interpreting the Henkin constant \underline{c}_{h(γ)} so as to make the Henkin sentence true.

Stage 2γ + 2: Let S_{2γ+2} = S_{2γ+1} ∪ {σ_{γ}} if this is finitely consistent; otherwise S_{2γ+2} = S_{2γ+1} ∪ {¬σ_{γ}}. If the former is not fintely consistent then the latter is.

Stage δ ≤ κ, δ limit ordinal: Let S_{δ} = ⋃_{γ<δ} S_{γ}. This is still finitely consistent.

We now build a model M directly from S_{κ}. Let T be the set of all variable free terms in S_{κ}. Define an equivalence relation ≈ on T by t_{1} ≈ t_{2} if and only if t_{1} = t_{2} ∈ S_{κ}. Put |M| = T/≈. If [t_{1}], …, [t_{n}] ∈ T/≈ and \underline{R} is an n-ary relation symbol, put

R([t_{1}], …, [t_{n}]) if and only if \underline{R}(t_{1}, …, t_{n}) ∈ S_{κ} .

If \underline{o} is an n-ary operation symbol define

o([t_{1}], …, [t_{n}]) = [\underline{o}(t_{1}, …, t_{n})] .

For \underline{c} a constant symbol put c = [\underline{c}]. Our model M = (|M|, Φ) is defined by |M| = T/≈, Φ(\underline{R}) = R, Φ(\underline{o}) = o, Φ(\underline{c}) = c.

We claim that, for all sentences σ with sig(σ) ⊆ W, M ⊧ σ if and only if σ ∈ S_{κ}. We prove this by induction on the number of propositional connectives in σ. For atomic σ this holds by definition of M. For σ = σ_{1} ∨σ_{2} or σ = ¬σ_{1} it is easy to check. Suppose σ = ∃yφ(y). If M ⊧ σ then M ⊧ φ(t) for some t ∈ T. Hence by induction φ(t) ∈ S_{κ}. Therefore ∃yφ(y) ∈ S_{κ} by finite consistency. Conversely, suppose ∃yφ(y) ∈ S_{κ}. By relabeling variables we may assume that y = x. Also φ(x) = φ_{γ}(x) for some γ < κ. Hence (∃xφ(x)) → φ(\underline{c}_{β}) ∈ S_{κ} where β = h(γ). Hence φ(\underline{c}_{β}) ∈ S_{κ} by finite consistency. Hence by induction M ⊧ φ(\underline{c}_{β}), hence M ⊧ ∃yφ(y). This completes the proof.

3.2 Some applications to field theory

1.

Theorem (A. Robinson). Suppose σ is a sentence which is true in all fields of characteristic 0. Then σ is true in all fields of characteristic p, for all but finitely many primes p (the “exceptional primes”).

Proof. If the conclusion fails, then ¬σ is consistent with the field axioms plus \underbrace{1 + ⋯ + 1}_{p} = 0, for infinitely many primes p. But, for primes p,

\underbrace{1 + ⋯ + 1}_{p} = 0 implies \underbrace{1 + ⋯ + 1}_{n} ≠ 0 for all n < p. Hence ¬σ is finitely

consistent with the theory of fields of characteristic 0. Hence, by the compactness theorem, ¬σ holds in some field of characteristic 0, contradiction.

2.

Corollary. The theory of fields of characteristic 0 is not finitely axiomatizable.

3.

An affine variety is a set X ⊆ ℂ^{n} such that

X = {(z_{1}, …, z_{n}) : f_{i}(z_{1}, …, z_{n}) = 0, 1 ≤ i ≤ k}

where f_{i}, 1 ≤ i ≤ k are polynomials in n variables with coefficients from ℂ. A mapping G : X → ℂ^{n} is said to be polynomial if there exist polynomials g_{j}, 1 ≤ j ≤ n in n variables with coefficients from ℂ, such that for all (z_{1}, …, z_{n}) ∈ X,

G(z_{1}, …, z_{n}) = (g_{1}(z_{1}, …, z_{n}), …, g_{n}(z_{1}, …, z_{n})) .

Theorem (Ax). Let G : X → X be a polynomial map of an affine variety in ℂ^{n} into itself. If G is one-one, then G is onto.

Proof. More generally, we shall prove that the theorem holds for an arbitrary algebraically closed field in place of ℂ. Besides the compactness theorem, we shall use completeness of the theory T_{p} of algebraically closed fields of characteristic p where p is 0 or a prime.

For prime p let \overline{𝔽}_{p} be the algebraic closure of the prime field 𝔽_{p} = ℤ/pℤ. Note that any finite set of elements in \overline{𝔽}_{p} is contained in a finite subfield of \overline{𝔽}_{p}. Hence the theorem holds for \overline{𝔽}_{p}.

Observe that the theorem holds for a particular field F if and only if F satisfies a certain collection of sentences. If one of these sentences σ is false in ℂ, then by completeness of T_{0} we have T_{0} ⊧ ¬σ. Hence T_{p} ⊧ ¬σ for all sufficiently large primes p. Hence \overline{𝔽}_{p} ⊧ ¬σ. This is a contradiction.

For more applications of the compactness theorem in field theory, see Robinson’s book and more recent literature. For applications to “local properties” in group theory, see Malcev’s book.

3.3 The Löwenheim-Skolem-Tarski theorem

1.

Note that the proof of the compactness theorem also established the following result: If S is (finitely) consistent then S has a model of power ≤ max(ℵ_{0}, card(S)).

2.

Theorem (Löwenheim-Skolem-Tarski). Let S be a set of sentences which has an infinite model. Let κ be a cardinal ≥ max(ℵ_{0}, card(S)). Then S has a model of power κ.

Proof. Let \{\underline{c}_{γ} : γ < κ\} be new constant symbols. Put

S^{∗} = S ∪ \{\underline{c}_{β} ≠ \underline{c}_{γ} : β < γ < κ\} .

Since S has an infinite model, S^{∗} is finitely consistent. Hence by the compactness theorem S^{∗} is consistent. Applying the remark above we find that S^{∗} has a model of power ≤ max(ℵ_{0}, card(S^{∗})) = κ. This model must have power exactly κ.

3.

Corollary (Vaught’s test). Let T be a theory which

1. has no finite models

2. is κ-categorical for some κ ≥ card(T).

Then T is complete.

Proof. Suppose not. Let A, B ∈ Mod(T) such that A ≢ B. By the Löwenheim-Skolem-Tarski theorem find A′, B′ of power κ such that A ≡ A′, B ≡ B′. Then A′ ≢ B′. Hence A′ ≅ B̸′ so T is not κ-categorical.

26 CHAPTER 3. THE COMPACTNESS THEOREM

Decidability

4.1 Recursively axiomatizable theories

1.

Let V be a fixed recursive^{1} signature. The formulas φ with sig(φ) ⊆ V can be Gödel numbered in the usual way. This permits notions from recursion theory to be introduced. For instance, a set F of formulas is said to be recursive if its set of Gödel numbers {♯(φ) : φ ∈ F } is recursive, etc.

2.

Definition. A theory T is said to be recursively axiomatizable if (i) sig(T) is recursive, and (ii) T has a recursive set of axioms.

Remark. The notion of recursive axiomatizability is an important generalization of that of finite axiomatizability. Most theories which arise in practice have finite signature and are recursively axiomatizable, e.g. the theory of groups, the theory of fields of characteristic 0, first order Peano arithmetic, ZF set theory. Examples of theories which are not recursively axiomatizable are: the theory of finite groups; Th(Z) where Z = (ℤ, +, −, ·, 0, 1, <).

1i.e. V is a recursive set, and we can recursively identify the elements of V as n-ary relation or operation symbols or constant symbols. This is the case if V is finite.

3.

A very important general result about recursively axiomatizable theories is the following, which is a reformulation of Gödel’s completeness theorem.

Theorem (essentially Gödel 1929). Let T be a recursively axiomatizable theory. Then T is recursively enumerable.

This theorem would usually be proved, following Gödel, by showing that T can be generated from its axioms and a certain explicit recursive set of “logical axioms” by means of a certain explicit recursive set of “logical rules”. One would then apply Church’s thesis to conclude that T is recursively enumerable. Such a proof would give more or less information depending on the choice of logical axioms and rules. We shall give a “bare bones” proof which avoids these concepts entirely.

4.

Definition. A sentence τ is logically valid if A ⊧ τ for all structures A with sig(A) ⊆ sig(τ).

5.

Lemma. Let V be a fixed recursive signature. The set of all logically valid sentences τ with sig(τ) ⊆ V is recursively enumerable.

Proof. We may safely assume that V contains no operation symbols. We may also assume that the only logical symbols are ¬, ∨, ∃. (Thus we are dispensing with =.)

Let \{\underline{c}_{n} : n ∈ ω\} be a recursive set of new constant symbols and put W = V ∪ \{\underline{c}_{n} : n ∈ ω\}. Let \{φ_{n}(v_{i_{n}}) : n ∈ ω\} be a recursive enumeration of all formulas φ(v_{i}) with exactly one free variable and with sig(φ) ⊆ W. We can choose^{2} our enumeration so that

sig(φ_{n}(v_{i_{n}})) ⊆ V ∪ \{\underline{c}_{0}, …, \underline{c}_{2n−1}\} .

We shall work with Henkin sentences (∃v_{i_{n}}φ_{n}(v_{i_{n}})) → φ(\underline{c}_{2n}). Let S = \{σ_{n} : n ∈ ω} be a recursive enumeration of all sentences σ with sig(σ) ⊆ W.

2This amounts to arranging things so that, in the proof of the compactness theorem 3.1, the function h is given by h(n) = 2n.

4.1. RECURSIVELY AXIOMATIZABLE THEORIES 29

Given a sentence τ with sig(τ) ⊆ V, we have

τ is logically valid

⇔ ¬τ has no model

⇔ ¬τ has no countable model (Löwenheim-Skolem theorem)

⇔ there is no structure A such that |A| = \{\underline{c}_{n} : n ∈ ω\} and sig(A) = W and A ⊧ ¬τ and, for all n, A ⊧ (∃v_{i_{n}}φ_{n}(v_{i_{n}})) → φ_{n}(\underline{c}_{2n})

⇔ there is no function f : S → {0, 1} such that for all n, f(¬σ_{n}) = 1 − f(σ_{n}), and for all m and n, f(σ_{m} ∨ σ_{m}) = max(f(σ_{m}), f(σ_{n})) and f(∃v_{i_{n}}φ_{n}(v_{i_{n}})) = f(φ_{n}(\underline{c}_{2n}) ≥ f(φ_{n}(\underline{c}_{m})).

⇔ ∀f : S → {0, 1} ∃nR(f ↾ S_{n}, τ) where S_{n} = {σ_{0}, …, σ_{n−1}} and R is a fixed primitive recursive relation

⇔ ∃N ∀f : S → {0, 1} (∃n ≤ N) R(f ↾ S_{n}, τ) (by König’s lemma)

⇔ ∃N P (N, τ) where P is a fixed primitive recursive relation.

This proves the lemma.

Remark. The set of logically valid sentences is not recursively enumerable (“Church’s theorem”).

6.

Proof of the theorem. Given a recursively axiomatizable theory T, let A = {τ_{n} : n ∈ ω} be a recursive set of axioms for T. Put A_{n} = {τ_{0}, …, τ_{n−1}}. If σ is a sentence with sig(σ) ⊆ sig(T), we have

σ ∈ T

⇔ A ⊧ σ

⇔ ∃n A_{n} ⊧ σ (compactness theorem)

⇔ ∃n [ ⋀_{i=0}^{n−1} τ_{i} → σ is logically valid ].

By the lemma, the expression in square brackets is recursively enumerable. Hence so is T.

7.

Exercise (Craig). Prove the converse of the above theorem: If a theory T with sig(T) recursive is recursively enumerable, then it is recursively axiomatizable.

4.2 Decidable theories

1.

Definition. A theory T is decidable if (i) sig(T) is recursive, (ii) T is recursive.

Remark. Every decidable theory is recursively axiomatizable, but the converse fails, e.g. first order Peano arithmetic. there even exist finitely axiomatizable undecidable theories, e.g. Robinson’s Q, the theory of groups, the theory of fields.

2.

Remark. The first order theories which are important in algebra tend to be decidable. We make a short table.

Decidable  Undecidable
Abelian groups  (finite) groups
Boolean algebras  (finite) distributive lattices

linear orderings

∗algebraically closed fields  fields of characteristic p
∗Th(ℝ) = real closed fields  fields of characteristic 0
finite fields  ordered fields

∗differentially closed fields of char. 0

ordered Abelian groups

Th(ℚ_{p}), ℚ_{p} = p-adic rationals

Note: A ∗ indicates that these decidability results will be proved later.

A useful sufficient condition for decidability is the following:

3.

Theorem. Let T be a theory which is recursively aximatizable and complete. Then T is decidable.

Proof. By the previous theorem, T is recursively enumerable. Also its complement

\overline{T} = \{σ : σ is a sentence, sig(σ) ⊆ sig(T), σ ∉ T \}
= {σ : ¬σ ∈ T } (by completeness)

is recursively enumerable. Hence T is recursive.

4.

Examples. We have seen in exercise 2.1.4 that the theory of dense linear orderings without end points is complete. It is also recursively (in fact finitely) axiomatizable. Hence by the previous theorem, it is complete.

Remark. Each of the following theories will be proved complete later: algebraically closed fields of characteristic 0 or a prime p, real closed fields, differentially closed fields of characteristic 0. Decidability then follows by the previous theorem.

5.

Remark. The most versatile method for proving that an algebraic theory T is decidable is quantifier elimination. In order to decide whether σ ∈ T one constructs an equivalent quantifier-free sentence σ^{∗}. It should be easy to decide whether σ^{∗} ∈ T.

4.3 Decidable models

1.

Definition. A countable structure A is decidable if (i) sig(A) is finite; (ii) there exists an enumeration of the universe of A, |A| = {a_{k} : k ∈ ω}, such that

{(♯(φ(v_{1}, …, v_{n})), ⟨k_{1}, …, k_{n}⟩) : A ⊧ φ(a_{k_{1}}, …, a_{k_{n}})}

is recursive.

2.

Definition. A countable structure A is computable if (i) sig(A) is finite, and (ii) as above but restricted to atomic formulas φ.

For example, the structure Z = (ℤ, +, −, ·, 0, 1, <) is computable but not decidable. The structure (ℚ, <) is computable and hence decidable in view of the following proposition.

3.

Proposition. Let T be a recursively axiomatizable theory which admits elimination of quantifiers. If M ∈ Mod(T) is computable, then it is decidable.

Proof. To decide whether M ⊧ φ(a_{1}, …, a_{n}) find a quantifier free φ^{∗} such that T ⊧ ∀x_{1} … ∀x_{n}(φ ↔ φ^{∗}). Since T is recursively enumerable, we can find φ^{∗} recursively. So M ⊧ φ(a_{1}, …, a_{n}) if and only if M ⊧ φ^{∗}(a_{1}, …, a_{n}). Since φ^{∗} is a Boolean combination of atomic formulas, we can recursively decide whether M ⊧ φ^{∗}(a_{1}, …, a_{n}).

Example. It is fairly easy to see that the field \overline{ℚ} of algebraic numbers is recursive. However, it is also a model of the theory of algebraically closed fields of characteristic 0. We shall see later that this theory admits elimination of quantifiers. Hence \overline{ℚ} is decidable. Similarly, all countable algebraically closed fields are computable and hence decidable.

4.

Theorem. Let T be a decidable theory such that sig(T) is finite. Then T has a decidable model.

Proof. We imitate the proof of the compactness theorem 3.1.2. Put V = sig(T) and let \{\underline{c}_{m} : m ∈ ω\} be a recursive list of new constant symbols. Put W = V ∪ \{\underline{c}_{m} : m ∈ ω\}. Fix a variable x and let \{φ_{n}(x) : n ∈ ω\} be a recursive enumeration of all formulas φ(x) with only one free variable x and with sig(φ) ⊆ W. Let {σ_{n} : n ∈ ω} be a recursive enumeration of all sentences σ with sig(σ) ⊆ W. Perform the following recursive construction.

Stage 0: Let S_{0} = T.

Stage 2n + 1: Let h(n) be the least m such that \underline{c}_{m} does not occur in S_{2n} ∪ \{φ_{n}(x)\}. Put S_{2n+1} = S_{2n} ∪ \{(∃xφ_{n}(x)) → φ_{n}(\underline{c}_{h(n)})\}.

State 2n+2: Put S_{2n+2} = S_{2n+1}∪{σ_{n}} if this is consistent; S_{2n+2} = S_{2n+1}∪ {¬σ_{n}} otherwise. To see that we can make this decision recursively, note that S_{2n+1} = T ∪ {τ_{0}, …, τ_{2n}} for some finitely many sentences τ_{0}, …, τ_{2n}. Let τ̃_{0}, …, τ̃_{2n}, σ̃_{n} be the result of replacing the new constant symbols \underline{c}_{m} by new variables z_{m}. Then

S_{2n+1} ∪ {σ_{n}} is consistent

⇔ T ∪ ∃z_{0} … z_{j} (⋀_{i=0}^{2n} τ̃_{i} ∧ σ̃_{n}) is consistent

⇔ ¬∃z_{0} … z_{j} (⋀_{i=0}^{2n} τ̃_{i} ∧ σ̃_{n}) ∉ T,

and we can decide this recursively.

At the end of the construction, S_{ω} = ⋃_{n∈ω} S_{n} is a complete recursive theory. As in the proof of 3.1.2 we can build a model M = (|M|, Φ) where |M| = T/≈, T = {Gödel numbers of variable free terms}, t_{1} ≈ t_{2} if and only if t_{1} ≈ t_{2} ∈ S_{ω}, etc. M is decidable because we can identify |M| with the set of least elements of equivalence classes under ≈, and then M ⊧ φ(t_{1}, …, t_{n}) ⇔ φ(t_{1}, …, t_{n}) ∈ S_{ω}.

5.

Remark. There exist examples of recursively (even finitely) axiomatizable theories with no decidable (even computable) model. For example, we may take as axioms a finite fragment of Peano arithmetic together with a false Σ_{1}^{0} sentence.

34 CHAPTER 4. DECIDABILITY

Elementary extensions

5.1 Definition and examples

1.

Definition. Let A, B be structures with sig(A) = sig(B) and |A| ⊆ |B|. We say that A ⊆_{e} B if for all formulas φ(x_{1}, …, x_{n}) with only the free variables shown, and all a_{1}, …, a_{n} ∈ |A|, A ⊧ φ(a_{1}, …, a_{n}) if and only if B ⊧ φ(a_{1}, …, a_{n}). We then say that A is an elementary substructure of B, or B is an elementary extension of A.

2.

Let A, B be as above. We say that A ⊆ B (A is a substructure of B, B is an extension of A) if the above condition holds for atomic formulas φ.

3.

Example. Algebra is full of examples of substructures. E.g. if A and B are groups, A ⊆ B if and only if A is a subgroup of B. Similarly for rings, fields, linear orderings, etc.

4.

Example. Let Q = (ℚ, +, −, ·, 0, 1, <) and R = (ℝ, +, −, ·, 0, 1, <). Then clearly Q ⊆ R, but Q ⊈_{e} R since, for example, R ⊧ ∃x(x · x = 1 + 1) while Q does not. This example actually shows that Q ≢ R, i.e. Q and R are not elementarily equivalent (definition 2.1.2).

5.

Proposition. If A ⊆_{e} B then A ≡ B.

Proof. Obvious.

The converse does not hold, e.g.

6.

Example. Let ℕ = {0, 1, 2, … }, ℙ = {1, 2, … }. Then (ℙ, <) ⊆ (ℕ, <), and (ℙ, <) ≡ (ℕ, <) since they are isomorphic. However (ℙ, <) ⊧ ∀x(1 = x∨1 < x) and (ℕ, <) ⊧ ∃x(x < 1) so (ℙ, <) ⊈_{e} (ℕ, <) .

However, this phenomenon does not occur in theories which admit elimination of quantifiers:

7.

Proposition. If A, B ∈ Mod(T) where T admits elimination of quantifiers, then A ⊆ B implies A ⊆_{e} B.

Proof. Obvious.

8.

Examples. Let X be any densely ordered subset of the real numbers such that X has no first or last element. E.g. X = (0, 1) ∪ (1, 2) or X = (0, 1) ∪ ℚ. Then (X, <) ⊆_{e} (ℝ, <) because the theory of dense linear ordering without endpoints admits elimination of quantifiers.

9.

Example. The fact that the theory of algebraically closed fields admits elimination of quantifiers yields the following result:

Let \overline{ℚ} be the field of algebraic numbers. Let

f_{1}(x_{1}, …, x_{n}) = ⋯ = f_{k}(x_{1}, …, x_{n}) = 0 ≠ g(x_{1}, …, x_{n})

be a finite system of equations and inequations with coefficients in \overline{ℚ}. If the system has a solution in some extension field of ℚ, then it has one in \overline{ℚ}.

Proof. We may assume that the extension field is algebraically closed. Hence it is an extension of \overline{ℚ}, and by quantifier elimination the extension is elementary. This gives the result immediately if we look at the formula

∃x_{1} … ∃x_{n} [ ⋀_{i=1}^{k} f_{i}(x_{1}, …, x_{n}) = 0 ∧ g(x_{1}, …, x_{n}) ≠ 0 ] .

In other words, if a variety is nonempty, then it has a point with coordinates in \overline{ℚ}. This is closely related to Hilbert’s Nullstellensatz. (See chapter 6.)

9.

Definition (A. Robinson). A theory T is said to be model complete if for all A, B ∈ Mod(T), A ⊆ B implies A ⊆_{e} B.

The previous proposition says that if T admints elimination of quantifiers, then T is model complete. The converse is not true, e.g. T = Th(ℤ, +, −, 0, 1, <) = Presburger arithmetic. This theory is model complete but does not admint elimination of quantifiers. However, it admits elimination of quantifiers if we add defined relations ≡_{m}, m ≥ 2.

10.

Example. We shall show later that the theory of algebraically closed fields is model complete and admits elimination of quantifiers. These concepts have algebraic meaning: model completeness expresses the Hilbert Nullstellensatz, while quantifier elimination is an abstract formulation of the theory of resultants.

5.2 Existence of elementary extensions

1.

Theorem. Any infinite structure A has a proper elementary extension A^{∗}.

Proof. Let A = (|A|, Φ). Introduce new constant symbols \underline{a} for each a ∈ |A| and form the elementary diagram of A, i.e. the set of all sentences φ(\underline{a}_{1}, …, \underline{a}_{n}), sig(φ(x_{1}, …, x_{n})) ⊆ sig(A), a_{1}, …, a_{n} ∈ |A|, such^{1} that A ⊧ φ(\underline{a}_{1}, …, \underline{a}_{n}). Note that an elementary extension of A is virtually the same thing as a model of the elementary diagram of A.

Let \underline{c} be a new constant symbol and let S = (elementary diagram of A) ∪ \{\underline{c} ≠ \underline{a} : a ∈ |A|\}. Since |A| is infinite, S is finitely consistent. [ Details: Let S_{0} be a finite subset of S. Let c_{0} ∈ |A|, c_{0} ≠ a for all \underline{a} mentioned in S_{0}. Then A ⊧ S_{0} if we interpret \underline{a} as a, \underline{c} as c_{0}. ] Therefore by the compactness theorem, S is consistent, i.e. has a model B = (|B|, Ψ). Put A^{∗} = (|A^{∗}|, Φ^{∗}) where |A^{∗}| = |B|, Φ^{∗} = Ψ ↾ sig(A). Clearly A ⊆_{e} A^{∗} since B ⊧ elementary diagram of A. Also |A| ≠ |A^{∗}| since c = Ψ(\underline{c}) ∈ |A^{∗}| \ |A|.

2.

Example. Let R = (ℝ, +, −, ·, 0, 1, <, ⋯) where ⋯ represents other structure on ℝ. Let R^{∗} be a proper elementary extension of R. Then R^{∗} will contain infinitesimals, i.e. quantities δ such that 0 < δ < r for all r ∈ ℝ, r > 0. Elements of R^{∗} are sometimes called hyperreal numbers. They can be used to give a rigorous development of calculus based on infinitesimals. This is the beginning of a subject known as nonstandard analysis (A. Robinson).

3.

Exercise. Prove the upward Löwenheim-Skolem-Tarski theorem: Let A be an infinite structure. Let κ be a cardinal ≥ max(∥A∥, |sig(A)|). Then A has a proper elementary extension of power κ.

(Hint: Combine the elementary diagram method (used in the proof of the previous theorem) with the proof of the Löwenheim-Skolem-Tarski theorem in §3.3.)

1To be precise, instead of A ⊧ φ(\underline{a}_{1}, …, \underline{a}_{n}) we should write A_{|A|} ⊧ φ(\underline{a}_{1}, …, \underline{a}_{n})

where A_{|A|} = (|A|, Φ ∪ \{(\underline{a}, a) : a ∈ |A|\}).

In addition to the compactness theorem, another useful method for constructing elementary extensions is the method of elementary chains (Tarski/Vaught):

4.

A chain is a collection of structures (A_{α})_{α<δ} where δ is a limit ordinal, such that A_{α} ⊆ A_{β} for all α < β < δ.

5.

Proposition. Given a chain as above, there is one and only one structure A_{δ} = ⋃_{α<δ} A_{α} with the following properties:

1. |A_{δ}| = ⋃_{α<δ} |A_{α}|;

2. A_{α} ⊆ A_{δ} for all α < δ.

Proof. Obvious. Note that R^{A_{δ}} = ⋃_{α<δ} R^{A_{α}}, o^{A_{δ}} = ⋃_{α<δ} o^{A_{α}}, and c^{A_{δ}} = c^{A_{0}}.

6.

Theorem (Tarski/Vaught elementary chain principle). Given an elementary chain, i.e. a chain (A_{α})_{α<δ} such that A_{α} ⊆_{e} A_{β} for all α < β < δ, put A_{δ} = ⋃_{α<δ} A_{α}. Then A_{α} ⊆_{e} A_{δ} for all α < δ.

Proof. Show by induction on the length of a formula φ(x_{1}, …, x_{n}) that, for all α < δ and a_{1}, …, a_{n} ∈ |A_{α}|, A_{α} ⊧ φ(a_{1}, …, a_{n}) if and only if A_{δ} ⊧ φ(a_{1}, …, a_{n}). This is trivial if φ is atomic or a Boolean combination of shorter formulas. Assume that φ(x_{1}, …, x_{n}) = ∃yψ(x_{1}, …, x_{n}, y). If A_{α} ⊧ ∃yψ(a_{1}, …, a_{n}, y), let a_{n+1} ∈ |A_{α}| be such that A_{α} ⊧ ψ(a_{1}, …, a_{n}, a_{n+1}). Then A_{δ} ⊧ ψ(a_{1}, …, a_{n}, a_{n+1}) by induction, so A_{δ} ⊧ ∃yψ(a_{1}, …, a_{n}, y). Conversely, suppose A_{δ} ⊧ ∃yψ(a_{1}, …, a_{n}, y). Then A_{δ} ⊧ ψ(a_{1}, …, a_{n}, b) for some b ∈ |A_{δ}| = ⋃_{α<δ} |A_{α}|. Let β < δ be such that b ∈ |A_{β}|. Then A_{β} ⊧ ψ(a_{1}, …, a_{n}, b) by induction. Hence A_{β} ⊧ ∃yψ(a_{1}, …, a_{n}, y). Hence A_{α} ⊧ ∃yψ(a_{1}, …, a_{n}, y) since A_{α} ⊆_{e} A_{β}.

Later we shall use this theorem plus compactness to construct saturated models.

5.3 Elementary monomorphisms

1.

Let A, B be structures with sig(A) = sig(B). We say that f : |A| → |B| is an elementary embedding or elementary monomorphism if f is one-one and, for all formulae φ(x_{1}, …, x_{n}) and all a_{1}, …, a_{n} ∈ |A|, A ⊧ φ(a_{1}, …, a_{n}) ⇔ B ⊧ φ(f(a_{1}), …, f(a_{n})).

2.

If the above equivalence holds for atomic φ, we say that f is an embedding or monomorphism of A into B, or an isomorphism of A into (not necessarily onto) B. For example, what is usually called a monomorphism of groups, rings, etc. is a monomorphism in this sense.

The concepts of monomorphism and elementary monomorphism are essentially just trivial variants of the concepts of extension and elementary extension.

3.

Theorem. If A ≡ B then there exists a structure C such that both A and B are elementarily embeddable into C. (The converse is obvious.)

Proof. Let S = (elementary diagram of A) ∪ (elementary diagram of B). [ We assume that \{\underline{a} : a ∈ |A|\} ∩ \{\underline{b} : b ∈ |B|\} = ∅. ] Clearly any model of S yields a C as desired. So by the compactness theorem it suffices to show that S is finitely consistent. Let S_{0} be a finite subset of S. Say S_{0} = \{φ(\underline{a}_{1}, …, \underline{a}_{m}), ψ(\underline{b}_{1}, …, \underline{b}_{n})\} where sig(φ ∧ ψ) ⊆ sig(A) = sig(B), a_{1}, …, a_{m} ∈ |A|, b_{1}, …, b_{n} ∈ |B|. Since A ⊧ ∃x_{1} … x_{m}φ(x_{1}, …, x_{m}) and B ⊧ ∃y_{1} … y_{n}ψ(y_{1}, …, y_{n}) and A ≡ B, we see that ∃x_{1} … x_{m}φ(x_{1}, …, x_{m})∧ ∃y_{1} … y_{n}ψ(y_{1}, …, y_{n}) is consistent. Hence S_{0} is consistent, Q.E.D.

4.

From the above we can derive a criterion for model completeness:

Theorem (Robinson’s test). A theory T is model complete ⇔ for any A, B ∈ Mod(T) and monomorphism A → B, we can find an elementary extension A^{∗} of A and a monomorphism B → A^{∗} so that the diagram

\xymatrix{B \ar[drr] \\ A \ar[u] & ⊆_{e} & A^{∗}}

commutes.

Proof. ⇒: Since T is model complete, the monomorphism A → B is elementary, so we may take A^{∗} = B.

⇐: Given a monomorphism A → B where A, B ∈ Mod(T). Use the hypothesis repeatedly to construct a pair of elementary chains

[figure: B; =; B_{0}; e; B_{1}; e; ⋯; e; B_{n}; e; ⋯; A; =; A_{0}; e; A_{1}; e; ⋯; e; A_{n}; e; ⋯]

where all triangles commute. Hence A_{ω} = ⋃_{n∈ω} A_{n} ≅ ⋃_{n∈ω} B_{n} = B_{ω} so we have by Tarski/Vaught

[figure: A_{ω}; ≅; B_{ω}; A; e; B; e]

whence A → B is elementary. So T is model complete.

42 CHAPTER 5. ELEMENTARY EXTENSIONS

Algebraically closed fields

6.1 Simple field extensions

1.

Let A be any structure. For each a ∈ |A| introduce a new constant symbol \underline{a}. The diagram of A is the set of atomic sentences φ(\underline{a}_{1}, …, \underline{a}_{n}) which hold in A. Recall that an extension of A is any structure B ⊇ A. Note that an extension of A is virtually the same thing as a model of the diagram of A.

2.

Let A be a field. A field extension of A is an extension B ⊇ A such that B is a field. A field extension of A is thus virtually the same thing as a model of (field axioms) ∪ (diagram of A).

3.

If A, B are fields, A ⊆ B, and b ∈ |B|, let A[b] be the smallest substructure of B containing |A| ∪ {b}, i.e. the subring generated by |A| ∪ {b}. Let A(b) be the smallest subfield of B containing |A| ∪ {b}. A field extension of A is said to be simple if it is of the form A(b).

We want to survey all possible simple field extensions of A. This survey is the main piece of algebraic information that we need for our model-theoretic analysis.

4.

Let A be a field and consider terms t(x) such that sig(t(x)) ⊆ sig(diagram of A)) and x is the only free variable in t(x). Two such terms t_{1}(x) and t_{2}(x) are said to be equivalent if

(field axioms) ∪ (diagram of A) ⊧ ∀x(t_{1}(x) = t_{2}(x)) .

The set of equivalence classes is naturally a commutative ring and is denoted A[x]. We shall see that A[x] is a domain.

5.

A polynomial is a term f(x) as above with either f(x) ≡ 0 or f(x) = \underline{a}_{n}x^{n} + ⋯ + \underline{a}_{1}x + \underline{a}_{0}, a_{i} ∈ |A|. Clearly each equivalence class in A[x] contains a polynomial. We claim that each equivalence class contains only one polynomial. Thus the polynomials are a system of representatives for the equivalence classes in A[x].

Obviously the polynomials over A form a domain, since if f(x) = \underline{a}_{m}x^{m} + ⋯ + \underline{a}_{1}x + \underline{a}_{0}, g(x) = \underline{b}_{n}x^{n} + ⋯ + \underline{b}_{1}x + \underline{b}_{0}, \underline{a}_{m} ≠ 0 ≠ \underline{b}_{n}, then f(x) · g(x) = \underline{a}_{m}\underline{b}_{n}x^{m+n} + ⋯ ≠ 0. We now use the following fact: any domain is embeddable in a field, its field of quotients. In particular, the set of polynomials over A is embedded in a field extension of A. Hence distinct polynomials represent distinct equivalence classes in A[x], as claimed above.

6.

It follows that A[x] is a domain. The quotient field of A[x] is denoted A(x). This is in agreement with our earlier notation for simple extensions. A(x) is our first example of a simple extension of A.

7.

The degree of a nonzero polynomial f(x) ∈ A[x] is deg(f) = n where f(x) = \underline{a}_{n}x^{n} + ⋯ + \underline{a}_{1}x + \underline{a}_{0}, a_{n} ≠ 0. The degree of the zero polynomial, deg(0), is undefined.

Lemma (division algorithm). If f(x), g(x) ∈ A[x], g ≠ 0, there exist q(x), r(x) ∈ A[x] such that f(x) = g(x) · q(x) + r(x) and either r ≡ 0 or deg(r) < deg(g).

Proof. As usual.

In the above lemma, if r ≡ 0 we say that g divides f.

8.

Definition. For f(x) ∈ A[x] we say that f(x) is nonconstant if deg(f) > 0. We say that f(x) is irreducible if f is nonconstant and there is no nonconstant g(x) ∈ A[x] of lower degree than f(x) such that g(x) divides f(x).

9.

Let f(x) ∈ A[x] be nonconstant. For g_{1}, g_{2} ∈ A[x] say g_{1} = g_{2} mod f if f divides g_{1} − g_{2}. Let A[x]/(f(x)) be the set of equivalence classes mod f. Clearly A[x]/(f(x)) has the structure of a commutative ring with A as a subfield. Clearly each equivalence class mod f contains one and only one polynomial g(x) ∈ A[x] such that deg(g) < deg(f) or g ≡ 0. Thus A[x]/(f(x)) may be viewed as a vector space of dimension deg(f) over A.

10.

Lemma. If f(x) is irreducible then A[x]/(f(x)) is a field.

Proof. Given g ∈ A[x], deg(g) < deg(f), g ≠ 0 mod f, to find an inverse mod f. Put

I = {sf + tg : s, t ∈ A[x]} .

Let h ∈ I, h ≢ 0 be of least possible degree. Apply the division algorithm to get f(x) = g(x) · q(x) + r(x). Note that r ∈ I, hence deg(r) < deg(h) is impossible. Hence r ≡ 0, i.e. h divides f. Also deg(h) ≤ deg(g) < deg(f). Since f is irreducible it follows that h is a constant. h ≠ 0 since f ≠ 0. We now have sf + tg = h ∈ |A|, so h^{−1}tg = 1 mod f, so h^{−1}t is the desired inverse, Q.E.D.

11.

In the above lemma, let b be the equivalence class of x in A[x]/(f(x)). Then A(b) = A[x]/(f(x)) is a simple field extension of A. Note also that A[b] = A(b) in this case, so the dimension of A(b) over A as a vector space is finite, being just deg(f).

We now have two kinds of examples of simple field extensions of A. The next theorem says that there are no others.

12.

Theorem. Let A(b) be any simple field extension of A. Then either 1. A(b) ≅ A[x]/(f(x)) for some irreducible f ∈ A[x], or

2. A(b) ≅ A(x). In both cases the isomorphism is the identity on A and sends b to x.

Proof. Case 1: b is algebraic over A, i.e. f(b) = 0 for some nonzero f ∈ A[x]. Let f be of least degree such that this holds. Clearly f is irreducible.

We claim that g(b) = 0 if and only if f divides g. One direction is obvious. For the other direction, suppose g(b) = 0. The division algorithm gives g(x) = f(x) · q(x) + r(x). Hence r(b) = f(b) · q(b) + r(b) = g(b) = 0. Hence we cannot have deg(r) < deg(f). Hence r ≡ 0, i.e. f divides g. This proves the claim.

It follows that g_{1}(b) = g_{2}(b) if and only if f divides g_{1} − g_{2}. This matches the definition of A[x]/f, so we have A[b] ≅ A[x]/f. But by lemma 10 the latter is a field, hence so is the former, i.e. A[b] = A(b).

Case 2: not case 1, i.e. b is transcendental over A. Thus g_{1}(b) = g_{2}(b) if and only if g_{1}(x) ≡ g_{2}(x). Thus A[b] ≅ A[x] as rings. Hence the quotient fields are also isomorphic, i.e. A(b) ≅ A(x).

13.

Corollary. Let A(b_{1}) and A(b_{2}) be two simple extensions of A. If f(b_{1}) = f(b_{2}) = 0 for some ireducible f ∈ A[x], then A(b_{1}) ≅ A(b_{2}).

14.

Corollary. b is algebraic over A if and only if A(b) is finite dimensional over A.

6.2 Algebraic closure

1.

A field extension B ⊇ A is algebraic over A if each b ∈ |B| is algebraic over A.

Lemma. If A ⊆_{alg} B ⊆_{alg} C then A ⊆_{alg} C.

Proof. Given c ∈ |C|, to show that |A(c) : A| (the dimension of A(c) over A as a vector space) is finite. Let g ∈ B[x] be nonzero such that g(c) = 0. Put B_{0} = A(b_{0})(b_{1}) ⋯ (b_{n}) where g(x) = b_{n}x^{n} + ⋯ + b_{1}x + b_{0}. Hence |B_{0}(c) : A| is finite. Hence |A(c) : A| is finite.

[figure: B; finite; B(c); A; finite; A(c)]

2.

Definition. A field B is algebraically closed if every nonconstant g(x) ∈ B[x] has a root in B, i.e. g(b) = 0 for some b ∈ |B|. For any field A, an algebraic closure of A is a field extension B ⊇ A such that (i) B is algebraic over A, and (ii) B is algebraically closed.

3.

Proposition. Every field A has an algebraic closure.

Proof. Note first that for any nonconstant g(x) ∈ A[x] we can adjoin a root, i.e. we can find a simple algebraic field extension A(b) such that g(b) = 0. (Just factor g(x) into irreducibles and apply the construction of Lemma 6.1.10 to one of these irreducible factors.)

Now let g_{α}(x), α < β be an enumeration of all the nonconstant g(x) ∈ A[x]. Put A_{0} = A, A_{α+1} = A_{α}(b_{α}) where g_{α}(b_{α}) = 0, and A_{δ} = ⋃_{α<δ} A_{α} for limit ordinals δ ≤ β. Finally put B_{1} = A_{β}. By Lemma 6.2.1 B_{1} is algebraic over A, and by construction every nonconstant g(x) ∈ A[x] has a root in B_{1}.

Repeating this construction ω times, we get

A = B_{0} ⊆_{alg} B_{1} ⊆_{alg} ⋯ ⊆_{alg} B_{n} ⊆_{alg} ⋯,

n ∈ ω, such that each nonconstant g(x) ∈ B_{n}[x] has a root in B_{n+1}. Thus B = ⋃_{n∈ω} B_{n} is an algebraic closure of A.

4.

Lemma. If A is algebraically closed and A ⊆_{alg} B, then A = B.

Proof. Since A is algebraically closed, the only irreducible polynomials in A[x] are linear, i.e. of degree 1. Hence by Theorem 6.1.12 every element of an algebraic extension of A actually belongs to A.

5.

Proposition. Any two algebraic closures of a field A are isomorphic over A.

Proof. Let B_{1} and B_{2} be two algebraic closures of A.

\xymatrix{B_{1} &  & B_{2} \\  & A \ar@{-->}[ul] \ar@{-->}[ur]}

If A is algebraically closed, then B_{1} = B_{2} = A by the previous lemma. By Zorn’s lemma or transfinite induction, it suffices to find b_{i} ∈ |B_{i}| \ |A|, i = 1, 2, such that A(b_{1}) ≅ A(b_{2}) over A. Since A is not algebraically closed, let f ∈ A[x] be nonconstant with no root in A. We may assume that f is irreducible. Take b_{i} ∈ |B_{i}| so that f(b_{i}) = 0, i = 1, 2. Then A(b_{1}) ≅ A(b_{2}) over A by Corollary 6.1.13. This completes the proof.

By the above proposition we are justified in writing \overline{A} = the algebraic closure of A (unique up to isomorphism over A). By the proof of Proposition 6.2.3 we have ∥\overline{A}∥ = max(∥A∥, ℵ_{0}).

6.

Corollary. If B ⊇ A is algebraically closed, then \overline{A} is isomorphic over A to a subfield of B.

[figure: B; \overline{A}; ⊇; A]

Proof. Let C be the subfield of B with |C| = {b ∈ |B| : b is algebraic over A}. By Lemma 6.2.4 C is algebraically closed. Hence C is an algebraic closure of A. Hence by Proposition 6.2.5 we have that \overline{A} is isomorphic to C over A.

6.3 Completeness and model completeness

In this section we show that the theory T_{p} of algebraically closed fields of characteristic p (p = 0 or prime) is complete and model complete.

1.

Lemma. Let A be a field and let B_{1}, B_{2} be algebraically closed extensions of A such that ∥B_{1}∥ = ∥B_{2}∥ = κ > max(ℵ_{0}, ∥A∥). Then B_{1} and B_{2} are isomorphic over A.

\xymatrix{B_{1} &  & B_{2} \\  & A \ar@{-->}[ul] \ar@{-->}[ur]}

Proof. We use a back-and-forth argument. Let |B_{i}| = {b_{i}^{γ} : γ < κ}, i = 1, 2. At stage γ of our construction we will have a partial isomorphism i_{γ} : A_{1}^{γ} ≅ A_{2}^{γ} where A ⊆ A_{i}^{γ} ⊆ B_{i}, ∥A_{i}^{γ}∥ < κ, i = 1, 2.

\xymatrix{ & B_{1} &  & B_{2} \\ i_{γ} : & A_{1}^{γ} \ar[u] & ≅ & A_{2}^{γ} \ar[u] \\  &  & A \ar@{-->}[ul] \ar@{-->}[ur]}

Stage 0: A_{1}^{0} = A_{2}^{0} = A, i_{0} = identity.

Stage 2γ + 1: If b_{1}^{γ} is algebraic over A_{1}^{2γ}, let f ∈ A_{1}^{2γ}[x] be irreducible such that f(b_{1}^{γ}) = 0, and take b ∈ |B_{2}| such that i_{2γ}(f)(b) = 0. If b_{1}^{γ} is transcendental over A_{1}^{2γ}, take b ∈ |B_{2}| \ |\overline{A}_{2}^{2γ}|; this is possible since ∥\overline{A}_{2}^{2γ}∥ <

κ, and b is then transcendental over A_{2}^{2γ} by Lemma 6.2.4. In either case, by Theorem 6.1.12 and Corollary 6.1.13 we can define an isomorphism

i_{2γ+1} : A_{1}^{2γ+1} = A_{1}^{2γ}(b_{1}^{γ}) ≅ A_{2}^{2γ}(b) = A_{2}^{2γ+1}

by i_{2γ+1} ⊇ i_{2γ}, i_{2γ+1}(b_{1}^{γ}) = b.

Stage 2γ + 2: Same as stage 2γ + 1 except reverse the roles of B_{1} and B_{2}. Stage limit δ ≤ κ: A_{i}^{δ} = ⋃_{γ<δ} A_{i}^{γ}, i = 1, 2, i_{δ} = ⋃_{γ<δ} i_{γ}. Finally we have

i_{κ} : B_{1} = A_{1}^{κ} ≅ A_{2}^{κ} = B_{2}, Q.E.D.

2.

Theorem. T_{p} is κ-categorical for all κ > ℵ_{0}.

Proof. Let A be the smallest field of characteristic p, i.e. A = Q = (ℚ, +, −, ·, 0, 1) if p = 0, A = ℤ/p if p is prime. Note that A is a subfield of any field of characteristic p. Let B_{1}, B_{2} ∈ Mod(T_{p}), ∥B_{1}∥ = ∥B_{2}∥ = κ. Then we have that B_{1} ≅ B_{2} over A by Lemma 6.3.1.

3.

Corollary. T_{p} is complete.

Proof. Immediate by Vaught’s test 2.2.4.

4.

Corollary. T_{p} is decidable.

Proof. Immediate from theorem 4.2.3.

5.

Exercise. Prove that the theory of algebraically closed fields (of all characteristics) is decidable.

6.

Theorem (A. Robinson). T_{p} is model complete.

Proof. Given a monomorphism A → B where A, B are algebraically closed, we want to show that this monomorphism is elementary. Let κ be a cardinal > ∥B∥. By Exercise 5.2 we can get elementary extensions A∗ of A and B∗ of B such that ∥A∗∥ = ∥B∗∥ = κ. Then A∗ ≅ B∗ over A by Lemma 6.3.1.

[figure: A∗; ≅; B∗; A; e; B; e]

Since the diagram commutes, the monomorphism A → B is elementary, Q.E.D.

7.

Corollary (Hilbert). Let A be a field and let \overline{A} be its algebraic closure. Let

\begin{matrix}g_{1}(x_{1}, …, x_{n}) = ⋯ = g_{m}(x_{1}, …, x_{n}) = 0 \\ f(x_{1}, …, x_{n}) ≠ 0 \end{matrix} \} (∗)

be a finite system of polynomial equations and inequations with coefficients in A. If (∗) has a solution in some field extension of A, then it has a solution in \overline{A}.

(Algebraic reformulation: The algebraic points on a variety are dense with respect to the Zariski topology on that variety.)

Proof. This is immediate from model completeness of the theory of algebraically closed fields. Consider the sentence

σ = ∃x_{1} ⋯ x_{n} (⋀_{i=0}^{m} g_{i} = 0 ∧ f ≠ 0) .

If A ⊆ B ⊧ σ then \overline{B} ⊧ σ. By Corollary 6.2.6 we have A ⊆ \overline{A} ⊆ \overline{B}. Hence \overline{A} ⊧ σ by model completeness.

6.4 Hilbert’s Nullstellensatz

1.

Let A be a field and let R = A[x_{1}, …, x_{n}] be the ring of polynomials in n variables x_{1}, …, x_{n} over A. A zero of f ∈ R is an n-tuple b_{1}, …, b_{n} ∈ |B|, where B is a field extension of A, such that f(b_{1}, …, b_{n}) = 0. An algebraic zero of f is a zero whose coordinates b_{1}, …, b_{n} lie in \overline{A}, the algebraic closure of A.

2.

Theorem (Nullstellensatz). Suppose f, g_{1}, …, g_{m} ∈ R such that every common algebraic zero of g_{1}, …, g_{m} is a zero of f. Then there exists a nonnegative integer k such that

f^{k} = ∑_{i=1}^{m} p_{i}g_{i}

where p_{1}, …, p_{m} ∈ R. (The converse holds trivially.)

Proof. Let I be the set of f ∈ R for which the conclusion holds. Suppose the conclusion fails, i.e. f ∉ I. then we claim that I is an ideal in R, i.e.

(i) g, h ∈ I ⇒ g + h ∈ I;

(ii) g ∈ I, h ∈ R ⇒ g · h ∈ I;

(iii) 0 ∈ I and 1 ∉ I.

To prove (i), suppose g, h ∈ I, say g^{k} = ∑ p_{i}g_{i} and h^{l} = ∑ q_{i}g_{i}. Then

(g + h)^{k+l} = ∑_{i+j=k+l} \binom{k + l}{i}g^{i}h^{j} .

Since i + j = k + l, we must have either i ≥ k or j ≥ l. Therefore each term on the right hand side contains g^{k} or h^{l}. Therefore each term is of the form ∑ r_{i}g_{i}. So (g + h)^{k+l} is also of this form. So g + h ∈ I. To prove (ii) just note that if g^{k} = ∑ p_{i}g_{i} then (g · h)^{k} = ∑ h^{k}p_{i}g_{i} so g · h ∈ I. Part (iii) is obvious since f ∉ I.

Thus I is an ideal containing no power of f. By Zorn’s lemma let J ⊇ I be an ideal containing no power of f and maximal with this property.

We claim that J is a prime ideal^{1}, i.e. g ∉ J, h ∉ J ⇒ g · h ∉ J. If g ∉ J then the ideal generated by J ∪ {g} is properly larger than J, so some power of f belongs to it, say f^{k} = sg + u where s ∈ R, u ∈ J. Similarly, if h ∉ J then f^{l} = th + v where t ∈ R, v ∈ J. Hence

f^{k+l} = (sg + u) · (th + v) = stgh + \underbrace{sgv + thu + uv}_{∈ J} .

If gh ∈ J then f^{k+l} ∈ J, contradiction. This proves the claim.

Put R_{1} = R/J = the quotient ring of R by J. Since J is prime, R_{1} is a domain. Let B be the quotient field of R_{1}. We claim that A is canonically isomorphic to a subfield of B. This is clear since |A| ∩ J = {0} (since |A| ∩ J ≠ {0} implies 1 ∈ J).

Let b_{1}, …, b_{n} ∈ |B| correspond to x_{1}, …, x_{n} ∈ R, i.e. b_{i} = [x_{i}]_{J}. Then for any g ∈ R, g(b_{1}, …, b_{n}) = 0 if and only if g ∈ J.

In particular, g_{1}(b_{1}, …, b_{n}) = ⋯ = g_{m}(b_{1}, …, b_{n}) = 0 and f(b_{1}, …, b_{n}) ≠ 0. Hence by model completeness (Corollary 6.3.7) we can find a_{1}, …, a_{n} ∈ |\overline{A}| such that g_{1}(a_{1}, …, a_{n}) = ⋯ = g_{m}(a_{1}, …, a_{n}) = 0 and f(a_{1}, …, a_{n}) ≠ 0. Q.E.D.

3.

Given the statement of Hilbert’s Nullstellensatz, it is natural to ask whether a bound on the exponent k can be computed. We can use Gödel’s completeness theorem 4.1.3 to show that this is the case:

1The Nullstellensatz actually implies that J is a maximal ideal, i.e. R/J is a field.

Theorem (effective bounds for Hilbert’s Nullstellensatz). We can find a recursive function K : ω^{3} → ω with the following property:

Let A be a field and let f, g_{1}, …, g_{m} ∈ R = A[x_{1}, …, x_{n}] be such that every common algebraic zero of g_{1}, …, g_{m} is a zero of f. If f, g_{1}, …, g_{m} are of degree ≤ d, then f^{k} = ∑ p_{i}g_{i} for some k ≤ K(m, n, d) and some p_{i} ∈ R of degree ≤ K(m, n, d).

Proof. Let T be the theory of algebraically closed fields with a distinguished subfield. Let σ_{mndk} be a sentence in the language of T asserting that, for all polynomials f, g_{1}, …, g_{m} of degree ≤ d in n variables x_{1}, …, x_{n} with coefficients in the distinguished subfield, if all common zeros of g_{1}, …, g_{m} are zeros of f, then there exists polynomials p_{1}, …, p_{m} of degree ≤ k in variables x_{1}, …, x_{n} with coefficients in the distinguished subfield, such that f^{l} = ∑ p_{i}g_{i} for some l ≤ k.

We claim that ∀m, n, d ∃k σ_{mndk} ∈ T. To see this, assume the contrary for some fixed m, n, d and consider a theory T′ ⊇ T with new constant symbols intended to denote the coefficients of f, g_{1}, …, g_{m}. Let T′ say that for all k, σ_{mndk} fails for this choice of f, g_{1}, …, g_{m}. By the compactness theorem, T′ is consistent. But any model of T′ would give a counterexample to Hilbert’s Nullstellensatz.

Let R(m, n, d, k) ⇔ σ_{mndk} ∈ T. By Gödel’s completeness theorem, T is recursively enumerable. Hence so is R. Hence we can find a recursive function K : ω^{3} → ω such that R(m, n, d, K(m, n, d)) for all m, n, d. This completes the proof.

4.

One could actually show that the bounding function K can be taken to be primitive recursive. This would be done by giving an explicit quantifier elimination procedure for the theory of algebraically closed fields.

Saturated models

7.1 Element types

1.

Given a theory T and a nonnegative integer n, let F_{n}(T) be the set of all formulas φ(v_{1}, …, v_{n}) with no free variables other than v_{1}, …, v_{n}, such that sig(φ) ⊆ sig(T). We say that Y ⊆ F_{n}(T) is consistent over T if there exist A ∈ Mod(T) and a_{1}, …, a_{n} ∈ |A| such that A ⊧ φ(a_{1}, …, a_{n}) for all φ ∈ Y. Note that by compactness, if each finite subset of Y is consistent over T then so is Y.

2.

A realization of Y ⊆ F_{n}(T) is an n-tuple a_{1}, …, a_{n} ∈ |A|, A ∈ Mod(T), such that A ⊧ φ(a_{1}, …, a_{n}) for all φ ∈ Y. We then say that Y is realized in the model A.

We say that ψ ∈ F_{n}(T) is a logical consequence of Y ⊆ F_{n}(T) over T if every realization of Y is a realization of ψ.

3.

Definition. An n-type over T is a set p ⊆ F_{n}(T) which is consistent over T and closed under logical consequence over T.

4.

Definition. An n-type p over T is said to be complete if, for all φ ∈ F_{n}(T), either φ ∈ p or ¬φ ∈ p. The set of all complete n-types over T is denoted S_{n}(T).

5.

Remark. Let us say that φ, ψ ∈ F_{n}(T) are equivalent over T if

T ⊧ ∀v_{1} ⋯ ∀v_{n}(φ ↔ ψ) .

The equivalence classes form a Boolean algebra B_{n}(T) where the Boolean operations are given by

[φ] · [ψ] = [φ ∧ ψ]
[φ] + [ψ] = [φ ∨ ψ]
−[φ] = [¬φ]
1 = [v_{1} = v_{1}] , 0 = [v_{1} ≠ v_{1}]

(For n = 0 this Boolean algebra is sometimes known as the Lindenbaum algebra of T.) A complete n-type over T is essentially the same thing as an ultrafilter on B_{n}(T). Thus S_{n}(T) is just the Stone space of B_{n}(T).

6.

Example. Suppose T admits elimination of quantifiers. Then an n-type over T is determined by the quantifier-free formulas in it (at least for n ≥ 1). For example, let T be the theory of dense linear order without end points. A complete n-type over T is determined by specifying the order relations among v_{1}, …, v_{n}. Thus |S_{n}(T)| = ∑_{k=1}^{n} k^{n}. For example |S_{1}(T)| = 1, |S_{2}(T)| = 3, |S_{3}(T)| = 13, etc.

We shall see later that a theory T is ℵ_{0}-categorical if and only if ∀n(S_{n}(T) is finite). Here T is assumed to be countable and complete and to have an infinite model.

7.

Remark. Let T be a complete theory and let p be a complete n-type over T, n ≥ 1. It is easy to see that every finite subset of p is realized in every model of T. (Consider sentences of the form ∃v_{1} ⋯ ∃v_{n}(φ_{1} ∧ ⋯ ∧ φ_{k}) where φ_{1}, …, φ_{k} ∈ p.) However, p itself need not be realized in a given model of T. For example, let T = T_{0} = the theory of algebraically closed fields of characteristic zero. Let p ∈ S_{1}(T) be a 1-type saying that v_{1} is transcendental, i.e. a_{n}v_{1}^{n} + ⋯ + a_{1}v_{1} + a_{0} ≠ 0 for a_{i} ∈ ℤ, a_{n} ≠ 0. Clearly every finite subset of p is realized in every algebraically closed field of characteristic 0. But p itself is not realized in \overline{Q} = the algebraic closure of the rational field Q = (ℚ, +, −, ·, 0, 1).

8.

Proposition. Let A be an infinite model of a complete theory T and assume |T | ≤ ∥A∥.

(i) Given p ∈ S_{n}(T) we can find an elementary extension of A of the same power as A in which p is realized.

(ii) A has an elementary extension of power max(∥A∥, |S_{n}(T)|) in which every p ∈ S_{n}(T) is realized.

Proof. (i) Let \underline{c}_{1}, …, \underline{c}_{n}, \underline{a} (a ∈ |A|) be new constant symbols. Since each finite subset of p is realized n A, we have that

(elementary diagram of A) ∪ \{φ(\underline{c}_{1}, …, \underline{c}_{n}) : φ ∈ p\}

is finitely consistent. Hence by the compactness and Löwenheim-Skolem theorems, this has a model of cardinality max(∥A∥, |p|) = ∥A∥. This is an elementary extension of A and the interpretation of \underline{c}_{1}, …, \underline{c}_{n} realizes p.

(ii) We use an elementary chain argument. Let S_{n}(T) = {p_{α} : α < κ} where κ = |S_{n}(T)|. Put A_{0} = A, A_{α+1} = an elementary extension of A_{α} of the same power as A_{α} in which p_{α} is realized; A_{δ} = ⋃_{α<δ} A_{α} for limit δ ≤ κ; finally B = A_{κ}. We can show by induction on α ≤ κ that ∥A_{α}∥ ≤ max(∥A∥, |α|). Hence ∥B∥ ≤ max(∥A∥, κ). If need be, use the upward Löwenheim-Skolem theorem to raise the cardinality of B to max(∥A∥, κ).

7.2 Saturated models

1.

Given a structure B = (|B|, Φ) and a set X ⊆ |B|, introduce new constant symbols \underline{a} (a ∈ X) and let B_{X} = (|B|, Φ_{X}) where Φ_{X} = Φ ∪ \{(\underline{a}, a) : a ∈ X}. Thus B_{X} is just like B but with its signature expanded to include constant symbols denoting the elements of X. Th(B_{X}) is just the set of all sentences φ(\underline{a}_{1}, …, \underline{a}_{n}) with a_{1}, …, a_{n} ∈ X, sig(φ) ⊆ sig(B), such that B ⊧ φ(a_{1}, …, a_{n}).

2.

Definition. Let κ be an infinite cardinal. We say that B is κ-saturated if for all X ⊆ |B| of cardinality less than κ, every complete 1-type over X is realized in B.

(To be precise we should say: every complete 1-type over Th(B_{X}) is realized in B_{X}.)

3.

Exercise. Show that if B is κ-saturated, then for all X ⊆ |B| of cardinality < κ and all n-types p over X (n ≥ 1), p is realized in B.

4.

Example. Let B = (|B|, <) be a linear ordering, and let κ be an infinite cardinal. We say that B is κ-dense if for every pair of sets X_{0}, X_{1} ⊆ |B| of cardinality < κ, if X_{0} < X_{1} we can find b ∈ |B| so that X_{0} < b < X_{1}. For example, (ℚ, <) is ℵ_{0}-dense (in our previous terminology, dense without endpoints). Also, (ℝ, <) is not ℵ_{1}-dense, as may be seen by taking X_{0} = {0}, X_{1} = {1/2, 1/4, 1/8, … }.

Proposition. Let B be a dense linear ordering without end points. B is κ-dense if and only if B is κ-saturated.

Proof. This is easy using the fact that the theory of dense linear orderings without end points admits elimination of quantifiers.

5.

We note that a finite structure is κ-saturated for all infinite κ. If an infinite structure B is κ-saturated, then ∥B∥ ≥ κ.

6.

Definition. A structure B is saturated if it is ∥B∥-saturated.

For example, (ℚ, <) is ℵ_{0}-saturated, hence saturated.

7.

Proposition. (i) every uncountable algebraically closed field is saturated. (ii) \overline{ℚ} and \overline{𝔽}_{p} are not saturated. (iii) There exist countable saturated algebraically closed fields of every characteristic.

Proof. Let X ⊆ |B| where B is an algebraically closed field. A complete 1type over X is virtually the same thing as a simple extension of the subfield A generated by X. We may therefore apply our classification of simple field extensions (see §6.1). The details are left to the reader.

8.

Theorem (uniqueness of saturated models). Let A and B be saturated models of the same power. If A and B are elementarily equivalent, then they are isomorphic.

Proof. We use a back-and-forth argument. Let ∥A∥ = ∥B∥ = κ and fix well orderings of |A| and |B| of order type κ. We shall define enumerations |A| = {a_{γ} : γ < κ} and |B| = {b_{γ} : γ < κ} in such a way that (A, a_{γ})_{γ<κ} ≡ (B, b_{γ})_{γ<κ}.

Stage γ < κ, γ even: We have inductively (A, a_{α})_{α<γ} ≡ (B, b_{α})_{α<γ}. Let a_{γ} be the least element of |A| (with respect to the fixed well ordering) different from a_{α}, α < γ. Let

p_{γ} ∈ S_{1}(Th((A, a_{α})_{α<γ})) = S_{1}(Th((B, b_{α})_{α<γ}))

be the complete 1-type over {a_{α} : α < γ} realized by a_{γ}. Since B is κsaturated we can find b_{γ} ∈ |B| realizing p_{γ} over {b_{α} : α < γ}. Thus

(A, a_{α})_{α≤γ} ≡ (B, b_{α})_{α≤γ} .

Stage γ < κ, γ odd: Reverse the roles of A, B.

Finally (A, a_{γ})_{γ<κ} ≡ (B, b_{γ})_{γ<κ} and these enumerations exhaust the universes of |A| and |B| respectively since the elements were chosen by means of fixed well orderings of order type κ.

Thus a_{γ} ↦ b_{γ} is an isomorphism of A onto B.

9.

Theorem (universality of saturated models). Let B be a κ-saturated model and A ≡ B, ∥A∥ ≤ κ. Then there exists an elementary monomorphism of A into B.

Proof. Similar to the previous proof.

10.

Example. For algebraically closed fields, theorems 8 and 9 have the following significance. Let p = 0 or a prime. There is exactly one countable saturated algebraically closed field. Every countable algebraically closed field of characteristic p is embeddable into this one.

7.3 Existence of saturated models

1.

We begin with an existence theorem for countable saturated models.

Theorem (Vaught). Let T be a complete countable theory. The following are equivalent.

(1) T has a countable saturated model;

(2) |S_{n}(T)| ≤ ℵ_{0} for all n.

Proof. (1) ⇒ (2): Easy. Let A be the countable saturated model of T. Then each p ∈ S_{n}(T) is realized in A. Hence S_{n}(T) is countable.

(2) ⇒ (1): Note first that (2) implies

(3) for all finite X ⊆ |B|, B ∈ Mod(T), one has |S_{1}(X)| ≤ X_{0}.

We shall prove (3) ⇒ (1) by an elementary chain argument.

Stage 0. Let A_{0} be any countable model of T.

Stage n + 1. We have a countable A_{n} ∈ Mod(T). Let {X_{n}^{i} : i ∈ ω} be an enumeration of the finite subsets of |A_{n}|. Put A_{n}^{0} = A_{n}, A_{n}^{i+1} = a countable elementary extension of A_{n}^{i} in which all complete 1-types over X_{n}^{i} are realized. (A_{n}^{i+1} exists because S_{1}(X_{n}^{i}) is countable.) Finally put A_{n+1} = ⋃_{i∈ω} A_{n}^{i}. This completes stage n.

Finally put B = ⋃_{n∈ω} A_{n}. We claim that B is ℵ_{0}-saturated. Let X ⊆ B be finite. Then X ⊆ |A_{n}| for some n. Hence X = X_{n}^{i} for some i. Hence every 1-type over X is realized in A_{n}^{i+1}. This is an elementary submodel of B, so these types are realized in B, Q.E.D.

2.

Example. We give an example of a countable complete theory T with no countable saturated model. Let T = Th(Q_{ℚ}) where Q = (ℚ, <). Then |S_{1}(T)| = 2^{ℵ_{0}} because each Dedekind cut in (ℚ, <) gives rise to a different complete 1-type over T. (There are other complete 1-types over T which do not correspond to Dedekind cuts.)

3.

The basic theorem on the existence of uncountable saturated models is the following:

Theorem (Morley and Vaught). Let A be an infinite model and let κ be an infinite cardinal such that κ ≥ sig(A). Then A has a κ^{+}-saturated elementary extension of power ∥A∥^{κ}.

Proof. We use an elementary chain argument as in the proof of the previous theorem. Put λ = ∥A∥^{κ} and note that λ^{κ} = λ. We construct an elementary chain in which each model has power λ.

Stage 0: Let A ⊆_{e} A_{0} where ∥A_{0}∥ = λ.

Stage γ + 1, γ < κ^{+}: We have A_{γ} of power λ. Let {X_{γ}^{α} : α < λ} be an enumeration of all X ⊆ |A_{γ}| of cardinality ≤ κ. Stage γ + 1 has λ substages: Put A_{γ}^{0} = A_{γ}; A_{γ}^{α+1} an elementary extension of A_{γ}^{α} realizing all 1-types over X_{γ}^{α} (we can do this because |S_{1}(X_{γ}^{α})| ≤ 2^{κ} ≤ λ); and A_{γ}^{β} = ⋃_{α<β} A_{γ}^{α} for limit β ≤ λ. Finally put A_{γ+1} = A_{γ}^{λ}.

Stage δ ≤ κ^{+}, δ limit: Put A_{δ} = ⋃_{γ<δ} A_{γ}.

Finally put B = A_{κ^{+}}. Clearly A ⊆_{e} B and ∥B∥ = λ. We claim B is κ^{+}-saturated. Suppose X ⊆ |B|, |X| ≤ κ. Since κ^{+} is a regular cardinal, X ⊆ A_{γ} for some γ < κ^{+}. Hence X = X_{γ}^{α} for some α < λ. So every 1-type over X is realized in A_{γ}^{α+1} ⊆_{e} B. This completes the proof.

4.

Corollary. Let T be a complete theory of cardinality ≤ κ, and suppose that T has an infinite model. Then T has a κ^{+}-saturated model of power 2^{κ}.

Proof. By Löwenheim-Skolem let A be a model of T of power κ. Apply the previous theorem to get a κ^{+}-saturated elementary extension of power κ^{κ} = 2^{κ}.

5.

Corollary. Assume the Generalized Continuum Hypothesis. Let T be a complete theory of cardinality ≤ κ. Then T has a saturated model of power κ^{+}. This model is unique up to isomorphism.

Proof. The G.C.H. tells us that 2^{κ} = κ^{+}. Apply the previous corollary and the uniqueness result for saturated models (§7.2).

6.

The previous corollary may be applied to give the following useful variant of Vaught’s test. Unlike Vaught’s test itself, the following provides a necessary and sufficient condition for completeness.

Theorem. Assume 2^{ℵ_{0}} = ℵ_{1}. Let T be a countable complete theory with no finite models. T is complete ⇔ any two saturated models of T of power ℵ_{1} are isomorphic.

Proof. Immediate from the previous corollary.

7.

Remark. The G.C.H. is needed for the above results. For example, let T be the complete theory of dense linear ordering without end points. Then any ℵ_{1}-saturated model of T has cardinality ≥ 2^{ℵ_{0}}. Thus we do not get satisfactory results unless we assume 2^{ℵ_{0}} = ℵ_{1}.

However, the G.C.H. can be eliminated from most applications of saturated models, by observing that the conclusions are usually absolute. Thus, if we are trying to prove that a certain theory T is complete, we may assume G.C.H., apply the variant of Vaught’s test referred to above, and then eliminate G.C.H. by noting that completeness is an absolute property of T.

Actually, there are several ways to avoid the need to assume the G.C.H.

(1) Assume G.C.H. and then eliminate it by absoluteness arguments.

(2) Assume the existence of inaccessible cardinals (some people might consider this assumption more reasonable than G.C.H.).

(3) Use “special” models (Morley-Vaught).

(4) Use “recursively saturated” models (Barwise-Schlipf).

We shall simply assume the G.C.H. when needed.

7.4 Preservation theorems

In this section we present a typical application of saturated models, namely to the proofs of “preservation theorems”. Preservation theorems relate model theoretic properties of T to syntactic properties of axioms for T.

1.

The following syntactical classification of formulas is occasionally useful.

Definition. A formula ψ(\overline{y}) is Σ_{k} if it is of the form

ψ(\overline{y}) = ∃\overline{x}_{1}∀\overline{x}_{2} ⋯ \overline{x}_{k} φ(\overline{x}_{1}, \overline{x}_{2}, …, \overline{x}_{k}, \overline{y})

where φ is quantifier free and \overline{x}_{i} = x_{i1} … x_{in_{i}}. Thus a Σ_{k} formula consists of k alternating blocks of quantifiers followed by a quantifier free matrix, and the first block is existential. The class of Π_{k} formulas is defined similarly except that the first block is universal.

2.

Let Γ be a class of formulas (e.g. Γ = Σ_{k} or Π_{k}). A Γ-theory is a theory T

such that T ∩ Γ is a set of axioms for T. We write [figure: A; Γ; B] to mean that sig(A) = sig(B) and Th(A) ∩ Γ ⊆ Th(B) ∩ Γ.

3.

Lemma (localization lemma). Let Γ be a class of formulas which is closed under disjunction. Let T be a theory such that Mod(T) is closed under

[figure: Γ], i.e. A ∈ Mod(T), [figure: A; Γ; B] implies B ∈ Mod(T). Then T is a Γ-theory.

Proof. Let B ⊧ T ∩ Γ, sig(B) = sig(T). We must show that B ⊧ T. Suppose not. Let Δ = {σ ∈ Γ : B ⊧ ¬σ}. Then for each A ∈ Mod(T) there exists σ ∈ Δ such that A ⊧ σ. Hence by compactness T ⊧ ⋁_{i=1}^{k} σ_{i} for some σ_{1}, …, σ_{k} ∈ Δ. Hence ⋁_{i=1}^{k} σ_{i} ∈ T ∩ Γ. Hence B ⊧ ⋁_{i=1}^{k} σ_{i}, a contradiction.

4.

If sig(A) = sig(B), we write f : [figure: A; Γ; B] (f is a Γ-morphism of A into B) to mean that f : |A| → |B| and f preserves satisfaction of Γ formulas, i.e. for all Γ formulas φ(x_{1}, …, x_{n}) and a_{1}, …, a_{n} ∈ |A|, if A ⊧ φ(a_{1}, …, a_{n}) then B ⊧ φ(f(a_{1}), …, f(a_{n})).

Examples:

(1) If Γ = Π_{0} = Σ_{0} = {quantifier free formulas}, then f : [figure: A; Γ; B] means that f is a monomorphism of A into B.

(2) If Γ = {atomic formulas}, then f : [figure: A; Γ; B] means that f is a homomorphism of A into B. (We have not previously defined the concept of homomorphism, so this may be taken as the definition. If A and B are groups or rings, this coincides with the usual definition of homomorphism.)

(3) If Γ = {all formulas} then f : [figure: A; Γ; B] means of course that f is an elementary embedding of A into B.

5.

We now present our first preservation theorem.

Theorem (Tarski). Suppose that T is preserved under substructures, i.e. every substructure of a model of T is a model of T. Then T is a universal (i.e. Π_{1}-) theory.

Proof. By the localization lemma, it suffices to prove that if B ∈ Mod(T),

[figure: B; Π_{1}; A] , then A ∈ Mod(T). Let B ≡ B∗ where B∗ is κ-saturated, κ =

∥A∥. We have [figure: A; Σ_{1}; B] , hence [figure: A; Σ_{1}; B∗] .

Claim: There exists a monomorphism of A into B∗. To see this, let |A| = {a_{γ} : γ < κ}. As in the proof of Theorem 7.2.9 we choose b_{γ} ∈ |B∗|, γ < κ, so that the embedding a_{γ} ↦ b_{γ} is a Σ_{1}-morphism. Stage γ < κ: Let Y_{γ} be the set of Σ_{1} formulas ψ(\underline{a}_{α_{1}}, …, \underline{a}_{α_{n}}, v_{1}), α_{1} < ⋯ < α_{n} < γ, such that A ⊧ ψ(a_{1}, …, a_{n}, a_{γ}). By inductive hypothesis we have

[figure: (A, a_{α})_{α<γ}; Σ_{1}; (B∗, b_{α})_{α<γ}] .

Hence B∗ ⊧ ∃v_{1}ψ(b_{α_{1}}, …, b_{α_{n}}, v_{1}) for each ψ(\underline{a}_{α_{1}}, …, \underline{a}_{α_{n}}, v_{1}) ∈ Y_{γ}. Hence by κ-saturation there exists b_{γ} ∈ |B∗| such that B∗ ⊧ ψ(b_{α_{1}}, …, b_{α_{n}}, b_{γ}) for all ψ(\underline{a}_{α_{1}}, …, \underline{a}_{α_{n}}, v_{1}) ∈ Y_{γ}.

[ Details: To show that Y_{γ} is realized in (B∗, b_{α})_{α<γ} it suffices to show that each finite subset is, i.e. (B∗, b_{α})_{α<γ} ⊧ ∃v ⋀_{i=1}^{k} ψ_{i}(b_{α_{1}}, …, b_{α_{n}}, v) for all ψ_{1}, …, ψ_{k} ∈ Y_{γ}. But this is a Σ_{1} sentence, true in (A, a_{α})_{α<γ}, hence true in (B∗, b_{α})_{α<γ}. ]

Now clearly

[figure: (A, a_{α})_{α≤γ}; Σ_{1}; (B∗, b_{α})_{α≤γ}]

so the induction hypothesis is preserved.

Finally

[figure: (A, a_{γ})_{γ<κ}; Σ_{1}; (B∗, b_{γ})_{γ<κ}]

so in particular a_{γ} ↦ b_{γ} is a monomorphism of A into B∗. This proves the claim.

Now B∗ ∈ Mod(T), hence A ∈ Mod(T) since Mod(T) is closed under substructure. This completes the proof.

6.

The above argument actually established the following result.

Lemma (embedding lemma). Let Γ be a class of formulas which is closed

under ∧ and ∃ (e.g. Γ = Σ_{k}, k ≥ 1). If [figure: A; Γ; B] and B is κ-saturated,

κ ≥ ∥A∥, then ∃f : [figure: A; Γ; B] .

We can use this lemma for Γ = Σ_{2} to prove the following preservation theorem.

7.

Theorem (Chang-Łos-Susko). Let T be a theory such that Mod(T) is closed under unions of ω-chains, i.e. A_{0} ⊆ ⋯ ⊆ A_{n} ⊆ ⋯ (n ∈ ω), A_{n} ∈ Mod(T) implies ⋃_{n∈ω} A_{n} ∈ Mod(T). Then T is a Π_{2}-theory. (The converse is obvious.)

Proof. By the localization lemma, in order to show that T is a Π_{2}-theory, it

suffices to show that if A ∈ Mod(T) and [figure: A; Π_{2}; B] then B ∈ Mod(T).

We have [figure: B; Σ_{2}; A] ∈ Mod(T). Let A ≡ A_{1} where A_{1} is ∥B∥-saturated.

Then by the embedding lemma we can find a Σ_{2} embedding f : [figure: B; Σ_{2}; A_{1}] . Let B ⊆_{e} B_{1}, B_{1} ∥A_{1}∥-saturated. Then

[figure: (A_{1}, f(b))_{b∈|B|}; Π_{2}; (B_{1}, b)_{b∈|B|}]

so by the embedding lemma again we can find an embedding g : [figure: A_{1}; Σ_{1}; B_{1}] such that the following diagram commutes:

[figure: A_{1}; Σ_{1}; B; Σ_{2}; ⊆_{e}; B_{1}]

Repeating ω times we get

[figure: A_{1}; Σ_{1}; A_{2}; Σ_{1}; A_{n+1}; Σ_{1}; B; =; B_{0}; Σ_{2}; ⊆_{e}; B_{1}; Σ_{2}; ⊆_{e}; B_{2}; ⊆_{e}; ⋯; ⊆_{e}; B_{n}; Σ_{2}; ⊆_{e}; B_{n+1}; ⊆_{e}; · · · .]

So finally B_{ω} = ⋃_{n∈ω} B_{n} = ⋃_{n∈ω} A_{n}. Since A_{n} ∈ Mod(T) we have by assumption ⋃_{n∈ω} A_{n} ∈ Mod(T). Since B ⊆_{e} B_{ω}, it follows that B ∈ Mod(T). This completes the proof.

8.

Corollary (Robinson). If T is model complete then T is a Π_{2}-theory.

Proof. If T is model complete, then any chain of models of T is an elementary chain. Hence Mod(T) is closed under unions of chains, so we apply the theorem.

For example, the theory of algebraically closed fields is model complete, and the given axioms for this theory are Π_{2}.

9.

We now prove Lyndon’s preservation theorem for positive sentences. A formula is said to be positive if it is built up from atomic formulas using only ∀, ∃, ∧, ∨ (and not using ¬, →, ↔). A positive theory is a theory with a set of positive sentences as axioms.

Theorem (Lyndon). Let T be a theory which is preserved under homomorphic images, i.e. any homomorphic image of a model of T is a model of T. Then T is a positive theory. (The converse is easy.)

For example, the theory of groups is positive, and each homomorphic image of a group is a group. The theory of commutative rings is not positive because of the presence of the axiom 0 ≠ 1. If we drop this axiom, the theory becomes positive, and every homomorphic image of a commutative ring is a commutative ring.

Proof. By the localization lemma, it suffices to show that if A ∈ Mod(T),

[figure: A; pos; B] , then B ∈ Mod(T). Let A ≡ A∗, B ≡ B∗ where ∥A∗∥ = ∥B∗∥ = κ and A∗, B∗ are κ-saturated. (We use the Generalized Continuum Hypothesis to obtain saturated models. By absoluteness, the use of G.C.H. can be eliminated.)

We have [figure: A∗; pos; B∗] . We claim that B∗ is a homomorphic image of A∗. The proof is similar to that of the embedding lemma (7.4.6), except we need a back-and-forth argument.

[ Details: Choose well orderings of |A∗| and |B∗| of order type κ. We construct enumerations |A∗| = {a_{γ} : γ < κ}, |B∗| = {b_{γ} : γ < κ}.

Stage γ, γ even: We have

[figure: (A∗, a_{α})_{α<γ}; pos; (B∗, b_{α})_{α<γ}] .

Let a_{γ} be the least element of |A∗| not among {a_{α} : α < γ}. Let Y_{γ} be the set of positive formulas φ(\underline{a}_{α_{1}}, …, \underline{a}_{α_{n}}, v) such that A∗ ⊧ φ(a_{α_{1}}, …, a_{α_{n}}, a_{γ}). As in the proof of the embedding lemma, we have A∗ ⊧ ∃v ⋀_{i=1}^{k} φ_{i}(a_{α_{1}}, …, a_{α_{n}}, v), hence B∗ ⊧ ∃v ⋀_{i=1}^{k} φ_{i}(b_{α_{1}}, …, b_{α_{n}}, v) for each finite set of formulas φ_{1}, …, φ_{k} ∈ Y_{γ}. Hence by saturation of B∗ it follows that Y_{γ} is realized in (B∗, b_{α})_{α<γ}, i.e. there exists b_{γ} ∈ |B∗| such that

[figure: (A∗, a_{α})_{α≤γ}; pos; (B∗, b_{α})_{α≤γ}] .

Stage γ, γ odd: We have

[figure: (A∗, a_{α})_{α<γ}; pos; (B∗, b_{α})_{α<γ}] ,

hence

[figure: (B∗, b_{α})_{α<γ}; neg; (A∗, a_{α})_{α<γ}] ,

where a negative formula is defined to be the negation of a positive one. Let b_{γ} be the least element of |B∗| not among {b_{α} : α < γ}. According to the DeMorgan laws, the class of negative formulas is closed under ∃ and ∧. Hence we can apply the same argument as before to find a_{γ} ∈ |A∗| such that

[figure: (B∗, b_{α})_{α≤γ}; neg; (A∗, a_{α})_{α≤γ}] ,

i.e.

[figure: (A∗, a_{α})_{α≤γ}; pos; (B∗, b_{α})_{α≤γ}] .

Note that a_{γ} ≠ a_{α}, α < γ, since v ≠ \underline{a}_{α} is a negative formula.

Finally we get enumerations |A∗| = {a_{γ} : γ < κ} and |B∗| = {b_{γ} : γ < κ} such that α < γ < κ ⇒ a_{α} ≠ a_{γ} and

[figure: (A∗, a_{γ})_{γ<κ}; pos; (B∗, b_{γ})_{γ<κ}] .

Hence in particular the mapping a_{γ} ↦ b_{γ} is a homomorphism of A∗ onto B∗. ]

Since A ≡ A∗ ∈ Mod(T), it follows by hypothesis that B∗ ∈ Mod(T). Hence B ∈ Mod(T), Q.E.D.

For more on preservation theorems, see Chang and Keisler, Model Theory.

70 CHAPTER 7. SATURATED MODELS

Elimination of quantifiers

8.1 The model completion of a theory

1.

Definition (Robinson). Let T and T ∗ be theories with the same signature. We say that T ∗ is a model completion of T if

(i) T ⊆ T ∗; (ii) every model of T can be extended to a model of T ∗; (iii) for any A ∈ Mod(T), T ∗ ∪ (diagram of A) is complete. (Recall that the diagram of A is the set of all quantifier free sentences φ(\underline{a}_{1}, …, \underline{a}_{n}), sig(φ) ⊆ sig(A), a_{1}, …, a_{n} ∈ |A|, A ⊧ φ(\underline{a}_{1}, …, \underline{a}_{n}).)

Condition (iii) is equivalent to (iii) if A ∈ Mod(T), A ⊆ B_{i} ∈ Mod(T ∗), i = 1, 2, then B_{1} and B_{2} are

“elementarily equivalent over A.”

\xymatrix{B_{1} & ≡ & B_{2} \\  & A \ar@{-->}[ul] \ar@{-->}[ur]}

2.

Example. The theory of algebraically closed fields is a model completion of the theory of fields.

Proof. (i) is trivial, and (ii) holds since every field can be extended to an algebraically closed field (Proposition 6.2.3). For (iii), let A be a field and let B_{1} and B_{2} be two algebraically closed fields extending A. We want to show that B_{1} ≡ B_{2} over A. By the upward Löwenheim-Skolem theorem let

B_{i} ⊆_{e} B∗_{i}, i = 1, 2, where ∥B∗_{1}∥ = ∥B∗_{2}∥ = κ and κ > max(ℵ_{0}, ∥A∥). By

Lemma 6.3.1 we have that B∗_{1} ≅ B∗_{2} over A. Hence B_{1} ≡ B_{2} over A.

[figure: B∗_{1}; ≅; B∗_{2}; B_{1}; e; B_{2}; e; A]

3.

Remarks. The following facts about model completions are obvious.

(a) If T ∗ is a model completion of T then T ∗ is model complete.

(b) T is model complete if and only if T is its own model completion.

4.

Theorem (Robinson). Let T_{0}, T_{1} be model completions of T. Then T_{0} = T_{1}.

Proof. Given A ∈ Mod(T_{0}), we shall show that A ∈ Mod(T_{1}). We use an elementary chain argument. Let A = A_{0} ∈ Mod(T_{0}). By (i) and (ii) of the definition, we can find A_{1} ∈ Mod(T_{1}), A_{0} ⊆ A_{1}. More generally, given A_{2n} ∈ Mod(T_{0}) let A_{2n} ⊆ A_{2n+1} ∈ Mod(T_{1}) and A_{2n+1} ⊆ A_{2n+2} ∈ Mod(T_{0}). Put B = ⋃_{n∈ω} A_{n}. Since T_{0} is model complete, we have A_{2n} ⊆_{e} A_{2n+2} so by the elementary chain principle, A = A_{0} ⊆_{e} B. But since T_{1} is model complete, we also have A_{2n+1} ⊆_{e} A_{2n+3} so B ∈ Mod(T_{1}). Hence A ∈ Mod(T_{1}), Q.E.D.

Thus the model completion of T is unique if it exists.

4.

Another example. The theory of dense linear order without end points is the model completion of the theory of linear order. (This is an easy consequence of quantifier elimination.)

8.2 Substructure completeness

1.

Definition. A theory T is substructure complete if T ∪ (diagram of A) is complete whenever A is a substructure of a model of T.

2.

Definition. T admits elimination of quantifiers if for all n ≥ 1 and all φ ∈ F_{n}(T), there exists a quantifier free formula φ∗ ∈ F_{n}(T) such that T ⊧ ∀v_{1} … ∀v_{n}[φ(v_{1}, …, v_{n}) ↔ φ∗(v_{1}, …, v_{n})].

3.

Theorem. Let T be a theory. The following are equivalent.

(i) T is the model completion of a universal (i.e. Π_{1}) theory.

(ii) T is substructure complete.

(iii) T admits elimination of quantifiers.

Proof. (i) ⇒ (ii). Let T be the model completion of a universal theory U. Let A ⊆ B ∈ Mod(T). Then A ∈ Mod(U) since U is universal. Hence T ∪ (diagram of A) is complete, by the definition of model completion.

(ii) ⇒ (iii). Assume that T is substructure complete. Given φ ∈ F_{n}(T), to find a quantifier free φ∗ ∈ F_{n}(T) such that T ∗ ⊧ φ ↔ φ∗. We proceed as in the proof of the localization lemma 7.4.3. Let Y be the set of quantifier free ψ ∈ F_{n}(T) such that T ⊧ φ → ψ. If φ∗ does not exist, then by compactness we can find B ∈ Mod(T) and a_{1}, …, a_{n} ∈ |B| so that B ⊧ ¬φ(a_{1}, …, a_{n}) ∧ ψ(a_{1}, …, a_{n}) for all ψ ∈ Y. Let A be the substructure of B generated by a_{1}, …, a_{n}. By substructure completeness we have

T ∪ (diagram of A) ⊧ ¬φ(\underline{a}_{1}, …, \underline{a}_{n}) .

Hence there exists a quantifier free formula θ ∈ F_{n}(T) such that θ(\underline{a}_{1}, …, \underline{a}_{n}) ∈ diagram of A and

T ⊧ ∀v_{1} … v_{n} [θ(v_{1}, …, v_{n}) → ¬φ(v_{1}, …, v_{n})] ,

i.e. T ⊧ ∀v_{1} … v_{n}[φ → ¬θ]. Hence ¬θ ∈ Y. Hence B ⊧ ¬θ(a_{1}, …, a_{n}). This is a contradiction.

(iii) ⇒ (i). Suppose T admits elimination of quantifiers. Let U be the theory whose axioms are the universal sentences of T. We claim that T is a the model completion of U. If A ∈ Mod(U) then an easy compactness argument shows that T ∪(diagram of A) is consistent. Hence A is extendible to a model of T. The last part of the definition of model completion is immediate from elimination of quantifiers.

(Note: Mod(U) is just the class of substructures of models of T.)

4.

Example. The theory of dense linear ordering without end points is the model completion of the theory of linear orderings. the latter theory is universal so we conclude:

Theorem. The theory of dense linear ordering without endpoints admits elimination of quantifiers.

(This can also be proved by a direct syntactical argument. See Exercise 2.1.4.)

5.

Example. We have seen that the theory T of algebraically closed fields is the model completion of the theory of fields. Unfortunately, the theory of fields is not universal. (The key axiom is ∀x(x ≠ 0 → ∃y(x · y = 1)).) However, T is also the model completion of the theory of domains, and the latter theory is universal. (The key axiom is ∀x∀y((x ≠ 0 ∧ y ≠ 0) → x · y ≠ 0).)

(To see that T is the model completion of the theory of domains, just note that any field containing a domain also contains its fraction field, and apply Example 8.1.2. See also Example 8.3.3 below.)

Hence we have:

Theorem (Tarski). The theory of algebraically closed fields admits elimination of quantifiers. (In the language of +, ·, −, 0, 1.)

6.

This theorm has algebraic applications; e.g.

Corollary (elimination theory). Let S be a finite system of equations and inequations in n unknowns (variables) x_{1}, …, x_{n} with coefficients (constants) \underline{c}_{1}, …, \underline{c}_{N}. Then we can effectively find a finite set S_{1}, …, S_{k} of systems of equations and inequations in \underline{c}_{1}, …, \underline{c}_{N} alone, such that for any c_{1}, …, c_{N} in an algebraically closed field, S is solvable if and only if one of S_{1}, …, S_{k} holds.

Proof. Regard \underline{c}_{1}, …, \underline{c}_{N} as variables and effectively eliminate quantifiers from the formula ∃x_{1} ⋯ ∃x_{n} S. Put the resulting quantifier free formula into disjunctive normal form.

Special cases of the above result are known classically. For example, in van der Waerden (vol. 1, §27) one finds the following result. Let S be a system of two equations

a_{0}x^{m} + a_{1}x^{m−1} + ⋯ + a_{m} = 0
b_{0}x^{n} + b_{1}x^{n−1} + ⋯ + b_{n} = 0 .

These two polynomials have a common root if and only if the determinant

| \begin{matrix}a_{0} & a_{1} & … & a_{m} \\ & a_{0} & a_{1} & … & a_{m} \\ & & a_{0} & a_{1} & … & a_{m} \\ b_{0} & b_{1} & … & b_{n} \\ & b_{0} & b_{1} & … & b_{n} \\ & & b_{0} & b_{1} & … & b_{n} \end{matrix} |

vanishes. This (m + n) × (m + n) determinant is called the resultant of the system S. In general, the theory of “resultants” or “elimination theory” is a branch of classical algebra concerned with explicit determination of S_{1}, …, S_{k} given S as in the corollary.

7.

Recall that a variety X ⊆ ℂ^{n} is the solution set of a system of equations in n unknowns with complex coefficients.

Corollary (Tarski). Let X ⊆ ℂ^{n} be a variety. Let Y ⊆ ℂ^{k} be the image of X under the projection (x_{1}, …, x_{n}) ↦ (x_{1}, …, x_{k}), 1 ≤ k ≤ n. Then Y is a Boolean combination of varieties.

(This is already nontrivial for k = 2, n = 3.)

8.3 The role of simple extensions

In this section we discuss the role of simple extensions in quantifier elimination.

1.

Definition. Let U be a universal theory. Let A ⊆ B ∈ Mod(U). Given b ∈ |B|, we write A[b] for the substructure of B generated by |A| ∪ {b}. This is called a simple extension of A.

2.

Theorem (L. Blum). Let U be a universal theory and let T be a theory with sig(T) = sig(U), U ⊆ T, such that every model of U is extendible to a model of T. The following are equivalent.

(i) T is the model completion of U.

(ii) Suppose A ⊆ B ∈ Mod(T), B κ^{+}-saturated, where κ = max(ℵ_{0}, ∥A∥). Then up to isomorphism over A, B contains every simple extension of A.

(iii) Suppose A ⊆ B_{i} ∈ Mod(T), i = 1, 2. If B_{2} is κ-saturated, κ ≥ ∥B_{1}∥, then there exists an embedding of B_{1} into B_{2} such that the following diagram commutes.

\xymatrix{B_{1} \ar@{-->}[rr] &  & B_{2} \\  & A \ar@{-->}[ul] \ar@{-->}[ur]}

Proof. (i) ⇒ (ii). Immediate from the definitions.

(ii) ⇒ (iii). Let |B_{1}| = {b_{α} : α < κ} and define a tower of simple extensions A_{0} = A, A_{α+1} = A_{α}[b_{α}], A_{β} = ⋃_{α<β} A_{α} for limit β ≤ κ. Apply (ii) κ times to get an embedding of B_{1} into B_{2}.

(iii) ⇒ (i). Given A ⊆ B_{i} ∈ Mod(T), i = 1, 2. To show B_{1} ≡ B_{2} over A. We use an elementary chain argument.

[figure: B_{1}; e; B′_{1}; e; B′′_{1}; e; ⋯; A; B_{2}; e; B′_{2}; e; B′′_{2}; e; ⋯]

First choose B′_{2} ⊇_{e} B_{2} sufficiently saturated, and apply (ii) to get B_{1} → B′_{2} over A. Then choose B′_{1} ⊇_{e} B_{1} sufficiently saturated and apply (ii) to get B_{2} → B′_{1} over A. Etc. Finally we get

[figure: B_{1}; e; B∗_{1}; =; ⋃_{n∈ω} B_{1}^{(n)}; A; ≅; B_{2}; e; B∗_{2}; =; ⋃_{n∈ω} B_{2}^{(n)}]

and the diagram gives an isomorphism of B∗_{1} onto B∗_{2} over A. Hence B_{1} ≡ B_{2} over A.

3.

Example. We can use the above criterion to prove (using a minimum of algebra) that the theory of algebraically closed fields is the model completion of the theory of domains. Suppose A ⊆ B, B algebraically closed and κ^{+}- saturated, where κ ≥ max(ℵ_{0}, ∥A∥). We must show that B contains every simple extension A[b] of the domain A. All such extensions are contained in simple field extensions of the quotient field of A. Using our classification of simple field extensions (§6.1) we see immediately that B contains all such extensions.

In the next chapter we shall use this criterion to show that the theory of real closed ordered fields is the model completion of the theory of ordered fields.

Real closed ordered fields

9.1 Ordered fields

1.

The axioms for ordered fields are as follows:

(a) the field axioms (as in example 2.3.4)

(b) the axioms for linear order: ∀x∀y∀z((x < y ∧ y < z) → x < z) ∀x∀y(x < y → x ≠ y) ∀x∀y(x < y ∨ x = y ∨ y < x)

(c) special axioms: ∀x∀y∀z(x < y → x + z < y + z) ∀x∀y((0 < x ∧ 0 < y) → 0 < x · y)

An ordered field is a model of these axioms. An ordered domain is defined similarly.

2.

Examples.

Q = (ℚ, +, −, ·, 0, 1, <) = the ordered field of rationals.

R = (ℝ, +, −, ·, 0, 1, <) = the ordered field of real numbers.

Z = (ℤ, +, −, ·, 0, 1, <) = the ordered field of rationals.

3.

The following facts are easily proved.

(a) In an ordered domain, we have

x < y ↔ y − x > 0

x > 0 ↔ −x < 0

x ≠ 0 → x^{2} > 0

(x < y ∧ z > 0) → x · z < y · z

(b) Any ordered field (or ordered domain) has characteristic 0. (Because

\underbrace{1 + 1 + ⋯ + 1}_{n} > 0.)

(c) The ordering of an ordered field is dense (because x < y implies x < (x + y)/2 < y).

(d) Any ordered field contains Q as an ordered subfield. Any ordered domain contains Z as an ordered subdomain.

4.

Proposition. Let A be an ordered domain and let A_{1} be its field of quotients. Then there is one and only one way to order A_{1} so that it becomes an ordered field with A as an ordered subdomain.

Proof. We are forced to order A_{1} by

\frac{x}{y} > 0 ⇔ x · y = \frac{x}{y} · y^{2} > 0 .

It is easy to check that this makes A_{1} an ordered field, etc.

For example, there is only one way to order the rational field so as to make it an ordered field.

5.

Definition. Let F be an ordered field and let f ∈ F[x]. We say that F has the intermediate value property (IVP) for f if a, b ∈ |A|, a < b, f(a) < 0 < f(b) imply f(c) = 0 for some c ∈ |F|, a < c < b.

We say that F is real closed if it has the IVP for all f ∈ F[x].

6.

Examples. The rational field Q does not have the IVP for f(x) = x^{2} − 2. The real field R does have IVP for x^{2} − 2. The real field R is in fact real closed. The complex field ℂ is not real closed, indeed it cannot be ordered (since i^{2} = −1).

7.

The property of being real closed is first order, so we may speak of the theory of real closed ordered fields, RCOF. The axioms of RCOF are those for ordered fields plus the following, for each n ≥ 1:

\begin{matrix}∀w_{0} ⋯ w_{n}xy [(x < y ∧ w_{n}x^{n} + ⋯ + w_{0} < 0 < w_{n}y^{n} + ⋯ + w_{0}) \\ → ∃z (x < z < y ∧ w_{n}z^{n} + ⋯ + w_{0} = 0)] . \end{matrix}

8.

Our main goal is to show that RCOF is the model completion of the theory of ordered fields, and hence of ordered domains. From this it will follow that RCOF admits elimination of quantifiers, and is complete and decidable (Tarski).

9.

Lemma. Let F be an ordered field which is not real closed. Then there is an ordered field F_{1} ⫌ F such that F_{1} is algebraic over F.

Proof. Pick f ∈ F[x] such that the IVP fails for f but holds for all g ∈ F[x] of smaller degree. Let a, b ∈ F[x] be such that a < b, f(a) < 0 < f(b), f(c) ≠ 0 for all c ∈ [a, b] = {c ∈ |F| : a ≤ c ≤ b}. We employ a sort of “Dedekind cut” construction. Put A = {a′ ∈ [a, b] : f(c) < 0 for all c ∈ [a, a′]} and B = [a, b] \ A. Obviously A, B ≠ ∅, [a, b] = A ∪ B, and a′ < b′ for all a′ ∈ A, b′ ∈ B.

Claim: A has no greatest element and B has no least element.

Proof: This is clear since f is “continuous” (by an ϵ-δ-argument).

Claim: For every g ∈ F[x] of degree < deg(f) we can find a′ ∈ A, b′ ∈ B so that g has constant sign (positive, negative, or zero) on the interval [a′, b′].

Proof: If g ≡ 0 there is nothing to prove. Otherwise g has only finitely many roots in |F|. Find a′ ∈ A, b′ ∈ B such that [a′, b′] does not contain any of these roots. By the IVP for g, we conclude that g does not change sign on [a′, b′].

Claim: f is irreducible. For suppose f = f_{1}·f_{2}, deg(f_{i}) < deg(f), i = 1, 2. We must have f_{i}(a)f_{i}(b) < 0 for at least one i. Then by the IVP for f_{i} we must have f_{i}(c) = 0 for some c ∈ [a′, b′]. Hence f(c) = 0, contradiction.

Let F_{1} = F(α) = F[x]/f where f(α) = 0. (See Lemma 6.1.10.) To define the order relation on F(α), recall that a typical element of F(α) is of the form g(α) where deg(g) < deg(f). Put g(α) > 0 if g > 0 on some interval [a′, b′], a′ ∈ A, b′ ∈ B; g(α) < 0 if g < 0 on some interval [a′, b′], a′ ∈ A, b′ ∈ B; g(α) = 0 if g ≡ 0.

Claim: this makes F(α) an ordered field. The only nontrivial axiom to be checked is the product rule: the product of positive elements is positive. Suppose g_{i}(α) > 0, deg(g_{i}) < deg(f), i = 1, 2. Let g_{1}(α) · g_{2}(α) = g_{3}(α), deg(g_{3}) < deg(f). We must show g_{3}(α) > 0. We have

g_{1}(x) · g_{2}(x) − g_{3}(x) = f(x) · h(x) .

Put m = deg(f). The left side has degree ≤ 2m − 2. Hence so does the right side, so deg(h) ≤ m − 2. Let a′ ∈ A, b′ ∈ B be such that g_{1}, g_{2}, g_{3}, h all have constant sign on [a′, b′].

Case 1: h > 0 on [a′, b′]. Let c ∈ [a′, b′] be such that f(c) < 0. then g_{3}(c) > 0 since

\underbrace{g_{1}(c) · g_{2}(c)}_{pos} = g_{3}(c) + \underbrace{f(c) · h(c)}_{neg} ,

hence g_{3} > 0 on [a′, b′]. Hence g_{3}(α) > 0.

Case 2: h < 0 on [a′, b′]. Take c ∈ [a′, b′] so that f(c) > 0. Then by an argument similar to the above, g_{3}(c) > 0, so g_{3}(α) > 0.

Case 3: h = 0 on [a′, b′]. Hence h ≡ 0 so g_{3} = g_{1} · g_{2} > 0 on [a′, b′], hence g_{3}(α) > 0. This completes the proof.

10.

Definition. Let F be an ordered field. A real closure of F is an ordered field G ⊇ F so that (1) G is algebraic over F; (2) G is real closed.

11.

Proposition. Any ordered field F has a real closure.

Proof. This is an easy consequence of the previous lemma plus Zorn’s lemma (or transfinite induction). Let B be the algebraic closure of F regarded as a field. Form a transfinite sequence of extensions F = F_{0}, F_{α+1} = proper ordered extension of F_{α}, F_{β} = ⋃_{α<β} F_{β} for limit β, all within B. The process must eventually stop, so by lemma 9.1.9 we then have a real closure of F.

9.2 Uniqueness of real closure

The purpose of this section is to prove that the real closure of an ordered field F is unique up to isomorphism over F. The usual proofs of this result use either Galois theory or Sturm’s test. We give a more elementary argument based on Rolle’s theorem.

1.

Lemma (Rolle’s theorem). Let G be a real closed ordered field, g ∈ G[x]. Between any two distinct roots of g lies at least one root of g′.

(Here g′ is the formal derivative of g. If g(x) = a_{n}x^{n} + ⋯ + a_{1}x + a_{0} then g′(x) = na_{n}x^{n−1} + ⋯ + a_{1}.)

Proof. Given a < b, g(a) = g(b) = 0. Say g(x) = (x − a)^{k}(x − b)^{l}p(x) where p ∈ G[x] and p(a) ≠ 0, p(b) ≠ 0. We may safely assume that g(c) ≠ 0 for a < c < b. Hence p(c) ≠ 0 for c ∈ [a, b]. Hence p has constant sign on [a, b]. We have

g(x) = (x − a)^{k−1}(x − b)^{l−1}q(x)

where

q(x) = [k(x − b) + l(x − a)]p(x) + (x − a)(x − b)p′(x) .

We have q(a) = k(a−b)p(a), q(b) = l(b−a)p(b) so q(a) and q(b) have opposite sign, hence q(c) = 0 for some a < c < b. Hence g′(c) = 0.

2.

Lemma (maximum principle). Let G be a real closed ordered field, g ∈ G[x], a, b ∈ G, a < b. Then g takes on a maximum value in the interval [a, b], say at γ. If a < γ < b then g′(γ) = 0.

Proof. If g is a linear function there is nothing to prove. Otherwise g′ has only finitely many roots in the interval [a, b]. Let

a = c_{0} < c_{1} < ⋯ < c_{k} < c_{k+1} = b

be the set consisting of a, b, and all the roots of g′ in [a, b]. We claim that g takes on a maximum value at one of these c_{i}’s. Suppose not. Then there exists d ∈ [a, b] such that g(d) > g(c_{i}) for all i. Then c_{i} < d < c_{i+1} for some i ≤ k. Hence by Rolle’s theorem there must exist e such that c_{i} < e < c_{i+1} and g′(e) = 0. This is a contradiction.

3.

Lemma. Let F be an ordered field. Let g ∈ F[x] be a nonconstant polynomial such that F satisfies the IVP for all polynomials of degree ≤ deg(g). Suppose g(α) = 0 where α lies in some ordered field extension of F. Then actually α ∈ |F|.

Proof. We prove the lemma by induction on n = deg(g). Assume that the conclusion fails, i.e. α ∉ |F|. It follows that g is irreducible. (Otherwise we could apply the induction hypothesis to the factors and get a contradiction.) In particular g has no roots in |F|, so by the IVP g has constant sign on |F|. Without loss of generality, assume that g < 0 on |F|.

Since g(α) = 0, an easy calculation shows that |α| < 1+|a_{1}|+⋯+|a_{n}| = M where g(x) = x^{n} +a_{1}x^{n−1} +⋯+a_{n}. Thus we have g(−M) < 0, g(α) = 0, g(M) < 0, and −M < α < M. Let G be a RCOF extending F (by proposition 9.1.11). By the maximum principle we must have g(γ) ≥ 0, g′(γ) = 0 for some γ ∈ |G| with −M < γ < M. By the induction hypothesis, g′(γ) = 0 gives γ ∈ |F|. But then g(γ) ≥ 0 contradicts the fact that g < 0 on |F|.

4.

Proposition. If G is a RCOF and G_{1} is an ordered field extension of G which is algebraic over G, then G_{1} = G.

Proof. Immediate from the previous lemma.

5.

Proposition. Let F be an ordered field. Then any two real closures of F are isomorphic over F.

Proof. Let G_{1} and G_{2} be real closures of F. If F is real closed, then G_{1} = G_{2} = F by the previous proposition. Therefore, by Zorn’s lemma or transfinite induction, it suffices to show that if F is not real closed, then we can find α_{i} ∈ |G_{i}| \ |F|, i = 1, 2, such that F(α_{1}) ≅ F(α_{2}) over F as ordered fields.

In order to find α_{1}, α_{2} we imitate the proof of lemma 9.1.9. Let f ∈ F[x] be such that the IVP fails for f but holds for all g of lower degree. Let a, b, A, B be as in the proof of lemma 9.1.9. Since G_{1} is real closed, |G_{1}| \ |F| contains α_{1} such that f(α_{1}) = 0 and a′ < α_{1} < b′ for all a′ ∈ A, b′ ∈ B. We claim that these facts determine the structure of F(α_{1}) as an ordered field. First of all, the field structure of F(α_{1}) is determined by the fact that F(α_{1}) ≅ F[x]/f since f is irreducible. Let g ∈ F[x] be of lower degree than f such that g > 0 on some interval [a′, b′] in F where a′ ∈ A, b′ ∈ B. By the previous lemma we know that any root of g lying in |G_{1}| already lies in |F|. Hence g > 0 on [a′, b′] in G_{1}. Hence in particular g(α_{1}) > 0. Since every element of F(α_{1}) is of the form g(α_{1}), g ∈ F[x], deg(g) < deg(f), our claim is proved. Similarly we can find α_{2} ∈ |G_{2}| \ |F| such that f(α_{2}) = 0 and a′ < α_{2} < b′ for all a′ ∈ A, b′ ∈ B, and we then have F(α_{1}) ≅ F(α_{2}) over F as ordered fields. This completes the proof.

6.

Definition. If F is an ordered field, we denote its real closure by \overline{F}. (The previous result shows that \overline{F} is unique up to isomorphism over F.)

7.

Corollary. Let F be an ordered field and let G be a RCOF extending F. Then G contains (an isomorphic copy of) \overline{F}.

Proof. Let F_{1} be the algebraic closure of F within G. Clearly F_{1} is a real closure of F. By the previous result it follows that \overline{F} is isomorphic to F_{1} over F.

9.3 Quantifier elimination for RCOF

1.

Lemma. Let G be an RCOF and let G(α) be a simple ordered field extension of G, α ∉ |G|. Then α is transcendental over G, and the ordering of G is completely determined by the sets A = {a ∈ |G| : a < α} and B = {b ∈ |G| : α < b}.

Proof. The fact that α is transcendental over G follows immediately from the uniqueness of the real closure of G. The ordering of G(α) is completely determined by that of G[α] which is completely determined by the following claim.

Claim: Let g ∈ G[x].

(i) If A = ∅ (respectively B = ∅) then the sign of g(−α) (respectively g(α)) is the same as that of the leading coefficient of g.

(ii) If A ≠ ∅ ≠ B, then g(α) > 0 if and only if there exist a ∈ A, b ∈ B such that g(c) > 0 for all c ∈ |G|, a < c < b.

Part (i) is obvious, and part (ii) is an easy consequence of lemma 9.2.3. (One may compare the proof of lemma 9.1.9, but note that in the present situation it is possible that A has a greatest element.)

2.

Theorem. The theory of real closed ordered fields is the model completion of the theory of ordered fields.

Proof. It suffices to show that if F ⊆ F_{1} are ordered fields and if F ⊆ G where G is a real closed ordered field and G is κ-saturated, κ = ∥F_{1}∥, then F_{1} is embeddable into G over F. (Cf. theorem 8.3.2.) By transfinite induction we may safely assume that either (1) F_{1} is algebraic over F, or (2) F_{1} = F(α), α transcendental over F, α ∉ |F|, and F is real closed.

In case (1), we have F_{1} ⊆ \overline{F} and by corollary 9.2.7 \overline{F} is embeddable into G over F. In case (2), put A = {a ∈ |F| : a < α} and B = {b ∈ |F| : α < b}. Consider the set of formulas

\{\underline{a} < v : a ∈ A\} ∪ \{v < \underline{b} : b ∈ B\} ∪ \{\underline{f}(v) ≠ 0 : f ∈ F[x], f ≢ 0\} .

This set of formulas is finitely realizable in F. Hence by saturation it is realized in G, say by β ∈ |G|. By the previous lemma it follows that F(α) is order isomorphic to F(β) over F. This completes the proof.

3.

Corollary (Tarski). The theory of real closed ordered fields is complete and decidable.

Proof. Any RCOF has an ordered subfield isomorphic to

Q = (ℚ, +, −, ·, 0, 1, <) .

By the previous theorem, any two RCOFs are elementary equivalent over Q. In particular any two RCOFs are elementarily equivalent, so the theory RCOF is complete. Decidability follows by theorem 4.2.3.

(Tarski actually gave a decision procedure based on a specific explicit quantifier elimination procedure.)

4.

Corollary (Tarski’s transfer principle). Any first order sentence which is true in the real field R = (ℝ, +, −, ·, 0, 1, <) is true in any real closed ordered field.

5.

Examples. (1) The fact that the complex field C is algebraically closed (i.e. the fundamental theorem of algebra) is expressible as a set of first order sentences in the theory of RCOF. (We identify a±b\sqrt{−1} ∈ ℂ with an ordered pair (a, b) ∈ ℝ^{2}.) It follows by Tarski’s principle that, if G is any RCOF, then G(\sqrt{−1}) = G[x]/(x^{2} + 1) is algebraically closed.

(2) Bott and Milnor have used homotopy theory to prove that the only finite dimensional nonassociative algebras over ℝ are those of dimensions 1, 2, 4, and 8 respectively (i.e. ℝ, ℂ, quaternions, octonians). By Tarski’s transfer principle, the same holds for any RCOF.

6.

Corollary (Tarski). The first order theory of the real field

R = (ℝ, +, −, ·, 0, 1, <)

is decidable.

(In other words, there is a decision procedure for “high school mathematics”, including plane and solid geometry since the latter can be interpreted into the first order theory of R using Cartesian coordinates.)

7.

Corollary (Tarksi). Given a finite system S of equations and inequalities in n variables with rational coefficients, we can decide recursively whether S has a solution in reals.

8.

Theorem (Tarksi). The theory of real closed ordered fields admits elimination of quantifiers.

Proof. From proposition 9.1.4 and theorem 9.3.3 it follows that RCOF is the model completion of the theory of ordered domains. The latter theory is universal so by theorem 8.2.3 it follows that RCOF admits elimination of quantifiers.

9.

Corollary (Tarski). The theory of real closed ordered fields is model complete.

10.

Corollary (Artin). Let S be a finite system of equations and inequalities in n unknowns with coefficients in an ordered field F. If S has a solution in some ordered field extension of F, then S has a solution in \overline{F}, the real closure of F.

Proof. Immediate from model completeness plus corollary 9.2.7.

In the next section we shall apply this result to obtain Artin’s solution of Hilbert’s 17th problem.

9.4 The solution of Hilbert’s 17th problem

1.

Let F be an ordered field, \overline{F} its real closure. Put B = F(x_{1}, …, x_{n}) = the field of rational functions over F in n variables x_{1}, …, x_{n}. Hilbert’s 17th problem is concerned with the representation of rational functions as sums of squares.

Theorem (Artin). Let f ∈ |B|, f ≢ 0. Suppose that f(a_{1}, …, a_{n}) ≥ 0 for all a_{1}, …, a_{n} ∈ |\overline{F}| such that f(a_{1}, …, a_{n}) is defined. Then there exists a positive integer k such that

f = ∑_{i=1}^{k} c_{i}g_{i}^{2}

where c_{i} ∈ |F|, c_{i} > 0, g_{i} ∈ |B|, g_{i} ≢ 0.

Proof. Let I ⊂ |B| be the set of all f of this form. We have

(i) g^{2} ∈ I for all g ∈ |B|, g ≢ 0

(ii) g, h ∈ I implies g + h, g · h ∈ I

(iii) 0 ∉ I.

A set I ⊂ |B| satisfying (i), (ii) and (iii) is called an order ideal.

The following lemma holds for any order ideal in any field B.

Lemma. Let I be an order ideal, f ∉ I, f ≢ 0. Then there exists an order ideal J ⊇ I such that −f ∈ J.

Proof of lemma. Assume f ≠ 0. Let J be the set of elements of |B| of the form

p(−f) = (−f)^{m_{1}} · g_{1} + ⋯ + (−f)^{m_{l}} · g_{l}

where l ≥ 1, g_{i} ∈ I, m_{i} ≥ 0. Clearly −f ∈ J and J satisfies (i) and (ii). Suppose (iii) fails for J, say p(−f) = 0. We then have

p(−f) = q(f^{2}) − f · r(f^{2}) = 0

where q(f^{2}) and r(f^{2}) ∈ I or = 0. If r(f^{2}) = 0 then q(f^{2}) = 0 so both are 0. This is impossible since l ≥ 1. Hence r(f^{2}) ≠ 0. Hence

f = \frac{q(f^{2})}{r(f^{2})} = q(f^{2}) · r(f^{2}) · (\frac{1}{r(f^{2})})^{2} ∈ I

since f ≠ 0. This proves the lemma.

Now to prove the theorem, suppose f ∉ I, f ≠ 0. By the lemma, get an order ideal J ⊇ I containing −f. By Zorn’s lemma let K ⊇ J be a maximal order ideal. Then K satisfies (i), (ii), (iii) and also

(iv) for all g ≠ 0 either g ∈ K or −g ∈ K.

This is immediate from the lemma, by maximality of K.

For g, h ∈ |B| define g < h if and only if h − g ∈ K. It is easy to check that this definition makes B an ordered field. Furthermore, if c ∈ |F| is positive in F, then it is positive in B. So B is an ordered field extension of F.

We see now that there exist b_{1} …, b_{n} lying in an ordered field extension of F, such that f(b_{1}, …, b_{n}) < 0 (namely b_{i} = x_{i} lying in B). Hence by model completeness of RCOF (see also corollary 9.3.10), it follows that there exist a_{1}, …, a_{n} ∈ |\overline{F}| such that f(a_{1}, …, a_{n}) < 0. Q.E.D.

2.

Corollary (Artin’s solution of Hilbert’s 17th problem). Let F be either the real field ℝ or the rational field ℚ. Suppose f(x_{1}, …, x_{n}) ∈ F(x_{1}, …, x_{n}) is definite over F, i.e. f(a_{1}, …, a_{n}) ≥ 0 for all a_{1}, …, a_{n} ∈ |F| such that f(a_{1}, …, a_{n}) is defined. Then there exist g_{1}, …, g_{k} in F(x_{1}, …, x_{n}) such that

f = ∑_{i=1}^{k} g_{i}^{2} .

Proof. For the reals this is immediate from the previous theorem. For the rationals, it is immediate from the theorem plus the following two observations: (1) ℚ is dense in ℝ; (2) every positive element of ℚ is the sum of 4 squares in ℚ.

3.

Remark. An ordered field F is said to be Hilbertian if (1) F is dense in \overline{F}, (2) every positive element of F is a sum of squares in F. For example, F = reals, F = rationals, F = any RCOF are Hilbertian. Clearly the above corollary holds for any Hilbertian ordered field. McKenna^{1} has proved the converse: If the corollary holds for F, then F is Hilbertian.

4.

We now derive a corollary concerning effective bounds, analogous to theorem 6.4.3.

Corollary. We can find a recursive function K : ω^{2} → ω with the following property:

Let F be an ordered field, and let f ∈ F(x_{1}, …, x_{n}) be such that f(a_{1}, …, a_{n}) ≥ 0 for all a_{1}, …, a_{n} ∈ \overline{F} such that this is defined. If f is of degree ≤ d then f = ∑_{i=1}^{k} c_{i}g_{i}^{2} for some k ≤ K(n, d), c_{i} ∈ F, c_{i} ≥ 0, g_{i} ∈ F(x_{1}, …, x_{n}) of degree ≤ K(n, d).

1SLNM 498, pp. 220-230.

Proof. Let T be the theory of real closed ordered fields with a distinguished subfield, F. Let σ_{ndm} be the sentence asserting that the desired conclusion holds with K(n, d) replaced by m. We have ∀n ∀d ∃m σ_{ndm} ∈ T (otherwise we could use compactness to construct a counterexample to theorem 9.4.1). So put K(n, d) = least m such that σ_{ndm} ∈ T. This is recursive since T is decidable.

5.

Remark. Ax (unpublished) and Pfister (1967)^{2} have shown that for real closed F we can always get k ≤ 2^{n} (but apparently with no bound on the degrees). There are some open problems in this area.

6.

Exercise. Prove the following result which is known as the Nullstellensatz for ordered fields.

Theorem (Dubois^{3}). Let f, h_{1}, …, h_{m} ∈ F[x_{1}, …, x_{n}] be polynomials in n variables over an ordered field F. Suppose that every common zero of h_{1}, …, h_{m} in \overline{F}, the real closure of F, is a zero of f. Then there exist nonnegative integers r and k such that

f^{2r} + ∑_{i=1}^{k} c_{i}g_{i}^{2} = ∑_{j=1}^{m} p_{j}h_{j}

where c_{i} ∈ |F|, c_{i} ≥ 0, g_{i}, p_{j} ∈ F[x_{1}, …, x_{n}].

Deduce a version with effective bounds.

2Proc. Symp. Pure Math. 28, pp. 483-491.

3Ark. Mat. 8 (1969), pp. 111-114. See also Prestel’s monograph.

Prime models (countable case)

10.1 The omitting types theorem

1.

Definition. Let p be an n-type over a theory T. A model A of T is said to omit p if there is no n-tuple a_{1}, …, a_{n} ∈ |A| which realizes p.

We have already seen how to use the compactness theorem to construct a model which realizes p. It is somewhat more difficult to construct a model which omits p. Indeed, such a model may not even exist. The omitting types theorem gives a sufficient condition for the existence of a model of T which omits p. (If T is complete, this sufficient condition is also necessary.)

2.

Definition. We say that p is principal over T if it is generated by a single formula, i.e. there exists φ ∈ F_{n}(T) such that p = {ψ ∈ F_{n}(T) : T ⊧ ∀v_{1} ⋯ v_{n}(φ(v_{1}, …, v_{n}) → ψ(v_{1}, …, v_{n})). Such a φ is called a generator of p.

We say that p is essentially nonprincipal over T if p is not included in any principal n-type over T.

3.

Theorem (the omitting types theorem). Let T be a countable theory and let p be an n-type over T. Suppose that p is essentially nonprincipal over T.

Then there exists a model of T which omits p.

Proof. We go back to the Henkin proof of the completeness theorem. Let C = \{\underline{c}_{i} : i ∈ ω\} be a countable set of new constant symbols. Let \{σ_{s} : s ∈ ω} be an enumeration of all sentences σ with sig(σ) ⊆ sig(T) ∪ C. Let {φ_{S}(v) : s ∈ ω} be an enumeration of all formulas φ(v) with no free variables other than v, such that sig(φ(v)) ⊆ sig(T) ∪ C. Let \{⟨\underline{c}_{1}^{s}, …, \underline{c}_{n}^{s}⟩ : s ∈ ω\} be an enumeration of all n-tuples of constant symbols from C.

Stage 0: T_{0} = T.

Stage 3s + 1: Put T_{3s+1} = T_{3s} ∪ {σ_{s}} if this is consistent, otherwise T_{3s+1} = T_{3s} ∪ {¬σ_{s}}.

Stage 3s + 2: Let h(s) be the least i such that \underline{c}_{i} does not appear in T_{3s+1} ∪ \{φ_{s}(v)\}. Put T_{3s+2} = T_{3s+1} ∪ \{(∃vφ_{s}(v)) → φ_{s}(\underline{c}_{h(s)})\}.

Stage 3s + 3: Let q be the set of all ψ ∈ F_{n}(T) such that T_{3s+2} ∪ \{¬ψ(\underline{c}_{1}^{s}, …, \underline{c}_{n}^{s})\} is inconsistent. Clearly q is a principal n-type over T. Hence q does not include p. Pick a formula φ ∈ p \ q and put T_{3s+3} = T_{3s+2} ∪ \{¬φ(\underline{c}_{1}^{s}, …, \underline{c}_{n}^{s})\}.

Finally put T_{∞} = ⋃_{s∈ω} T_{s}. Define a Henkin model M as in the proof of theorem 3.1.2. Each n-tuple of elements of |M| is denoted by an n-tuple of Henkin constants \underline{c}_{1}^{s}, …, \underline{c}_{n}^{s}. Thus M omits p.

4.

Remark. The hypothesis that T is countable cannot be omitted from the omitting types theorem.

5.

We digress to present a typical application of the omitting types theorem.

Theorem. Let A = (|A|, ∈^{A}) be a countable model of ZF set theory. Then A has a proper elementary extension B such that ω^{A} = ω^{B}, i.e. A and B have the same natural numbers.

Proof. Let T be the theory generated by

(elementary diagram of A) ∪ \{rank(\underline{c}) > rank(\underline{a}) : a ∈ |A|\}

where \underline{c} is a new constant symbol. T is consistent by the compacttness theorem, and every model of T gives rise to a proper elementary extension of A. Let p be the 1-type over T generated by \{v_{1} ∈ \underline{ω}\} ∪ \{v_{1} ≠ \underline{n} : n ∈ ω^{A}\}. To prove the theorem, it suffices to find a model of T which omits p.

Suppose this were not possible. By the omitting types theorem, p is included in a principal 1-type over T. Let φ ∈ F_{n}(T) be a generator of such a principal 1-type. In particular T ⊧ ¬φ(\underline{n}) for all n ∈ ω^{A}. Let φ(v) = ψ(\underline{c}, v) where sig(ψ) ⊆ sig(elementary diagram of A). Then for each n ∈ ω^{A} we have T ⊧ ¬ψ(\underline{c}, \underline{n}). Hence by compactness, for each n ∈ ω^{A} there exists a ∈ |A| such that the elementary diagram of A contains

∀x (rank(x) > rank(\underline{a}) → ¬ψ(x, \underline{n})) .

Hence

A ⊧ ∀n ∈ ω ∃y ∀x (rank(x) > rank(y) → ¬ψ(x, n)) .

By the replacement axiom in A it follows that

A ⊧ ∃y ∀n ∈ ω ∀x (rank(x) > rank(y) → ¬ψ(x, n)) .

Let a ∈ |A| be such that

A ⊧ ∀n ∈ ω ∀x (rank(x) > rank(\underline{a}) → ¬ψ(x, n)) .

Since T ⊧ rank(\underline{c}) > rank(\underline{a}) it follows that T ⊧ ∀n ∈ ω ¬ψ(\underline{c}, \underline{n}). In other words, T ⊧ ∀v_{1} (φ(v_{1}) → v_{1} ∉ \underline{ω}). This contradicts the assumption that the principal 1-type generated by φ includes p.

6.

The omitting types theorem can be generalized as follows:

Theorem. Let T be a countable theory. For each i ∈ ω, let p_{i} be an essentially nonprincipal n_{i}-type over T. Then T has a model which omits p_{i} for each i ∈ ω.

The proof is a straightforward generalization of the proof of the omitting types theorem.

7.

Exercise. Use the above generalization of the omitting types theorem to prove the following result, which generalizes theorem 10.1.4 above.

Theorem (Keisler and Morley). Let A be a countable model of ZF set theory. Then A has a proper elementary end extension, i.e. a proper elementary extension B such that rank(a) < rank(b) for all a ∈ |A|, b ∈ |B| \ |A|.

In the next section, the omitting types theorem will be used to study prime models.

10.2 Prime models

1.

Definition. Let T be a complete theory. A model A of T is said to be prime if every model of T has an elementary submodel which is isomorphic to A.

2.

Examples.

1. Let T = ACF(0). This theory has a prime model \overline{Q} = the algebraic closure of the rational field Q = (ℚ, +, −, ·, 0, 1).

2. Similarly for T = ACF(p), the theory of algebraically closed fields of prime characteristic p. The prime model is the algebraic closure of F_{p} = (𝔽_{p}, +, −, ·, 0, 1).

3. Generalizing examples 1 and 2, let A be any field and let T = ACF ∪ (diagram of A). We know that T is complete because ACF admits elimination of quantifiers. The prime model of T is \overline{A}, the algebraic closure of A.

4. T = RCOF. The prime model is \overline{Q} = the real closure of the ordered field Q = (ℚ, +, −, ·, 0, 1, <).

5. T = RCOF ∪ (diagram of F) where F is any ordered field. The prime model is \overline{F}, the real closure of F.

6. T = theory of dense linear ordering without end points. The prime model is (ℚ, <).

7. We give an example of a complete countable theory with no prime model. Let T have 1-place relations S_{i}(x), i ∈ ω, and axioms saying that the S_{i}’s are independent, i.e. any nontrivial Boolean combination of them is nonempty. The completeness of T can be proved by quantifier elimination. It is easy to see that no model of T is prime.

3.

Remark. It is clear from the definition of prime model that any elementary submodel of a prime model is prime. Example 6 shows that a prime model may have proper elementary submodels.

4.

The purpose of this section is to establish necessary and sufficient conditions for a complete theory T to have a prime model, and to establish the uniqueness of prime models when they exist. Throughout this chapter we deal with countable theories T; for the uncountable case, see chapter 13.

5.

The following lemma is just a restatement of the omitting types theorem in the special case when T and p are complete.

Lemma. Let T be a countable complete theory, and let p ∈ S_{n}(T) be a complete n-type over T. The following are equivalent.

(i) p is principal over T.

(ii) p is realized in every model of T.

Proof. Assume that p is principal, say generated by φ ∈ F_{n}(T). In particular T ∪ {∃v_{1} ⋯ v_{n} φ(v_{1}, …, v_{n})} is consistent. Since we are assuming that T is complete, it follows that T ⊧ ∃v_{1} ⋯ v_{n} φ(v_{1}, …, v_{n}). Let A be any model of T. Since A ⊧ ∃v_{1} ⋯ v_{n} φ(v_{1}, …, v_{n}), there exist a_{1}, …, a_{n} ∈ |A| such that A ⊧ φ(a_{1}, …, a_{n}). Then clearly the n-tuple a_{1}, …, a_{n} realizes p.

Conversely, suppose that p is nonprincipal over T. Since p is complete, it follows that p is essentially nonprincipal over T. Hence by the omitting types theorem, there exists a model of T which omits p.

6.

Definition. A structure A is atomic if for every a_{1}, …, a_{n} ∈ |A| the complete n-type realized by a_{1}, …, a_{n} is principal over Th(A).

7.

Theorem (Vaught). Let T be a countable complete theory. The following are equivalent for A ∈ Mod(T).

(i) A is prime.

(ii) A is countable and atomic.

Proof. (i) ⇒ (ii). Assume A is prime. Since T has a countable model B and A is isomorphic to an elementary submodel of B, it follows that A is countable. To show that A is atomic, let a_{1}, …, a_{n} ∈ |A| and let p be the complete n-type over T realized by a_{1}, …, a_{n}. Since A is prime, p is realized in every model of T. Hence by the previous lemma it follows that p is principal. Thus A is atomic.

(ii) ⇒ (i). Assume that A is countable and atomic. Let |A| = {a_{n} : n ∈ ω} be an enumeration of |A|. Let B be a model of T. We want to construct an elementary embedding of A into B. Assume inductively that we have chosen b_{0}, …, b_{n−1} ∈ |B| so that (A, a_{i})_{i<n} ≡ (B, b_{i})_{i<n}. Since A is atomic, so is (A, a_{i})_{i<n}. [ For, let c_{1}, …, c_{k} ∈ |A|. The complete (n + k)- type realized by ⟨a_{0}, …, a_{n−1}, c_{1}, …, c_{k}⟩ is principal over T, say generated by θ(u_{0}, …, u_{n−1}, w_{1}, …, w_{k}). Put ψ(w_{1}, …, w_{k}) ≡ θ(\underline{a}_{0}, …, \underline{a}_{n−1}, w_{1}, …, w_{k}). Then ψ generates the complete k-type realized by c_{1}, …, c_{k} over Th((A, a_{i})_{i<n}). ]

Let p_{n} ∈ S_{1}((A, a_{i})_{i<n}) be the complete 1-type realized by a_{n}. Since p_{n} is principal, it follows by the previous lemma that p_{n} is realized in (B, b_{i})_{i<n}, say by b_{n} ∈ |B|. Then (A, a_{i})_{i≤n} ≡ (B, b_{i})_{i≤n}. Finally (A, a_{i})_{i∈ω} ≡ (B, b_{i})_{i∈ω}. Thus a_{i} ↦ b_{i} gives an elementary embedding of A into B.

8.

Theorem (Vaught). Let T be a countable complete theory. If T has a prime model, it is unique up to isomorphism.

Proof. By the previous theorem it suffices to show that any two countable atomic models of T are isomorphic. We use a back-and-forth argument. The inductive step is as in the proof of the previous theorem. The details are routine.

9.

Theorem (Vaught). Let T be a countable complete theory. The following are equivalent.

(i) T has a prime model.

(ii) T has an atomic model.

(iii) Every principal n-type over T is included in a complete principal n-type over T.

10.

Remark. A Boolean algebra B is said to be atomic if for all b ∈ B, b ≠ 0, there exists a ≤ b such that a is an atom, i.e. a ≠ 0 and there is no a_{1} such that 0 < a_{1} < a. The condition (iii) in the theorem can be restated as follows: for each n ∈ ω, the Boolean algebra B_{n}(T) is atomic.

11.

Proof of theorem 9.

(i) ⇒ (ii). Let A be a prime model of T. By 10.2.7 above, A is atomic. (ii) ⇒ (iii). Let A be an atomic model. Let q be a principal n-type

over T, say generated by φ ∈ F_{n}(T). Since T is complete, we have T ⊧ ∃v_{1} … v_{n} φ(v_{1}, …, v_{n}). Hence q is realized in A, say by a_{1}, …, a_{n}. Let p ∈ S_{n}(T) be the complete n-type realized by a_{1}, …, a_{n}. Then p ⊇ q and p is principal.

(iii) ⇒ (i). Assuming (iii) we construct a countable atomic model of T. We employ a Henkin construction as in the proof of the omitting types theorem 10.1.3. Let \{⟨\underline{c}_{1}^{s}, …, \underline{c}_{n_{s}}^{s}⟩ : s ∈ ω\} be an enumeration of all finite sequences of Henkin constants. Stages 0, 3s + 1, and 3s + 2 are as in the proof of theorem 10.1.3.

Stage 3s + 3: Put n = n_{s} and let q be the set of ψ ∈ F_{n}(T) such that T_{3s+2} ∪ \{¬ψ(\underline{c}_{1}^{s}, …, \underline{c}_{n}^{s})\} is inconsistent. Let p ⊇ q be a principal complete n-type over T. Let φ ∈ F_{n}(T) be a generator of p. Put T_{3s+3} = T_{3s+2} ∪ \{φ(\underline{c}_{1}^{s}, …, \underline{c}_{n}^{s})\}. Clearly T_{3s+3} is consistent.

At the end of the construction we obtain a countable atomic model of T. This is prime by theorem 10.2.7.

12.

Corollary (Vaught). Let T be a countable complete theory. Suppose S_{n}(T) is countable for each n ∈ ω. Then T has a prime model.

Proof. Assuming that S_{n}(T) is countable, we shall show that B_{n}(T) is atomic, i.e. every principal n-type q over T is included in a complete principal n-type over T. Suppose not, i.e. any principal n-type which includes q is incomplete. We use a splitting argument. For each finite sequence s of 0’s and 1’s we define a principal n-type q_{s} which includes q. Begin with q_{∅} = q. Given q_{s}, we know that q_{s} is incomplete, so let φ_{s} ∈ F_{n}(T) be a formula such that q_{s} ∪{φ_{s}} and q_{s} ∪{¬φ_{s}} are both consistent. Let q_{s1} be the n-type generated by q_{s} ∪ {φ_{s}} and let q_{s0} be the n-type generated by q_{s} ∪ {¬φ_{s}}.

For each f ∈ 2^{ω} let q_{f} = ⋃{q_{f↾n} : n ∈ ω}. Then q_{f} is an n-type over T, and f ≠ g implies q_{f} ∪ q_{g} is inconsistent. Let p_{f} be a complete n-type over T which includes q_{f}. Then f ≠ g implies p_{f} ≠ p_{g}. Hence |S_{n}(T)| = 2^{ℵ_{0}} contradicting our assumption that S_{n}(T) is countable.

13.

Remark. In terms of Boolean algebras, the previous argument shows that if B is a countable Boolean algebra with S(B) countable, then B is atomic.

10.3 The number of countable models

1.

Let T be a complete theory and let κ be a cardinal. We write ν(T, κ) = the number of nonisomorphic models of T of cardinality κ. This function is a central object of study in pure model theory.

In this section, we study ν(T, ℵ_{0}) where T is complete and countable. We begin with the case when ν(T, ℵ_{0}) = 1, i.e. T is ℵ_{0}-categorical.

2.

Theorem (Ryll-Nardzewski). Let T be a complete countable theory with no finite models. The following are equivalent:

(1) T is ℵ_{0}-categorical.

(2) S_{n}(T) is finite for each n ∈ ω.

(3) Every countable model of T is prime.

(4) Every countable model of T is saturated.

(The equivalence of (1) and (2) is due to Ryll-Nardzewski.)

Proof. (1) ⇒ (2). Suppose that S_{n}(T) is infinite. We claim that there exists a nonprincipal q ∈ S_{n}(T). To see this, for each principal p ∈ S_{n}(T) let φ_{p} ∈ F_{n}(T) be a generator of p. Put Y = {¬φ_{p} : p ∈ S_{n}(T), p non-principal}. Since S_{n}(T) is infinite, it follows by compactness that Y is consistent over T. Hence Y can be extended to a complete n-type q ∈ S_{n}(T). Clearly q is nonprincipal.

By lemma 10.2.5 there exists a countable model A ∈ Mod(T) such that A omits q. Also there exists a countable B ∈ Mod(T) such that B realizes q. A and B are nonisomorphic, so T is not ℵ_{0}-categorical.

(2) ⇒ (3). Since S_{n}(T) is finite, every p ∈ S_{n}(T) is principal. Hence every model of T is atomic. Hence by theorem 10.2.7 it follows that every countable model of T is prime.

(2) ⇒ (4). Let A be a countable model of T., and let X ⊆ |A| be finite. From (2) it follows that S_{1}(X) is finite. hence each p ∈ S_{1}(X) is principal, hence realized in A_{X}. This shows that A is saturated.

(3) ∨ (4) ⇒ (1). This is because of uniqueness of prime models (10.2.8) or saturated models (7.2.8) respectively.

3.

Remark. In terms of Boolean algebras, the argument for (1) ⇒ (2) above shows that if B is a Boolean algebra with S(B) infinite (equivalently B is infinite), then B has a nonprincipal ultrafilter.

4.

Next we consider the situation where 1 < ν(T, ℵ_{0}) < ℵ_{0}. We say that a countable model A of T is weakly saturated if every p ∈ S_{n}(T), n ∈ ω is realized in A.

5.

Theorem (Rosenstein). Suppose 1 < ν(T, ℵ_{0}) < ℵ_{0} where T is a countable complete theory. Then T has a weakly saturated countable model which is not saturated.

Proof. Suppose not. Let A_{1}, …, A_{k} be the countable models of T which are not saturated. By assumption these models are not weakly saturated, so let p_{i} ∈ S_{n_{i}}(T) be omitted in A_{i}, 1 ≤ i ≤ k.

Introduce new constant symbols \underline{c}_{1}^{i}, …, \underline{c}_{n_{i}}^{i}, 1 ≤ i ≤ k, and let T ∗ be a countable complete theory which includes T ∪ \{φ(\underline{c}_{1}^{i}, …, \underline{c}_{n_{i}}^{i}) : φ ∈ p_{i}, 1 ≤ i ≤ k}. Let A∗ = (|A∗|, Φ∗) be any countable model of T ∗. Then A = (|A∗|, Φ∗↾sig(T)) is a countable model of T. Since each p_{i} is realized in A, 1 ≤ i ≤ k, it follows that A is saturated. Hence A∗ is saturated. We have now shown that any countable model of T ∗ is saturated. Hence T ∗ is ℵ_{0}-categorical. Hence by Ryll-Nardzewski’s theorem 10.3.2, it follows that S_{n}(T ∗) is finite for all n ∈ ω. Hence S_{n}(T) is finite for all n ∈ ω. Hence by 10.3.2 again it follows that T is ℵ_{0}-categorical, i.e. ν(T, ℵ_{0}) = 1, contradicting the hypothesis of the theorem.

6.

Theorem (Vaught). Let T be a countable complete theory. Then ν(T, ℵ_{0}) ≠ 2.

Proof. Suppose 1 < ν(T, ℵ_{0}) < ℵ_{0}. From ν(T, ℵ_{0}) ≤ ℵ_{0} it follows that S_{n}(T) is countable for each n ∈ ω. Hence among the countable models of T are a prime one, a saturated one, and a weakly saturated one (corollary 10.2.12 and theorems 7.3.1 and 10.3.5). These three countable models are nonisomorphic (theorems 10.2.7 and 10.3.5).

7.

Examples. (1) We give examples of countable complete theories T_{k} with ν(T, ℵ_{0}) = k, 1 ≤ k < ℵ_{0}. We may take T_{1} to be the theory of dense linear ordering without endpoints (ℵ_{0}-categorical by 2.3.1). By the previous theorem, T_{2} does not exist.

We may take T_{3} to be the theory whose axioms are T_{1} ∪ \{\underline{c}_{n} < \underline{c}_{n+1} : n ∈ ω}. Thus a model of T_{3} consists of a dense linear ordering without endpoints together with an increasing sequence of distinguished elements c_{n}, n ∈ ω. In the three countable models, the c_{n}’s are unbounded, bounded with no limit, or bounded with a limit. (These three models are respectively prime, saturated, and weakly saturated.)

For m ≥ 1 we take axioms for T_{3+m} to consist of

T_{3} ∪ \{\underline{P}_{0}(\underline{c}_{n}) : n ∈ ω\}
∪ \{∀x (\underline{P}_{i}(x) for exactly one i, 0 ≤ i ≤ m)\}
∪ \{∀x ∀y (x < y → ∃z(\underline{P}_{i}(z) ∧ x < z < y)) : 0 ≤ i ≤ m\} .

Thus a model of T_{3+m} is a model of T_{3} in which the points are colored with m + 1 densely shuffled colors P_{i}, 0 ≤ i ≤ m, and the distinguished points c_{n} have color P_{0}. In a given model of T_{3+m} we may have c_{n}’s unbounded, bounded with no limit, or bounded with a limit in P_{i}, 0 ≤ i ≤ m. This gives m + 3 distinct countable models. (All except the prime one are weakly saturated.)

(2) There are plenty of examples of countable complete theories T with ν(T, ℵ_{0}) = ℵ_{0} or 2^{ℵ_{0}}. For instance ν(ACF(0), ℵ_{0}) = ℵ_{0} and ν(RCOF, ℵ_{0}) = 2^{ℵ_{0}}.

8.

We omit the proof of the following theorem.

Theorem (Morley). Let T be a countable complete theory. If ν(T, ℵ_{0}) is infinite, then it is equal to either ℵ_{0}, ℵ_{1}, or 2^{ℵ_{0}}.

9.

Remark. Vaught has conjectured that for all countable complete theories T, if ν(T, ℵ_{0}) > ℵ_{0} then ν(T, ℵ_{0}) = 2^{ℵ_{0}}. No counterexample to Vaught’s conjecture is known. Steel^{1} has shown that Vaught’s conjecture holds for theories T whose models are trees. (A tree is a partially ordered set such that the predecessors of any element are linearly ordered.) Shelah has shown that Vaught’s conjecture holds for superstable theories. Also, Lachlan^{2} has shown that for superstable theories, ν(T, ℵ_{0}) < ℵ_{0} implies ν(T, ℵ_{0}) = 1.

10.4 Decidable prime models

1.

Let A be a countable model such that sig(A) is finite (or recursive). Recall that A is said to be decidable if there exists an enumeration |A| = {a_{n} : 1 ≤ n < ω} of the elements of A, such that

{φ ∈ ⋃_{n∈ω} F_{n}(T) : A ⊧ φ(a_{1}, …, a_{n})}

is recursive. (This is easily seen to be equivalent to definition 4.3.1.)

2.

Recall theorem 4.3.4 which said that if T is a decidable theory, then T has a decidable model. However, it is not in general true that if T is a complete decidable theory which has a prime model, then T has a decidable prime model. We now present a theorem which gives a necessary and sufficient condition for T to have a decidable prime model.

1SLNM 689

2FM 81

3.

Theorem (Harrington). Let T be a complete decidable theory. The following are equivalent.

(a) T has a decidable prime model.

(b) Given n ≥ 1 and φ ∈ F_{n}(T) such that φ is consistent with T, we can recursively enumerate a complete n-type p^{φ} ∈ S_{n}(T), such that φ ∈ p^{φ} and p^{φ} is principal.

Note. We do not assume in (b) that it is possible to pass recursively from φ to a generator of p^{φ}.

Proof. (a) ⇒ (b). Let A be a decidable prime model of T. Given φ ∈ F_{n}(T) consistent with T, since T is complete we have T ⊧ ∃v_{1} ⋯ v_{n} φ so we can recursively find an n-tuple a_{1}, …, a_{n} ∈ |A| such that A ⊧ φ(a_{1}, …, a_{n}). We can then enumerate the complete n-type realized by a_{1}, …, a_{n} and define p^{φ} to be this type. Clearly φ ∈ p^{φ}, and p^{φ} is principal by theorem 10.2.7.

(b) ⇒ (a). Let T be a complete decidable theory such that (b) holds. Introduce a recursive set of new constant symbols C = \{\underline{c}_{n} : 1 ≤ n < ω\} and let T_{0} = T ∪ \{H_{n}(\underline{c}_{1}, …, \underline{c}_{n}) : 1 ≤ n < ω\} where H_{n}(\underline{c}_{1}, …, \underline{c}_{n}) is the nth Henkin sentence (∃x ψ_{n}(x)) → ψ_{n}(\underline{c}_{n}). Here we assume that {ψ_{n}(x) : 1 ≤ n < ω} is an enumeration of all formulas ψ(x) with one free variable x such that sig(ψ(x)) ⊆ sig(T)∪C, and we assume that sig(ψ_{n}(x)) ⊆ sig(T) ∪ \{\underline{c}_{1}, …, \underline{c}_{n}\}.

We shall construct a complete decidable theory T_{∞} extending T_{0} such that, for each m ≥ 1, there will exist a formula φ_{m} ∈ F_{m}(T) such that \underline{c}_{1}, …, \underline{c}_{m} realizes p^{φ_{m}}. This clearly implies that the Henkin model associated with T (as in the proof of theorem 4.3.4) is decidable and prime.

If it were possible to pass recursively from φ to a generator of p^{φ}, we could construct T_{∞} by straightforwardly combining the proofs of theorem 4.3.4 and 10.2.9. It would then be the case that φ_{m} is a recursive function of m. Unfortunately this is not possible. We shall have to define φ_{m} as the limit of a recursive sequence of approximations φ_{m}^{s}. We shall use a priority argument to show that the approximations converge.

We shall construct T_{∞} recursively in stages T_{0} ⊆ T_{1} ⊆ ⋯ ⊆ T_{s} ⊆ · · ·. At each stage s ≥ 0, T_{s} will consist of T_{0} plus finitely many sentences.

Let τ^{s}(\underline{c}_{1}, …, \underline{c}_{N_{s}}) be the conjunction of this finite set of sentences, where τ^{s} ∈ F_{N_{s}}(T). Put

τ_{m}^{s}(v_{1}, …, v_{m}) ≡ ∃v_{m+1} ⋯ v_{n} [ H_{1}(v_{1}) ∧ ⋯ ∧ H_{n}(v_{1}, …, v_{n}) ∧ τ^{s}(v_{1}, …, v_{N_{s}}) ]

where n = max(m, N_{s}). Thus τ_{m}^{s} expresses all the assertions about \underline{c}_{1}, …, \underline{c}_{m} to which we are committed at the end of stage s. Note that τ_{m}^{s} ∈ F_{m}(T).

At each stage s, there will be a recursive sequence of formulas φ_{m}^{s} ∈ F_{m}(T), 1 ≤ m < ω. Here φ_{m}^{s} is the stage s approximation of the desired formula φ_{m}.

We now present the construction.

Stage 0. Let T_{0} be as above. Put φ_{m}^{0}(v_{1}, …, v_{m}) = τ_{m}^{0}(v_{1}, …, v_{m}).

Stage s + 1. Let s = (n − 1, k, t) in some fixed recursive enumeration of ω × ω × ω. Let θ(v_{1}, …, v_{n}) be the kth formula in some fixed recursive enumeration of F_{n}(T). At this stage we shall consider whether to add θ(\underline{c}_{1}, …, \underline{c}_{n}) to our theory.

If θ ∈ p^{φ_{n}^{s}} and T |̸= τ_{n}^{s} → θ and T ⊧ τ_{m}^{s} → ∃v_{m+1} ⋯ v_{n} [ τ_{n}^{s} ∧ θ] for each m, 1 ≤ m < n, then put

T_{s+1} = T_{s} ∪ \{θ(\underline{c}_{1}, …, \underline{c}_{n})\}

and, for all m ≥ 1,

φ_{m}^{s+1} = \{ \begin{matrix}φ_{m}^{s} & if 1 ≤ m ≤ n , \\ τ_{m}^{s+1} & if m > n . \end{matrix}

Otherwise do nothing, i.e. T_{s+1} = T_{s} and φ_{m}^{s+1} = φ_{m}^{s} for all m ≥ 1.

It is clear that the construction is recursive and hence produces a recursively axiomatizable theory T_{∞}. We shall now prove a sequence of claims leading to the conclusion that this theory is complete and gives rise to an atomic Henkin model.

Claim 1: T ⊧ τ_{m}^{s} → φ_{m}^{s}.

This is clear by induction on s since φ_{m}^{0} = τ_{m}^{0} and φ_{m}^{s+1} = either φ_{m}^{s} or τ_{m}^{s+1}.

Claim 2: τ_{m}^{s} ∈ p^{φ_{m}^{s}}.

We prove this by induction on s. For s = 0 it is trivial since τ_{m}^{0} = φ_{m}^{0} ∈ p^{φ_{m}^{0}}. If no action is taken at stage s + 1, the induction step is trivial. Consider a stage s + 1 at which action is taken. Let n and θ be as in the construction. For m < n we have τ_{m}^{s+1} ≡ ∃v_{1} ⋯ v_{n} [ τ_{n}^{s} ∧ θ] so by hypothesis T ⊧ τ_{m}^{s} → τ_{m}^{s+1}. Also φ_{m}^{s+1} = φ_{m}^{s} so by induction τ_{m}^{s+1} ∈ p^{φ_{m}^{s}} = p^{φ_{m}^{s+1}}. For m = n, we have τ_{n}^{s+1} = τ_{n}^{s} ∧ θ and τ_{n}^{s} ∈ p^{φ_{n}^{s}} by induction, and θ ∈ p^{φ_{n}^{s}} by hypothesis. Hence τ_{n}^{s+1} ∈ p^{φ_{n}^{s}} = p^{φ_{n}^{s+1}} since φ_{n}^{s+1} = φ_{n}^{s}. Finally, for m > n, we have τ_{m}^{s+1} = φ_{m}^{s+1} ∈ p^{φ_{m}^{s+1}}.

Claim 3: ∀n ∃s ∀s′ ≥ s φ_{n}^{s′} = φ_{n}^{s}. (We then define φ_{n} = lim_{s} φ_{n}^{s}.)

Claim 4: ∀n ∃s (τ_{n}^{s} is a generator of p^{φ_{n}}).

We prove claims 3 and 4 simultaneously by induction on n. Assume that 3 nd 4 hold for all m < n. Let σ be a stage such that for all m < n and all s ≥ σ, φ_{m}^{s} = φ_{m}^{σ} and τ_{m}^{s} generates p^{φ_{m}^{s}}.

We first prove 3 for n. Given s ≥ σ, let s = (m − 1, k, t) and let θ be the kth formula in F_{m}(T). If m ≥ n, then φ_{n}^{s+1} = φ_{n}^{s}. If m < n, then θ ∈ p^{φ_{m}^{s}} implies T ⊧ τ_{m}^{s} → θ, so nothing was done at stage s. Hence again φ_{n}^{s+1} = φ_{n}^{s}. Thus by induction we have ∀s ≥ σ φ_{n}^{s} = φ_{n}^{σ}.

Next we prove claim 4 for n. Let θ be a generator of p^{φ_{n}} = p^{φ_{n}^{σ}}. Look at what happens at a stage s ≥ σ such that s = (n − 1, k, t) where θ is the kth formula in F_{n}(T). We have θ ∈ p^{φ_{n}^{s}} and, by claim 2, τ_{n}^{s} ∈ p^{φ_{n}^{s}}. Hence τ_{n}^{s} ∧ θ is consistent with T. Hence, for each m < n, since τ_{m}^{s} generates p^{φ_{m}^{s}}, it follows that τ_{m}^{s} is an atom in B_{m}(T), so

T ⊧ τ_{m}^{s} → ∃v_{m+1} ⋯ v_{n} [ τ_{n}^{s} ∧ θ] .

Thus, unless T ⊧ τ_{n}^{s} → θ already, we have T_{s+1} = T_{s} ∪ \{θ(\underline{c}_{1}, …, \underline{c}_{n})\}. In any case T ⊧ τ_{n}^{s+1} → θ so τ_{n}^{s+1} is a generator of p^{φ_{n}}. This completes the proof of claims 3 and 4.

From claim 4 it follows that T_{∞} = ⋃_{s∈ω} T_{s} generates a complete decidable extension of T_{0} whose asociated Henkin model is atomic. This completes the proof of the theorem.

4.

Remark. In chapter 11 we shall apply the above theorem to show that the differential closure of a computable differential field of characteristic 0 is computable. This was Harrington’s original application.

5.

Exercise. Prove the following theorem of Morley^{3}:

3Israel J. Math. vol. 25 pp. 233-240

Theorem (Morley). A complete decidable theory T has a decidable saturated model if and only if there is a uniform recursive enumeration of ⋃_{n∈ω} S_{n}(T).

For more information on decidable models, see e.g. Millar, Annals of Math. Logic vol. 13, pp. 45-72.

6.

Exercise. Use theorem 10.4.3 to prove that the algebraic closure of a computable field is computable, and the real closure of a computable ordered field is computable.

Differentially closed fields of characteristic 0

11.1 Simple extensions

1.

The theory of differential fields, DF, has the following set of axioms:

(a) field axioms

(b) ∀x ∀y (x + y)′ = x′ + y′

(c) ∀x ∀y (x · y)′ = x′ · y + x · y′

Here ′ is a 1-place operation symbol.

A differential field is a model of these axioms. A differential domain is a model of the axioms for domains plus (b), (c). A differential ring is defined similarly. The characteristic of a diffrential field is the characteristic of the underlying field.

2.

Examples. (1) Let A be any field. The polynomial ring A[x] can be made into a differential ring by interpreting ′ as the formal derivative, i.e. if f = a_{n}x^{n} + ⋯ + a_{1}x + a_{0}, a_{i} ∈ |A|, then f′ = na_{n}x^{n−1} + ⋯ + a_{1}.

We can extend the derivative to the field of rational functions A(x) = field of quotients of A[x] in the usual way:

(\frac{f}{g} )′ = \frac{f′ · g − f · g′}{g^{2}} .

Then A(x) becomes a differential field.

(2) Any field A can be made into a differential field in a trivial way by putting a′ = 0 for all a ∈ |A|.

Note that this is the only way to make the rational field Q = (ℚ, +, −, ·, 0, 1) into a differential field. Thus the differential field Q is embedded in every differential field of characteristic 0.

(3) Let D be a connected open set in the complex z-plane (or more generally any Riemann surface). Let M be the field of meromorphic functions on D, i.e. the field of quotients of the ring of holomorphic functions on D. This can be regarded as a differential field in the obvious way: f′ = derivative of f = df/dz.

(4) Let N be the set of all functions which are meromorphic in some open set containing 0 in the z-plane. (Identify two such functions if they are equal on some open set containing 0.) This is again a differential field in an obvious way.

3.

Remark. Ritt and Seidenberg^{1} have shown that every differential field which is finitely generated over the reational field is isomorphic to a differential subfield of N. Thus everything we shall do in this chapter is meaningful for analysis.

4.

We now study simple extensions of differential fields of characteristic 0.

Lemma. Let D be a differential domain and let F be its field of quotients, F = {c/d : c, d ∈ |D|, d ≠ 0}. Then there is one and only one way to make F into a differential field extension of D.

1Proc. AMS 9 (1958) 159-164; 23 (1969) 689-691.

Proof. We must have

c′ = (\frac{c}{d} · d)′ = (\frac{c}{d})′ · d + \frac{c}{d} · d′

so

(\frac{c}{d})′ = \frac{c′ · d − c · d′}{d^{2}} .

It is easy to check that this makes F a differential field, etc.

5.

Lemma. Let A be a differential field of characteristic 0. Let B = A(b_{0}, …, b_{n−1}, b_{n}) be a finitely generated field extension of A such that

(i) for each i < n, b_{i} is transcendental over A(b_{0}, …, b_{i−1}),

(ii) b_{n} is algebraic over A(b_{0}, …, b_{n−1}).

Then there is one and only one way to make B into a differential field extension of A subject to the conditions b′_{i} = b_{i+1}, i < n.

6.

Before proving this lemma, we give an example. Let b_{0} be transcendental over A and let b_{1} satisfy b_{1}^{2} − b_{0} = 0. Then A(b_{0}, b_{1}) can be made into a differential field extension of A in which b_{0} is a solution of the first order differential equation (y′)^{2} − y = 0 and is not the solution of any algebraic equation over A.

7.

Proof of lemma 5. Consider the ring A[y⃗] = A[y_{0}, …, y_{n−1}, y_{n}]. A typical element g of A[y_{0}, …, y_{n−1}, y_{n}] looks like

g(y⃗) = ∑_{j} a_{j}y^{j}

where a_{j} = a_{j_{0}j_{1}...j_{n}} ∈ |A| and y^{j} = y_{0}^{j_{0}} ⋯ y_{n−1}^{j_{n−1}}y_{n}^{j_{n}}. Let us write

g̃(y⃗) = ∑_{j} a′_{j}y^{j}

and ∂g/∂y_{i} = the formal partial derivative of g(y_{0}, …, y_{n−1}, y_{n}) with respect to y_{i}. Given g(b_{0}, …, b_{n−1}, b_{n}) ∈ A[b_{0}, …, b_{n−1}, b_{n}] we are forced to define

g(b_{0}, …, b_{n−1}, b_{n})′ = g̃(b_{0}, …, b_{n−1}, b_{n}) + ∑_{i=0}^{n} \frac{∂g}{∂y_{i}} (b_{0}, …, b_{n−1}, b_{n}) · b_{i+1}

where however b_{n+1} remains to be determined.

Let f(b_{0}, b_{1}, …, b_{n−1}, y_{n}) ∈ A(b_{0}, …, b_{n−1})[y_{n}] be irreducible such that B ≅ A(b_{0}, …, b_{n−1})[y_{n}]/f (by theorem 6.1.12). Multiplying f by a suitable element of A[b_{0}, …, b_{n−1}], we may safely assume that f(y_{0}, …, y_{n−1}, y_{n}) ∈ A[y_{0}, …, y_{n−1}, y_{n}]. As in the previous paragraph, we want

0 = f(b_{0}, b_{1}, …, b_{n−1}, b_{n})′ = f̃(b_{0}, …, b_{n−1}, b_{n}) + ∑_{i=0}^{n} \frac{∂f}{∂y_{i}} (b_{0}, …, b_{n−1}, b_{n}) · b_{i+1} .

Since ∂f/∂y_{n} is of lower degree than f in y_{n}, we must have

\frac{∂f}{∂y_{n}} (b_{0}, …, b_{n−1}, b_{n}) ≠ 0 .

Hence we are forced to define

b_{n+1} = \frac{f̃(b_{0}, …, b_{n−1}, b_{n}) + ∑_{i=0}^{n−1} \frac{∂f}{∂y_{i}} (b_{0}, …, b_{n−1}, b_{n}) · b_{i+1}}{−\frac{∂f}{∂y_{n}} (b_{0}, …, b_{n−1}, b_{n})} .

We must check that′ is well defined. We have f(b_{0}, …, b_{n−1}, b_{n}) = 0. Also f(b_{0}, …, b_{n−1}, b_{n})′ = 0 by choice of b_{n+1}. Suppose g_{1}, g_{2} ∈ A[y_{0}, …, y_{n−1}, y_{n}] are such that g_{1}(b_{0}, …, b_{n−1}, b_{n}) = g_{2}(b_{0}, …, b_{n−1}, b_{n}). Then

g_{1}(b_{0}, …, b_{n−1}, y_{n}) ≡ g_{2}(b_{0}, …, b_{n−1}, y_{n}) mod f(b_{0}, …, b_{n−1}, y_{n})

in the polynomial ring A(b_{0}, …, b_{n−1})[y_{n}]. Hence g_{1} − g_{2} = f · h where h ∈ A(y_{0}, …, y_{n−1})[y_{n}]. Letting h = p/q, we have

q · (g_{1} − g_{2}) = f · p

where p ∈ A[y_{0}, …, y_{n−1}, y_{n}] q ∈ A[y_{0}, …, y_{n−1}], q ≢ 0. Substituting b_{i} for y_{i} and differentiating both sides we have

q(b⃗) · (g_{1}(b⃗)′ − g_{2}(b⃗)′) = f(b⃗)′ · p(b⃗) + f(b⃗ · p(b⃗)′

and q(b⃗) ≠ 0, hence g_{1}(b_{0}, …, b_{n−1}, b_{n})′ = g_{2}(b_{0}, …, b_{n−1}, b_{n})′. This shows that′ is well defined on the ring A[b_{0}, …, b_{n−1}, b_{n}]. It is easy to check the sum and product rules, so we now know that there is one and only one way to make A[b_{0}, …, b_{n−1}, b_{n}] into a differential ring extension of A. By lemma 11.1.4 we get the same conclusion for the field of quotients B = A(b_{0}, …, b_{n−1}, b_{n}). This completes the proof.

8.

Remark. Let A be a differential field. We have considered four different kinds of “simple extensions” of A, namely:

A[b] = ring generated by |A| ∪ {b},

A(b) = field generated by |A| ∪ {b},

A{b} = differential ring generated by |A| ∪ {b},

A⟨b⟩ = differential field generated by |A| ∪ {b}.

Our goal is to classify the simple differential field extensions A⟨b⟩.

9.

Definition. Let A be a differential field. A differential polynomial f(y) = f(y, y′, …, y^{(n)}) is an element of the differential ring

A{y} = A[y, y′, …, y^{(n)}, …]

where of course y^{(n)} = y\underbrace{′′···′}_{n times} and y is a differential indeterminate. (Alternatively, we could define a differential polynomial to be an equivalence class of terms t(y) in the language of the diagram of A, as in 6.1.4.)

Note that A{y} is a differential domain and A⟨y⟩, its field of quotients, is a differential field by lemma 11.1.4.

10.

Definition. If f(y) ∈ A{y} is a nonzero differential polynomial over A, we define the order of f to be the largest n such that y^{(n)} occurs in f, and the degree of f to be the largest k such that (y^{(n)})^{k} occurs in f, where n is the order of f.

For example, the differential polynomial (y^{(3)})^{4} + (y′)^{5} · y^{(3)} − y has order 3 and degree 4.

11.

We now survey all simple differential field extensions A⟨b⟩ of a differential field A of characteristic 0.

Case 1: f(b) = 0 for some nonzero f ∈ A{y}. Choose such an f of lowest possible order n, and then of lowest possible degree k for that order. Note that ∂f/∂y^{(n)} has lower order or else the same order and lower degree. Hence

\frac{∂f}{∂y^{(n)}} (b) ≠ 0 .

Hence, as in 11.1.7, we have

b^{(n+1)} = \frac{f̃(b) + ∑_{i=0}^{n−1} \frac{∂f}{∂y^{(i)}} (b) · b^{(i+1)}}{−\frac{∂f}{∂y^{(n)}} (b)}

so in particular b^{(n+1)} ∈ A(b, …, b^{(n−1)}, b^{(n)}). From this it follows that b^{(j)} ∈ A(b, …, b^{(n−1)}, b^{(n)}) for all j, and hence the field A(b, …, b^{(n−1)}, b^{(n)}) is closed under ′. Hence A⟨b⟩ = A(b, …, b^{(n−1)}, b^{(n)}) and its structure is as in lemma 11.1.5. In this case we say that b is differentially algebraic over A.

Case 2: negation of case 1. In this case it is easy to see that A{b} ≅ A{y}, hence the quotient fields A⟨b⟩ ≅ A⟨y⟩ by lemma 11.1.4. In this case we say that b is differentially transcendental over A.

This completes our survey of the simple differential field extensions of A.

12.

From the above survey of simple extensions we immediately obtain the following result.

Theorem. Let A be a differential field of characteristic 0. Up to isomorphism over A, there are exactly ∥A∥ distinct simple differential field extensions A⟨b⟩.

11.2 Differentially closed fields

1.

Definition (Blum). Let B be a differential field of characteristic 0. We say that B is differentially closed if B is algebraically closed and, for all f, g ∈ B{y} with 0 ≤ order(g) < order(f), there exists b ∈ |B| with f(b) = 0, g(b) ≠ 0.

2.

Lemma. Let A be a differential field of characteristic 0. Then there exists a differential field B ⊇ A such that (i) B is differentially closed, (ii) B is differentially algebraic over A, i.e. every b ∈ |B| is differentially algebraic over A.

Proof. By transfinite induction, it suffices to show:

3.

Sublemma. Given f ∈ A{y} of order > 0, there exists a simple differential field extension A⟨b⟩ such that f(b) = 0 and g(b) ≠ 0 for all g ∈ A{y} with 0 ≤ order(g) < order(f).

(In this event b is called a generic solution of the differential equation f(y) = 0 over A.)

To prove the sublemma, let n be the order of f and let A∗ = A(b_{0}, …, b_{n−1}) be a field extension of A in which each b_{i}, i < n, is transcendental over A(b_{0}, …, b_{i−1}). Define a polynomial p(x) ∈ A∗[x] by p(x) = f(b_{0}, …, b_{n−1}, x) where f = f(y, …, y^{(n−1)}, y^{(n)}) ∈ A[y, …, y^{(n−1)}, y^{(n)}]. Let A∗(c) be a simple algebraic field extension of A∗ such that p(c) = 0. Put b_{n} = c. By lemma 11.1.5 we can make A∗(c) = A(b_{0}, …, b_{n−1}, b_{n}) into a simple differential field extension A⟨b⟩ of A where b = b_{0}, b′_{i} = b_{i+1} for i < n. We then have f(b) = f(b_{0}, …, b_{n−1}, b_{n}) = p(b_{n}) = p(c) = 0 and by construction g(b_{0}, …, b_{n−1}) ≠ 0 for all nonzero g ∈ A[y_{0}, …, y_{n−1}], in other words g(b) ≠ 0 for all g ∈ A{y} of order m, 0 ≤ m < n. This completes the proof.

4.

Remark. In the statement of the lemma B is not unique. See 11.3.4 below.

5.

Theorem (Robinson, Blum). The theory of differentially closed fields of characteristic 0 (DCF(0)) is the model completion of the theory of differential fields of characteristic 0 (DF(0)).

Proof. By the previous lemma plus theorem 8.3.2 it suffices to show the following:

Let A ⊆ B where A is a DF(0), B a DCF(0), B κ^{+}-saturated where κ = ∥A∥. Then for any simple differential field extension A⟨c⟩ of A, we can find b ∈ |B| such that A⟨b⟩ ≅ A⟨c⟩ over A.

To prove this, we consider two cases.

Case 1: c is differential algebraic over A, i.e. f(c) = 0 for some nonzero f ∈ A{y}. Take f to be of least order, and of least degree for that order. Let p be the 1-type over A generated by the differential equation f(y) = 0 and the inequations g(y) ≠ 0, g ∈ A{y}, 0 ≤ order(g) < order(f). Since B is differentially closed, every finite subset of p is realized in B. Hence by saturation p is realized in B, say by b ∈ |B|. We claim that A⟨b⟩ ≅ A⟨c⟩ over A. This is clear from 11.1.5 and 11.1.11.

Case 2: c is differentially transcendental over A. Consider the 1-type p over A generated by g(y) ≠ 0 for all g ∈ A{y}, 0 ≤ order(g). Again, since B is differentially closed, each finite subset of p is realized in B. Hence p is realized in B, say by b ∈ |B|. Then b is differentially transcendental over A, so A⟨b⟩ ≅ A⟨c⟩. This completes the proof.

6.

Corollary. DCF(0) is complete and decidable.

Proof. By the previous theorem DCF(0) ∪ (diagram of ℚ) is complete, but any DCF(0) has ℚ as a uniquely embedded differential subfield, so DCF(0) is complete. Decidability follows by theorem 4.2.3.

7.

Corollary (Seidenberg). Let S be a system of finitely many algebraic differential equations in n unknown functions y_{1}, …, y_{n} and their derivatives, with rational coefficients. Then we can recursively decide whether S has a solution in some differential field of characteristic 0 (equivalently by 11.1.3 in some field of meromorphic functions).

8.

Corollary. DCF(0) admits elimination of quantifiers.

Proof. From theorem 11.2.5 and lemma 11.1.4 it follows that DCF(0) is the model completion of the theory of differential domains of characteristic 0. The latter theory is universal so quantifier elimination follows by theorem 8.2.3.

9.

Corollary (Seidenberg). There exists an elimination theory for finite systems of algebraic differential equations and inequations (cf. 8.2.6).

11.3 Differential closure (countable case)

1.

Definition. Let A be a DF(0). A differential closure of A is a differential field B ⊇ A such that (i) B is differentially closed, and (ii) if B_{1} is any differentially closed field containing A, then B is embeddable into B_{1} over A.

In view of theorem 11.2.5 this is equivalent to saying that B is a prime model of the complete theory generated by DCF(0) ∪ (diagram of A).

2.

Theorem (Blum). Let A be a countable DF(0). Then A has a differential closure, denoted \overline{A}. Furthermore \overline{A} is unique up to isomorphism over A.

(We shall see in chapters 12 and 13 that the hypothesis of countability can be dropped.)

Proof. Let T be the complete countable theory generated by DCF(0) ∪ (diagram of A). By quantifier elimination, a complete n-type over T is essentially the same thing as an isomorphism type of an n-fold simple differential field extension A⟨b_{1}, …, b_{n}⟩ over A. Hence by theorem 11.1.12 it follows that S_{n}(T) is countable for all n. Hence by Vaught’s theorem 10.2.12 it follows that T has a prime model B = \overline{A}. Furthermore, the uniqueness theorem for prime models 10.2.8 implies that \overline{A} is unique up to isomorphism over A.

3.

Remark. By lemma 11.2.2 it follows that the differential closure \overline{A} is differentially algebraic over A. However, this fact alone does not suffice to characterize \overline{A} among all differentially closed fields B ⊇ A.

For example, let A⟨b⟩ be a simple extension in which b is a generic solution of y′ = 0. In other words, b is transcendental over A but b′ = 0. Put B = \overline{A⟨b⟩}. Then B is differentially closed, and differentially algebraic over A, but we claim that B is not isomorphic to \overline{A} over A. To see this, let p be the complete 1-type over T = DCF(0) ∪ (diagram of A) realized by b ∈ |B|. Clearly p is nonprincipal. Hence by theorem 10.2.7 it follows that p is not realized in \overline{A}.

4.

In order to prove our next theorem, we need the following algebraic result which we state without proof.

Lemma. Let A be a differential field of characteristic 0. Let S be an infinite set of algebraic differential equations in finitely many unknowns y_{1}, …, y_{n} with coefficients in |A|. Then there exists a finite subset S_{0} of S such that every solution of S_{0} (in some differential field extension of A) is a solution of S.

This is an immediate corollary of the Ritt basis theorem, i.e. theorem 11.4.4 below. For a proof, see Kaplansky, Introduction to Differential Algebra.

5.

Theorem (Harrington). Let A be a computable differential field of characteristic 0. Then \overline{A}, the differential closure of A, is computable.

Proof. \overline{A} is by definition the prime model of the complete theory T whose axioms are DCF(0)∪(diagram of A). Since A is computable, T is recursively axiomatizable, and hence decidable. But theorem 10.4.3 gives a necessary and sufficient condition for a complete decidable theory to have a decidable prime model. Thus, in order to show that \overline{A} is computable, it suffices to show that T verifies condition (b) of that theorem.

Given φ ∈ F_{n}(T) consistent with T, by quantifier elimination we may safely assume that φ(y_{1}, …, y_{n}) consists of finitely many algebraic diferential equations and inequations in n unknowns y_{1}, …, y_{n} with coefficients in |A|. Let {ψ_{k}(y_{1}, …, y_{n}) : k ∈ ω} be a recursive enumeration of all algebraic differential equations in n unknowns y_{1}, …, y_{n} with coefficients in |A|. Let p^{φ} be the n-type over T generated by {φ_{k} : k ∈ ω} where φ_{0} = φ, φ_{k+1} = φ_{k}∧ψ_{k} if this is consistent with T, φ_{k+1} = φ_{k} otherwise. The passage from φ to p^{φ} is clearly recursive, and by quantifier elimination, p^{φ} is complete.

It remains to show that p^{φ} is principal. Let S be the set of all algebraic differential equations in p^{φ}. By lemma 11.3.4 there exists a finite set S_{0} ⊆ S such that S_{0} is equivalent to S over T. Let ψ_{k_{1}}, …, ψ_{k_{m}} be the elements of S_{0}. Then clearly φ ∧ ψ_{k_{1}} ∧ ⋯ ∧ ψ_{k_{m}} is a generator of p^{φ}. This completes the proof.

6.

Corollary. The differential closure of the rational field ℚ is computable.

7.

Remark. An explicit presentation of the differential closure of ℚ is lacking. It is unknown whether the following decision problem has a positive solution:

Given a finite system of differential equations and inequations in n unknowns y_{1}, …, y_{n} with rational coefficients, to decide whether the principal n-type generated by the system is complete.

In the absence of such a decision procedure, the only known construction of the differential closure of ℚ is by means of Harrington’s priority construction in the proof of theorem 10.4.3.

11.4 Ritt’s Nullstellensatz

1.

Let A be a differential field of characteristic 0. Let R = A{y_{1}, …, y_{n}} be the ring of differential polynomials in n indeterminates y_{1}, …, y_{n} over A. Let \overline{A} be the differential closure of A.

2.

Theorem (Ritt’s Nullstellensatz). Let f, g_{1}, …, g_{m} ∈ R be such that every common zero of g_{1}, …, g_{m} in \overline{A} is a zero of f. Then there exist positive integers k and l such that

f^{k} = ∑_{i=1}^{m} ∑_{j=1}^{l} p_{ij}g_{i}^{(j)}

where p_{ij} ∈ R and g_{i}^{(j)} is the jth derivative of g_{i}.

Proof. Let I be the set of all f ∈ R for which the conclusion holds. Suppose f ∉ I. Then we have

(i) g, h ∈ I ⇒ g + h ∈ I

(ii) g ∈ I, h ∈ R ⇒ g · h ∈ I

(iii) 0 ∈ I, 1 ∉ I

(iv) g ∈ I ⇒ g′ ∈ I

i.e. I is a differential ideal. Here (i), (ii), (iii) are proved as in the proof of Hilbert’s Nullstellensatz 6.4.2. For (iv), suppose g ∈ I, say g^{k} ≡ 0 mod g_{1}, …, g_{m}. Differentiate and multiply by 1/k to get

g^{k−1}g′ ≡ 0 mod g_{1}, …, g_{m} .

This is the case i = 1 of the statement

g^{k−i}(g′)^{2i−1} ≡ 0 mod g_{1}, …, g_{m}

which we prove by induction on i, 1 ≤ i ≤ k. Differentiating and multiplying by g′ we get

(k − i)g^{k−i−1}(g′)^{2i+1} + \underbrace{(2i − 1)g^{k−i}(g′)^{2i−1}g′′}_{≡0} ≡ 0 .

Multiplying by 1/(k − i) we get

g^{k−i−1}(g′)^{2i+1} ≡ 0 mod g_{1}, …, g_{m}

so the induction step is proved. Finally for i = k we get

(g′)^{2k−1} ≡ 0 mod g_{1}, …, g_{m}

so (iv) is proved.

It is also clear that I is a radical differential ideal, i.e. I satisfies

(v) g^{k} ∈ I ⇒ g ∈ I ,

and f ∉ I. By Zorn’s lemma let J ⊇ I be a radical differential ideal such that f ∉ J and maximal with this property.

We claim that J is prime, i.e. g ∉ J, h ∉ J imply g · h ∉ J. Suppose not. Note that g · h ∈ J implies (g′ · h + g · h′) · g′ · h ∈ J whence (g′ · h)^{2} ∈ J, whence g′ · h ∈ J. Similarly g^{(i)} · h^{(j)} ∈ J for all i, j ≥ 0. If g ∉ J then the radical differential ideal generated by J and g must contain f, say

f^{k} = s + ∑_{i} p_{i}g^{(i)}

where s ∈ J, p_{i} ∈ R. Similarly if h ∉ J then

f^{l} = t + ∑_{j} q_{j}h^{(j)}

where t ∈ J, q_{j} ∈ R. Hence

f^{k+l} = \underbrace{s · f^{l} + t · f^{k} + ∑_{i} ∑_{j} p_{i}q_{j}g^{(i)}h^{(j)}}_{∈J}

contradicting the fact that J is radical and f ∉ J. This proves the claim.

Now let R_{1} = R/J = the quotient ring of R mod J. Clearly R_{1} is a differential domain. Let B be the field of quotients of R_{1}. Then B is a differential field extension of A. Furthermore, there exist b_{1}, …, b_{n} ∈ |B| (corresponding to y_{1}, …, y_{n} ∈ |R|) such that for all g ∈ R, g(b_{1}, …, b_{n}) = 0 if and only if g ∈ J. In particular f(b_{1}, …, b_{n}) ≠ 0 while g_{1}(b_{1}, …, b_{n}) = ⋯ = g_{m}(b_{1}, …, b_{n}) = 0. Hence by model completeness of DCF(0) we can find a_{1}, …, a_{n} ∈ |\overline{A}| such that f(a_{1}, …, a_{n}) ≠ 0 and g_{1}(a_{1}, …, a_{n}) = ⋯ = g_{m}(a_{1}, …, a_{n}) = 0. This completes the proof of the theorem.

3.

Remark. As in the case of Hilbert’s Nullstellensatz, we can deduce a version of Ritt’s Nullstellensatz with effective bounds. We leave to the reader the formulation and proof of this result. (Compare 6.4.3.)

4.

An interesting theorem related to Ritt’s Nullstellensatz is the following.

Theorem (Ritt’s basis theorem). Let R be as above and let I be a radical differential ideal in R. Then I has a finite basis, i.e. there exists a finite set g_{1}, …, g_{r} ∈ I such that I is the radical differential ideal generated by g_{1}, …, g_{r}, i.e. the set of all f ∈ R such that

f^{k} = ∑_{i=0}^{r} ∑_{j=0}^{l} p_{ij}g_{i}^{(j)}

for some k, l ∈ ω and p_{ij} ∈ R.

Proof. See Kaplansky, Introduction to Differential Algebra.

5.

Remark. The Ritt Basis Theorem tends to clarify several aspects of the proof of the Ritt Nullstellensatz. In the first place, the Ritt Basis Theorem shows that the use of Zorn’s lemma could have been eliminated. In the second place, since the radical differential ideal J has a finite basis g_{1}, …, g_{r}, it follows by quantifier elimination that the complete n-type of b_{1}, …, b_{n} over |A| is generated by the differential equations g_{1}(y_{1}, …, y_{n}) = ⋯ = g_{r}(y_{1}, …, y_{n}) = 0 and the single inequation f(y_{1}, …, y_{n}) ≠ 0. In particular this n-type is principal^{2} and hence already realized in \overline{A}. In other words, the differential field B = A⟨b_{1}, …, b_{n}⟩ is already embeddable into \overline{A}. (We could have used Hilbert’s Basis Theorem to make similar remarks about the proof of the Hilbert Nullstellensatz.)

2The algebraists express this fact by saying that J is constrained. See Wood, Israel J.

Math. vol. 25, p. 331.

124 CHAPTER 11. DIFF. CLOSED FIELDS OF CHAR. 0

Chapter 12

Totally transcendental theories

12.1 Stability

1.

12.2 Rank of an element type 12.3 Indiscernibles 12.4 Existence of saturated models

126 CHAPTER 12. TOTALLY TRANSCENDENTAL THEORIES

Prime models (uncountable case)

13.1 Strongly atomic models

1.

13.2 Normal sets 13.3 Uniqueness and characterization of prime

models