Fundamentals of Model Theory

William Weiss and Cherie D’Mello

Department of Mathematics University of Toronto

\begin{matrix}c \\ ◯ \end{matrix}1997 W.Weiss and C. D’Mello

Introduction

Model Theory is the part of mathematics which shows how to apply logic to the study of structures in pure mathematics. On the one hand it is the ultimate abstraction; on the other, it has immediate applications to every-day mathematics. The fundamental tenet of Model Theory is that mathematical truth, like all truth, is relative. A statement may be true or false, depending on how and where it is interpreted. This isn’t necessarily due to mathematics itself, but is a consequence of the language that we use to express mathematical ideas.

What at first seems like a deficiency in our language, can actually be shaped into a powerful tool for understanding mathematics. This book provides an introduction to Model Theory which can be used as a text for a reading course or a summer project at the senior undergraduate or graduate level. It is also a primer which will give someone a self contained overview of the subject, before diving into one of the more encyclopedic standard graduate texts.

Any reader who is familiar with the cardinality of a set and the algebraic closure of a field can proceed without worry. Many readers will have some acquaintance with elementary logic, but this is not absolutely required, since all necessary concepts from logic are reviewed in Chapter 0. Chapter 1 gives the motivating examples; it is short and we recommend that you peruse it first, before studying the more technical aspects of Chapter 0. Chapters 2 and 3 are selections of some of the most important techniques in Model Theory. The remaining chapters investigate the relationship between Model Theory and the algebra of the real and complex numbers. Thirty exercises develop familiarity with the definitions and consolidate understanding of the main proof techniques.

Throughout the book we present applications which cannot easily be found elsewhere in such detail. Some are chosen for their value in other areas of mathematics: Ramsey’s Theorem, the Tarski-Seidenberg Theorem. Some are chosen for their immediate appeal to every mathematician: existence of infinitesimals for calculus, graph colouring on the plane. And some, like Hilbert’s Seventeenth Problem, are chosen because of how amazing it is that logic can play an important role in the solution of a problem from high school algebra. In each case, the derivation is shorter than any which tries to avoid logic. More importantly, the methods of Model Theory display clearly the structure of the main ideas of the proofs, showing how theorems of logic combine with theorems from other areas of mathematics to produce stunning results.

The theorems here are all are more than thirty years old and due in great part to the cofounders of the subject, Abraham Robinson and Alfred Tarski. However, we have not attempted to give a history. When we attach a name to a theorem, it is simply because that is what mathematical logicians popularly call it.

The bibliography contains a number of texts that were helpful in the preparation of this manuscript. They could serve as avenues of further study and in addition, they contain many other references and historical notes. The more recent titles were added to show the reader where the subject is moving today. All are worth a look.

This book began life as notes for William Weiss’s graduate course at the University of Toronto. The notes were revised and expanded by Cherie D’Mello and William Weiss, based upon suggestions from several graduate students. The electronic version of this book may be downloaded and further modified by anyone for the purpose of learning, provided this paragraph is included in its entirety and so long as no part of this book is sold for profit.

Contents

Chapter 0. Models, Truth and Satisfaction 4 Formulas, Sentences, Theories and Axioms 4 Prenex Normal Form 9

Chapter 1. Notation and Examples 11

Chapter 2. Compactness and Elementary Submodels 14 Compactness Theorem 14 Isomorphisms, elementary equivalence and complete theories 15 Elementary Chain Theorem 16 Löwenheim-Skolem Theorems 19 The Łoś-Vaught Test 21 Every complex one-to-one polynomial map is onto 23

Chapter 3. Diagrams and Embeddings 24 Diagram Lemmas 24 Every planar graph can be four coloured 25 Ramsey’s Theorem 26 The Leibniz Principle and infinitesimals 26 Robinson Consistency Theorem 27 Craig Interpolation Theorem 31

Chapter 4. Model Completeness 32 Robinson’s Theorem on existentially complete theories 32 Lindström’s Test 35 Hilbert’s Nullstellensatz 38

Chapter 5. The Seventeenth Problem 39 Positive definite rational functions are the sums of squares 39

Chapter 6. Submodel Completeness 45 Elimination of quantifiers 45 The Tarski-Seidenberg Theorem 49

Chapter 7. Model Completions 50 Almost universal theories 52 Saturated models 54 Blum’s Test 55

Bibliography 60

Index 61

CHAPTER 0 Models, Truth and Satisfaction

We will use the following symbols:

• logical symbols:

– the connectives ∧ ,∨ , ¬ , → , ↔ called “and”, “or”, “not”, “implies” and “iff” respectively

– the quantifiers ∀ , ∃ called “for all” and “there exists”

– an infinite collection of variables indexed by the natural numbers ℕ v_{0} ,v_{1} , v_{2} , …

– the two parentheses ), (

– the symbol = which is the usual “equal sign”

• constant symbols : often denoted by the letter c with subscripts

• function symbols : often denoted by the letter F with subscripts; each function symbol is an m-placed function symbol for some natural number m ≥ 1

• relation symbols : often denoted by the letter R with subscripts; each relational symbol is an n-placed relation symbol for some natural number n ≥ 1.

We now define terms and formulas.

Definition 1. A term is defined as follows:

(1) a variable is a term

(2) a constant symbol is a term

(3) if F is an m-placed function symbol and t_{1}, …, t_{m} are terms, then F (t_{1} … t_{m}) is a term.

(4) a string of symbols is a term if and only if it can be shown to be a term by a finite number of applications of (1), (2) and (3).

Remark. This is a recursive definition.

Definition 2. A formula is defined as follows :

(1) if t_{1} and t_{2} are terms, then (t_{1} = t_{2}) is a formula.

(2) if R is an n-placed relation symbol and t_{1}, …, t_{n} are terms, then (R(t_{1} … t_{n})) is a formula.

(3) if φ is a formula, then (¬φ) is a formula

(4) if φ and ψ are formulas then so are (φ∧ψ), (φ∨ψ), (φ → ψ) and (φ ↔ ψ)

(5) if v_{i} is a variable and φ is a formula, then (∃v_{i})φ and (∀v_{i})φ are formulas (6) a string of symbols is a formula if and only if it can be shown to be a

formula by a finite number of applications of (1), (2), (3), (4) and (5).

Remark. This is another recursive definition. ¬φ is called the negation of φ; φ ∧ ψ is called the conjunction of φ and ψ; and φ ∨ ψ is called the disjunction of φ and ψ.

Definition 3. A subformula of a formula φ is defined as follows:

(1) φ is a subformula of φ

(2) if (¬ψ) is a subformula of φ then so is ψ

(3) if any one of (θ ∧ ψ), (θ ∨ ψ), (θ → ψ) or (θ ↔ ψ) is a subformula of φ , then so are both θ and ψ

(4) if either (∃v_{i})ψ or (∀v_{i})ψ is a subformula of φ for some natural number i , then ψ is also a subformula of φ

(5) A string of symbols is a subformula of φ, if and only if it can be shown to be such by a finite number of applications of (1), (2), (3) and (4).

Definition 4. A variable v_{i} is said to occur bound in a formula φ iff for some subformula ψ of φ either (∃v_{i})ψ or (∀v_{i})ψ is a subformula of φ. In this case each occurence of v_{i} in (∃v_{i})ψ or (∀v_{i})ψ is said to be a bound occurence of v_{i}. Other occurences of v_{i} which do not occur bound in φ are said to be free.

Example 1.

F (v_{3}) is a term.
(((∃v_{3})(v_{0} = v_{3}) ∨ (∃v_{2})(v_{1} = v_{2})) ∧ (∀v_{0})(v_{0} = v_{0}))

is a formula. In this formula the variables v_{2} and v_{3} occurs bound, the variable v_{1} occurs free, but the variable v_{0} occurs both bound and free.

Exercise 1. Using the previous definitions as a guide, define the substitution of a term t for a variable v_{i} in a formula φ. In particular, demonstrate how to substitute the term for the variable v_{0} in the formula of the example above.

Definition 5. A language L is a set consisting of all the logical symbols with perhaps some constant, function and/or relational symbols included. It is understood that the formulas of L are made up from this set in the manner prescribed above. Note that all the formulas of L are uniquely described by listing only the constant, function and relation symbols of L.

We use t(v_{0}, …, v_{k}) to denote a term t all of whose variables occur among v_{0}, …, v_{k}.

We use φ(v_{0}, …, v_{k}) to denote a formula φ all of whose free variables occur among v_{0}, …, v_{k}.

Example 2. These would be formulas of any language :

• For any variable v_{i}: (v_{i} = v_{i})

• for any term t(v_{0}, …, v_{k}) and other terms t_{1} and t_{2}:

((t_{1} = t_{2}) → (t(v_{0}, …, v_{i−1}, t_{1}, v_{i+1}, …, v_{k}) = t(v_{0}, …, v_{i−1}, t_{2}, v_{i+1}, …, v_{k})))

• for any formula φ(v_{0}, …, v_{k}) and terms t_{1} and t_{2}:

((t_{1} = t_{2}) → (φ(v_{0}, …, v_{i−1}, t_{1}, v_{i+1}, …, v_{k}) ↔ φ(v_{0}, …, v_{i−1}, t_{2}, v_{i+1}, …, v_{k})))

Note the simple way we denote the substitution of t_{1} for v_{i}.

Definition 6. A model (or structure) 𝔄 for a language L is an ordered pair ⟨A, I⟩ where A is a nonempty set and I is an interpretation function with domain the set of all constant, function and relation symbols of L such that:

(1) if c is a constant symbol, then I(c) ∈ A; I(c) is called a constant

(2) if F is an m-placed function symbol, then I(F) is an m-placed function on A (3) if R is an n-placed relation symbol, then I(R) is an n-placed relation on

A. A is called the universe of the model 𝔄. We generally denote models with

Gothic letters and their universes with the corresponding Latin letters in boldface. One set may be involved as a universe with many different interpretation functions of the language L. The model is both the universe and the interpretation function.

Remark. The importance of Model Theory lies in the observation that mathematical objects can be cast as models for a language. For instance, the real numbers with the usual ordering < < < and the usual arithmetic operations, addition + + + and multiplication ··· along with the special numbers 0 and 1 can be described as a model. Let L contain one two-placed (i.e. binary) relation symbol R_{0}, two two-placed function symbols F_{1} and F_{2} and two constant symbols c_{0} and c_{1}. We build a model by letting the universe A be the set of real numbers. The interpretation function I will map R_{0} to < < <, i.e. R_{0} will be interpreted as < < <. Similarly, I(F_{1}) will be + + +, I(F_{2}) will be ···, I(c_{0}) will be 0 and I(c_{1}) will be 1. So ⟨A, I⟩ is an example of a model for the language described by {R_{0}, F_{1}, F_{2}, c_{0}, c_{1}}.

We now wish to show how to use formulas to express mathematical statements about elements of a model. We first need to see how to interpret a term in a model.

Definition 7. The value t[x_{0}, …, x_{q}] of a term t(v_{0}, …, v_{q}) at x_{0}, …, x_{q} in the universe A of the model 𝔄 is defined as follows:

(1) if t is v_{i} then t[x_{0}, ⋯, x_{q}] is x_{i},

(2) if t is the constant symbol c, then t[x_{0}, …, x_{q}] is I(c), the interpretation of c in A,

(3) if t is F (t_{1} … t_{m}) where F is an m-placed function symbol and t_{1}, …, t_{m} are terms, then t[x_{0}, …, x_{q}] is G(t_{1}[x_{0}, …, x_{q}], …, t_{m}[x_{0}, …, x_{q}]) where G is the m-placed function I(F), the interpretation of F in A.

Definition 8. Suppose 𝔄 is a model for a language L. The sequence x_{0}, …, x_{q} of elements of A satisfies the formula φ(v_{0}, …, v_{q}) all of whose free and bound variables are among v_{0}, …, v_{q}, in the model 𝔄, written 𝔄 ⊧ φ[x_{0}, …, x_{q}] provided we have:

(1) if φ(v_{0}, …, v_{q}) is the formula (t_{1} = t_{2}), then

𝔄 ⊧ (t_{1} = t_{2})[x_{0}, …, x_{q}] means that t_{1}[x_{0}, …, x_{q}] equals t_{2}[x_{0}, …, x_{q}],

(2) if φ(v_{0}, …, v_{q}) is the formula (R(t_{1} … t_{n})) where R is an n-placed relation symbol, then

𝔄 ⊧ (R(t_{1} … t_{n}))[x_{0}, …, x_{q}] means S(t_{1}[x_{0}, …, x_{q}], …, t_{n}[x_{0}, …, x_{q}])

where S is the n-placed relation I(R), the interpretation of R in A,

(3) if φ is (¬θ), then

𝔄 ⊧ φ[x_{0}, …, x_{q}] means not 𝔄 ⊧ θ[x_{0}, …, x_{q}],

(4) if φ is (θ ∧ ψ), then

𝔄 ⊧ φ[x_{0}, …, x_{q}] means both 𝔄 ⊧ θ[x_{0}, …, x_{q}] and 𝔄 ⊧ ψ[x_{0}, … x_{q}],

(5) if φ is (θ ∨ ψ) then

𝔄 ⊧ φ[x_{0}, …, x_{q}] means either 𝔄 ⊧ θ[x_{0}, …, x_{q}] or 𝔄 ⊧ ψ[x_{0}, …, x_{q}], (6) if φ is (θ → ψ) then

𝔄 ⊧ φ[x_{0}, …, x_{q}] means that 𝔄 ⊧ θ[x_{0}, …, x_{q}] implies 𝔄 ⊧ ψ[x_{0}, …, x_{q}],

(7) if φ is (θ ↔ ψ) then

𝔄 ⊧ φ[x_{0}, …, x_{q}] means that 𝔄 ⊧ θ[x_{0}, …, x_{q}] iff 𝔄 ⊧ ψ[x_{0}, …, x_{q}],

(8) if φ is ∀v_{i}θ, then

𝔄 ⊧ φ[x_{0}, …, x_{q}] means for every x ∈ A, 𝔄 ⊧ θ[x_{0}, …, x_{i−1}, x, x_{i+1}, …, x_{q}],

(9) if φ is ∃v_{i}θ, then

𝔄 ⊧ φ[x_{0}, …, x_{q}] means for some x ∈ A, 𝔄 ⊧ θ[x_{0}, …, x_{i−1}, x, x_{i+1}, …, x_{q}].

Exercise 2. Each of the formulas of Example 2 is satisfied in any model 𝔄 for any language L by any (long enough) sequence x_{0}, x_{1}, …, x_{q} of A. This is where you test your solution to Exercise 1.

We now prove two lemmas which show that the preceding concepts are welldefined. In the first one, we see that the value of a term only depends upon the values of the variables which actually occur in the term. In this lemma the equal sign = is used, not as a logical symbol in the formal sense, but in its usual sense to denote equality of mathematical objects — in this case, the values of terms, which are elements of the universe of a model.

Lemma 1. Let 𝔄 be a model for L and let t(v_{0}, …, v_{p}) be a term of L. Let x_{0}, …, x_{q} and y_{0}, …, y_{r} be sequences from A such that p ≤ q and p ≤ r, and let x_{i} = y_{i} whenever v_{i} actually occurs in t(v_{0}, …, v_{p}). Then

t[x_{0}, …, x_{q}] = t[y_{0}, …, y_{r}]

.

Proof. We use induction on the complexity of the term t.

(1) If t is v_{i} then x_{i} = y_{i} and so we have

t[x_{0}, …, x_{q}] = x_{i} = y_{i} = t[y_{0}, …, y_{r}] since p ≤ q and p ≤ r.

(2) If t is the constant symbol c, then

t[x_{0}, …, x_{q}] = I(c) = t[y_{0}, …, y_{r}]

where I(c) is the interpretation of c in A.

(3) If t is F (t_{1} … t_{m}) where F is an m-placed function symbol, t_{1}, …, t_{m} are terms and I(F) = G, then t[x_{0}, …, x_{q}] = G(t_{1}[x_{0}, …, x_{q}], …, t_{m}[x_{0}, …, x_{q}]) and t[y_{0}, …, y_{r}] = G(t_{1}[y_{0}, …, y_{r}], …, t_{m}[y_{0}, …, y_{r}]). By the induction hypothesis we have that t_{i}[x_{0}, …, x_{q}] = t_{i}[y_{0}, …, y_{r}] for 1 ≤ i ≤ m since t_{1}, …, t_{m} have all their variables among {v_{0}, …, v_{p}}. So we have t[x_{0}, …, x_{q}] = t[y_{0}, …, y_{r}].

□

In the next lemma the equal sign = is used in both senses — as a formal logical symbol in the formal language L and also to denote the usual equality of mathematical objects. This is common practice where the context allows the reader to distinguish the two usages of the same symbol. The lemma confirms that satisfaction of a formula depends only upon the values of its free variables.

Lemma 2. Let 𝔄 be a model for L and φ a formula of L, all of whose free and bound variables occur among v_{0}, …, v_{p}. Let x_{0}, …, x_{q} and y_{0}, …, y_{r} (q, r ≥ p) be two sequences such that x_{i} and y_{i} are equal for all i such that v_{i} occurs free in φ. Then

𝔄 ⊧ φ[x_{0}, …, x_{q}] iff 𝔄 ⊧ φ[y_{0}, …, y_{r}]

Proof. Let 𝔄 and L be as above. We prove the lemma by induction on the complexity of φ.

(1) If φ(v_{0}, …, v_{p}) is the formula (t_{1} = t_{2}), then we use Lemma 1 to get:

𝔄 ⊧ (t_{1} = t_{2})[x_{0}, …, x_{q}] iff t_{1}[x_{0}, …, x_{q}] = t_{2}[x_{0}, …, x_{q}]
iff t_{1}[y_{0}, …, y_{r}] = t_{2}[y_{0}, …, y_{r}]
iff 𝔄 ⊧ (t_{1} = t_{2})[y_{0}, …, y_{r}].

(2) If φ(v_{0}, …, v_{p}) is the formula (R(t_{1} … t_{n})) where R is an n-placed relation symbol with interpretation S, then again by Lemma 1, we get:

𝔄 ⊧ (R(t_{1} … t_{n}))[x_{0}, …, x_{q}] iff S(t_{1}[x_{0}, …, x_{q}], …, t_{n}[x_{0}, …, x_{q}])
iff S(t_{1}[y_{0}, …, y_{r}], …, t_{n}[y_{0}, …, y_{r}])
iff 𝔄 ⊧ R(t_{1} … t_{n})[y_{0}, …, y_{r}].

(3) If φ is (¬θ), the inductive hypothesis gives that the lemma is true for θ.

So,

𝔄 ⊧ φ[x_{0}, …, x_{q}] iff not 𝔄 ⊧ θ[x_{0}, …, x_{q}]
iff not 𝔄 ⊧ θ[y_{0}, …, y_{r}]
iff 𝔄 ⊧ φ[y_{0}, …, y_{r}].

(4) If φ is (θ ∧ ψ), then using the inductive hypothesis on θ and ψ we get

𝔄 ⊧ φ[x_{0}, …, x_{q}] iff both 𝔄 ⊧ θ[x_{0}, …, x_{q}] and 𝔄 ⊧ ψ[x_{0}, … x_{q}]
iff both 𝔄 ⊧ θ[y_{0}, …, y_{r}] and 𝔄 ⊧ ψ[y_{0}, … y_{r}]
iff 𝔄 ⊧ φ[y_{0}, …, y_{r}].

(5) If φ is (θ ∨ ψ) then

𝔄 ⊧ φ[x_{0}, …, x_{q}] iff either 𝔄 ⊧ θ[x_{0}, …, x_{q}] or 𝔄 ⊧ ψ[x_{0}, …, x_{q}]
iff either 𝔄 ⊧ θ[y_{0}, …, y_{r}] or 𝔄 ⊧ ψ[y_{0}, …, y_{r}]
iff 𝔄 ⊧ φ[y_{0}, …, y_{r}].

(6) If φ is (θ → ψ) then

𝔄 ⊧ φ[x_{0}, …, x_{q}] iff 𝔄 ⊧ θ[x_{0}, …, x_{q}] implies 𝔄 ⊧ ψ[x_{0}, …, x_{q}]
iff 𝔄 ⊧ θ[y_{0}, …, y_{r}] implies 𝔄 ⊧ ψ[y_{0}, …, y_{r}]
iff 𝔄 ⊧ φ[y_{0}, …, y_{r}].

(7) If φ is (θ ↔ ψ) then

𝔄 ⊧ φ[x_{0}, …, x_{q}] iff we have 𝔄 ⊧ θ[x_{0}, …, x_{q}] iff 𝔄 ⊧ ψ[x_{0}, …, x_{q}]
iff we have 𝔄 ⊧ θ[y_{0}, …, y_{r}] iff 𝔄 ⊧ ψ[y_{0}, …, y_{r}]
iff 𝔄 ⊧ φ[y_{0}, …, y_{r}].

(8) If φ is (∀v_{i})θ, then

𝔄 ⊧ φ[x_{0}, …, x_{q}] iff for every z ∈ A, 𝔄 ⊧ θ[x_{0}, …, x_{i−1}, z, x_{i+1}, …, x_{q}]

iff for every z ∈ A, 𝔄 ⊧ θ[y_{0}, …, y_{i−1}, z, y_{i+1}, …, y_{r}]

iff 𝔄 ⊧ φ[y_{0}, …, y_{r}].

The inductive hypothesis uses the sequences x_{0}, …, x_{i−1}, z, x_{i+1}, …, x_{q}

and y_{0}, …, y_{i−1}, z, y_{i+1}, …, y_{r} with the formula θ.

(9) If φ is (∃v_{i})θ, then

𝔄 ⊧ φ[x_{0}, …, x_{q}] iff for some z ∈ A, 𝔄 ⊧ θ[x_{0}, …, x_{i−1}, z, x_{i+1}, …, x_{q}]

iff for some z ∈ A, 𝔄 ⊧ θ[y_{0}, …, y_{i−1}, z, y_{i+1}, …, y_{r}]

iff 𝔄 ⊧ φ[y_{0}, …, y_{r}].

The inductive hypothesis uses the sequences x_{0}, …, x_{i−1}, z, x_{i+1}, …, x_{q}

and y_{0}, …, y_{i−1}, z, y_{i+1}, …, y_{r} with the formula θ.
□

Definition 9. A sentence is a formula with no free variables.

If φ is a sentence, we can write 𝔄 ⊧ φ without any mention of a sequence from A since by the previous lemma, it doesn’t matter which sequence from A we use. In this case we say:

• 𝔄 satisfies φ

• or 𝔄 is a model of φ

• or φ holds in 𝔄

• or φ is true in 𝔄 If φ is a sentence of L, we write ⊧ φ to mean that 𝔄 ⊧ φ for every model 𝔄

for L. Intuitively then, ⊧ φ means that φ is true under any relevant interpretation (model for L). Alternatively, no relevant example (model for L) is a counterexample to φ — so φ is true.

Lemma 3. Let φ(v_{0}, …, v_{q}) be a formula of the language L. There is another formula φ′(v_{0}, …, v_{q}) of L such that

(1) φ′ has exactly the same free and bound occurences of variables as φ.

(2) φ′ can possibly contain ¬, ∧ and ∃ but no other connective or quantifier.

(3) ⊧ (∀v_{0}) … (∀v_{q})(φ ↔ φ′)

Exercise 3. Prove the above lemma by induction on the complexity of φ. As a reward, note that this lemma can be used to shorten future proofs by induction on complexity of formulas.

Definition 10. A formula φ is said to be in prenex normal form whenever (1) there are no quantifiers occurring in φ, or

(2) φ is (∃v_{i})ψ where ψ is in prenex normal form and v_{i} does not occur bound in ψ, or

(3) φ is (∀v_{i})ψ where ψ is in prenex normal form and v_{i} does not occur bound in ψ.

Remark. If φ is in prenex normal form, then no variable occurring in φ occurs both free and bound and no bound variable occurring in φ is bound by more than one quantifier. In the written order, all of the quantifiers precede all of the connectives.

Lemma 4. Let φ(v_{0}, …, v_{p}) be any formula of a language L. There is a formula φ^{∗} of L which has the following properties:

(1) φ^{∗} is in prenex normal form

(2) φ and φ^{∗} have the same free occurences of variables, and

(3) ⊧ (∀v_{0}) … (∀v_{p})(φ ↔ φ^{∗})

Exercise 4. Prove this lemma by induction on the complexity of φ.

There is a notion of rank on prenex formulas — the number of alternations of quantifiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantifiers. For example:

(∀x)(∀y)(2xy ≤ x^{2} + y^{2}).

However, the ϵ − δ definition of a limit of a function has prenex rank 2 and is much more difficult for students to comprehend at first sight:

(∀ϵ)(∃δ)(∀x)((0 < ϵ ∧ 0 < |x − a| < δ) → |F (x) − L| < ϵ).

A formula of prenex rank 4 would make any mathematician look twice.

CHAPTER 1 Notation and Examples

Although the formal notation for formulas is precise, it can become cumbersome and difficult to read. Confident that the reader would be able, if necessary, to put formulas into their formal form, we will relax our formal behaviour. In particular, we will write formulas any way we want using appropriate symbols for variables, constant symbols, function and relation symbols. We will omit parentheses or add them for clarity. We will use binary function and relation symbols between the arguments rather than in front as is the usual case for “plus”, “times” and “less than”.

Whenever a language L has only finitely many relation, function and constant symbols we often write, for example:

L = {<, R_{0}, +, F_{1}, c_{0}, c_{1}}

omitting explicit mention of the logical symbols (including the infinitely many variables) which are always in L. Correspondingly we may denote a model 𝔄 for L as:

𝔄 = ⟨A,< < <, S_{0},+ + +, G_{1}, a_{0}, a_{1}⟩

where the interpretations of the symbols in the language L are given by I(<) = < < <, I(R_{0}) = S_{0}, I(+) = + + + , I(F_{1}) = G_{1}, I(c_{0}) = a_{0} and I(c_{1}) = a_{1}.

Example 3. ℜ = ⟨ℝ,< < <,+ + +, ·, 0, 1⟩ and 𝔔 = ⟨ℚ,< < <,+ + +, ·, 0, 1⟩, where ℝ is the reals, ℚ the rationals , are models for the language L = {<, +, ·, 0, 1}. Here < is a binary relation symbol, + and · are binary function symbols, 0 and 1 are constant symbols whereas < < <, + + +, ·, 0, 1 are the well known relations, arithmetic functions and constants.

Similarly, ℭ = ⟨ℂ,+ + +, ·, 0, 1⟩, where ℂ is the complex numbers, is a model for the language L = {+, ·, 0, 1}. Note the exceptions to the boldface convention for these popular sets.

Example 4. Here L = {<, +, ·, 0, 1}, where < is a binary relation symbol, + and · are binary function symbols and 0 and 1 are constant symbols. The following formulas are sentences.

(1) (∀x)¬(x < x)

(2) (∀x)(∀y)¬(x < y ∧ y < x)
(3) (∀x)(∀y)(∀z)(x < y ∧ y < z → x < z)
(4) (∀x)(∀y)(x < y ∨ y < x ∨ x = y)
(5) (∀x)(∀y)(x < y → (∃z)(x < z ∧ z < y))
(6) (∀x)(∃y)(x < y)
(7) (∀x)(∃y)(y < x)
(8) (∀x)(∀y)(∀z)(x + (y + z) = (x + y) + z)
(9) (∀x)(x + 0 = x)

(10) (∀x)(∃y)(x + y = 0)

(11) (∀x)(∀y)(x + y = y + x)

(12) (∀x)(∀y)(∀z)(x · (y · z) = (x · y) · z)

(13) (∀x)(x · 1 = x)

(14) (∀x)(x = 0 ∨ (∃y)(y · x = 1)

(15) (∀x)(∀y)(x · y = y · x)

(16) (∀x)(∀y)(∀z)(x · (y + z) = (x · y) + (y · z))

(17) 0 ≠ 1

(18) (∀x)(∀y)(∀z)(x < y → x + z < y + z)

(19) (∀x)(∀y)(∀z)(x < y ∧ 0 < z → x · z < y · z)

(20) for each n ≥ 1 we have the formula

(∀x_{0})(∀x_{1}) ⋯ (∀x_{n})(∃y)(x_{n} · y^{n} + x_{n−1} · y^{n−1} + ⋯ + x_{1} · y + x_{0} = 0 ∨ x_{n} = 0)

where, as usual, y^{k} abbreviates \overbrace{y · y · · · · · y}^{k}

The latter formulas express that each polynomial of degree n has a root. The following formulas express the intermediate value property for polynomials of degree n: if the polynomial changes sign from w to z, then it is zero at some y between w and z.

(21) for each n ≥ 1 we have

(∀x_{0}) … (∀x_{n})(∀w)(∀z)[(x_{n} · w^{n} + x_{n−1} · w^{n−1} + ⋯ + x_{1} · w + x_{0})·

(x_{n} · z^{n} + x_{n−1} · z^{n−1} + ⋯ + x_{1} · z + x_{0}) < 0
→ (∃y)(((w < y ∧ y < z) ∨ (z < y ∧ y < w))

∧ (x_{n} · y^{n} + x_{n−1} · y^{n−1} + ⋯ + x_{1} · y + x_{0} = 0))]

The most fundamental concept is that of a sentence σ being true when interpreted in a model 𝔄. We write this as 𝔄 ⊧ σ, and we extend this concept in the following definitions.

Definition 11. If Σ is a set of sentences, 𝔄 is said to be a model of Σ, written 𝔄 ⊧ Σ, whenever 𝔄 ⊧ σ for each σ ∈ Σ. Σ is said to be satisfiable iff there is some 𝔄 such that 𝔄 ⊧ Σ.

Definition 12. A theory T is a set of sentences. If T is a theory and σ is a sentence, we write T ⊧ σ whenever we have that for all 𝔄 if 𝔄 ⊧ T then 𝔄 ⊧ σ. We say that σ is a consequence of T . A theory is said to be closed whenever it contains all of its consequences.

Definition 13. If 𝔄 is a model for the language L, the theory of 𝔄, denoted by Th𝔄, is defined to be the set of all sentences of L which are true in 𝔄,

{σ of L : 𝔄 ⊧ σ}.

This is one way that a theory can arise. Another way is through axioms.

Definition 14. Σ ⊆ T is said to be a set of axioms for T whenever Σ ⊧ σ for every σ in T ; in this case we write Σ ⊧ T .

Remark. We will generally assume our theories are closed and we will often describe theories by specifying a set of axioms Σ. The theory will then be all consequences σ of Σ.

Example 5. We will consider the following theories and their axioms:

(1) The theory of Linear Orderings (LOR) which has as axioms sentences 1-4 from Example 4.

(2) The theory of Dense Linear Orders (DLO) which has as axioms all the axioms of LOR, and sentence 5, 6 and 7 of Example 4.

(3) The theory of Fields (FEI) which has as axioms sentences 8-17 from Example 4.

(4) The theory of Ordered Fields (ORF) which has as axioms all the axioms of FEI, LOR and sentences 18 and 19 from Example 4.

(5) The theory of Algebraically Closed Fields (ACF) which has as axioms all the axioms of FEI and all sentences from 20 of Example 4, i.e. infinitely many sentences, one for each n ≥ 1.

(6) The theory of Real Closed Ordered Fields (RCF) which has as axioms all the axioms of ORF, and all sentences from 21 of Example 4, i.e. infinitely many sentences, one for each n ≥ 1.

Exercise 5. Show that :

(1) 𝔔 ⊧ DLO

(2) ℜ ⊧ RCF using the Intermediate Value theorem

(3) ℭ ⊧ ACF using the Fundamental Theorem of Algebra where 𝔔, ℜ and ℭ are as in Example 3.

Remark. The theory of Real Closed Ordered Fields is sometimes axiomatized differently. All the axioms of ORF are retained, but the sentences from 21 of Example 4, which amount to an Intermediate Value Property, are replaced by the sentences from 20 for odd n and the sentence

(∀x)(0 < x → (∃y)y^{2} = x)

which states that every positive element has a square root. A significant amount of algebra would then be used to verify the Intermediate Value Property from these axioms.

CHAPTER 2 Compactness and Elementary Submodels

Theorem 1. The Compactness Theorem (Malcev) A set of sentences is satisfiable iff every finite subset is satisfiable.

Proof. There are several proofs. We only point out here that it is an easy consequence of the following, a theorem which appears in all elementary logic texts:

Proposition. The Completeness Theorem (Gödel, Malcev) A set of sentences is consistent iff it is satisfiable.

Although we do not here formally define “consistent”, it does mean what you think it does. In particular, a set of sentences is consistent if and only if each finite subset is consistent.

□

Remark. The Compactness Theorem is the only one for which we do not give a complete proof. If the reader has not previously seen the Completeness Theorem, there are other proofs of the Compactness Theorem which may be more easily absorbed: set theoretic (using ultraproducts), topological (using compact spaces, hence the name) or Boolean algebraic. However these topics are too far afield to enter into the proofs here. We will use the Compactness Theorem as a starting point — in fact, all that follows can be seen as its corollaries.

Exercise 6. Suppose T is a theory for the language L and σ is a sentence of L such that T ⊧ σ. Prove that there is some finite T′ ⊆ T such that T′ ⊧ σ. Recall that T ⊧ σ iff T ∪ {¬σ} is not satisfiable.

Definition 15. If L, and L′ are two languages such that L ⊆ L′ we say that L′ is an expansion of L and L is a reduction of L′. Of course when we say that L ⊆ L′ we also mean that the constant, function and relation symbols of L remain (respectively) constant, function and relation symbols of L′.

Definition 16. Given a model 𝔄 for the language L, we can expand it to a model 𝔄′ of L′ by giving appropriate interpretations to the symbols in L′ \ L. We say that 𝔄′ is an expansion of 𝔄 to L′ and that 𝔄 is a reduct of 𝔄′ to L. We also use the notation 𝔄′|L for the reduct of 𝔄′ to L.

Theorem 2. If a theory T has arbitrarily large finite models, then it has an infinite model.

Proof. Consider new constant symbols c_{i} for i ∈ ℕ, the usual natural numbers, and expand from L, the language of T , to L′ = L ∪ {c_{i} : i ∈ ℕ}.

Let

Σ = T ∪ {¬c_{i} = c_{j} : i ≠ j, i, j ∈ ℕ}.

We first show that every finite subset of Σ has a model by interpreting the finitely many relevant constant symbols as different elements in an expansion of some finite model of T . Then we use compactness to get a model 𝔄′ of Σ.

The model that we require is for the language L, so we take 𝔄 to be the reduct of 𝔄′ to L.

□

Definition 17. Two models 𝔄 and 𝔄′ for L are said to be isomorphic whenever there is a bijection f : A → A′ such that

(1) for each n-placed relation symbol R of L and corresponding interpretations S of 𝔄 and S′ of 𝔄′ we have

S(x_{1}, …, x_{n}) iff S′(f(x_{1}), …, f(x_{n})) for all x_{1}, …, x_{n} in A

(2) for each n-placed function symbol F of L and corresponding interpretations G of 𝔄 and G′ of 𝔄′ we have

f(G(x_{1}, …, x_{n})) = G′(f(x_{1}), …, f(x_{n})) for all x_{1}, …, x_{n} in A

(3) for each constant symbol c of L and corresponding constant elements a of

𝔄 and a′ of 𝔄′ we have f(a) = a′.

We write 𝔄 ≅ 𝔄′. This is an equivalence relation.

Example 6. Number theory is Th⟨ℕ,+ + +,···,< < <,000,111⟩, the set of all sentences of L = {+, ·, <, 0, 1} which are true in ⟨ℕ,+ + +,···,< < <,000,111⟩, the standard model which we all learned in school. Any model not isomorphic to the standard model of number theory is said to be a non-standard model of number theory.

Theorem 3. (T. Skolem) There exist non-standard models of number theory.

Proof. Add a new constant symbol c to L. Consider

Th⟨ℕ, +, ·, <, 0, 1⟩ ∪ \{\overbrace{1 + 1 + ⋯ + 1}^{n} < c : n ∈ ℕ\}

and use the Compactness Theorem. The interpretation of the constant symbol c will not be a natural number. □

Definition 18. Two models 𝔄 and 𝔄′ for L are said to be elementarily equivalent whenever we have that for each sentence σ of L

𝔄 ⊧ σ iff 𝔄′ ⊧ σ

We write 𝔄 ≡ 𝔄′. This is another equivalence relation.

Exercise 7. Suppose f : 𝔄 → 𝔄′ is an isomorphism and φ is a formula such that 𝔄 ⊧ φ[a_{0}, …, a_{k}] for some a_{0}, …, a_{k} from A; prove 𝔄′ ⊧ φ[f(a_{0}), …, f(a_{k})].

Use this to show that 𝔄 ≅ 𝔄′ implies 𝔄 ≡ 𝔄′.

Definition 19. A model 𝔄′ is called a submodel of 𝔄 iff ϕ ≠ A′ ⊆ A and (1) each n-placed relation S′ of 𝔄′ is the restriction to A′ of the corresponding

relation S of 𝔄, i. e. S′ = S ∩ (A′)^{n}

(2) each m-placed function G′ of 𝔄′ is the restriction to A′ of the corresponding function G of 𝔄, i. e. G′ = G ↾ (A′)^{m}

(3) each constant of 𝔄′ is the corresponding constant of 𝔄.

We write 𝔄′ ⊆ 𝔄.

Definition 20. Let 𝔄 and 𝔅 be two models for L. We say 𝔄 is an elementary submodel of 𝔅 and 𝔅 is an elementary extension of 𝔄 and we write 𝔄 ≺ 𝔅 whenever

(1) A ⊆ B and

(2) for all formulas φ(v_{0}, …, v_{k}) of L and all a_{0}, …, a_{k} ∈ A

𝔄 ⊧ φ[a_{0}, …, a_{k}] iff 𝔅 ⊧ φ[a_{0}, …, a_{k}].

Exercise 8. Prove that if 𝔄 ≺ 𝔅 then 𝔄 ⊆ 𝔅 and 𝔄 ≡ 𝔅.

Example 7. Let ℕ be the usual natural numbers with < < < as the usual ordering. Let 𝔅 = ⟨ℕ,< < <⟩ and 𝔄 = ⟨ℕ \ {0},< < <⟩ be models for the language with one binary relation symbol <. Then 𝔄 ⊆ 𝔅 and 𝔄 ≡ 𝔅; in fact 𝔄 ≅ 𝔅. But we do not have 𝔄 ≺ 𝔅; 1 satisfies the formula describing the least element of the ordering in 𝔄 but in 𝔅. So we see that being an elementary submodel is a very strong condition indeed. Nevertheless, later in the chapter we will obtain many examples of elementary submodels.

Exercise 9. Show that • if 𝔄 ⊆ 𝔅 and 𝔅 ⊆ ℭ then 𝔄 ⊆ ℭ and

• if 𝔄 ≺ 𝔅 and 𝔅 ≺ ℭ then 𝔄 ≺ ℭ.

Definition 21. A chain of models for a language L is an increasing sequence of models

𝔄_{0} ⊆ 𝔄_{1} ⊆ ⋯ ⊆ 𝔄_{n} ⊆ ⋯ n ∈ ℕ.

The union of the chain is defined to be the model 𝔄 = ∪{𝔄_{n} : n ∈ ℕ} where the universe of 𝔄 is A = ∪{A_{n} : n ∈ ℕ} and:

(1) each relation S on 𝔄 is the union of the corresponding relations S_{n} of 𝔄_{n}; S = ∪{S_{n} : n ∈ ℕ}, i.e. the relation extending each S_{n}

(2) each function G on 𝔄 is the union of the corresponding functions G_{n} of 𝔄_{n}; G = ∪{G_{n} : n ∈ ℕ}, i.e. the function extending each G_{n}

(3) all the models 𝔄_{n} and 𝔄 have the same constant elements. Note that each 𝔄_{n} ⊆ 𝔄.

Example 8. For each n ∈ ℕ, let

A_{n} = {−n, −n + 1, −n + 2, …, 0, 1, 2, 3, … } ⊆ ℤ.

Let 𝔄_{n} = ⟨A_{n}, ≤⟩. Each 𝔄_{n} ≡ 𝔄_{0}, but we don’t have 𝔄_{0} ≡ ∪{𝔄_{n} : n ∈ ℕ}.

Remark. To be sure, what is defined here is a chain of models indexed by the natural numbers ℕ. More generally, a chain of models could be indexed by any ordinal. However we will not need the concept of an ordinal at this point.

Definition 22. An elementary chain is a chain of models {𝔄_{n} : n ∈ ℕ} such that for each m < n we have 𝔄_{m} ≺ 𝔄_{n}.

Theorem 4. (Tarski’s Elementary Chain Theorem) Let {𝔄_{n} : n ∈ ℕ} be an elementary chain. For all n ∈ ℕ we have

𝔄_{n} ≺ ∪{𝔄_{n} : n ∈ ℕ}.

Proof. Denote the union of the chain by 𝔄. We have 𝔄_{k} ⊆ 𝔄 for each k ∈ ℕ.

Claim. If t is a term of the language L and a_{0}, …, a_{p} are in A_{k}, then the value of the term t[a_{0}, …, a_{p}] in 𝔄 is equal to the value in 𝔄_{k}.

Proof of Claim. We prove this by induction on the complexity of the term.

(1) If t is the variable v_{i} then both values are just a_{i}.

(2) If t is the constant symbol c then the values are equal because c has the same interpretation in 𝔄 and in 𝔄_{k}.

(3) If t is F (t_{1} … t_{m}) where F is a function symbol and t_{1}, …, t_{m} are terms such that each value t_{i}[a_{0}, …, a_{p}] is the same in both 𝔄 and 𝔄_{k}, then the value

F (t_{1} … t_{m})[a_{0}, …, a_{p}]

in 𝔄 is

G(t_{1}[a_{0}, …, a_{p}], …, t_{m}[a_{0}, …, a_{p}])

where G is the interpretation of F in 𝔄 and the value of

F (t_{1} … t_{m})[a_{0}, …, a_{p}]

in 𝔄_{k} is

G_{k}(t_{1}[a_{0}, …, a_{p}], …, t_{m}[a_{0}, …, a_{p}])

where G_{k} is the interpretation of F in 𝔄_{k}. But G_{k} is the restriction of G to A_{k} so these values are equal.

In order to show that each 𝔄_{k} ≺ 𝔄 it will suffice to prove the following statement for each formula φ(v_{0}, …, v_{p}) of L.

“ For all k ∈ ℕ and all a_{0}, …, a_{p} in A_{k}:

𝔄 ⊧ φ[a_{0}, …, a_{p}] iff 𝔄_{k} ⊧ φ[a_{0}, …, a_{p}].”

Claim. The statement is true whenever φ is t_{1} = t_{2} where t_{1} and t_{2} are terms.

Proof of Claim. Fix k ∈ ℕ and a_{0}, …, a_{p} in A_{k}.

𝔄 ⊧ (t_{1} = t_{2})[a_{0}, …, a_{p}] iff t_{1}[a_{0}, …, a_{p}] = t_{2}[a_{0}, …, a_{p}] in 𝔄
iff t_{1}[a_{0}, …, a_{p}] = t_{2}[a_{0}, …, a_{p}] in 𝔄_{k}
iff 𝔄_{k} ⊧ (t_{1} = t_{2})[a_{0}, …, a_{p}].

Claim. The statement is true whenever φ is R(t_{1} … t_{n}) where R is a relation symbol and t_{1}, …, t_{n} are terms.

Proof of Claim. Fix k ∈ ℕ and a_{0}, …, a_{p} in A_{k}. Let S be the interpretation of R in 𝔄 and S_{k} be the interpretation in 𝔄_{k}; S_{k} is the restriction of S to A_{k}.

𝔄 ⊧ R(t_{1} … t_{n})[a_{0}, …, a_{p}] iff S(t_{1}[a_{0}, …, a_{p}], …, t_{n}[a_{0}, …, a_{p}])
iff S_{k}(t_{1}[a_{0}, …, a_{p}], …, t_{n}[a_{0}, …, a_{p}])
iff 𝔄_{k} ⊧ R(t_{1} … t_{n})[a_{0}, …, a_{p}]

Claim. If the statement is true when φ is θ, then the statement is true when φ is ¬θ.

2. COMPACTNESS AND ELEMENTARY SUBMODELS 18

Proof of Claim. Fix k ∈ ℕ and a_{0}, …, a_{p} in A_{k}.

𝔄 ⊧ (¬θ)[a_{0}, …, a_{p}] iff not 𝔄 ⊧ θ[a_{0}, …, a_{p}]
iff not 𝔄_{k} ⊧ θ[a_{0}, …, a_{p}]
iff 𝔄_{k} ⊧ (¬θ)[a_{0}, …, a_{p}].

Claim. If the statement is true when φ is θ_{1} and when φ is θ_{2} then the statement is true when φ is θ_{1} ∧ θ_{2}.

Proof of Claim. Fix k ∈ ℕ and a_{0}, …, a_{p} in A_{k}.

𝔄 ⊧ (θ_{1} ∧ θ_{2})[a_{0}, …, a_{p}] iff 𝔄 ⊧ θ_{1}[a_{0}, …, a_{p}] and 𝔄 ⊧ θ_{2}[a_{0}, …, a_{p}]
iff 𝔄_{k} ⊧ θ_{1}[a_{0}, …, a_{p}] and 𝔄_{k} ⊧ θ_{2}[a_{0}, …, a_{p}]
iff 𝔄_{k} ⊧ (θ_{1} ∧ θ_{2})[a_{0}, …, a_{p}].

Claim. If the statement is true when φ is θ then the statement is true when φ is ∃v_{i}θ.

Proof of Claim. Fix k ∈ ℕ and a_{0}, …, a_{p} in A_{k}. Note that A = ∪{A_{j} : j ∈ ℕ}.

𝔄 ⊧ ∃v_{i}θ[a_{0}, …, a_{p}] iff 𝔄 ⊧ ∃v_{i}θ[a_{0}, …, a_{q}] where q is the maximum of i and p (by Lemma 2), iff 𝔄 ⊧ θ[a_{0}, …, a_{i−1}, a, a_{i+1}, …, a_{q}] for some a ∈ A, iff 𝔄 ⊧ θ[a_{0}, …, a_{i−1}, a, a_{i+1}, …, a_{q}] for some a ∈ A_{l} for some l ≥ k iff 𝔄_{l} ⊧ θ[a_{0}, …, a_{i−1}, a, a_{i+1}, …, a_{q}] since the statement is true for θ, iff 𝔄_{l} ⊧ ∃v_{i}θ[a_{0}, …, a_{q}] iff 𝔄_{k} ⊧ ∃v_{i}θ[a_{0}, …, a_{q}] since 𝔄_{k} ≺ 𝔄_{l} iff 𝔄_{k} ⊧ ∃v_{i}θ[a_{0}, …, a_{p}] (by Lemma 2).

By induction on the complexity of φ, we have proven the statement for all formulas φ which do not contain the connectives ∨, → and ↔ or the quantifier ∀. To verify the statement for all φ we use Lemma 3. Let φ be any formula of L. By Lemma 3 there is a formula ψ which does not use ∨, →, ↔ nor ∀ such that

⊧ (∀v_{0}) … (∀v_{p})(φ ↔ ψ).

Now fix k ∈ ℕ and a_{0}, …, a_{p} in A_{k}. We have

𝔄 ⊧ (φ ↔ ψ)[a_{0}, …, a_{p}] and 𝔄_{k} ⊧ (φ ↔ ψ)[a_{0}, …, a_{p}].

𝔄 ⊧ φ[a_{0}, …, a_{p}] iff 𝔄 ⊧ ψ[a_{0}, …, a_{p}]
iff 𝔄_{k} ⊧ ψ[a_{0}, …, a_{p}]
iff 𝔄_{k} ⊧ φ[a_{0}, …, a_{p}]

which completes the proof of the theorem.

□

Lemma 5. (The Tarski-Vaught Condition) Let 𝔄 and 𝔅 be models for L with 𝔄 ⊆ 𝔅. The following are equivalent:

(1) 𝔄 ≺ 𝔅

(2) for any formula ψ(v_{0}, …, v_{q}) and any i ≤ q and any a_{0}, …, a_{q} from A: if there is some b ∈ B such that

𝔅 ⊧ ψ[a_{0}, …, a_{i−1}, b, a_{i+1}, …, a_{q}]

then we have some a ∈ A such that

𝔅 ⊧ ψ[a_{0}, …, a_{i−1}, a, a_{i+1}, …, a_{q}].

Proof. Only the implication (2) ⇒ (1) requires a lot of proof. We will prove that for each formula φ(v_{0}, …, v_{p}) and all a_{0}, …, a_{p} from A we will have:

𝔄 ⊧ φ[a_{0}, …, a_{p}] iff 𝔅 ⊧ φ[a_{0}, …, a_{p}]

by induction on the complexity of φ using only the negation symbol ¬, the connective ∧ and the quantifier ∃ (recall Lemma 3).

(1) The cases of formulas of the form t_{1} = t_{2} and R(t_{1} … t_{n}) come immediately from the fact that 𝔄 ⊆ 𝔅.

(2) For negation: suppose φ is ¬ψ and we have it for ψ, then

𝔄 ⊧ φ[a_{0}, …, a_{p}] iff not 𝔄 ⊧ ψ[a_{0}, …, a_{p}]
iff not 𝔅 ⊧ ψ[a_{0}, …, a_{p}] iff 𝔅 ⊧ φ[a_{0}, …, a_{p}].

(3) The ∧ case proceeds similarly.

(4) For the ∃ case we consider φ as ∃v_{i}ψ. If 𝔄 ⊧ ∃v_{i}ψ[a_{0}, …, a_{p}], then the inductive hypothesis for ψ and the fact that A ⊆ B ensure that 𝔅 ⊧ ∃v_{i}ψ[a_{0}, …, a_{p}]. It remains to show that if 𝔅 ⊧ φ[a_{0}, …, a_{p}] then 𝔄 ⊧ φ[a_{0}, …, a_{p}].

Assume 𝔅 ⊧ ∃v_{i}ψ[a_{0}, …, a_{p}]. By Lemma 2, 𝔅 ⊧ ∃v_{i}ψ[a_{0}, …, a_{q}] where q is the maximum of i and p. By the definition of satisfaction, there is some b ∈ B such that

𝔅 ⊧ ψ[a_{0}, …, a_{i−1}, b, a_{i+1}, …, a_{q}].

By (2), there is some a ∈ A such that

𝔅 ⊧ ψ[a_{0}, …, a_{i−1}, a, a_{i+1}, …, a_{q}].

By the inductive hypothesis on ψ, for that same a ∈ A,

𝔄 ⊧ ψ[a_{0}, …, a_{i−1}, a, a_{i+1}, …, a_{q}].

By the definition of satisfaction,

𝔄 ⊧ ∃v_{i}ψ[a_{0}, …, a_{q}].

Finally, by Lemma 2, 𝔄 ⊧ ϕ[a_{0}, …, a_{p}].

□

Recall that |B| is used to represent the cardinality, or size, of the set B. Note that since any language L contains infinitely many variables, |L| is always infinite, but may be countable or uncountable depending on the number of other symbols. We often denote an arbitrary infinite cardinal by the lower case Greek letter κ.

Theorem 5. (Downward Löwenheim-Skolem Theorem) Let 𝔅 be a model for L and let κ be any cardinal such that |L| ≤ κ < |B|. Then 𝔅 has an elementary submodel 𝔄 of cardinality κ.

Furthermore if X ⊆ B and |X| ≤ κ, then we can also have X ⊆ A.

Proof. Without loss of generosity assume |X| = κ. We recursively define sets X_{n} for n ∈ ℕ such that X = X_{0} ⊆ X_{1} ⊆ ⋯ ⊆ X_{n} ⊆ ⋯ and such that for each formula φ(v_{0}, …, v_{p}) of L and each i ≤ p and each a_{0}, …, a_{p} from X_{n} such that

𝔅 ⊧ ∃v_{i}φ[a_{0}, …, a_{p}]

we have x ∈ X_{n+1} such that

𝔅 ⊧ φ[a_{0}, …, a_{i−1}, x, a_{i+1}, …, a_{p}].

Since |L| ≤ κ and each formula of L is a finite string of symbols from L, there are at most κ many formulas of L. So there are at most κ elements of B that need to be added to each X_{n} and so, without loss of generosity each |X_{n}| = κ. Let A = ∪{X_{n} : n ∈ ℕ}; then |A| = κ. Since A is closed under functions from 𝔅 and contains all constants from 𝔅, A gives rise to a submodel 𝔄 ⊆ 𝔅.

The Tarski-Vaught Condition is used to show that 𝔄 ≺ 𝔅.

□

Theorem 6. (The Upward Löwenheim-Skolem Theorem) Let 𝔄 be an infinite model for L and κ be any cardinal such that |L| ≤ κ and |A| < κ. Then 𝔄 has an elementary extension of cardinality κ.

Proof. For each a ∈ A, let c_{a} be a new constant symbol; let

L′ = L ∪ {c_{a} : a ∈ A}.

Note that sentences of L′ are just formulas of L with all free variables replaced by constant symbols.

In addition, add κ many new constant symbols to L′ to make L′′. Define Σ to be the following set of sentences of L′′:

{¬d = d′ : d and d′ are distinct new constant symbols of L′′ \ L′}∪

{σ : σ is a sentence of L′ obtained from the formula φ(v_{0}, …, v_{p}) of L by replacing each free variable v_{i} by the constant symbol c_{a_{i}}

and 𝔄 ⊧ φ[a_{0}, …, a_{p}]}

By interpreting c_{a} as a and the new constant symbols as distinct elements of A we can transform 𝔄 into a model of any finite subset of Σ. Using the Compactness Theorem, we obtain a model 𝔇′′ for L′′ such that 𝔇′′ ⊧ Σ.

Note that 𝔇′′ has size at least κ and that for any sentence σ of L′, 𝔇′′ ⊧ σ iff σ ∈ Σ.

Obtain a model ℭ′′ for L′′ from 𝔇′′ by simply switching elements of the universe of 𝔇′′ with A to ensure that for each a ∈ A the interpretation of c_{a} in ℭ′′ is a.

Hence the universe of ℭ′′ contains A and ℭ′′ ⊧ Σ. Let ℭ be the reduct of ℭ′′ to L. The following argument will show that 𝔄 ≺ ℭ.

Let φ be any formula of L and a_{0}, …, a_{p} any elements from A. Let σ be the sentence of L′ formed by replacing free occurences of v_{i} with c_{a_{i}}. We have

𝔄 ⊧ φ[a_{0}, …, a_{p}] iff σ ∈ Σ
iff 𝔇′′ ⊧ σ
iff ℭ′′ ⊧ σ
iff ℭ ⊧ φ[a_{0}, …, a_{p}].

However, ℭ may have size strictly larger than κ. In this case we obtain our final 𝔅 by using the previous theorem to get 𝔅 ≺ ℭ with A ⊆ B. It is now straightforward to conclude that 𝔄 ≺ 𝔅.

□

Definition 23. A theory T for a language L is said to be complete whenever for each sentence σ of L either T ⊧ σ or T ⊧ ¬σ.

Lemma 6. A theory T for L is complete iff any two models of T are elementarily equivalent.

Proof. (⇒) easy. (⇐) easy. □

Definition 24. A theory T is said to be categorical in cardinality κ whenever any two models of T of cardinality κ are isomorphic. We also say that T is κcategorical.

The most interesting cardinalities in the context of categorical theories are ℵ_{0}, the cardinality of countably infinite sets, and ℵ_{1}, the first uncountable cardinal.

Exercise 10. Show that DLO is ℵ_{0}-categorical. There are two well-known proofs. One uses a back-and-forth construction of an isomorphism. The other constructs, by recursion, an isomorphism from the set of dyadic rational numbers between 0 and 1:

\{\frac{n}{2^{m}} : m is a positive integer and n is an integer 0 < n < 2^{m}\},

onto a countable dense linear order without endpoints.

Now use the following theorem to show that DLO is complete.

Theorem 7. (The Łoś-Vaught Test) Suppose that a theory T has only infinite models for a language L and that T is κ-categorical for some cardinal κ ≥ |L|. Then T is complete.

Proof. We will show that any two models of T are elementarily equivalent. Let 𝔄 of cardinality λ_{1}, and 𝔅 of cardinality λ_{2}, be two models of T .

If λ_{1} < κ use the Upward Löwenheim-Skolem Theorem to get 𝔄′ such that |A′| = κ and 𝔄 ≺ 𝔄′.

If λ_{1} > κ use the Downward Löwenheim-Skolem Theorem to get 𝔄′ such that |A′| = κ and 𝔄′ ≺ 𝔄.

Either way, we can get 𝔄′ such that |A′| = κ and 𝔄′ ≡ 𝔄. Similarly, we can get 𝔅′ such that |B′| = κ and 𝔅′ ≡ 𝔅. Since T is κ -categorical, 𝔄′ ≅ 𝔅′. Hence 𝔄 ≡ 𝔅. □

Recall that the characteristic of a field is the prime number p such that

\overbrace{1 + 1 + ⋯ + 1}^{p} = 0

provided that such a p exists, and, if no such p exists the field has characteristic 0. All of our best-loved fields: ℚ, ℝ and ℂ have characteristic 0. On the other hand, fields of characteristic p include the finite field of size p (the prime Galois field).

Theorem 8. The theory of algebraically closed fields of characteristic 0 is complete.

Proof. We use the Łoś-Vaught Test and the following Lemma. □

Lemma 7. Any two algebraically closed fields of characteristic 0 and cardinality ℵ_{1} are isomorphic.

Proof. Let 𝔄 be such a field containing the rationals 𝔔 = ⟨ℚ,+ + +,···, 0, 1⟩ as a prime subfield. In a manner completely analogous to finding a basis for a vector space, we can find a transcendence basis for 𝔄, that is, an indexed subset {a_{α} : α ∈ I} ⊆ A such that 𝔄 is the algebraic closure of the subfield 𝔄′ generated by {a_{α} : α ∈ I} but no a_{β} is in the algebraic closure of the subfield generated by the rest: {a_{α} : α ∈ I and α ≠ β}.

Since the subfield generated by a countable subset would be countable and the algebraic closure of a countable subfield would also be countable, we must have that the transcendence base is uncountable. Since |A| = ℵ_{1}, the least uncountable cardinal, we must have in fact that |I| = ℵ_{1}.

Now let 𝔅 be any other algebraically closed field of characteristic 0 and size ℵ_{1}. As above, obtain a transcendence basis {b_{β} : β ∈ J} with |J| = ℵ_{1} and its generated subfield 𝔅′. Since |I| = |J|, there is a bijection g : I → J which we can use to build an isomorphism from 𝔄 to 𝔅.

Since 𝔅 has characteristic 0, a standard theorem of algebra gives that the rationals are isomorphically embedded into 𝔅. Let this embedding be:

f : 𝔔 ↪ 𝔅.

We extend f as follows: for each α ∈ I, let f(a_{α}) = b_{g(α)}, which maps the transcendence basis of 𝔄 into the transcendence basis of 𝔅.

We now extend f to map 𝔄′ onto 𝔅′ as follows: Each element of 𝔄′ is given by

\frac{p(a_{α_{1}}, …, a_{α_{m}})}{q(a_{α_{1}}, …, a_{α_{m}})},

where p and q are polynomials with rational coefficients and the a’s come, of course, from the transcendence basis.

Let f map such an element to

\frac{p̄(b_{g(α_{1})}, …, b_{g(α_{m})})}{q̄(b_{g(α_{1})}, …, b_{g(α_{m})})}

where p̄ and q̄ are polynomials whose coefficients are the images under f of the rational coefficients of p and q.

The final extension of f to all of 𝔄 and 𝔅 comes from the uniqueness of algebraic closures.

□

Remark. Lemma 7 is also true when 0 is replaced by any fixed characteristic and ℵ_{1} by any uncountable cardinal.

Theorem 9. Let H be a set of sentences in the language of field theory which are true in algebraically closed fields of arbitrarily high characteristic. Then H holds in some algebraically closed field of characteristic 0.

Proof. A field is a model in the language {+, ·, 0, 1} of the axioms of field theory. Let ACF be the set of axioms for the theory of algebraically closed fields; see Example 5. For each n ≥ 2, let τ_{n} denote the sentence

¬(\overbrace{1 + 1 + ⋯ + 1}^{n}) = 0

Let Σ = ACF ∪ H ∪ {τ_{n} : n ≥ 2} Let Σ′ be any finite subset of Σ and let m be the largest natural number such

that τ_{m} ∈ Σ′ or let m = 1 by default.

Let 𝔄 be an algebraically closed field of characteristic p > m such that 𝔄 ⊧ H; then in fact 𝔄 ⊧ Σ′.

So by compactness there is 𝔅 such that 𝔅 ⊧ Σ. 𝔅 is the required field.

□

Corollary 1. Let ℂ denote, as usual, the complex numbers. Every one-to-one polynomial map f : ℂ^{m} → ℂ^{m} is onto.

Proof. A polynomial map is a function of the form

f(x_{1}, …, x_{m}) = ⟨p_{1}(x_{1}, …, x_{m}), …, p_{m}(x_{1}, …, x_{m})⟩

where each p_{i} is a polynomial in the variables x_{1}, …, x_{m}.

We call max { degree of p_{i} : i ≤ m} the degree of f. Let L be the language of field theory and let θ_{m,n} be the sentence of L which

expresses that “each polynomial map of m variables of degree < n which is one-to-one is also onto”.

We wish to show that there are algebraically closed fields of arbitrarily high characteristic which satisfy H = {θ_{m,n} : m, n ∈ ℕ}. We will then apply Theorem 9, Theorem 8, Lemma 6 and Exercise 5 and be finished.

Let p be any prime and let F_{p} be the prime Galois field of size p. The algebraic closure F̃_{p} is the countable union of a chain of finite fields

F_{p} = A_{0} ⊆ A_{1} ⊆ A_{2} ⊆ ⋯ ⊆ A_{k} ⊆ A_{k+1} ⊆ ⋯

obtained by recursively adding roots of polynomials.

We finish the proof by showing that each ⟨F̃_{p},+ + +, ·, 0, 1⟩ satisfies H. Given any polynomial map f : (F̃_{p}^{m}) → (F̃_{p}^{m}) which is one-to-one, we show

that f is also onto. Given any elements b_{1}, …, b_{m} ∈ F̃_{p}, there is some A_{k} containing b_{1}, …, b_{m} as well as all the coefficients of f.

Since f is one-to-one, f ↾ A_{k}^{m} : A_{k}^{m} → A_{k}^{m} is a one-to-one polynomial map. Hence, since A_{k}^{m} is finite, f ↾ A_{k}^{m} is onto and so there are a_{1}, …, a_{m} ∈ A_{k} such

that f(a_{1}, …, a_{m}) = ⟨b_{1}, …, b_{m}⟩. Therefore f is onto.

Thus, for each prime number p and each m, n ∈ ℕ, θ_{m,n} holds in a field of characteristic p, i.e. ⟨F̃_{p},+ + +,···,000,111⟩ satisfies H.

□

It is a significant problem to replace “one-to-one” with “locally one-to-one”.

CHAPTER 3 Diagrams and Embeddings

Let 𝔄 = ⟨A, I⟩ be a model for a language L and X ⊆ A. Expand L to L_{X} = L ∪ {c_{a} : a ∈ X} by adding new constant symbols to L. We can expand 𝔄 to a model 𝔄_{X} = ⟨A, I′⟩ for L_{X} by choosing I′ extending I such that I′(c_{a}) = a for each a ∈ X. We sometimes write this as ⟨𝔄, x⟩_{x∈X}. We often deal with the case X = A, to obtain 𝔄_{A}.

Exercise 11. Let 𝔄 and 𝔅 be models for L with X ⊆ A ⊆ B. Prove:

(i) if 𝔄 ⊆ 𝔅 then 𝔄_{X} ⊆ 𝔅_{X}. (ii) if 𝔄 ≺ 𝔅 then 𝔄_{X} ≺ 𝔅_{X}. Hint: 𝔄 ⊧ φ[a_{1}, …, a_{p}] iff 𝔄_{A} ⊧ φ^{∗} where φ^{∗} is the sentence of L_{A} formed by

replacing each free occurence of v_{i} with c_{a_{i}}.

Definition 25. Let 𝔄 be a model for L.

(1) The elementary diagram of 𝔄 is Th𝔄_{A}, the set of all sentences of L_{A} which hold in 𝔄_{A}.

(2) The diagram of 𝔄, denoted by △_{𝔄}, is the set of all those sentences in Th𝔄_{A} without quantifiers.

Remark. There is a notion of atomic formula, which is a formula of the form t_{1} = t_{2} or R(t_{1} … t_{n}) where t_{1}, …, t_{n} are terms. Sometimes △_{𝔄} is defined to be the set of all atomic formulas and negations of atomic formulas which occur in Th𝔄_{A}. However this is not substantially different from Definition 25, since the reader can quickly show that for any model 𝔅, 𝔅 ⊧ △_{𝔄} in one sense iff 𝔅 ⊧ △_{𝔄} in the other sense.

Definition 26. 𝔄 is said to be isomorphically embedded into 𝔅 whenever (1) there is a model ℭ such that 𝔄 ≅ ℭ and ℭ ⊆ 𝔅

or

(2) there is a model 𝔇 such that 𝔄 ⊆ 𝔇 and 𝔇 ≅ 𝔅.

Exercise 12. Prove that, in fact, (1) and (2) are equivalent conditions.

Definition 27. 𝔄 is said to be elementarily embedded into 𝔅 whenever

(1) there is a model ℭ such that 𝔄 ≅ ℭ and ℭ ≺ 𝔅 or

(2) there is a model 𝔇 such that 𝔄 ≺ 𝔇 and 𝔇 ≅ 𝔅.

Exercise 13. Again, prove that, in fact, (1) and (2) are equivalent.

Theorem 10. (The diagram lemmas) Let 𝔄 and 𝔅 be models for L.

(1) 𝔄 is isomorphically embedded in 𝔅 iff 𝔅 can be expanded to a model of △_{𝔄}.

(2) 𝔄 is elementarily embedded in 𝔅 iff 𝔅 can be expanded to a model of Th(𝔄_{A}).

Proof. We sketch the proof of 1.

(⇒) If f is as in 1 of Definition 26 above, then ⟨𝔅, f(a)⟩_{a∈A} ⊧ △_{𝔄}.

(⇐) If ⟨𝔅, b_{a}⟩_{a∈A} ⊧ △_{𝔄}, then let f(a) = b_{a}.

□

Exercise 14. Give a careful proof of part 2 of the theorem.

We now apply these notions to graph theory and to calculus. The natural language for graph theory has one binary relation symbol which we call E (to suggest the word “edge”). Graph Theory has the following two axioms:

• (∀x)(∀y)E(x, y) ↔ E(y, x)

• (∀x)¬E(x, x). A graph is, of course, a model of graph theory.

Corollary 2. Every planar graph can be four coloured.

Proof. We will have to use the famous result of Appel and Haken that every finite planar graph can be four coloured. Model Theory will take us from the finite to the infinite. We recall that a planar graph is one that can be embedded, or drawn, in the usual Euclidean plane and to be four coloured means that each vertex of the graph can be assigned one of four colours in such a way that no edge has the same colour for both endpoints.

Let 𝔄 be an infinite planar graph. Introduce four new unary relation symbols: R, G, B, Y (for red, green, blue and yellow). We wish to prove that there is some expansion 𝔄′ of 𝔄 such that 𝔄′ ⊧ σ where σ is the sentence in the expanded language:

(∀x)[R(x) ∨ G(x) ∨ B(x) ∨ Y (x)]

∧ (∀x)[R(x) → ¬(G(x) ∨ B(x) ∨ Y (x))] ∧ …
∧ (∀x)(∀y)¬(R(x) ∧ R(y) ∧ E(x, y)) ∧ ⋯

which will ensure that the interpretations of R, G, B and Y will four colour the graph.

Let Σ = △_{𝔄} ∪ {σ}. Any finite subset of Σ has a model, based upon the appropriate finite subset of 𝔄. By the compactness theorem, we get 𝔅 ⊧ Σ. Since 𝔅 ⊧ σ, the interpretations of R, G, B and Y four colour it. By the diagram lemma 𝔄 is isomorphically embedded in the reduct of 𝔅, and this isomorphism delivers the four-colouring of 𝔄.

□

A graph with the property that every pair of vertices is connected with an edge is called complete. At the other extreme, a graph with no edges is called discrete. A very important theorem in finite combinatorics says that most graphs contain an example of one or the other as a subgraph. A subgraph of a graph is, of course, a submodel of a model of graph theory.

Corollary 3. (Ramsey’s Theorem) For each n ∈ ℕ there is an r ∈ ℕ such that if 𝔊 is any graph with r vertices, then either 𝔊 contains a complete subgraph with n vertices or a discrete subgraph with n vertices.

Proof. We follow F. Ramsey who began by proving an infinite version of the theorem (also called Ramsey’s Theorem).

Claim. Each infinite graph 𝔊 contains either an infinite complete subgraph or an infinite discrete subgraph.

Proof of Claim. By force of logical necessity, there are two possiblities:

(1) there is an infinite X ⊆ G such that for all x ∈ X there is a finite F_{x} ⊆ X such that E(x, y) for all y ∈ X \ F_{x},

(2) for all infinite X ⊆ G there is a x ∈ X and an infinite Y ⊆ X such that ¬E(x, y) for all y ∈ Y.

If (1) occurs, we recursively pick x_{1} ∈ X, x_{2} ∈ X \F_{x_{1}}, x_{3} ∈ X \(F_{x_{1}} ∪F_{x_{2}}), etc, to obtain an infinite complete subgraph. If (2) occurs we pick x_{0} ∈ G and Y_{0} ⊆ G with the property and then recursively choose x_{1} ∈ Y_{0} and Y_{1} ⊆ Y_{0} , x_{2} ∈ Y_{1} and Y_{2} ⊆ Y_{1} and so on, to obtain an infinite discrete subgraph.

We now use Model Theory to go from the infinite to the finite. Let σ be the sentence, of the language of graph theory, asserting that there is no complete subgraph of size n.

(∀x_{1} … ∀x_{n})[¬E(x_{1}, x_{2}) ∨ ¬E(x_{1}, x_{3}) ∨ ⋯ ∨ ¬E(x_{n−1}, x_{n})].

Let τ be the sentence asserting that there is no discrete subgraph of size n.

(∀x_{1} … ∀x_{n})[E(x_{1}, x_{2}) ∨ E(x_{1}, x_{3}) ∨ ⋯ ∨ E(x_{n−1}, x_{n})].

Let T be the set consisting of σ, τ and the axioms of graph theory.

If there is no r as Ramsey’s Theorem states, then T has arbitrarily large finite models. By Theorem 2, T has an infinite model, contradicting the claim.

□

The following theorem of A. Robinson finally solved the centuries old problem of infinitesimals in the foundations of calculus.

Theorem 11. (The Leibniz Principle) There is an ordered field ^{∗}ℝ called the hyperreals, containing the reals ℝ and an infinitesimal number such that any statement about the reals which holds in ℝ also holds in ^{∗}ℝ.

Proof. Let ℜ be ⟨ℝ,+ + +,···,< < <,000,111⟩. We will make the statement of the theorem precise by proving that there is some model ℌ, in the same language L as ℜ and with the universe called ^{∗}ℝ , such that ℜ ≺ ℌ and there is b ∈ ^{∗}ℝ such that 0 < b < a for each positive a ∈ ℝ.

For each real number a, we introduce a new constant symbol c_{a}. In addition, another new constant symbol d is introduced. Let Σ be the set of sentences in the expanded language given by:

Thℜ_{ℝ} ∪ {0 < d < c_{a} : a is a positive real }

We can obtain a model ℭ ⊧ Σ by the compactness theorem. Let ℭ′ be the reduct of ℭ to L. By the elementary diagram lemma ℜ is elementarily embedded in ℭ′, and so there is a model ℌ for L such that ℭ′ ≅ ℌ and ℜ ≺ ℌ.

□

Remark. This idea is extremely useful in understanding calculus. An element x ∈ ^{∗}ℝ is said to be infinitesimal whenever −r < x < r for each positive r ∈ ℝ. 0 is infinitesimal. Two elements x, y ∈ ℝ are said to be infinitely close, written x ≈ y whenever x − y is infinitesimal. Note: x is infinitesimal iff x ≈ 0. An element x ∈ ^{∗}ℝ is said to be finite whenever −r < x < r for some positive r ∈ ℝ. Else it is infinite.

Each finite x ∈ ^{∗}ℝ is infinitely close to some real number, called the standard part of x, written st(x).

To differentiate f, for each △x ∈ ^{∗}ℝ generate △y = f(x+ △x) − f(x). Then f′(x) = st (\frac{△y}{△x}) whenever this exists and is the same for each infinitesimal △x ≠ 0.

The increment lemma states that if y = f(x) is differentiable at x and △ x ≈ 0, then △y = f′(x) △x + ε △x for some infinitesimal ε.

Proofs of the usual theorems of calculus are now easier.

The following theorem is considered one of the most fundamental results of mathematical logic. We give a detailed proof.

Theorem 12. (Robinson Consistency Theorem) Let L_{1} and L_{2} be two languages with L = L_{1} ∩L_{2}. Suppose T_{1} and T_{2} are satisfiable theories in L_{1} and L_{2} respectively. Then T_{1} ∪T_{2} is satisfiable iff there is no sentence σ of L such that T_{1} ⊧ σ and T_{2} ⊧ ¬σ.

Proof. The direction ⇒ is easy and motivates the whole theorem.

We begin the proof in the ⇐ direction. Our goal is to show that T_{1} ∪ T_{2} is satisfiable. The following claim is a first step.

Claim. T_{1} ∪ { sentences σ of L : T_{2} ⊧ σ} is satisfiable.

Proof of Claim. Using the compactness theorem and considering conjunctions, it suffices to show that if T_{1} ⊧ σ_{1} and T_{2} ⊧ σ_{2} with σ_{2} a sentence of L, then {σ_{1}, σ_{2}} is satisfiable. But this is true, since otherwise we would have σ_{1} ⊧ ¬σ_{2} and hence T_{1} ⊧ ¬σ_{2} and so ¬σ_{2} would be a sentence of L contradicting our hypothesis.

The basic idea of the proof from now on is as follows. In order to construct a model of T_{1} ∪ T_{2} we construct models 𝔄 ⊧ T_{1} and 𝔅 ⊧ T_{2} and an isomorphism f : 𝔄|L → 𝔅|L between the reducts of 𝔄 and 𝔅 to the language L, witnessing that 𝔄|L ≅ 𝔅|L. We then use f to carry over interpretations of symbols in L_{1} \ L from 𝔄 to 𝔅 , giving an expansion 𝔅^{∗} of 𝔅 to the language L_{1} ∪ L_{2}. Then, since 𝔅^{∗}|L_{1} ≅ 𝔄 and 𝔅^{∗}|L_{2} = 𝔅 we get 𝔅^{∗} ⊧ T_{1} ∪ T_{2}.

The remainder of the proof will be devoted to constructing such an 𝔄, 𝔅 and f. 𝔄 and 𝔅 will be constructed as unions of elementary chains of 𝔄_{n}’s and 𝔅_{n}’s while f will be the union of f_{n} : 𝔄_{n} ↪ 𝔅_{n}.

We begin with n = 0, the first link in the elementary chain.

Claim. There are models 𝔄_{0} ⊧ T_{1} and 𝔅_{0} ⊧ T_{2} with an elementary embedding f_{0} : 𝔄_{0}|L ↪ 𝔅_{0}|L.

Proof of Claim. Using the previous claim, let

𝔄_{0} ⊧ T_{1} ∪ { sentences σ of L : T_{2} ⊧ σ}

We first wish to show that Th(𝔄_{0}|L)_{A_{0}}∪T_{2} is satisfiable. Using the compactness theorem, it suffices to prove that if σ ∈ Th(𝔄_{0}|L)_{A_{0}} then T_{2} ∪ {σ} is satisfiable. For such a σ let c_{a_{0}}, …, c_{a_{n}} be all the constant symbols from L_{A_{0}} \L which appear in σ. Let φ be the formula of L obtained by replacing each constant symbol c_{a_{i}} by a new variable u_{i}. We have

𝔄_{0}|L ⊧ φ[a_{0}, …, a_{n}]
and so 𝔄_{0}|L ⊧ ∃u_{0} … ∃u_{n}φ

By the definition of 𝔄_{0}, it cannot happen that T_{2} ⊧ ¬∃u_{0} … ∃u_{n}φ and so there is some model 𝔇 for L_{2} such that 𝔇 ⊧ T_{2} and 𝔇 ⊧ ∃u_{0} … ∃u_{n}φ. So there are elements d_{0}, …, d_{n} of D such that 𝔇 ⊧ φ[d_{o}, …, d_{n}]. Expand 𝔇 to a model 𝔇^{∗} for L_{2} ∪ L_{A_{0}}, making sure to interpret each c_{a_{i}} as d_{i}. Then 𝔇^{∗} ⊧ σ, and so 𝔇^{∗} ⊧ T_{2} ∪ {σ}.

Let 𝔅_{0}^{∗} ⊧ Th(𝔄_{0}|L)_{A_{0}} ∪T_{2}. Let 𝔅_{0} be the reduct of 𝔅_{0}^{∗} to L_{2}; clearly 𝔅_{0} ⊧ T_{2}. Since 𝔅_{0}|L can be expanded to a model of Th(𝔄_{0}|L)_{A_{0}}, the Elementary Diagram Lemma gives an elementary embedding

f_{0} : 𝔄_{0}|L ↪ 𝔅_{0}|L

and finishes the proof of the claim.

The other links in the elementary chain are provided by the following result.

Claim. For each n ≥ 0 there are models 𝔄_{n+1} ⊧ T_{1} and 𝔅_{n+1} ⊧ T_{2} with an elementary embedding

f_{n+1} : 𝔄_{n+1}|L ↪ 𝔅_{n+1}|L

such that

𝔄_{n} ≺ 𝔄_{n+1}, 𝔅_{n} ≺ 𝔅_{n+1}, f_{n+1} extends f_{n} and B_{n} ⊆ range of f_{n+1}.

𝔄_{0} ≺ 𝔄_{1} ≺ ⋯ ≺ 𝔄_{n} ≺ 𝔄_{n+1} ≺ ⋯
↓_{f_{0}} ↓_{f_{1}} ↓_{f_{n}} ↓_{f_{n+1}}
𝔅_{0} ≺ 𝔅_{1} ≺ ⋯ ≺ 𝔅_{n} ≺ 𝔅_{n+1} ≺ ⋯

The proof of this claim will be discussed shortly. Assuming the claim, let 𝔄 = ⋃_{n∈ℕ} 𝔄_{n}, 𝔅 = ⋃_{n∈ℕ} 𝔅_{n} and f = ⋃_{n∈ℕ} f_{n}. The Elementary Chain Theorem gives that 𝔄 ⊧ T_{1} and 𝔅 ⊧ T_{2}. The proof of the theorem is concluded by simply verifying that f : 𝔄|L → 𝔅|L is an isomorphism.

The proof of the claim is long and quite technical; it would not be inappropriate to omit it on a first reading. The proof, of course, must proceed by induction on n. The case of a general n is no different from the case n = 0 which we state and prove in some detail.

Claim. There are models 𝔄_{1} ⊧ T_{1} and 𝔅_{1} ⊧ T_{2} with an elementary embedding f_{1} : 𝔄_{1}|L ↪ 𝔅_{1}|L such that 𝔄_{0} ≺ 𝔄_{1}, 𝔅_{0} ≺ 𝔅_{1}, f_{1} extends f_{0} and B_{0} ⊆ range of f_{1}.

\begin{aligned}𝔄_{0} & ≺ & 𝔄_{1} \\ ↓_{f_{0}} & & ↓_{f_{1}} \\ 𝔅_{0} & ≺ & 𝔅_{1} \end{aligned}

Proof of Claim. Let 𝔄_{0}^{+} be the expansion of 𝔄_{0} to the language L_{1}^{+} = L_{1} ∪ {c_{a} : a ∈ A_{0}} formed by interpreting each c_{a} as a ∈ A_{0}; 𝔄_{0}^{+} is just another notation for (𝔄_{0})_{A_{0}}. The elementary diagram of 𝔄_{0}^{+} is Th (𝔄_{0}^{+})_{A_{0}^{+}}. Let 𝔅_{0}^{∗} be the expansion of 𝔅_{0}|L to the language

L^{∗} = L ∪ {c_{a} : a ∈ A_{0}} ∪ {c_{b} : b ∈ B_{0}}

formed by interpreting each c_{a} as f_{0}(a) ∈ B_{0} and each c_{b} as b ∈ B_{0}.

We wish to prove that Th (𝔄_{0}^{+})_{A_{0}^{+}} ∪ Th𝔅_{0}^{∗} is satisfiable. By the compactness

theorem it suffices to prove that Th (𝔄_{0}^{+})_{A_{0}^{+}} ∪{σ} is satisfiable for each σ in Th𝔅_{0}^{∗}. For such a sentence σ, let c_{a_{0}}, …, c_{a_{m}}, c_{b_{0}}, …, c_{b_{n}} be all those constant symbols occuring in σ but not in L. Let φ(u_{0}, …, u_{m}, w_{0}, …, w_{m}) be the formula of L obtained from σ by replacing each constant symbol c_{a_{i}} by a new variable u_{i} and each constant symbol c_{b_{i}} by a new variable w_{i}. We have 𝔅_{0}^{∗} ⊧ σ so

𝔅_{0}|L ⊧ φ[f_{0}(a_{0}), …, f_{0}(a_{m}), b_{0}, …, b_{n}]
So 𝔅_{0}|L ⊧ ∃w_{0} … ∃w_{n}φ[f_{0}(a_{0}), …, f_{0}(a_{m})]

Since f_{0} is an elementary embedding we have :

𝔄_{0}|L ⊧ ∃w_{0} … ∃w_{n}φ[a_{0}, …, a_{m}]

Let φ̂(w_{0}, …, w_{n}) be the formula of L_{1}^{+} obtained by replacing occurences of u_{i} in φ(u_{0}, …, u_{m}, w_{0}, …, w_{n}) by c_{a_{i}}; then 𝔄_{0}^{+} ⊧ ∃w_{0} … ∃w_{n}φ̂. So, of course,

(𝔄_{0}^{+})_{A_{0}^{+}} ⊧ ∃w_{0} … ∃w_{n}φ̂

and this means that there are d_{0}, …, d_{n} in A_{0}^{+} = A_{0} such that

(𝔄_{0}^{+})_{A_{0}^{+}} ⊧ φ̂[d_{0}, …, d_{n}].

We can now expand (𝔄_{0}^{+})_{A_{0}^{+}} to a model 𝔇 by interpreting each c_{b_{i}} as d_{i} to obtain

𝔇 ⊧ σ and so Th (𝔄_{0}^{+})_{A_{0}^{+}} ∪ {σ} is satisfiable.

Let 𝔈 ⊧ Th (𝔄_{0}^{+})_{A_{0}^{+}} ∪ Th𝔅_{0}^{∗}. By the elementary diagram lemma 𝔄_{0}^{+} is ele-

mentarily embedded into 𝔈|L_{1}^{+}. So there is a model 𝔄_{1}^{+} for L_{1}^{+} with 𝔄_{0}^{+} ≺ 𝔄_{1}^{+} and an isomorphism g : 𝔄_{1}^{+} → 𝔈|L_{1}^{+}. Using g we expand 𝔄_{1}^{+} to a model 𝔄′_{1} isomorphic to 𝔈. Let 𝔄_{1}^{∗} denote 𝔄′_{1}|L^{∗}; we have 𝔄_{1}^{∗} ⊧ Th𝔅_{0}^{∗}.

We now wish to prove that Th (𝔄_{1}^{∗})_{A_{1}^{∗}} ∪ Th (𝔅_{0}^{+})_{B_{0}^{+}} is satisfiable, where 𝔅_{0}^{+} is the common expansion of 𝔅_{0} and 𝔅_{0}^{∗} to the language

L_{2}^{+} = L_{2} ∪ {c_{a} : a ∈ A_{0}} ∪ {c_{b} : b ∈ 𝔅_{0}}.

By the compactness theorem, it suffices to show that

Th (𝔅_{0}^{+})_{B_{0}^{+}} ∪ {σ}

is satisfiable for each σ in Th (𝔄_{1}^{∗})_{A_{1}^{∗}}. Let c_{x_{0}}, …, c_{x_{n}} be all those constant symbols which occur in σ but are not in L^{∗}. Let ψ(u_{0}, …, u_{n}) be the formula of L^{∗} obtained from σ by replacing each c_{x_{i}} with a new variable u_{i}. Since (𝔄_{1}^{∗})_{A_{1}^{∗}} ⊧ σ we have

𝔄_{1}^{∗} ⊧ ψ[x_{0}, …, x_{n}],

and so

𝔄_{1}^{∗} ⊧ ∃u_{0} … ∃u_{n}ψ.

Also 𝔄_{1}^{∗} ⊧ Th𝔅_{0}^{∗} and Th𝔅_{0}^{∗} is a complete theory in the language L^{∗}; hence ∃u_{0} … ∃u_{n}ψ is in Th𝔅_{0}^{∗}. Thus

𝔅_{0}^{∗} ⊧ ∃u_{0} … ∃u_{n}ψ

and so

(𝔅_{0}^{+})_{B_{0}^{+}} ⊧ ∃u_{0} … ∃u_{n}ψ

and therefore there are b_{0}, …, b_{n} in B_{0}^{+} = B_{0} such that

(𝔅_{0}^{+})_{B_{0}^{+}} ⊧ ψ[b_{0}, …, b_{n}].

We can now expand (𝔅_{0}^{+})_{B_{0}^{+}} to a model 𝔉 by interpreting each c_{x_{i}} as b_{i}; then

𝔉 ⊧ σ and Th (𝔅_{0}^{+})_{B_{0}^{+}} ∪ {σ} is satisfiable.

Let 𝔊 ⊧ Th (𝔄_{1}^{∗})_{A_{1}^{∗}} ∪ Th (𝔅_{0}^{+})_{B_{0}^{+}}. By the elementary diagram lemma 𝔅_{0}^{+} is

elementarily embedded into 𝔊|L_{2}^{+}. So there is a model 𝔅_{1}^{+} for L_{2}^{+} with 𝔅_{0}^{+} ≺ 𝔅_{1}^{+} and an isomorphism h : 𝔅_{1}^{+} → 𝔊|L_{2}^{+}. Using h we expand 𝔅_{1}^{+} to a model 𝔅′_{1} isomorphic to 𝔊. Let 𝔅_{1}^{∗} denote 𝔅′_{1}|L^{∗}. Again by the elementary diagram lemma 𝔄_{1}^{∗} is elementarily embedded into 𝔅_{1}^{∗}. Let this be denoted by

f_{1} : 𝔄_{1}^{∗} ↪ 𝔅_{1}^{∗}.

Let a ∈ A_{0}; we will show that f_{0}(a) = f_{1}(a). By definition we have 𝔅_{0}^{∗} ⊧ (v_{0} = c_{a})[f_{0}(a)] and so 𝔅_{0}^{+} ⊧ (v_{0} = c_{a})[f_{0}(a)]. Since 𝔅_{0}^{+} ≺ 𝔅_{1}^{+}, 𝔅_{1}^{+} ⊧ (v_{0} = c_{a})[f_{0}(a)] and so 𝔅_{1}^{∗} ⊧ (v_{0} = c_{a})[f_{0}(a)]. Now 𝔄_{0}^{+} ⊧ (c_{a} = v_{1})[a] and 𝔄_{0}^{+} ≺ 𝔄_{1}^{+} so 𝔄_{1}^{+} ⊧ (c_{a} = v_{1})[a] so 𝔄_{1}^{∗} ⊧ (c_{a} = v_{1})[a]. Since f_{1} is elementary, 𝔅_{1}^{∗} ⊧ (c_{a} = v_{1})[f_{1}(a)] so 𝔅_{1}^{∗} ⊧ (v_{0} = v_{1})[f_{0}(a), f_{1}(a)] and so f_{0}(a) = f_{1}(a).

Thus f_{1} extends f_{0}.

Let b ∈ B_{0}; we will prove that b = f_{1}(a) for some a ∈ A_{1}. By definition we have: 𝔅_{0}^{∗} ⊧ (v_{0} = c_{b})[b] so 𝔅_{0}^{+} ⊧ (v_{0} = c_{b})[b]. Since 𝔅_{0}^{+} ≺ 𝔅_{1}^{+}, 𝔅_{1}^{+} ⊧ (v_{0} = c_{b})[b] so 𝔅_{1}^{∗} ⊧ (v_{0} = c_{b})[b]. On the other hand, since (∃v_{1})(v_{1} = c_{b}) is always satisfied, we have: 𝔄_{1}^{∗} ⊧ (∃v_{1})(v_{1} = c_{b}) so there is a ∈ A_{1} such that 𝔄_{1}^{∗} ⊧ (v_{1} = c_{b})[a]. Since f_{1} is elementary, 𝔅_{1}^{∗} ⊧ (v_{1} = c_{b})[f_{1}(a)] so 𝔅_{1}^{∗} ⊧ (v_{0} = v_{1})[b, f_{1}(a)] so b = f_{1}(a).

Thus 𝔅_{0} ⊆ range of f_{1}.

We now let 𝔄_{1} be 𝔄_{1}^{+}|L_{1} and let 𝔅_{1} be 𝔅_{1}^{+}|L_{2}. We get 𝔄_{0} ≺ 𝔄_{1} and 𝔅_{0} ≺ 𝔅_{1} and f_{1} : 𝔄_{1}|L → 𝔅_{1}|L remains an elementary embedding.

This completes the proof of the claim. □

Exercise 15. The Robinson Consistency Theorem was originally stated as:

Let T_{1} and T_{2} be satisfiable theories in languages L_{1} and L_{2} respectively and let T ⊆ T_{1}∩T_{2} be a complete theory in the language L_{1} ∩ L_{2}. Then T_{1} ∪ T_{2} is satisfiable in the language L_{1} ∪ L_{2}.

Show that this is essentially equivalent to our version in Theorem 12 by first proving that this statement follows from Theorem 12 and then also proving that this statement implies Theorem 12. Of course, for this latter argument you are looking for a proof much shorter than our proof of Theorem 12; however it will help to use the first claim of our proof in your own proof.

Theorem 13. (Craig Interpolation Theorem) Let φ and ψ be sentences such that φ ⊧ ψ. Then there exists a sentence θ, called the interpolant, such that φ ⊧ θ and θ ⊧ ψ and every relation, function or constant symbol occuring in θ also occurs in both φ and ψ.

Exercise 16. Show that the Craig Interpolation Theorem follows quickly from the Robinson Consistency Theorem. Also, use the Compactness Theorem to show that Theorem 12 follows quickly from Theorem 13.

CHAPTER 4 Model Completeness

The quantifier ∀ is sometimes said to be the universal quantifier and the quantifier ∃ to be the existential quantifier.

A formula φ is said to be quantifier free whenever no quantifiers occur in φ. A formula φ is said to be universal whenever it is of the form ∀x_{0} … ∀x_{k}θ

where θ is quantifier free.

A formula φ is said to be existential whenever it is of the form ∃x_{0} … ∃x_{k}θ where θ is quantifier free.

A formula φ is said to be universal-existensial whenever it is of the form ∀x_{0} … ∀x_{k}∃y_{0} … ∃y_{k}θ where θ is quantifier free.

We extend these notions to theories T whenever each axiom σ of T has the property.

Remark. Note that each quantifier free formula φ is trivially equialent to the existential formula ∃v_{i}φ where v_{i} does not occur in φ.

Exercise 17. Let 𝔄 and 𝔅 be models for L with A ⊆ B. Verify the following four statements:

(i) 𝔄 ≺ 𝔅 iff 𝔅_{A} ⊧ Th(𝔄_{A}) iff 𝔄_{A} ⊧ Th(𝔅_{A}).

(ii) 𝔄 ⊆ 𝔅 iff 𝔅_{A} ⊧ △_{𝔄} iff 𝔄_{A} ⊧ σ for each quantifier free σ of Th(𝔅_{A}). (iii) 𝔄 ⊆ 𝔅 iff 𝔅_{A} ⊧ σ for each existential σ of Th(𝔄_{A}). (iv) 𝔄 ⊆ 𝔅 iff 𝔄_{A} ⊧ σ for each universal σ of Th(𝔅_{A}).

Definition 28. A model 𝔄 of a theory T is said to be existentially closed if whenever 𝔄 ⊆ 𝔅 and 𝔅 ⊧ T , we have 𝔄_{A} ⊧ σ for each existential sentence σ of Th(𝔅_{A}).

Remark. If 𝔄 is existentially closed and 𝔄′ ≅ 𝔄 then 𝔄′ is also existentially closed.

Definition 29. A theory T is said to be model complete whenever T ∪ △_{𝔄} is complete in the language L_{A} for each model 𝔄 of T .

Theorem 14. ( A. Robinson ) Let T be a theory in the language L. The following are equivalent:

(1) T is model complete,

(2) T is existentially complete, i.e. each model of T is existentially closed.

(3) for each formula φ(v_{0}, …, v_{p}) of L there is a universal formula ψ(v_{0}, …, v_{p}) such that T ⊧ (∀v_{0} … ∀v_{p})(φ ↔ ψ)

(4) for all models 𝔄 and 𝔅 of T , 𝔄 ⊆ 𝔅 implies 𝔄 ≺ 𝔅.

Remark. Equivalently, in part (3) of this theorem the phrase “universal formula” could be replaced by “existential formula”. We chose the version which makes the proof smoother.

Proof. (1) ⇒ (2):

Let 𝔄 ⊧ T and 𝔅 ⊧ T with 𝔄 ⊆ 𝔅. Clearly 𝔄_{A} ⊧ △_{𝔄} and by Exercise 17 we 𝔅_{A} ⊧ △_{𝔄}. Now by (1), T ∪ △_{𝔄} is complete and both 𝔄_{A} and 𝔅_{A} are models of this theory so they are elementarily equivalent.

So let σ be any sentence of L_{A} (existential or otherwise). If 𝔅_{A} ⊧ σ then 𝔄_{A} ⊧ σ and (2) follows.

(2) ⇒ (3): Lemma 4 shows that it suffices to prove it for formulas φ in prenex normal form. We do this by induction on the prenex rank of φ which is the number of alternations of quantifiers in φ. The first step is prenex rank 0. Where only universal quantifiers are present the result is trivial. The existential formula case is non-trivial; it is the following claim:

Claim. For each existential formula φ(v_{0}, …, v_{p}) of L there is a universal formula ψ(v_{0}, …, v_{p}) such that

T ⊧ (∀v_{0}) … (∀v_{p})(φ ↔ ψ)

Proof of Claim. Add new constant symbols c_{0}, …, c_{p} to L to form

L^{∗} = L ∪ {c_{0}, …, c_{p}}

and to form a sentence φ^{∗} of L^{∗} obtained by replacing each free occurrence of v_{i} in φ with the corresponding c_{i}; φ^{∗} is an existential sentence. It suffices to prove that there is a universal sentence γ of L^{∗} such that T ⊧ φ^{∗} ↔ γ.

Let Γ = {universal sentences γ of L^{∗} such that T ⊧ φ^{∗} → γ}

We hope to prove that there is some γ ∈ Γ such that T ⊧ γ → φ^{∗}. Note, however, that any finite conjunction γ_{1} ∧ γ_{2} ∧ ⋯ ∧ γ_{n} of sentences from Γ is equivalent to a sentence γ in Γ which is simply obtained from γ_{1} ∧ γ_{2} ∧ ⋯ ∧ γ_{n} by moving all the quantifiers to the front. Thus it suffices to prove that there are finitely many sentences γ_{1}, γ_{2}, …, γ_{n} from Γ such that

T ⊧ γ_{1} ∧ γ_{2} ∧ ⋯ ∧ γ_{n} → φ^{∗}.

If no such finite set of sentences existed, then each

T ∪ {γ_{1}, γ_{2}, …, γ_{n}} ∪ {¬φ^{∗}}

would be satisfiable. By the compactness theorem, T ∪ Γ ∪ {¬φ^{∗}} would be satisfiable. Therefore it just suffices to prove that T ∪ Γ ⊧ φ^{∗}.

In order to prove that T ∪ Γ ⊧ φ^{∗}, let 𝔄 be any model of T ∪ Γ for the language L^{∗}. Consider the reduct 𝔄|L and form L_{A} as usual but ensure that if the interpretation of the new constant c_{i} in 𝔄 is a then c_{a} is chosen to be c_{i}. In this way we conveniently get L^{∗} ⊆ L_{A}.

Let

Σ = T ∪ {φ^{∗}} ∪ △_{(𝔄|L)}.

be a set of sentences for the language L_{A}; we wish to show that Σ is satisfiable.

By the compactness theorem it suffices to consider T ∪ {φ^{∗}, τ} where τ is a conjunction of finitely many sentences of △_{(𝔄|L)}. Let θ be the formula obtained from τ by exchanging each constant symbol from L_{A} \ L occurring in τ for a new variable u_{a}. So

𝔄|L ⊧ ∃u_{a_{0}} … ∃u_{a_{m}}θ(u_{a_{0}}, …, u_{a_{m}}).

But then 𝔄 is not a model of the universal sentence ∀u_{a_{0}} … ∀u_{a_{m}}¬θ(u_{a_{0}}, …, u_{a_{m}}). Recalling that 𝔄 ⊧ Γ, we are forced to conclude that this universal sentence is not in Γ and so not a consequence of T ∪ {φ^{∗}}. Therefore

T ∪ {φ^{∗}} ∪ {∃u_{a_{0}} … ∃u_{a_{m}}θ(u_{a_{0}}, …, u_{a_{m}})}

must be satisfiable, and any model of this can be expanded to a model of T ∪{φ^{∗}, τ} and so Σ is satisfiable.

Let ℭ ⊧ Σ. By the diagram lemma, there is a model 𝔅 for L such that 𝔅_{A} ≅ ℭ and 𝔄|L ⊆ 𝔅. Now, both 𝔄|L and 𝔅 are models of T and 𝔅_{A} ⊧ φ^{∗}, so by (2) we get that (𝔄|L)_{A} ⊧ φ^{∗}. So 𝔄 ⊧ φ^{∗}.

This means T ∪ Γ ⊧ φ^{∗} and finishes the proof of the claim.

We will now do the general cases for the proof of the induction on prenex rank. There are two cases, corresponding to the two methods available for increasing the number of alternations of quantifiers:

(a) the addition of universal quantifiers

(b) the addition of existential quantifiers.

For the case (a), suppose φ(v_{0}, …, v_{p}) is ∀w_{0} … ∀w_{m}χ(v_{0}, …, v_{p}, w_{0}, …, w_{m}) and χ has prenex rank lower than φ so that we have by the inductive hypothesis that there is a quantifier free formula θ(v_{0}, …, v_{p}, w_{0}, …, w_{m}, x_{0}, …, x_{n}) with new variables x_{0}, …, x_{n} such that

T ⊧ (∀v_{0} … ∀v_{p}∀w_{0} … ∀w_{m})(χ ↔ ∀x_{0} … ∀x_{n}θ)

Therefore, case (a) is concluded by noticing that this gives us

T ⊧ (∀v_{0} … ∀v_{p})(∀w_{0} … ∀w_{m}χ ↔ ∀w_{0} … ∀w_{m}∀x_{0} … ∀x_{n}θ).

Exercise 18. Check this step using the definition of satisfaction.

For case (b), suppose φ(v_{0}, …, v_{p}) is ∃w_{0} … ∃w_{n}χ(v_{0}, …, v_{p}, w_{0}, …, w_{m}) and χ has prenex rank less than φ. Here we will use the inductive hypothesis on ¬χ which of course also has prenex rank less than φ. We obtain a quantifier free formula θ(v_{0}, …, v_{p}, w_{0}, …, w_{m}, x_{0}, …, x_{n}) with new variables x_{0}, …, x_{n} such that

T ⊧ (∀v_{0} … ∀v_{p}∀w_{0} … ∀w_{m})(¬χ ↔ ∀x_{0} … ∀x_{n}θ)
So T ⊧ (∀v_{0} … ∀v_{p})(∀w_{0} … ∀w_{m}¬χ ↔ ∀w_{0} … ∀w_{m}∀x_{0} … ∀x_{n}θ)
And T ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{m}χ ↔ ∃w_{0} … ∃w_{m}∃x_{0} … ∃x_{n}¬θ)

Now ∃w_{0} … ∃w_{m}∃x_{0} … ∃x_{n}¬θ is an existential formula, so by the claim there is a universal formula ψ such that

T ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{m}∃x_{0} … ∃x_{n}¬θ ↔ ψ).
Hence T ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{n}χ ↔ ψ)

which is the final result which we needed.

(3) ⇒ (4) Let 𝔄 ⊧ T and 𝔅 ⊧ T with 𝔄 ⊆ 𝔅. Let φ be a formula of L and let a_{0}, …, a_{p} be in A such that

𝔅 ⊧ φ[a_{0}, …, a_{p}]

Obtain a universal formula ψ such that

T ⊧ (∀v_{0} … ∀v_{p})(φ ↔ ψ)

so

𝔅 ⊧ ψ[a_{0}, …, a_{p}]

Since 𝔄 ⊆ 𝔅

𝔄 ⊧ ψ[a_{0}, …, a_{p}]

and so 𝔄 ⊧ φ[a_{0}, …, a_{p}] and 𝔄 ≺ 𝔅.

(4) ⇒ (1): Let 𝔄 ⊧ T . We will show that T ∪ △_{𝔄} is complete by showing that for any model 𝔅 for L_{A}, 𝔅 ⊧ T ∪ △_{𝔄} implies 𝔅 ⊧ Th(𝔄_{A}).

Letting 𝔅 be such a model, we note that 𝔅|L, the restriction of 𝔅 to L, can be expanded to 𝔅, a model of △_{𝔄}. So by the diagram lemma 𝔄 is isomorphically embedded in 𝔅|L. Furthermore, by checking the proof of the diagram lemma we can ensure that there is an

f : 𝔄 ↪ 𝔅|L

such that for each a ∈ A, f(a) is the interpretation of c_{a} in 𝔅. (Recall that L_{A} = L ∪ {c_{a} : a ∈ A}). Moreover, as in Exercise 12, there is a model 𝔇 for L such that 𝔄 ⊆ 𝔇 and an isomorphism g : 𝔇 → 𝔅|L with the property that for each a ∈ A, g(a) is the interpretation of c_{a} in 𝔅.

Now let σ ∈ Th(𝔄_{A}), so that 𝔄_{A} ⊧ σ. Let φ(u_{0}, …, u_{k}) be the formula of L obtained by replacing each occurence of c_{a_{i}} in σ by the new variable u_{i}. We have

𝔄 ⊧ φ[a_{0}, …, a_{k}]

Since 𝔄 ⊆ 𝔇 we can use (4) to get 𝔄 ≺ 𝔇 and so we have 𝔇 ⊧ φ[a_{0}, …, a_{k}]. With the isomorphism g we get that

𝔅|L ⊧ φ[g(a_{0}), …, g(a_{k})]

and since g(a_{i}) is the interpretation of c_{a_{i}} in 𝔅 we have 𝔅 ⊧ σ. Thus 𝔅 ⊧ Th(𝔄_{A}) and this proves (1). □

Example 9. We will see later that the theory ACF is model complete. But ACF is not complete because the characteristic of the algebraically closed field can vary among models of ACF and the assertion that “I have characteristic p” can easily be expressed as a sentence of the language of ACF.

Exercise 19. Suppose that T is a model complete theory in L and that either (1) any two models of T are isomorphically embedded into a third or

(2) there is a model of T which is isomorphically embedded in any other. Then prove that T is complete.

Example 10. Let ℕ be the usual natural numbers and < the usual ordering. Let 𝔅 = ⟨ℕ, <⟩ and 𝔄 = ⟨ℕ \ {0}, <⟩ be models for the language with one binary relation symbol <. Th𝔄 is, of course, complete, but it is not model complete because it is not existentially complete. In fact the model 𝔄 is not existentially closed because 𝔅 ⊧ Th𝔄 and 𝔄 ⊆ 𝔅 and 𝔅_{A} ⊧ (∃v_{0})(v_{0} < c_{1}) where c_{1} is the constant symbol with interpretation 1. But 𝔄_{A} does not satisfy this existential sentence.

Theorem 15. (Lindström’s Test) Let T be a theory in a countable language L such that

(1) all models of T are infinite,

(2) the union of any chain of models of T is a model of T , and

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

Then T is model complete.

Proof. W.L.O.G. we assume that T is satisfiable. We use conditions (1) and (2) to prove the following:

Claim. T has existentially closed models of each infinite size κ.

Proof of Claim. By the Löwenheim-Skolem Theorems we get 𝔄_{0} ⊧ T with |A_{0}| = κ. We recursively construct a chain of models of T of size κ

𝔄_{0} ⊆ 𝔄_{1} ⊆ … ⊆ 𝔄_{n} ⊆ 𝔄_{n+1} ⊆ ⋯

with the property that

if 𝔅 ⊧ T and 𝔄_{n+1} ⊆ 𝔅 and σ is an existential sentence of Th(𝔅_{A_{n}}), then (𝔄_{n+1})_{A_{n}} ⊧ σ.

Suppose 𝔄_{n} is already constructed; we will construct 𝔄_{n+1}. Let Σ_{n} be a maximally large set of existential sentences of L_{A_{n}} such that for each finite Σ′ ⊆ Σ_{n} there is a model ℭ for L_{A_{n}} such that

ℭ ⊧ Σ′ ∪ T ∪ △_{𝔄_{n}}

By compactness T ∪ Σ_{n} ∪ △_{𝔄_{n}} has a model 𝔇 and without loss of generosity 𝔄_{n} ⊆ 𝔇. By the Downward Löwenheim-Skolem Theorem we get 𝔈 such that 𝔄_{n} ⊆ 𝔈, |𝔈| = κ and 𝔈 ≺ 𝔇.

Let 𝔄_{n+1} = 𝔈|L; we will show that 𝔄_{n+1} has the required properties. Since 𝔈 ≡ 𝔇, 𝔈 ⊧ T ∪ △_{𝔄_{n}} and so 𝔄_{n} ⊆ 𝔄_{n+1} (See Exercise 17).

Let 𝔅 ⊧ T with 𝔄_{n+1} ⊆ 𝔅 and σ be an existential sentence of Th(𝔅_{A_{n}}); we will show that (𝔄_{n+1})_{A_{n}} ⊧ σ. Since Σ_{n} consists of existential sentences and 𝔇 ≡ 𝔈 ≡ (𝔄_{n+1})_{A_{n}} ⊆ 𝔅_{A_{n}} we have (see Exercise 17) that 𝔅_{A_{n}} ⊧ Σ_{n}. The maximal property of Σ_{n} then forces σ to be in Σ_{n} because if σ ∉ Σ_{n} then there must be some finite Σ′ ⊆ Σ_{n} for which there is no ℭ such that ℭ ⊧ Σ′ ∪ {σ} ∪ T ∪ △_{𝔄_{n}}; but 𝔅_{A_{n}} is such a ℭ! Now since σ ∈ Σ_{n} and 𝔈 ≡ 𝔇 ⊧ Σ_{n} we must have 𝔈 = (𝔄_{n+1})_{A_{n}} ⊧ σ.

Now let 𝔄 be the union of the chain. By hypothesis 𝔄 ⊧ T . It is easy to check that |A| = κ. To check that 𝔄 is existentially closed, let 𝔅 ⊧ T with 𝔄 ⊆ 𝔅 and let σ be an existential sentence of Th𝔅_{A}. Since σ can involve only finitely many constant symbols, σ is a sentence of L_{A_{n}} for some n ∈ ℕ. Thus 𝔄_{n+1} ⊆ 𝔄 ⊆ 𝔅 gives that (𝔄_{n+1})_{A_{n}} ⊧ σ. Since σ is existential (see Exercise 17 again) we get that 𝔄 ⊧ σ. This completes the proof of the claim.

We now claim that T is model complete using Theorem 14 by showing that every model 𝔄 of T is existentially closed. There are three cases to consider:

(1) |A| = κ
(2) |A| > κ
(3) |A| < κ

where T is κ-categorical.

Case (1). Let 𝔄^{∗} be an existentially closed model of T of size κ. Then there is an isomorphism f : 𝔄 → 𝔄^{∗}. Hence 𝔄 is existentially closed.

Case (2). Let σ be an existential sentence of L_{A} and 𝔅 ⊧ T such that 𝔄 ⊆ 𝔅 and 𝔅_{A} ⊧ σ. Let X = {a ∈ A : c_{a} occurs in σ}. By the Downward Löwenheim-Skolem Theorem we can find 𝔄′ such that 𝔄′ ≺ 𝔄, X ⊆ A′ and |A′| = κ. Now by Case (1) 𝔄′ is existentially closed and we have 𝔄′ ⊆ 𝔅 and σ in L_{A′} so 𝔄′_{A′} ⊧ σ. But since σ ∈ Th(𝔄′_{A′}) and 𝔄′ ≺ 𝔄 we have 𝔄_{A} ⊧ σ.

Case (3). Let σ and 𝔅 be as in case (2). By the Upward Löwenheim-Skolem Theorem we can find 𝔄′ such that 𝔄 ≺ 𝔄′ and |𝔄′| = κ. By case (1) 𝔄′ is existentially closed.

Claim. There is a model 𝔅′ such that 𝔄′ ⊆ 𝔅′ and 𝔅_{A} ≡ 𝔅′_{A}.

Assuming this claim, we have 𝔅′ ⊧ T and 𝔅′_{A} ⊧ σ and by the fact that 𝔄′ is existentially closed we have 𝔄′_{A′} ⊧ σ. Since 𝔄 ≺ 𝔄′ we have 𝔄_{A} ⊧ σ.

The following lemma implies the claim and completes the proof of the theorem. □

Lemma 8. Let 𝔄, 𝔅 and 𝔄′ be models for L such that 𝔄 ⊆ 𝔅 and 𝔄 ≺ 𝔄′. Then there is a model 𝔅′ for L such that 𝔄′ ⊆ 𝔅′ and 𝔅_{A} ≡ 𝔅′_{A}.

Proof. Let 𝔄, 𝔅, 𝔄′ and L be as above. Note that since 𝔄 ⊆ 𝔅 we have 𝔅_{A} ⊧ △_{𝔄} and so 𝔄_{A} ⊆ 𝔅_{A}.

Let τ be a sentence from △_{𝔄′}. Let {d_{j} : 0 ≤ j ≤ m} be the constant symbols from L_{A′} \ L_{A} appearing in τ. Obtain a quantifier free formula φ(u_{0}, …, u_{m}) of L_{A} by exchanging each d_{j} in τ with a new variable u_{i}. Since 𝔄′_{A′} ⊧ τ we have 𝔄′_{A} ⊧ ∃u_{0} … ∃u_{m}φ. Since 𝔄 ≺ 𝔄′ we have 𝔄_{A} ≺ 𝔄′_{A} and so 𝔄_{A} ⊧ ∃u_{0} … ∃u_{m}φ. Since 𝔄_{A} ⊆ 𝔅_{A}, 𝔅_{A} ⊧ ∃u_{0} … ∃u_{m}φ. Hence for some b_{0}, …, b_{m} in B, 𝔅_{A} ⊧ φ[b_{0}, …, b_{m}]. Expand 𝔅_{A} to be a model 𝔅_{A}^{∗} for the w language L_{A} ∪{d_{j} : 0 ≤ j ≤ m} by interpreting each d_{j} as b_{j}. Then 𝔅_{A}^{∗} ⊧ τ and so Th(𝔅_{A})∪{τ} is satisfiable.

This shows that Th𝔅_{A} ∪ Σ is satisfiable for each finite subset Σ ⊆ △_{𝔄′}. By the Compactness Theorem there is a model ℭ ⊧ △_{𝔄′} ∪ Th𝔅_{A}. Using the Diagram Lemma for the language L_{A} we obtain a model 𝔅′ for L such that 𝔄′_{A} ⊆ 𝔅′_{A} and 𝔅′_{A} ≅ ℭ|L_{A}. Hence 𝔅′_{A} ⊧ Th𝔅_{A} and so 𝔅′_{A} ≡ 𝔅_{A}.

□

Exercise 20. Suppose 𝔄 ≺ 𝔄′ are models for L. Prove that for each sentence σ of L_{A}, if △_{𝔄′} ⊧ σ then △_{𝔄} ⊧ σ.

Exercise 21. Prove that if T has a universal-existential set of axioms, then the union of a chain of models of T is also a model of T .

Remark. The converse of this last exercise is also true; it is usually called the Chang - Łoś - Suszko Theorem.

Theorem 16. The following theories are model complete:

(1) dense linear orders without endpoints. (DLO)

(2) algebraically closed fields. (ACF)

Proof. (DLO): This theory has a universal existential set of axioms so that it is closed under unions of chains. It is ℵ_{0}-categorical (by Exercise 10) so Lindström’s test applies.

(ACF): We first prove that for any fixed characteristic p, the theory of algebraically closed fields of characteristic p is model complete. The proof is similar to that for DLO, with ℵ_{1}-categoricity (Lemma 7 ).

Let 𝔄 ⊆ 𝔅 be algebraically closed fields. They must have the same characteristic p. Therefore 𝔄 ≺ 𝔅.

□

Corollary 4. Any true statement about the rationals involving only the usual ordering is also true about the reals.

Proof. Let 𝔄 = ⟨ℚ,<_{1} <_{1} <_{1}⟩ and 𝔅 = ⟨ℝ,<_{2} <_{2} <_{2}⟩ where <_{1} <_{1} <_{1} and <_{2} <_{2} <_{2} are the usual orderings. The precise version of this corollary is: 𝔄 ≺ 𝔅. This follows from Theorem 14 and Theorem 16 and the easy facts that 𝔄 ⊧ DLO, 𝔅 ⊧ DLO and 𝔄 ⊆ 𝔅. The reader will appreciate the power of these theorems by trying to prove 𝔄 ≺ 𝔅 directly, without using them. □

Corollary 5. (Hilbert’s Nullstellensatz)

Let Σ be a finite system of polynomial equations and inequations in several variables with coefficients in the field 𝔄. If Σ has a solution in some field extending 𝔄 then Σ has a solution in the algebraic closure of 𝔄.

Proof. Let σ be the existential sentence of the language L_{A} which asserts the fact that there is a solution of Σ. Suppose Σ has a solution in a field 𝔅 with 𝔄 ⊆ 𝔅. Then 𝔅_{A} ⊧ σ. So 𝔅′_{A} ⊧ σ where 𝔅′ is the algebraic closure of 𝔅. Let 𝔄′ be the algebraic closure of 𝔄. Since 𝔄 ⊆ 𝔅, we have 𝔄′ ⊆ 𝔅′.

By Theorem 16, ACF is model complete, so 𝔄′ ≺ 𝔅′. Hence 𝔄′_{A} ≡ 𝔅′_{A} and 𝔄′_{A} ⊧ σ.

□

Remark. We cannot apply Lindström’s Test to the theory of real closed ordered fields (RCF) because RCF is not categorical in any infinite cardinal. This is because, as demonstrated in Theorem 11, RCF neither implies nor denies the existence of infinitesimals. Nevertheless, as we shall later prove, RCF is indeed model complete.

Exercise 22. Use Exercise 19 and the fact that RCF is model complete to show that the theory RCF ∪ △_{𝔔} is complete, where 𝔔 is from Example 3. Hint: step 0 – the rationals, step 1 – the algebraic numbers, step 2 …

CHAPTER 5 The Seventeenth Problem

We will give a complete proof later that RCF, the theory of real closed ordered fields, is model complete. However, by assuming this result now, we can give a solution to the seventeenth problem of the list of twenty-three problems of David Hilbert’s famous address to the 1900 International Congress of Mathematicians in Paris.

Corollary 6. (E. Artin) Let q(x_{1}, …, x_{n}) be a rational function with real coefficients, which is positive definite. i.e.

q(a_{1}, …, a_{n}) ≥ 0 for all a_{1}, …, a_{n} ∈ ℝ

Then there are finitely many rational functions with real coefficients f_{1}(x_{1}, …, x_{n}), …, f_{m}(x_{1}, …, x_{n}) such that

q(x_{1}, …, x_{n}) = ∑_{j=1}^{m}(f_{j}(x_{1}, …, x_{n}))^{2}

We give a proof of this theorem after a sequence of lemmas. The first lemma just uses calculus to prove the special case of the theorem in which q is a polynomial in only one variable. This result probably motivated the original question.

Lemma 9. A positive definite real polynomial is the sum of squares of real polynomials.

Proof. We prove this by induction on the degree of the polynomial. Let p(x) ∈ ℝ[x] with degree deg(p) ≥ 2 and p(x) ≥ 0 for all real x. Let p(a) = min{p(x) : x ∈ ℝ}, so

p(x) = (x − a)q(x) + p(a) and p′(a) = 0

for some polynomial q. But

p′(a) = [(x − a)q′(x) + q(x)]|_{x=a} = q(a)

so q(a) = 0 and q(x) = r(x)(x − a) for some polynomial r(x). So

p(x) = p(a) + (x − a)^{2}r(x).

For all real x we have

(x − a)^{2}r(x) = p(x) − p(a) ≥ 0.

Since r is continuous, r(x) ≥ 0 for all real x, and deg(r) = deg(p) − 2. So, by induction r(x) = ∑_{i=1}^{n} (r_{i}(x))^{2} where each r_{i}(x) ∈ ℝ[x].

So p(x) = p(a) + ∑_{i=1}^{n}(x − a)^{2} (r_{i}(x))^{2} .

i.e. p(x) = [\sqrt{p(a)}]^{2} + ∑_{i=1}^{n} [(x − a)r_{i}(x)]^{2} .

□

The following lemma shows why we deal with sums of rational functions rather than sums of polynomials.

Lemma 10. x^{4}y^{2} + x^{2}y^{4} − x^{2}y^{2} + 1 is positive definite, but not the sum of squares of polynomials.

Proof. Let the polynomial be p(x, y). A little calculus shows that the minimum value of p is \frac{26}{27} and confirms that p is positive definite.

Suppose

p(x, y) = ∑_{i=1}^{l} (q_{i}(x, y))^{2}

where q_{i}(x, y) are polynomials, each of which is the sum of terms of the form ax^{m}y^{n}. First consider powers of x and the largest exponent m which can occur in any of the q_{i}. Since no term of p contains x^{6} or higher powers of x, we see that we must have m ≤ 2. Considering powers of y similarly gives that each n ≤ 2. So each q_{i}(x, y) is of the form:

a_{i}x^{2}y^{2} + b_{i}x^{2}y + c_{i}xy^{2} + d_{i}x^{2} + e_{i}y^{2} + f_{i}xy + g_{i}x + h_{i}y + k_{i}

for some coefficients a_{i}, b_{i}, c_{i}, d_{i}, e_{i}, f_{i}, g_{i}, h_{i} and k_{i}. Comparing coefficients of x^{4}y^{4} in p and the sum of the q_{i}^{2} gives

0 = ∑_{i=1}^{l} a_{i}^{2}

so each a_{i} = 0. Comparing the coefficients of x^{4} and y^{4} gives that each d_{i} = 0 = e_{i}. Now comparing the coefficients of x^{2} and y^{2} gives that each g_{i} = 0 = h_{i}. Now comparing the coefficients of x^{2}y^{2} gives

−1 = ∑_{i=1}^{l} f_{i}^{2}

which is impossible.

□

The next lemma is easy but useful.

Lemma 11. The reciprocal of a sum of squares is a sum of squares.

Proof. For example

\frac{1}{A^{2} + B^{2}} = \frac{A^{2} + B^{2}}{(A^{2} + B^{2})^{2}} = [\frac{A}{A^{2} + B^{2}} ]^{2} + [\frac{B}{A^{2} + B^{2}} ]^{2}

□

The following lemma is an algebraic result of E. Artin and O. Schreier, who invented the theory of real closed fields.

Lemma 12. Let 𝔄 = ⟨A,+ + +,···,< < <_{A},000,111⟩ be an ordered field such that each positive element of A is the sum of squares of elements of A. Let 𝔅 be a field containing the reduct of 𝔄 to {+, ·, 0, 1} as a subfield and such that zero is not the sum of non-zero squares in 𝔅.

Let b ∈ B \ A be such that b is not the sum of squares of elements of B. Then there is an ordering < < <_{B} on B with b < < <_{B} 0 such that 𝔄 is an ordered subfield of ⟨B,+ + +,···,< < <_{B},000,111⟩ .

Proof. It suffices to find a set P ⊆ B of “positive elements” of B such that (1) −b ∈ P

(2) 0 ∉ P

(3) c^{2} ∈ P for each c ∈ B \ {0}

(4) P is closed under + and ·

(5) for any c ∈ B \ {0} either c ∈ P or −c ∈ P. Once P has been obtained, we define < < <_{B} as follows:

c_{1} < < <_{B} c_{2} iff c_{2} − c_{1} ∈ P.

For each a ∈ A, if 0 < < <_{A} a then a is a sum of squares and so by (3) and (4) a ∈ P. Thus < < <_{B} extends < < <_{A}.

So that all that remains to do is to construct such a P. The first approximation to P is P_{0}.

Let P_{0} = {∑_{i=1}^{l} c_{i}^{2} − ∑_{j=1}^{m} d_{j}^{2}b : l, m ∈ ℕ, c_{i} ∈ B, d_{j} ∈ B not all zero}

We claim that (1), (2), (3) and (4) hold for P_{0}. (1) and (3) are obvious. In order to verify (2), note that if ∑_{j=1}^{m} d_{j}^{2}b = ∑_{i=1}^{l} c_{i}^{2}, then by the previous lemma about reciprocals of sums of squares, b would be a sum of squares. Now (4) holds by definition of P_{0}, noting that c_{i}^{2}(−d_{j}^{2}b) = −(c_{i}d_{j})^{2}b and (−d_{j}^{2}b)(−d_{k}^{2}b) = (d_{j}d_{k}b)^{2}.

We now construct larger and larger versions of P_{0} to take care of requirement (5). We do this in the following way. Suppose P_{0} ⊆ P_{1}, P_{1} satisfies (1), (2), (3) and (4), and c ∉ P_{1} ∪ {0}. We define P_{2} to be:

{p(−c) : p is a polynomial with coefficients in P_{1}}.

It is easy to see that −c ∈ P_{2}, P_{1} ⊆ P_{2} and that (1), (3) and (4) hold for P_{2}.

To show that (2) holds for P_{2} we suppose that p(−c) = 0 and bring forth a contradiction. Considering even and odd exponents we obtain:

p(x) = q(x^{2}) + xr(x^{2})

for some polynomials q and r with coefficients in P_{1}.

If q(c^{2}) = 0, then by (3) and (4), q must be the zero polynomial and r could not be. But we would have

0 = p(−c) = −cr(c^{2})

which gives r(c^{2}) = 0 and a contradiction to (3) and (4). Similarly, r(c^{2}) ≠ 0. Now

0 = p(−c) = q(c^{2}) − cr(c^{2})

means that

c = q(c^{2}) · r(c^{2}) · (\frac{1}{r(c^{2})})^{2}

and since each of the factors on the right hand side is in P_{1} we get a contradiction.

□

Now we need:

Lemma 13. Every ordered field can be embedded as a submodel of a real closed ordered field.

Proof. It suffices to prove that for every ordered field 𝔄 there is an ordered field 𝔅 such that 𝔄 ⊆ 𝔅 and for each natural number n ≥ 1, 𝔅 ⊧ σ_{n} where σ_{n} is the sentence in the language of field theory which formally states:

If p is a polynomial of degree at most n and w < y such that p(w) < 0 < p(y) then there is an x such that w < x < y and p(x) = 0.

Consider the statement called IH(n):

For any ordered field 𝔈 there is an ordered field 𝔉 such that 𝔈 ⊆ 𝔉 and 𝔉 ⊧ σ_{n}.

IH(1) is true since any ordered field 𝔈 ⊧ σ_{1}. We will prove below that for each n, IH(n) implies IH(n + 1).

Given our model 𝔄 ⊧ ORF, we will then be able to construct a chain of models:

𝔄 ⊆ 𝔅_{1} ⊆ 𝔅_{2} ⊆ … ⊆ 𝔅_{n} ⊆ 𝔅_{n+1} ⊆ ⋯

such that each 𝔅_{n} ⊧ ORF ∪ {σ_{n}}. Let 𝔅 be the union of the chain. Since the theory ORF is preserved under unions of chains (see Exercise 21), 𝔅 ⊧ ORF. Furthermore, the nature of the sentences σ_{n} allows us to conclude that for each n, 𝔅 ⊧ σ_{n} and so 𝔅 ⊧ RCF. All that remains is to prove that for each n, IH(n) implies IH(n + 1). We first make a claim:

Claim. If 𝔈 ⊧ ORF ∪ {σ_{n}} and p is a polynomial of degree at most n + 1 with coefficients from E and a < d are in E such that p(a) < 0 < p(d) then there is a model 𝔉 such that 𝔈 ⊆ 𝔉, 𝔉 ⊧ ORF and there is b ∈ F such that a < b < d and p(b) = 0.

Let us first see how this claim helps us to prove that IH(n) implies IH(n+1). Let 𝔈 ⊧ ORF; we will use the claim to build a model 𝔉 such that 𝔈 ⊆ 𝔉 and 𝔉 ⊧ σ_{n+1}.

We first construct a chain of models of ORF

𝔈 = 𝔈_{0} ⊆ 𝔈_{1} ⊆ … ⊆ 𝔈_{m} ⊆ 𝔈_{m+1} ⊆ ⋯

such that for each m and each polynomial p of degree at most n+1 with coefficients from E_{m} and each pair of a, d of elements of E_{m} such that p(a) < 0 < p(d) there is a b ∈ E_{m+1} such that a < b < d and p(b) = 0.

Suppose 𝔈_{m} has been constructed; we construct 𝔈_{m+1} as follows: let Σ_{m} be the set of all existential sentences of L_{E_{m}} of the form

(∃x)(c_{a} < x ∧ x < c_{d} ∧ p(x) = 0)

where p is a polynomial of degree at most n + 1 and such that c_{a}, c_{d} and the coefficients of the polynomial p are constant symbols from L_{E_{m}} and

(𝔈_{m})_{E_{m}} ⊧ p(c_{a}) < 0 ∧ 0 < p(c_{d})

We claim that

ORF ∪ △_{𝔈_{m}} ∪ Σ_{m}

is satisfiable.

Using the Compactness Theorem, it suffices to find, for each finite subset {τ_{1}, …, τ_{k}} of Σ_{m}, a model ℭ such that 𝔈_{m} ⊆ ℭ and

ℭ ⊧ ORF ∪ {τ_{1}, …, τ_{k}}.

By IH(n), obtain a model 𝔉_{1} such that 𝔈_{m} ⊆ 𝔉_{1} and 𝔉_{1} ⊧ ORF ∪ {σ_{n}}. By the claim, obtain a model 𝔉_{2} such that 𝔉_{1} ⊆ 𝔉_{2} and 𝔉_{2} ⊧ ORF∪{τ_{1}}. Again by IH(n), obtain 𝔉_{3} such that 𝔉_{2} ⊆ 𝔉_{3} and 𝔉_{3} ⊧ ORF ∪ {σ_{n}}. Again by the claim, obtain 𝔉_{4} such that 𝔉_{3} ⊆ 𝔉_{4} and 𝔉_{4} ⊧ ORF ∪ {τ_{2}}. Continue in this manner, getting models of ORF

𝔈_{m} ⊆ 𝔉_{1} ⊆ … ⊆ 𝔉_{2k}

with each 𝔉_{2j} ⊧ τ_{j}. Since each τ_{j} is existential, we get that 𝔉_{2k} is a model of each τ_{j} (see Exercise 17).

Let 𝔇 ⊧ ORF ∪ △_{𝔈_{m}} ∪ Σ_{m}

and then use the Diagram Lemma to get 𝔈_{m+1} such that 𝔈_{m} ⊆ 𝔈_{m+1}, 𝔈_{m+1} ⊧ ORF and 𝔈_{m+1} ⊧ Σ_{m}, thus satisfying the required property concerning polynomials from E_{m}.

Let 𝔉 be the union of the chain. Since ORF is a universal-existential theory, 𝔉 ⊧ ORF (see Exercise 21) and 𝔉 ⊧ σ_{n+1} by construction. So IH(n + 1) is proved.

We now finish the entire proof by proving the claim.

Proof of Claim. Suppose that p(x) = q(x) · s(x) with the degree of q at most n. Since 𝔈 ⊧ σ_{n} we are guaranteed c ∈ E with a < c < d and q(c) = 0. Hence p(c) = 0 and we can let 𝔉 = 𝔈.

So we can assume that p is irreducible over E. Introduce a new element b to E where the place of b in the ordering is given by:

b < x iff p(y) > 0 for all y with x ≤ y ≤ d.

Note that continuity-style considerations show that b < d.

The fact that p is irreducible over E means that we can extend ⟨E,+ + +,···,000,111⟩ by quotients of polynomials in b of degree ≤ n in the usual way to form a field ⟨F,+ + +,···,000,111⟩ in which p(b) = 0. We leave the details to the reader, but point out that the construction cannot force q(b) = 0 for any polynomial q(x) with coefficients from E of degree ≤ n. This is because we could take such a q(x) of lowest degree and divide p(x) by it to get

p(x) = q(x) · s(x) + r(x)

where degree of r is less than the degree of q. This means that r(x) = 0 constantly and so p could have been factored over E.

Now we must expand ⟨F,+ + +,···,000,111⟩ to an ordered field 𝔉 while preserving the order of 𝔈. We are aided in this by the fact that if q is a polynomial of degree at most n with coefficients from E then there are a_{1} and a_{2} in E such that a_{1} < b < a_{2} and q doesn’t change sign between a_{1} and a_{2}; this comes from the fact that 𝔈 ⊧ σ_{n}.

□

Proof of the Corollary. Using Lemma 11 we see that it suffices to prove the corollary for a polynomial p(x_{1}, …, x_{n}) such that p(a_{1}, …, a_{n}) ≥ 0 for all a_{1}, …, a_{n} ∈ ℝ.

Let 𝔅 = ⟨ℝ(x_{1}, …, x_{n}),+ + +, ·, 0, 1⟩ be the field of “rational functions”. Note that 𝔅 contains the reduct of ℜ to {+, ·, 0, 1} as a subfield, where ℜ is defined as in Example 3 as the usual real numbers.

By Lemma 12, if p is not the sum of squares in 𝔅, then we can find an ordering <_{B} on 𝔅, extending the ordering on the reals, such that the expansion 𝔅′ of 𝔅 is an ordered field and p(x_{1}, …, x_{n}) <_{B} 0.

We now use Lemma 13 to embed 𝔅′ as a submodel of a real closed field 𝔐, 𝔅′ ⊆ 𝔐.

Let φ(v_{1}, …, v_{n}) be the quantifier free formula which we informally write as p(v_{1}, …, v_{n}) < 0 where φ involves constant symbols c_{r_{i}} for the real coefficients r_{i} of p. Let ψ be the formula of the language of field theory, obtained from φ by substituting a new variable u_{i} for each c_{r_{i}}. We have

𝔅′ ⊧ ∃v_{1} … ∃v_{n}ψ[r_{1}, …, r_{k}]
and so 𝔐 ⊧ ∃v_{1} … ∃v_{n}ψ[r_{1}, …, r_{k}]

Since RCF is model complete and ℜ ⊆ 𝔅′ ⊆ 𝔐, Theorem 14 gives ℜ ≺ 𝔐 and so

ℜ ⊧ ∃v_{1} … ∃v_{n}ψ[r_{1}, …, r_{k}]

i.e. there exist a_{1}, …, a_{n} in ℝ such that p(a_{1}, …, a_{n}) < 0.

□

Hilbert also asked:

If the coefficients of a positive definite rational function are rational numbers (i.e. it is an element of ℚ(x_{1}, …, x_{n})) is it in fact the sum of squares of elements of ℚ(x_{1}, …, x_{n})?

The answer is “yes” and the proof is very similar. Let 𝔔 = ⟨ℚ,+ + +.···,< < <,000,111⟩ be the ordered field of rationals as in Example 3. Lemma 12 holds for 𝔄 = 𝔔 and 𝔅 = ⟨ℚ(x_{1}, …, x_{n}),+ + +,···,000,111⟩; by Lemma 11 every positive rational number is the sum of squares since every positive integer is the sum of squares n = 1 + 1 + ⋯ + 1.

Exercise 23. Finish the answer to Hilbert’s question by making any appropriate changes to the proof of the corollary. Hint: create a real closed ordered field into which 𝔅′_{ℚ} and ℜ_{ℚ} are each isomorphically embedded. Exercise 15 and Exercise 22 may be useful.

CHAPTER 6 Submodel Completeness

Definition 30. A theory T is said to admit elimination of quantifiers in L whenever for each formula φ(v_{0}, …, v_{p}) of L there is a quantifier free formula ψ(v_{0}, …, v_{p}) such that:

T ⊧ (∀v_{0} … ∀v_{p})(φ(v_{0}, …, v_{p}) ↔ ψ(v_{0}, …, v_{p}))

Remark. There is a fine point with regard to the above definition. If φ is actually a sentence of L there are no free variables v_{0}, …, v_{p}. So T ⊧ φ ↔ ψ for some quantifier free formula with no free variables. But if L has no constant symbols, there are no quantifier free formulas with no free variables. For this reason we assume that L has at least one constant symbol, or we restrict to those formulas φ with at least one free variable. This will become relevant in the proof of Theorem 17 for (2) ⇒ (3).

Exercise 24. If T admits elimination of quantifiers in L and L has no constant symbols, show that for each sentence σ of L there is a quantifier free formula ψ(v_{0}) such that

T ⊧ σ ↔ ∀v_{0}ψ ↔ ∃v_{0}ψ

Definition 31. A theory T is said to be submodel complete whenever T ∪ △_{𝔄} is complete in L_{A} for each submodel 𝔄 of a model of T .

Exercise 25. Use Theorem 14 and the following theorem to find four proofs that every submodel complete theory is model complete.

Theorem 17. Let T be a theory of a language L. The following are equivalent:

(1) T is submodel complete

(2) If 𝔅 and ℭ are models of T and 𝔄 is a submodel of both 𝔅 and ℭ, then every existential sentence which holds in 𝔅_{A} also holds in ℭ_{A}.

(3) T admits elimination of quantifiers

(4) whenever 𝔄 ⊆ 𝔅, 𝔄 ⊆ ℭ, 𝔅 ⊧ T and ℭ ⊧ T there is a model 𝔇 such that both 𝔅_{A} and ℭ_{A} are elementarily embedded in 𝔇_{A}.

Proof. (1) ⇒ (2)

Let 𝔅 ⊧ T and ℭ ⊧ T with 𝔄 ⊆ 𝔅 and 𝔄 ⊆ ℭ. Then 𝔅_{A} ⊧ T ∪ △_{𝔄} and ℭ_{A} ⊧ T ∪ △_{𝔄}. So (1) and Lemma 6 give 𝔅_{A} ≡ ℭ_{A}. Thus (2) is in fact proved for all sentences, not just existential ones.

(2) ⇒ (3) Lemma 4 shows that it suffices to prove (3) for formulas in prenex normal form. We do this by induction on the prenex rank of φ. This claim is the first step.

Claim. For each existential formula φ(v_{0}, …, v_{p}) of L there is a quantifier free formula ψ(v_{0}, …, v_{p}) such that

T ⊧ (∀v_{0} … ∀v_{p})(φ ↔ ψ)

Proof of Claim. Add new constant symbols c_{0}, …, c_{p} to L to form

L^{∗} = L ∪ {c_{0}, …, c_{p}}

and to form a sentence φ^{∗} of L^{∗} obtained by replacing each free occurrence of v_{i} in φ with the corresponding c_{i}; φ^{∗} is an existential sentence. It suffices to prove that there is a quantifier free sentence σ of L^{∗} such that

T ⊧ φ^{∗} ↔ σ.
Let S = { quantifier free sentences σ of L^{∗} : T ⊧ φ^{∗} → σ}.

It suffices to find some σ in S such that T ⊧ σ → φ^{∗}. Since a finite conjunction of sentences of S is also in S, it suffices to find σ_{1}, …, σ_{n} in S such that

T ⊧ σ_{1} ∧ ⋯ ∧ σ_{n} → φ^{∗}.

If no such finite subset {σ_{1}, …, σ_{n}} of S exists, then each

T ∪ {σ_{1}, …, σ_{n}} ∪ {¬φ^{∗}}

would be satisfiable. So it suffices to prove that T ∪ S ⊧ φ^{∗}.

Let ℭ ⊧ T ∪ S with the intent of proving that ℭ ⊧ φ^{∗}. Let 𝔄 be the least submodel of ℭ in the sense of the language L^{∗}. That is, every element of 𝔄 is the interpretation of a constant symbol from L ∪ {c_{0}, …, c_{p}} or built from these using the functions of ℭ. As in the proof of Theorem 14, we can ensure that L^{∗} ⊆ L_{A}.

Let P = {σ ∈ △_{𝔄} : σ is a sentence of L^{∗}}.

We wish to show that T ∪ {φ^{∗}} ∪ P is satisfiable. By compactness, it suffices to consider T ∪ {φ^{∗}, τ} where τ is a sentence in P. If this set is not satisfiable then T ⊧ φ^{∗} → ¬τ so that by definition of S we have ¬τ ∈ S and hence ℭ ⊧ ¬τ. But this is impossible since 𝔄 ⊆ ℭ means that ℭ_{A} ⊧ △_{𝔄}.

Let 𝔅′ ⊧ T ∪{φ^{∗}}∪P. The interpretations of {c_{0}, …, c_{p}} generate a submodel of 𝔅′ isomorphic to 𝔄. So there is a model 𝔅 for L^{∗} such that 𝔅 ≅ 𝔅′ and 𝔄 ⊆ 𝔅.

In order to invoke (2) we use the restrictions 𝔄|L, 𝔅|L and ℭ|L of 𝔄, 𝔅 and ℭ to the language L. We have 𝔅|L ⊧ T , ℭ|L ⊧ T , 𝔄|L ⊆ 𝔅|L and 𝔄|L ⊆ ℭ|L. φ^{∗} is an existential sentence of L^{∗} ⊆ L_{A} and since 𝔅′ ⊧ φ^{∗} we have (𝔅|L)_{A} ⊧ φ^{∗}. So by (2), (ℭ|L)_{A} ⊧ φ^{∗} and finally ℭ ⊧ φ^{∗} which completes the proof of the claim.

We now do the general cases for the proof of the induction on prenex rank. There are two cases, corresponding to the two methods available for increasing the number of alternations of quantifiers:

(a) the addition of universal quantifiers

(b) the addition of existential quantifiers.

For case (a), suppose φ(v_{0}, …, v_{p}) is ∀w_{0} … ∀w_{m}χ(v_{0}, …, v_{p}, w_{0}, …, w_{m}) and χ has prenex rank lower than φ. Then ¬χ also has prenex rank lower than φ and we can use the inductive hypothesis on ¬χ to obtain a quantifier free formula θ_{1}(v_{0}, …, v_{p}, w_{0}, …, w_{m}) such that

\begin{matrix}T & ⊧ (∀v_{0} … ∀v_{p})(∀w_{0} … ∀w_{m})(¬χ ↔ θ_{1}) \\ So T & ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{m}¬χ ↔ ∃w_{0} … ∃w_{m}θ_{1}) \end{matrix}

By the claim there is a quantifier free formula θ_{2}(v_{0}, …, v_{p}) such that

\begin{matrix}T & ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{m}θ_{1} ↔ θ_{2}) \\ So T & ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{m}¬χ ↔ θ_{2}) \\ So T & ⊧ (∀v_{0} … ∀v_{p})(∀w_{0} … ∀w_{m}χ ↔ ¬θ_{2}) \end{matrix}

and so ¬θ_{2} is the quantifier free formula equivalent to φ.

For case (b), suppose φ(v_{0}, …, v_{p}) is ∃w_{0} … ∃w_{m}χ(v_{0}, …, v_{p}, w_{0}, …, w_{m}) and χ has prenex rank lower than φ. We use the inductive hypothesis on χ to obtain a quantifier free formula θ_{1}(v_{0}, …, v_{p}, , w_{0}, …, w_{m}) such that

\begin{matrix}T & ⊧ (∀v_{0} … ∀v_{p})(∀w_{0} … ∀w_{m})(χ ↔ θ_{1}) \\ So T & ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{m}χ ↔ ∃w_{0} … ∃w_{m}θ_{1}) \end{matrix}

By the claim there is a quantifier free formula θ_{2}(v_{0}, …, v_{p}) such that

\begin{matrix}T & ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{m}θ_{1} ↔ θ_{2}) \\ So T & ⊧ (∀v_{0} … ∀v_{p})(∃w_{0} … ∃w_{m}χ ↔ θ_{2}) \end{matrix}

and so θ_{2} is the quantifier free formula equivalent to φ. This completes the proof. (3) ⇒ (4) Let 𝔄 ⊆ 𝔅, 𝔄 ⊆ ℭ, 𝔅 ⊧ T and ℭ ⊧ T . Using the Elementary Diagram

Lemma it will suffice to show that Th(𝔅_{B})∪ Th(ℭ_{C}) is satisfiable. Without loss of generosity, we can ensure that L_{B} ∩ L_{C} = L_{A}.

By the Robinson Consistency Theorem, it suffices to show that there is no sentence σ of L_{A} such that both:

Th(𝔅_{B}) ⊧ σ and Th(ℭ_{C}) ⊧ ¬σ

Suppose σ is such a sentence and let {c_{a_{0}}, …, c_{a_{p}}} be the set of constant symbols from L_{A} \ L appearing in σ.

Let φ(u_{0}, …, u_{p}) be obtained from σ by exchanging each c_{a_{i}} for a new variable u_{i}. Let ψ(u_{0}, …, u_{p}) be the quantifier free formula from (3):

T ⊧ (∀u_{0}, …, ∀u_{p})(φ ↔ ψ)

Let ψ^{∗} be the result of substituting c_{a_{i}} for each u_{i} in ψ. ψ^{∗} is also quantifier free.

Since 𝔅_{B} ⊧ σ, 𝔅 ⊧ φ[a_{0}, …, a_{p}]. Since 𝔅 ⊧ T , 𝔅 ⊧ ψ[a_{0}, …, a_{p}] and so 𝔅_{A} ⊧ ψ^{∗}. Since ψ^{∗} is quantifier free and 𝔄_{A} ⊆ 𝔅_{A} we have 𝔄_{A} ⊧ ψ^{∗}; since 𝔄_{A} ⊆ ℭ_{A} we then get that ℭ_{A} ⊧ ψ^{∗}. Hence ℭ ⊧ ψ[a_{0}, …, a_{p}] and then since ℭ ⊧ T we then get that ℭ ⊧ φ[a_{0}, …, a_{p}]. But then this means that ℭ_{A} ⊧ σ and so ℭ_{C} ⊧ σ so σ is in Th(ℭ_{C}) and we are done.

(4) ⇒ (1) Let 𝔅 ⊧ T and 𝔄 ⊆ 𝔅; we show that T ∪ △_{𝔄} is complete. Noting that 𝔅_{A} ⊧ T ∪ △_{𝔄}, we see that it suffices by Lemma 6 to show that 𝔅_{A} ≡ ℭ′ for each ℭ′ ⊧ T ∪ △_{𝔄}.

For each such ℭ′, by the Diagram Lemma, there is a model ℭ for L such that 𝔄 ⊆ ℭ and ℭ_{A} ≅ ℭ′. Then ℭ ⊧ T so by (4) there is a 𝔇 into which both 𝔅_{A} and ℭ_{A} are elementarily embedded.

In particular 𝔅_{A} ≡ 𝔇_{A} ≡ ℭ_{A} so we are done.

□

Example 11. (Chang and Keisler) Let T be the theory in the language L = {U, V, W, R, S} where U, V and W are unary relation symbols and R and S are binary relation symbols having axioms which state that there are infinitely many things, that U ∪ V ∪ W is everything, that U, V and W are pairwise disjoint, that R is a one-to-one function from U onto V and that S is a one-to-one function from U ∪ V onto W.

Exercise 26. Show that T above is complete and model complete but not submodel complete.

Hints: For completeness, use the Łoś-Vaught test and for model completeness use Lindström’s test. For submodel completeness use (2) of the theorem with 𝔅 ⊧ T and 𝔄 ⊆ 𝔅 where a ∈ A = {b ∈ B : 𝔅 ⊧ W (v_{0})[b]} along with the sentence

(∃v_{0})(U(v_{0}) ∧ S(v_{0}, c_{a})).

Remark. We will prove in the next chapter that each of the following theories admits elimination of quantifiers:

(1) dense linear orders with no end points (DLO)

(2) algebraically closed fields (ACF)

(3) real closed ordered fields (RCF)

C. H. Langford proved elimination of quantifiers for DLO in 1924. The cases of ACF and RCF were more difficult and were done by A. Tarski. Thus, by Exercise 25, we will have model completeness of RCF which was promised at the beginning of Chapter 5.

Exercise 27. Use the fact that RCF admits elimination of quantifiers to prove that RCF is complete; another result originally due to A. Tarski.

Hint: Show that the standard model of Number Theory of Example 6 can be isomorphically embedded into any real closed field and then use (4) from Theorem 17.

Exercise 28. Let T be the theory DLO in the language L = {<, c_{1}, c_{2}} where c_{1} and c_{2} are constant symbols. Use the fact that DLO admits elimination of quantifiers in its own language {<} to show that T is submodel complete. But, show also, that T is not complete.

As an application of quantifier elimination of ACF we have the following:

Corollary 7. (Tarski) The truth value of any algebraic statement about the complex numbers can be determined algebraically in a finite number of steps.

Proof. Let ℭ be the complex numbers in the language of field theory L; let σ be a sentence of L_{ℂ}. Then let A be the finite subset of ℂ consisting of those elements of ℂ (other than 0 or 1 ) which are mentioned in σ. Let φ be the formula of L formed by exchanging each c_{a} for a new variable. Then ACF ⊧ ∀v_{0} … ∀v_{p}(φ ↔ ψ) for some quantifier free ψ. Hence ℭ ⊧ σ iff ℭ ⊧ φ[a_{0}, …, a_{p}] iff ℭ ⊧ ψ[a_{0}, …, a_{p}] but checking this last statement amounts to evaluating finitely many polynomials in a_{0}, …, a_{p}.

□

Remark. In fact Tarski’s original proof actually gave an explicit method for finding the quantifier free formulas and this led, via the corollary above, to an effective decision proceedure for determining the truth of elementary algebraic statements about the reals or the complex numbers.

As an application of quantifier elimination of RCF we have:

Corollary 8. (The Tarski-Seidenberg Theorem)

The projection of a semi-algebraic set in ℝ^{n} to ℝ^{m} for m < n is also semialgebraic. The semi-algebraic sets of ℝ^{n} are defined to be all those subsets of ℝ^{n} which can be obtained by repeatedly taking unions and intersections of sets of the form

{⟨x_{1}, …, x_{n}⟩ ∈ ℝ^{n} : p(x_{1}, …, x_{n}) = 0}
and {⟨x_{1}, …, x_{n}⟩ ∈ ℝ^{n} : q(x_{1}, …, x_{n}) < 0}

where p and q are polynomials with real coefficients.

Proof. We first need two simple results which we state as exercises.

Let ℜ = ⟨ℝ,+ + +,···,< < <, 0, 1⟩ be the usual model of the reals. Let T be RCF considered as a theory in the language L_{ℝ}.

Exercise 29. Since RCF admits elimination of quantifiers, T admits elimination of quantifiers as a theory in the language L_{ℝ}.

Exercise 30. A set X ⊆ ℝ^{n} is semi-algebraic iff there is a quantifier free formula φ(v_{1}, …, v_{n}) of L_{ℝ} such that

X = {⟨x_{1}, …, x_{n}⟩ : ℜ_{ℝ} ⊧ φ[x_{1}, …, x_{n}]}.

Now, in order to prove the corollary, let X ⊆ ℜ^{n} be semi-algebraic and let φ be its associated quantifier free formula. The projection Y of X into ℜ^{m} is

{⟨x_{1}, …, x_{m}⟩ : for some x_{m+1}, …, x_{n} ⟨x_{1}, …, x_{m}, x_{m+1}, …, x_{n}⟩ ∈ X}

So Y = {⟨x_{1}, …, x_{m}⟩ : ℜ_{ℝ} ⊧ ∃v_{m+1} … ∃v_{n}φ[x_{1}, …, x_{m}]}

Since T admits elimination of quantifiers, there is a quantifier free formula θ of L_{ℝ} such that

T ⊧ (∀v_{1} … ∀v_{m})(∃v_{m+1} … ∃v_{n}φ ↔ θ)
So for all x_{1}, …, x_{m}
ℜ_{ℝ} ⊧ ∃v_{m+1} … ∃v_{n}φ[x_{1}, …, x_{m}] iff ℜ_{ℝ} ⊧ θ[x_{1}, …, x_{m}]
So Y = {⟨x_{1}, …, x_{m}⟩ : ℜ_{ℝ} ⊧ θ[x_{1}, …, x_{m}]}

and by the exercise, Y is semi-algebraic.

□

CHAPTER 7 Model Completions

Closely related to the notions of model completeness and submodel completeness is the idea of a model completion.

Definition 32. Let T ⊆ T^{∗} be two theories in a language L. T^{∗} is said to be a model completion of T whenever T^{∗} ∪ △_{𝔄} is satisfiable and complete in L_{A} for each model 𝔄 of T .

Lemma 14. Let T be a theory in a language L.

(1) If T^{∗} is a model completion of T , then for each 𝔄 ⊧ T there is a 𝔅 ⊧ T^{∗} such that 𝔄 ⊆ 𝔅.

(2) If T^{∗} is a model completion of T , then T^{∗} is model complete.

(3) If T is model complete, then it is a model completion of itself.

(4) If T_{1}^{∗} and T_{2}^{∗} are both model completions of T , then T_{1}^{∗} ⊧ T_{2}^{∗} and T_{2}^{∗} ⊧ T_{1}^{∗}.

Proof. (1) Easy. (2) Easier. (3) Easiest. (4) This needs a proof.

Let 𝔄 ⊧ T_{2}^{∗}. It will suffice to prove that 𝔄 ⊧ T_{1}^{∗}.

Let 𝔄_{0} = 𝔄. since 𝔄_{0} ⊧ T and T_{1}^{∗} is a model completion of T we obtain, from (1), a model 𝔄_{1} ⊧ T_{1}^{∗} such that 𝔄_{0} ⊆ 𝔄_{1}. Similarly, since 𝔄_{1} ⊧ T and T_{2}^{∗} is a model completion of T we obtain 𝔄_{2} ⊧ T_{2}^{∗} such that 𝔄_{1} ⊆ 𝔄_{2}.

Continuing in this manner we obtain a chain:

𝔄_{0} ⊆ 𝔄_{1} ⊆ 𝔄_{2} ⊆ … ⊆ 𝔄_{n} ⊆ 𝔄_{n+1} ⊆ ⋯

Let 𝔅 be the union of the chain, ∪{𝔄_{n} : n ∈ ℕ}. For each n ∈ ℕ we have 𝔄_{2n} ⊧ T_{2}^{∗}. By part (2) of this lemma and by part (4) of Theorem 14 we get that for each n, 𝔄_{2n} ≺ 𝔄_{2n+2}. By the Elementary Chain Theorem 𝔄_{0} ≺ 𝔅. Similarly 𝔄_{1} ≺ 𝔅. So 𝔄_{0} ≡ 𝔄_{1} and hence 𝔄 ⊧ T_{1}^{∗}.

□

Remark. Part (4) of the above lemma shows that model completions are essentially unique. That is, if model completions T_{1}^{∗} and T_{2}^{∗} of T are closed theories in the sense of Definition 12 then T_{1}^{∗} = T_{2}^{∗}. Since there is no loss in assuming that model completions are closed theories, we speak of the model completion of a theory T .

Theorem 18. Suppose T ⊆ T^{∗} are theories for a language L such that for each 𝔄 ⊧ T there is a 𝔅 ⊧ T^{∗} with 𝔄 ⊆ 𝔅. The following are equivalent:

(1) T^{∗} is the model completion of T .

(2) For each 𝔄 ⊧ T , 𝔅 ⊧ T^{∗} and ℭ ⊧ T^{∗} such that 𝔄 ⊆ 𝔅 and 𝔄 ⊆ ℭ we have a model 𝔇 such that both 𝔅_{A} and ℭ_{A} are elementarily embedded into 𝔇_{A}.

(3) For each 𝔄 ⊧ T , 𝔅 ⊧ T^{∗} and ℭ ⊧ T^{∗} such that 𝔄 ⊆ 𝔅 and 𝔄 ⊆ ℭ we have a model 𝔇 such that 𝔅_{A} ⊆ 𝔇_{A} and ℭ_{A} is elementarily embedded into 𝔇_{A}.

(4) For each 𝔄 ⊧ T , 𝔅 ⊧ T^{∗} and ℭ ⊧ T^{∗} such that 𝔄 ⊆ 𝔅 and 𝔄 ⊆ ℭ we have a model 𝔇 such that 𝔅_{A} is isomorphically embedded into 𝔇_{A} and ℭ ≺ 𝔇.

Proof. (1) ⇒ (2) By the Elementary Diagram Lemma it suffices to prove that the union of the elementary diagrams of 𝔅_{A} and ℭ_{A}, is satisfiable. By the Robinson Consistency Theorem it suffices to show that there is no sentence σ of L_{A} such that Th𝔅_{A} ⊧ σ and Thℭ_{A} ⊧ ¬σ.

By (1) we have that T^{∗} ∪ △_{𝔄} is a complete theory in L_{A}. By assumption and the Diagram Lemma both 𝔅_{A} ⊧ T^{∗} ∪ △_{𝔄} and ℭ_{A} ⊧ T^{∗} ∪ △_{𝔄}. Therefore 𝔅_{A} ≡ ℭ_{A}. This means that Th𝔅_{A} = Thℭ_{A} and the result follows.

(2) ⇒ (3) and (3) ⇒ (4) easily follow from the definitions.

(4) ⇒ (1) We first show that T^{∗} is model complete using Theorem 14; we show that T^{∗} is existentially complete. Let 𝔄 ⊧ T^{∗}; we show that 𝔄 is existentially closed. Let 𝔅 ⊧ T^{∗} such that 𝔄 ⊆ 𝔅 and let σ be an existential sentence of L_{A} with 𝔅_{A} ⊧ σ; our aim is to prove that 𝔄_{A} ⊧ σ.

We invoke (4) with ℭ = 𝔄 to get a model 𝔇 such that 𝔄 ≺ 𝔇 and 𝔅_{A} is isomorphically embedded into 𝔇_{A}. Referring to Exercise 12 we get a model 𝔈 for L_{A} with 𝔅_{A} ⊆ 𝔈 and 𝔇_{A} ≅ 𝔈. Since σ is existential, By Exercise 17 we have that 𝔈 ⊧ σ; and by Exercise 7, 𝔇_{A} ⊧ σ. Now 𝔄 ≺ 𝔇 implies that 𝔄_{A} ≡ 𝔇_{A} so 𝔄_{A} ⊧ σ and T^{∗} is model complete.

We now show that T^{∗} is the model completion of T . Let 𝔄 ⊧ T ; by the hypothesis on T and T^{∗} we have that T^{∗} ∪△_{𝔄} is satisfiable. We show that T^{∗} ∪△_{𝔄} is complete in L_{A} by showing that for each 𝔅 ⊧ T^{∗} and ℭ ⊧ T^{∗} with 𝔄 ⊆ 𝔅 and 𝔄 ⊆ ℭ we have 𝔅_{A} ≡ ℭ_{A}.

Letting 𝔅 and ℭ be as above, we invoke (4) to obtain a model 𝔇 such that 𝔅_{A} is isomorphically embedded into 𝔇_{A} and ℭ ≺ 𝔇. ℭ ≺ 𝔇 gives that 𝔇 ⊧ T^{∗}. The isomorphic embedding gives us a model 𝔈 such that 𝔅 ⊆ 𝔈 and 𝔇_{A} ≅ 𝔈_{A}. So 𝔈 ⊧ T^{∗} . Using model completeness of T^{∗} and Theorem 14 we can conclude that 𝔅 ≺ 𝔈. We have:

𝔅_{A} ≡ 𝔈_{A} ≡ 𝔇_{A} ≡ ℭ_{A}

and we are done. □

Let’s compare the definitions of model completion and submodel complete. Let T^{∗} be the model completion of T . Then T^{∗} will be submodel complete provided that every submodel of a model of T^{∗} is a model of T . Since T ⊆ T^{∗}, it would be enough to show that every submodel of a model of T is again a model of T . And this is indeed the case whenever T is a universal theory, that is, whenever T has a set of axioms consisting of universal sentences. Unfortunately, this is not always the case.

Our ultimate aim is to show that DLO, ACF and RCF are submodel complete. We will in fact show that these theories are the model completions of LOR, FEI and ORF respectively. See Example 5 to recall the axioms for these theories. Now LOR is a universal theory but FEI and ORF are not. The culprits are the existence axioms for inverses:

∀x∃y(x + y = 0) and ∀x∃y((x ≠ 0) → (y · x = 1))

.

In fact, a submodel 𝔄 of a field 𝔅 is only a commutative semi-ring, not necessarily a subfield. Nevertheless, 𝔄 generates a subfield of 𝔅 in a unique way. This motivates the following definition.

Definition 33. A theory T is said to be almost universal whenever 𝔄 ⊆ 𝔅, 𝔅 ⊧ T and 𝔄 ⊆ ℭ, ℭ ⊧ T imply there are models 𝔇 and 𝔈 such that 𝔇 ⊧ T , 𝔄 ⊆ 𝔇 ⊆ 𝔅 and 𝔈 ⊧ T , 𝔄 ⊆ 𝔈 ⊆ ℭ and 𝔇_{A} ≅ 𝔈_{A}.

Example 12. LOR is almost universal since any universal theory T is almost universal — just let 𝔇 = 𝔈 = 𝔄 and note 𝔄 ⊧ T .

Example 13. FEI is almost universal — just let 𝔇 and 𝔈 be the subfields of 𝔅 and ℭ, respectively, generated by A. The isomorphism 𝔇_{A} ≅ 𝔈_{A} is the natural one obtained from the identity map on A.

Example 14. ORF is almost universal — again just let 𝔇 and 𝔈 be the ordered subfields of 𝔅 and ℭ, respectively, generated by A. The extension of the identity map on A to the isomorphism 𝔇_{A} ≅ 𝔈_{A} is aided by the fact that the order placement of the inverse of an element a is completely determined by the order placement of a.

Theorem 19. Let T and T^{∗} be theories of the language L such that T is almost universal and T^{∗} is the model completion of T . Then T^{∗} is submodel complete.

Proof. We show that condition (2) of Theorem 17 is satisfied. Let 𝔅 and ℭ be models of T^{∗} with 𝔄 a submodel of both 𝔅 and ℭ. We will show that, in fact, 𝔅_{A} ≡ ℭ_{A}.

Now T ⊆ T^{∗} so 𝔅 ⊧ T and ℭ ⊧ T . Since T is almost universal there are models 𝔇 and 𝔈 of T such that 𝔄 ⊆ 𝔇 ⊆ 𝔅, 𝔄 ⊆ 𝔈 ⊆ ℭ and 𝔇_{A} ≅ 𝔈_{A}. So 𝔅_{D} ⊧ T^{∗} ∪ △_{𝔇} and ℭ_{E} ⊧ T^{∗} ∪ △_{𝔈}.

Now 𝔅_{D} is a model for the language L_{D} whereas ℭ_{E} is a model for L_{E}. We wish to obtain a model ℭ′ for L_{D} which “looks exactly like” ℭ_{E}. We just let C′ be C and in fact let ℭ′|L_{A} = ℭ_{E}|L_{A}. The interpretation of a constant symbol c_{d} ∈ L_{D} \ L_{A} is the interpretation of c_{e} ∈ L_{E} \ L_{A} in ℭ_{E} where the isomorphism 𝔇_{A} ≅ 𝔈_{A} takes d to e.

Now 𝔇 ⊧ T and since T^{∗} is the model completion of T , T^{∗} ∪ △_{𝔇} is complete. The isomorphism 𝔇_{A} ≅ 𝔈_{A} ensures that ℭ′ ⊧ T^{∗} ∪ △_{𝔇}. So 𝔅_{D} ≡ ℭ′. Hence 𝔅_{D}|L_{A} ≡ ℭ′|L_{A}; that is, 𝔅_{A} ≡ ℭ_{A}.

□

The way to show that DLO, ACF and RCF admit elimination of quantifiers is now clear: use Theorem 19. This reduces to showing that DLO, ACF and RCF are the model completions of LOR, FEI and ORF respectively. To do this we will use Theorem 18, so we first need to show that each pair of these theories satisfy the general hypothesis of Theorem 18: if 𝔄 ⊧ T then there is a 𝔅 ⊧ T^{∗} such that 𝔄 ⊆ 𝔅.

For the case T = LOR and T^{∗} = DLO is easy; every linear order can be enlarged to a dense linear order without endpoints by judiciously placing copies of the rationals into the linear order.

The case T = FEI and T^{∗} = ACF is just the well known fact that every field has an algebraic closure.

The case T = ORF and T^{∗} = RCF is just Lemma 13.

So all that remains of the quest to prove elimination of quantifiers for DLO, ACF and RCF is to verify condition (4) of Theorem 18 in each of these cases. We rephrase this condition slightly as:

For each 𝔄 ⊧ T , 𝔅 ⊧ T^{∗} and ℭ ⊧ T^{∗} with 𝔄 ⊆ 𝔅 and 𝔄 ⊆ ℭ there is a 𝔇 such that ℭ ≺ 𝔇 and an isomorphic embedding f : 𝔅 ↪ 𝔇 such that f ↾ A is the identity on A.

At this point the reader may already be able to verify this condition for one or more of the pairs T = LOR and T^{∗} = DLO, T = FEI and T^{∗} = ACF, or T = ORF and T^{∗} = RCF. However the remainder of this chapter is devoted to a uniform method.

Definition 34. Let L be a language and Σ(v_{0}) a set of formulas of L in the free variable v_{0}. A model 𝔄 for L is said to realize Σ(v_{0}) whenever there is some a ∈ A such that 𝔄 ⊧ φ[a] for each φ(v_{0}) in Σ(v_{0}).

Definition 35. The set of formulas Σ(v_{0}) in the free variable v_{0}, is said to be a type of the model 𝔄 whenever

(1) every finite subset of Σ(v_{0}) is realized by 𝔄

(2) Σ(v_{0}) is maximal with respect to (1).

Remark. Every set of formulas Σ(v_{0}) having property (1) of the definition of type can be enlarged to also have property (2).

Lemma 15. Suppose 𝔄 is a model for a language L. Let X ⊆ A and let Σ(v_{0}) be a type of 𝔄_{X} in the language L_{X}. Then there is a 𝔅 such that 𝔄 ≺ 𝔅 and 𝔅_{X} realizes Σ(v_{0}).

Proof. Let T = Th𝔄_{A} ∪ Σ(c) where c is a new constant symbol and Σ(c) = {φ(c) : φ ∈ Σ(v_{0})} and of course φ(c) is φ(v_{0}) with c replacing v_{0}.

By the definition of type, for each finite T′ ⊆ T , there is an expansion 𝔄′ of 𝔄 such that 𝔄′ ⊧ T′. The Compactness Theorem and the Elementary Diagram Lemma will complete the proof.

□

Lemma 16. Suppose 𝔄 is a model for a language L. There is a model 𝔅 for L such that 𝔄 ≺ 𝔅 and 𝔅_{A} realizes each type of 𝔄_{A} in the language L_{A}.

Proof. Let {Σ_{α}(v_{0}) : α ∈ I} enumerate all types of 𝔄_{A} in the language L_{A}. For each α ∈ I introduce a new constant symbol c_{α} and let

Σ_{α}(c_{α}) = {φ(c_{α}) : φ ∈ Σ_{α}(v_{0})}.

Let Σ = ∪{Σ_{α}(c_{α}) : α ∈ I}. Let Σ′ ⊆ Σ be any finite subset.

Claim. Σ′ ∪ Th𝔄_{A} is satisfiable for the language L_{A} ∪ {c_{α} : α ∈ I}.

Proof of Claim. Let Σ_{α_{1}}(v_{0}), …, Σ_{α_{n}}(v_{0}) be finitely many types such that

Σ′ ⊆ Σ_{α_{1}}(c_{0}) ∪ Σ_{α_{2}}(c_{1}) ∪ ⋯ ∪ Σ_{α_{n}}(c_{α_{n}}).

By Lemma 15 there is a model 𝔄_{1} such that 𝔄 ≺ 𝔄_{1} and (𝔄_{1})_{A} realizes Σ_{α_{1}}(v_{0}). Using Lemma 15 repeatedly, we can obtain

𝔄 ≺ 𝔄_{1} ≺ 𝔄_{2} ≺ ⋯ ≺ 𝔄_{n}

such that each (𝔄_{j})_{A} realizes Σ_{α_{j}}(v_{0}).

Now 𝔄 ≺ 𝔄_{n} so (𝔄_{n})_{A} ⊧ Th𝔄_{A}. It is easy to check that since each 𝔄_{j} ≺ 𝔄_{n}, 𝔄_{n} realizes each Σ_{α_{j}}(v_{0}) and furthermore so does (𝔄_{n})_{A}. So we can expand (𝔄_{n})_{A} to the language L_{A} ∪ {c_{α_{1}}, …, c_{α_{n}}} to satisfy Σ′ ∪ Th𝔄_{A}.

By the claim and the Compactness Theorem, there is a model ℭ ⊧ Σ ∪ Th𝔄_{A}. By the Elementary Diagram Lemma, 𝔄 is elementarily embedded into ℭ|L, the restriction of ℭ to the language L. Therefore there is a model 𝔅 for L such that 𝔄 ≺ 𝔅 and 𝔅_{A} ≅ ℭ|L_{A}. It is now straightforward to check that 𝔅_{A} realizes each type Σ_{α}(v_{0}).

□

For any set X we denote by |X| the cardinality of X.

Definition 36. A model 𝔄 for L is said to be κ-saturated whenever we have that for each X ⊆ A with |X| < κ, 𝔄_{X} realizes each type of 𝔄_{X}.

Recall that κ^{+} is defined to be the cardinal number just larger than κ. So a model 𝔄 will be κ^{+}-saturated whenever we have that for each X ⊆ A with |X| ≤ κ, 𝔄_{X} realizes each type of 𝔄_{X}. In particular, if B is any set, 𝔄 will be |B|^{+}-saturated whenever we have that for each X ⊆ A with |X| ≤ |B|, 𝔄_{X} realizes each type of 𝔄_{X}.

Remark. A model 𝔄 is said to be saturated whenever it is |A|-saturated, where |A| is the size of the universe of 𝔄. For example, ⟨ℚ,< < <⟩ is saturated; to prove this let X be a finite subset of ℚ and let Σ(v_{0}) be a type of ⟨ℚ,< < <⟩_{X}. By Lemma 15 and the Downward Löwenheim-Skolem Theorem get a countable 𝔅 such that ⟨ℚ,< < <⟩_{X} ≺ 𝔅_{X} and 𝔅 realizes Σ(v_{0}). Use the hint for Exercise 10 to show that ⟨ℚ,< < <⟩_{X} ≅ 𝔅_{X} and then note that this means that Σ(v_{0}) is realized in ⟨ℚ,< < <⟩_{X}.

Lemma 17. (R. Vaught) Suppose ℭ is an infinite model for L and B is an infinite set. There is a |B|^{+}- saturated model 𝔇 such that ℭ ≺ 𝔇.

Proof. We build an elementary chain

ℭ = ℭ_{0} ≺ ℭ_{1} ≺ ℭ_{2} ≺ ⋯ ≺ ℭ_{n} ≺ ⋯ n ∈ ℕ

such that for each n ∈ ℕ (ℭ_{n+1})_{C_{n}} realizes each type of (ℭ_{n})_{C_{n}}. This comes immediately by repeatedly applying Lemma 16. Let 𝔇 be the union of the chain; the Elementary Chain Theorem assures us that ℭ ≺ 𝔇 and indeed each ℭ_{n} ≺ 𝔇.

Let X ⊆ D with |X| ≤ |B| and let Σ(v_{0}) be a type of 𝔇_{X}. If X ⊆ C_{n} for some n, then Σ(v_{0}) is a type of (ℭ_{n})_{X} since (ℭ_{n})_{X} ≺ 𝔇_{X}. Now Σ(v_{0}) can be enlarged to a type of (ℭ_{n})_{C_{n}} which is realized in (ℭ_{n+1})_{C_{n}} and so Σ(v_{0}) is realized in (ℭ_{n+1})_{C_{n}}. Since (ℭ_{n+1})_{C_{n}} ≺ 𝔇_{C_{n}}, we can easily check that Σ(v_{0}) is realized in 𝔇_{C_{n}}. Since Σ(v_{0}) involves only constant symbols associated with X, we have that 𝔇_{X} realizes Σ(v_{0}).

We have almost proved that 𝔇 is |B|^{+}-saturated, but not quite, because there is no guarantee that if

X ⊆ D = ∪{C_{n} : n ∈ ℕ}

and |X| ≤ |B|, then X ⊆ C_{n} for some n. However, there would be no problem if X was finite. The problem with infinite X is that the elementary chain is not long enough to catch X.

The solution is to upgrade the notion of an elementary chain to include chains which are indexed by any well ordered set, not just the natural numbers. We sketch the appropriate generalization of the above argument from the case of ⟨ℕ,< < <⟩ to the case of an arbitrary well ordered set ⟨I, <⟩ with least element 0.

We construct an elementary chain of models

ℭ = ℭ_{0} ≺ ⋯ ≺ ℭ_{β} ≺ … β ∈ I

recursively as follows. At stage β, suppose we have already constructed C_{α} for each α ∈ I with α < β. The union of the chain up to β

𝔈 = ∪{ℭ_{α} : α ∈ I and α < β}

falls under the scope of an upgraded Elementary Chain Theorem (which is proved exactly as Theorem 4) and so ℭ_{α} ≺ 𝔈 for each α ∈ I with α < β. We now use Lemma 16 as before to get ℭ_{β} such that 𝔈 ≺ ℭ_{β} and (ℭ_{β})_{E} realizes each type of 𝔈_{E}.

As before, let 𝔇 = ∪{ℭ_{α} : α ∈ I} be the union of the entire chain and by the upgraded Elementary Chain Theorem ℭ ≺ 𝔇. Also as before, 𝔇_{X} realizes each type of 𝔇_{X} for each X ⊆ D such that X ⊆ C_{α} for some α ∈ I.

But now we can complete the proof of the lemma by choosing a well ordered set ⟨I, <⟩ large enough so that if

X ⊆ D = ∪{C_{α} : α ∈ I}

and |X| ≤ |B| then there is some α ∈ I such that X ⊆ C_{α}. Such a well ordered set is well known to exist — for example, any ordinal with cofinality > |B|.

□

Definition 37. We say that 𝔅 is a simple extension of 𝔄 whenever

(1) 𝔄 ⊆ 𝔅 and

(2) there is some b ∈ B such that no properly smaller submodel of 𝔅 contains A ∪ {b}.

Theorem 20. (Blum’s Test) Suppose T ⊆ T^{∗} are theories of a language L. Suppose further that:

(1) T is an almost universal theory

(2) every model of T can be extended to a model of T^{∗} and

(3) for each 𝔄 ⊧ T and each simple extension 𝔅 of 𝔄 which is a submodel of a model of T , and for each ℭ ⊧ T^{∗} with 𝔄 ⊆ ℭ such that ℭ is |B|^{+}−saturated, there is an isomorphic embedding f : 𝔅 → ℭ such that f ↾ A is the identity on A. Then:

(4) for each 𝔄 ⊧ T , 𝔅 ⊧ T^{∗} and ℭ ⊧ T^{∗} such that 𝔄 ⊆ 𝔅 and 𝔄 ⊆ ℭ we have a model 𝔇 such that 𝔅_{A} is isomorphically embedded into 𝔇_{A} and ℭ ≺ 𝔇,

(5) T^{∗} is the model completion of T and

(6) T^{∗} admits elimination of quantifiers.

Proof. Because of Theorem 17, Theorem 18 and Theorem 19, (5) and (6) follow from (1), (2) and (4). We will therefore only need to prove (4).

Let 𝔄, 𝔅 and ℭ be as in (4). Using Lemma 17 we obtain a |B|^{+}-saturated model 𝔇 such that ℭ ≺ 𝔇.

We wish to prove that 𝔅_{A} is isomorphically embedded into 𝔇_{A}. Since 𝔄 ⊆ 𝔇, the following collection E of functions is nonempty.

{e : for some 𝔈 ⊆ 𝔅 e: 𝔈_{A} ↪ 𝔇_{A} is an isomorphic embedding}

and so has a maximal member f in the sense that no other e ∈ E extends f. From f: 𝔉_{A} ↪ 𝔇_{A} and Exercise 12 we get 𝔊 with 𝔉 ⊆ 𝔊 and an isomorphism g: 𝔊 → 𝔇 extending f.

Claim. 𝔉 ⊧ T

Proof of Claim. We have both 𝔉 ⊆ 𝔅 and 𝔉 ⊆ 𝔊. By condition (1), there are models ℌ and 𝔍 of T with 𝔉 ⊆ ℌ ⊆ 𝔅 and 𝔉 ⊆ 𝔍 ⊆ 𝔊 such that ℌ_{F} ≅ 𝔍_{F}. This gives an isomorphic embedding h: ℌ ↪ 𝔊 such that h ↾ F is the identity on F.

The composition g ∘ h: ℌ ↪ 𝔇 is an isomorphic embedding with the property that for all x ∈ F:

(g ∘ h)(x) = g(x) = f(x).

By the maximality of f, f = g ∘ h. Hence 𝔉 = ℌ and 𝔉 ⊧ T , finishing the proof of the claim.

Claim. 𝔉 = 𝔅

Proof of Claim. If not, pick b ∈ B \ F and form the simple extension 𝔉′ of 𝔉 by b. Since 𝔊 ≅ 𝔇, 𝔊 is also |B|^{+}− saturated so that we can apply condition (3) to 𝔉, 𝔉′ and 𝔊. We obtain an isomorphic embedding f′: 𝔉′ ↪ 𝔊 such that f′ ↾ F is the identity on F. But now g ∘ f′ contradicts the maximality of f and completes the proof of the claim.

Therefore f isomorphically embeds 𝔅_{A} into 𝔇_{A}.

□

The following lemma completes the proofs that each of the theories DLO, ACF and RCF admit elimination of quantifiers.

Lemma 18. Each of the following three pairs of theories T and T^{∗} satisfy condition (3) of Blum’s Test.

(1) T = LOR, theory of linear orderings. T^{∗} = DLO, theory of dense linear orderings without endpoints.

(2) T = FEI, theory of fields. T^{∗} = ACF, theory of algebraically closed fields.

(3) T = ORF, theory of ordered fields. T^{∗} = RCF, theory of real closed fields.

Proof of (1). Let 𝔄 and 𝔅 be linear orders, with B = A ∪ {b} and 𝔄 ⊆ 𝔅. Let ℭ be a |B|^{+}-saturated dense linear order without endpoints with 𝔄 ⊆ ℭ.

We wish to find an isomorphic embedding f : 𝔅 → ℭ which is the identity on A. Consider a type of ℭ_{A} containing the following formulas:

c_{a} < v_{0} for each a ∈ A such that a < b
v_{0} < c_{a} for each a ∈ A such that b < a

Since ℭ is a dense linear order without endpoints each finite subset of the type can be realized in ℭ_{A}.

Saturation now gives some t ∈ C realizing this type. We set f(b) = t and we are finished.

Proof of (2). Let 𝔄 be a field and 𝔅 a simple extension of 𝔄 witnessed by b such that 𝔅 is a submodel of a field (a commutative ring).

Let ℭ be a |B|^{+}-saturated algebraically closed field such that 𝔄 ⊆ ℭ. We wish to find an isomorphic embedding f : 𝔅 → ℭ which is the identity on 𝔄.

There are two cases:

(I) b is algebraic over 𝔄, (II) b is transcedental over 𝔄.

Case(I). Let p be a polynomial with coefficients from A such that p(b) = 0 but b is not the root of any such polynomial of lower degree. Since ℭ is algebraically closed there is a t ∈ C such that p(t) = 0. We extend the identity map f on A to make f(b) = t. We extend f to the rest of 𝔅 by letting f(r(b)) = r(t) for any polynomial r with coefficients from A. It is straightforward to show that f is still a well-defined isomorphic embedding.

Case (II). Let us consider a type of ℭ_{A} containing the following set of formulas:

{¬(p(v_{0}) = 0)}

where p is a polynomial with coefficients in {c_{a} : a ∈ A}.

Since ℭ is algebraically closed, it is infinite and hence each finite subset is realized in ℭ_{A}. Saturation will now give some t ∈ C such that t realizes the type.

We set f(b) = t. Since t is transcedental over 𝔄, the extension of f to all of B comes easily from the fact that every element of B \ A is the value at b of some polynomial function with coefficients from A.

□

Proof of (3). Let 𝔄 be an ordered field and 𝔅 be a simple extension of 𝔄 witnessed by b such that 𝔅 is a submodel of an ordered field (an ordered commutative ring).

Let ℭ be a |B|^{+}-saturated real closed field such that 𝔄 ⊆ ℭ. We wish to find an isomorphic embedding f : 𝔅 → ℭ which is the identity on 𝔄.

There are two cases:

(I) b is algebraic over 𝔄. (II) b is transcedental over 𝔄.

Case (I). Since b is algebraic over 𝔄 we have a polynomial p with coefficients in A such that p(b) = 0. All other elements of the universe of the simple extension 𝔅 are of the form q(b) where q is a polynomial with coefficients in A. Before beginning the main part of the proof we need some algebraic facts.

Claim. Let 𝔇 be a real closed ordered field and q(x) be a polynomial over 𝔇 of degree n. Then for any e ∈ 𝔇 we have:

q(x) = ∑_{m=0}^{n} \frac{q^{(m)}(e)}{m!}(x − e)^{m}

where q^{(m)} stands for the polynomial which is the m-th derivative of q.

Proof of Claim. This is Taylor’s Theorem from Calculus; unfortunately we cannot use Calculus to prove it because we are in 𝔇, not necessarily the reals ℜ. However the reader can check that the Binomial Theorem gives the identity for the special cases of q(x) = x^{n} and that these special cases readily give the full result.

Claim. Let 𝔇 be a real closed ordered field and q(x) a polynomial over 𝔇 with e ∈ D and q(e) = 0. If there is an a < e such that q(x) > 0 for all a < x < e then q′(e) ≤ 0. If there is an a > e such that q(x) > 0 for all e < x < a then q′(e) ≥ 0. Here q′ is the first derivative of q.

Proof of Claim. From the previous claim we get

\frac{q(x) − q(e)}{x − e} = q′(e) + (x − e) ( ∑_{m=2}^{n} \frac{q^{(m)}(e)}{m!}(x − e)^{m−2})

for any x ≠ e in 𝔇. By choosing x close enough to e we can ensure that the entire right hand side has the same sign as q′(e). A proof by contradiction now follows readily.

Claim. Let 𝔇 be a real closed ordered field and q(x) be a polynomial over 𝔇 with e ∈ D and q(e) = 0. If w and z are in D such that w < e < z and q(w) · q(z) > 0 then there is a d in D such that w < d < z and q′(d) = 0.

Proof of Claim. Without loss of generosity q(w) > 0 and q(z) > 0. Since q has only finitely many roots, we can pick d_{1} to be the least x such that w < x ≤ e and q(x) = 0. Since q(x) ≠ 0 for all w < x < d_{1}, the Intermediate Value Property of Real Closed Ordered Fields shows that q cannot change sign here and so q(x) > 0 for all w < x < d_{1}. By the previous claim, q′(d_{1}) ≤ 0. A similar argument with z shows that there is a d_{2} such that e ≤ d_{2} < z and q′(d_{2}) ≥ 0. If d_{1} = e = d_{2} take d = e. If d_{1} < d_{2} the Intermediate Value Property gives a d with the required properties.

Claim. Let 𝔇 be a real closed ordered field with an ordered field 𝔈 ⊆ 𝔇. Let f : 𝔈 → ℭ be an isomorphic embedding into a real closed ordered field. Let q be a polynomial with coefficients in E such that {x ∈ D : q′(x) = 0} ⊆ E. Let d ∈ D \ E be such that q(d) = 0 but d is not a root of a polynomial with coefficients from E which has lower degree. Then f can be extended over the subfield of 𝔇 generated by E ∪ {d}.

Proof of Claim. Since the finitely many roots of q′ from D actually lie in E, we can get e_{1} and e_{2} in E such that e_{1} < d < e_{2} and q′(x) ≠ 0 for all x in D such that e_{1} < x < e_{2}. Furthermore for all x in E we have q(x) ≠ 0. We can now apply the previous claim to get that q(w) · q(z) < 0 for all w and z in E such that e_{1} < w < d < z < e_{2}.

We now move to the real closed ordered field ℭ and the isomorphic embedding f. For each w and z in E such that e_{1} < w < d < z < e_{2} we have f(w) < f(z) and q(f(w)) · q(f(z)) < 0. By the Intermediate Value property of ℭ we get, for each such w and z, a y ∈ C such that f(w) < y < f(z) and q(y) = 0. Since q has only finitely many roots there is some t ∈ C such that q(t) = 0, f(w) < t for all e_{1} < w < d and t < f(z) for all d < z < e_{2}.

We now extend f by letting f(d) = t and f(r(d)) = r(t) for any polynomial r with coefficients from E. It is straightforward to check that the extension is a well-defined isomorphic embedding of the simple extension of 𝔈 by d into ℭ. We use the fact that ORF is almost universal to extend the isomorphic embedding to all of the subfield of 𝔇 generated by E ∪ {d}, since we can rephrase the definition of almost universal as follows:

Whenever ℭ ⊧ T , 𝔇 ⊧ T , 𝔈′ ⊆ 𝔇 and f : 𝔈′ ↪ ℭ is an isomorphic embedding there is a model 𝔈′′ ⊧ T such that 𝔈′ ⊆ 𝔈′′ ⊆ 𝔇 and f extends over 𝔈′′.

It is now time for the main part of the proof of this case. Using Lemma 13, let 𝔇 be a real closed ordered field with 𝔅 ⊆ 𝔇. We have a polynomial p with coefficients from A such that p(b) = 0. By induction on the degree of p, we can show that there is a sequence of elements d_{0}, …, d_{m} = b of elements of 𝔇, a sequence of subfields of 𝔇:

𝔄 = 𝔈_{0} ⊆ 𝔈_{1} ⊆ … ⊆ 𝔈_{m+1}

with each d_{j} ∈ E_{j+1} \ E_{j} and corresponding isomorphic embeddings

f_{j} : 𝔈_{j} → ℭ

coming from the previous claim and having the property that f_{0} is the identity and f_{j+1} extends f_{j}. In this way we extend the identity map f_{0} : 𝔄_{0} ↪ ℭ until we reach f_{m+1} : 𝔈_{m+1} ↪ ℭ. We then note that since b ∈ 𝔈_{m+1} we have 𝔅 ⊆ 𝔈_{m+1} and we are finished.

Case (II). Let us consider a type of ℭ_{A} containing the following formulas:

c_{a} < v_{0} for all a ∈ A with a < b
v_{0} < c_{a} for all a ∈ A with b < a

¬(p(v_{0}) = 0) for all polynomials p with coefficients in {c_{a} : a ∈ A} Since each interval of ℭ is infinite, each finite subset of this type is realized by

ℭ_{A}. Saturation now gives t ∈ C which realizes this type. We put f(b) = t.

We can now extend f on the rest of B \ A, since each such element is the value at b of a polynomial function with coefficients from A.

□

Question. Suppose 𝔎 is the reduct of a real closed ordered field to the language of field theory. Can you show that 𝔎[\sqrt{−1}] is algebraically closed using Model Theory and the Fundamental Theorem of Algebra?

Bibliography

1. J. Barwise (ed.), Handbook of Mathematical Logic, North Holland, 1997.

2. J. L. Bell and A. B. Slomson, Models and Ultraproducts, North Holland, 1969.

3. Felix E. Browder (ed.), Mathematical developments arising from Hilbert’s problems, Proceedings of Symposia in Pure Mathematics, vol. XXVIII - Parts 1 and II, AMS, 1976.

4. S. Buechler, Essential Stability Theory, Perspectives in Mathematical Logic, Springer, 1996.

5. C. C. Chang and H. J. Keisler, Model Theory, second ed., North Holland, 1977.

6. G. Cherlin, Model Theoretic Algebra, Selected Topics, LNM521, Springer-Verlag, 1976.

7. N. Jacobson, Basic Algebra I, W. H. Freeman, 1985.

8. H. J. Keisler, Foundations of Infinitesimal Calculus, Prindle, Weber and Schmidt, 1976.

9. M. D. Morley (ed.), Studies in Model Theory, MAA Studies in Mathematics, MAA, 1973.

10. A. Robinson, Introduction to Model Theory and the Metamathematics of Algebra, second ed., North-Holland, 1965.

11. , Non Standard Analysis, North Holland, 1966.

12. G. E. Sacks, Saturated Model Theory, W. A. Benjamin Inc., 1972.

13. D. H. Saracino and V. B. Weispfenning (eds.), Model theory and algebra: A Memorial Tribute to Abraham Robinson, LNM498, Springer Verlag, 1975.

14. S. Shelah, Classification Theory and the Numbers of Nonisomorphic models, second ed., North Holland, 1990.

15. J. R. Shoenfield, Mathematical Logic, Addison-Wesley, 1967.

16. A. Tarski, A Descision Method for Elementary Algebra and Geometry, second ed., The Rand Corporation, 1957.

Index

𝔄 ⊆ 𝔅, 15 𝔄 = ∪{𝔄_{n} : n ∈ ℕ}, 16 Th𝔄, 12 Th𝔄_{A}, 24 ⊧, 12 ≺, 16 𝔄′|L′, 14 ⊆, 14 t[x_{0}, …, x_{q}], 6

⟨ℂ,+ + +, ·, 0, 1⟩, 11 ⟨ℚ,< < <,+ + +, ·, 0, 1⟩, 11 ⟨ℝ,< < <,+ + +, ·, 0, 1⟩, 11 ⟨ℕ,+ + +,···,< < <,0 0 0,1 1 1⟩, 15

A. Robinson, 32 ACF, 13

submodel complete, 51 algebraically closed fields

axioms,theory of, 13 almost universal, 52, 59 axioms, 12

Blum’s Test, 55 bound variable, 5

categorical

κ-categorical theory, 21 chain of models, 16

elementary, 16 Compactness Theorem, 14 complete theory, 21 Completeness Theorem, 14 complex, 11 Craig Interpolation Theorem, 31

dense linear orders without endpoints

axioms,theory of, 13 diagram lemmas, 24 DLO, 13

submodel complete, 51

elementarily embedded model, 24 elementarily equivalent models, 15 Elementary Chain Theorem, 16 elementary diagram, 24 elementary extension, 16 elementary submodel, 16 elimination of quantifiers, 45 existentially closed, 32 expansion

language, 14 model, 14

FEI, 13

almost universal, 52 fields

axioms,theory of, 13 formula, 4 free variable, 5

isomorphic models, 15

isomorphically embedded model, 24

language, 5

Leibniz Principle, 26 Lindström’s Test, 35 linear orders

axioms,theory of, 13 LOR, 13

almost universal, 52 Łoś-Vaught Test, 21 Löwenheim-Skolem Theorems

Downward, 20 Upward, 20

model, 5

satisfies, 6 model complete theory, 32 model completion, 50

submodel complete, 52

Number Theory, 15 number theory

non-standard models, 15

ordered field, 42 ordered fields

axioms,theory of, 13 ORF, 13

almost universal, 52

prenex normal form, 9

rational numbers, 11 RCF, 13

submodel complete, 51 real closed ordered field, 42 real closed ordered fields

axioms, theory, 13

axioms,theory of, 13

Intermediate Value Property, 13 real numbers, 11 realize, 53 reduction

language, 14

model, 𝔄′|L′, 14 Robinson Consistency Theorem, 27

satisfaction

𝔄 ⊧ Σ, 12 saturated

κ-saturated model, 54 sentence, 9 simple extension, 55 subformula, 5 submodel, 15 submodel complete, 45 submodel complete theory, 45

T. Skolem, 15 Tarski’s Elementary Chain Theorem, 16 Tarski-Vaught Condition, 19 term, 4 theory, 12

almost universal, 52

model completion, 50 theory of 𝔄, 12 type, 53

variable, 4