An Invitation To MODEL THEORY PDF
An Invitation To MODEL THEORY PDF
J O NAT H A N K I R B Y
University of East Anglia
University Printing House, Cambridge CB2 8BS, United Kingdom
One Liberty Plaza, 20th Floor, New York, NY 10006, USA
477 Williamstown Road, Port Melbourne, VIC 3207, Australia
314–321, 3rd Floor, Plot 3, Splendor Forum, Jasola District Centre,
New Delhi – 110025, India
79 Anson Road, #06–04/06, Singapore 079906
www.cambridge.org
Information on this title: www.cambridge.org/9781107163881
DOI: 10.1017/9781316683002
© Jonathan Kirby 2019
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2019
Printed and bound in Great Britain by Clays Ltd, Elcograf S.p.A.
A catalogue record for this publication is available from the British Library.
Library of Congress Cataloging-in-Publication Data
Names: Kirby, Jonathan, 1979– author.
Title: An invitation to model theory / Jonathan Kirby, University of East Anglia.
Description: Cambridge, United Kingdom ; New York, NY : Cambridge University
Press, 2019. | Includes bibliographical references and index.
Identifiers: LCCN 2018052996 | ISBN 9781107163881 (hardback ; alk. paper) |
ISBN 1107163889 (hardback ; alk. paper) | ISBN 9781316615553 (pbk. ; alk.
paper) | ISBN 1316615553 (pbk. ; alk. paper)
Subjects: LCSH: Model theory.
Classification: LCC QA9.7 .K57 2019 | DDC 511.3/4–dc23
LC record available at https://lccn.loc.gov/2018052996
ISBN 978-1-107-16388-1 Hardback
ISBN 978-1-316-61555-3 Paperback
Cambridge University Press has no responsibility for the persistence or accuracy
of URLs for external or third-party internet websites referred to in this publication
and does not guarantee that any content on such websites is, or will remain,
accurate or appropriate.
To Pirita, Lumia, Tapio, and Sakari
Contents
Preface page ix
PART I LANGUAGES AND STRUCTURES 1
1 Structures 3
2 Terms 9
3 Formulas 13
4 Definable Sets 19
5 Substructures and Quantifiers 24
PART II THEORIES AND COMPACTNESS 29
6 Theories and Axioms 31
7 The Complex and Real Fields 37
8 Compactness and New Constants 42
9 Axiomatisable Classes 47
10 Cardinality Considerations 53
11 Constructing Models from Syntax 57
PART III CHANGING MODELS 63
12 Elementary Substructures 65
13 Elementary Extensions 70
vii
viii Contents
Bibliography 177
Index 179
Preface
ix
x Preface
Overview
The book is organised into six parts. Part I covers structures, languages, and
automorphisms, introduces definable sets, and proves the essential preservation
theorems.
Part II introduces theories and the programme of finding axiomatisations for
structures. Context is given with axiomatisations of the complex and real fields
and the natural numbers with addition and multiplication (Peano arithmetic).
The compactness theorem is then introduced, and examples of its use are given.
Part II concludes with the Henkin proof of the compactness theorem.
In Part III we show that even a complete theory can have many different
models with the Löwenheim–Skolem theorems. The notion of categoricity
is introduced via the example of vector spaces and is used to prove the
completeness of an axiomatisation. Further applications are given to dense
linear orders, where the back-and-forth method is introduced, and to the natural
numbers with the successor function.
The idea of quantifier elimination is introduced in Part IV, and used
to characterise the definable sets in dense linear orders and vector spaces.
Boolean algebras are introduced via an investigation into the theory of power
sets, partially ordered by the subset relation, and the definable subsets of a
structure in any number n of variables is shown to be a Boolean algebra, called
the Lindenbaum algebra of the theory. These Lindenbaum algebras are then
worked out in the examples of vector spaces and for the real ordered field.
Parts V and VI go in different directions and do not depend on each other.
Part V develops the notion of types, which is at the heart of modern model
theory. The first goal is the Ryll–Nardzewski theorem, which characterises
countably categorical theories as those for which there are only finitely many
definable sets in any given number of variables. There is then a brief discussion
of saturated models, leading to areas for further reading.
Part VI takes the model-theoretic techniques developed in the first four parts
and applies it to the theory of algebraically closed fields. Two chapters explain
Preface xi
31 32
30 5
29 27
7 13 28 26
25
24 20
22 23
21 7
20
18 19
17
16 15
14
13
12
10
7 19 9 8 11
6 10
4 5
Figure 0.1 Chapter dependencies: In order to make the diagram planar, Chapters
5, 7, 10, 13, 19, and 20 have been drawn in two (or even three) places. As the
diagram shows, Parts IV, V, and VI are largely independent of each other, with
much of Part V also independent of Part III. While Chapter 25 uses the concept of
Lindenbaum algebras from Chapter 20, that material does not rely on the rest of
Parts III or IV.
Preface xiii
For research students, Part VI, on algebraically closed fields, gives a pattern
for carrying out the programme of understanding definable sets in a theory
which is similar to the pattern which works in many other theories of fields,
such as real-closed fields, differentially closed fields, separably closed fields,
algebraically closed valued fields, exponentially closed fields, algebraically
closed fields with an automorphism, and so on.
Further Reading
There are several more advanced textbooks in model theory, including those
of Marker [Mar02], Hodges [Hod93, Hod97], Poizat [Poi00], Tent and Ziegler
[TZ12], Sacks [Sac10], and Chang and Keisler [CK90]. Rothmaler [Rot00] is
more at the level of this book, but there is more emphasis on algebra, especially
groups. Väänänen [Vää11] introduces model theory via back-and-forth games,
which complements the approach in this book. Bridge [Bri77] was based on
the incarnation of the Oxford model theory course from the early 1970s, and
the emphasis is much more on logic. Other suggestions for further reading are
given through the book, particularly at the end of Parts IV, V, and VI.
Acknowledgements
Thanks to Boris Zilber for allowing me to take his lecture notes as a starting
point both for my course and for this book. I learned model theory initially
from the books of Wilfrid Hodges and David Marker, and from Boris. My
writing style was much influenced by the late Harold Simmons.
I would like to thank Cambridge University Press for their help in producing
the book and, in particular, Silvia Barbina for initially suggesting that I write it.
Many people have made helpful comments on drafts or have otherwise
helped me to write the book. I would like to thank Lou van den Dries,
David Evans, Åsa Hirvonen, Wilfrid Hodges, Ehud Hrushovski, Tapani Hyt-
tinen, Gareth Jones, Asaf Karagila, David Marker, Alice Medvedev, Charles
Steinhorn, Alex Wilkie, and Boris Zilber for sharing their expertise. Thanks
to Francesco Parente for reading two drafts and providing many considered
comments.
Thanks also to the students who attended my courses or read drafts of the
book and provided essential feedback. They include Abeer Albalahi, Michael
Arnold, Emma Barnes, Matt Gladders, Grant Martin, Oliver Matheau-Raven,
Audie Warren, and Tim Zander.
Part I
In this first part of the book, we introduce the basic methods from predicate
logic which underpin the rest of the book. Mathematical objects are formalised
as L-structures, and statements about these structures are formalised in the
notions of L-terms and L-formulas. We introduce the central notion of a
definable set, a subset of an L-structure which is defined by an L-formula.
A key notion in mathematical logic is that of a recursive definition, and
both the notions of L-terms and L-formulas give examples of that. These
recursive definitions give rise to methods of proof by induction. Throughout
this part, these proofs by induction are used prove preservation theorems, most
importantly the preservation of definable sets by automorphisms of a structure.
From this result we get a method to show that certain subsets of a structure are
not definable, an essential tool which we will later exploit in the programme
of characterising the definable sets of a structure.
1
1
Structures
1.1 L-structures
Definition 1.1 A language L is specified by the following (sometimes called
the vocabulary or signature of L):
3
4 1 Structures
Example 1.3 The language of rings Lring = +, ·, −, 0, 1, where + and · are
function symbols of arity 2 (we say they are binary function symbols), − is a
function symbol of arity 1 (a unary function symbol for negation rather than
the binary function of subtraction), and 0 and 1 are constant symbols. Zring is
the Lring -structure with domain the set Z of integers. We interpret the symbols
+, ·, and − as the usual functions of addition, multiplication, and negation of
integers and the constant symbols 0 and 1 are interpreted as the usual zero and
one. We can write this as Zring = Z; +Z , ·Z , −Z , 0Z , 1Z if for example we want
to distinguish the symbol + from its interpretation +Z as a function from Z2
to Z. This distinction can be important in mathematical logic. For example we
also have the Lring -structure Rring with domain the set of real numbers R, and
the function +R : R2 → R is not the same function as +Z : Z2 → Z. However,
usually no ambiguity arises, and we just write + for the symbol and for its
interpretations in different structures.
Example 1.4 We write L< = <, where < is a binary relation symbol. Then
Z< is the L< -structure with domain
the set Z of integers,
and the symbol < is
interpreted as the set of pairs (a, b) ∈ Z2 | a < b . As above, we could write
this set as <Z , but usually we will not.
Examples 1.5 Many other languages can be built as variations on these two
languages:
(i) Lgp = ·, (−)−1 , 1 is the language of groups. Again, · is a binary function
symbol, (−)−1 is a unary function symbol representing the multiplicative
inverse function x → x−1 , and 1 is a constant symbol.
(ii) Ladgp = +, −, 0 is the language of groups written additively. It is a
sub-language of Lring , because every symbol in Ladgp is also in Lring (with
the same arity). We also say that Lring is an expansion of the language
Ladgp .
(iii) Lo-ring = +, ·, −, 0, 1, < is the language of ordered rings, consisting of
Lring ∪ L< .
(iv) A common language in which to consider the natural numbers is the
language of semirings, Ls-ring = +, ·, 0, 1. We will always use the
convention that 0 is a natural number.
(v) The language of monoids is Lmon = ·, 1 and the language of additive
monoids is Ladmon = +, 0.
we name the structure by putting the name of the language as a subscript, for
example Zring , Ro-ring , Q< , Ns-ring .
We can also specify structures directly, which is useful for creating simpler
examples. In this case we will often use a caligraphic letter for the name of the
structure and the corresponding Roman letter for the name of its domain, so
A would be the name of a structure with domain A. This convention of using
different notation for the name of a structure and its domain is useful when the
same set is the domain of different structures. However, where no confusion is
likely to arise, we will sometimes follow the common mathematical practice
of using the same notation for both.
Example 1.6 Take the language L = R, f, c, where R is a ternary
relation symbol, f is a unary function symbol, and c is a constant
symbol. We can define an L-structure A with domain A = {0, 1, 2, 3, 4},
by specifying the interpretation of the symbols as
f A (x) = x+1 mod 5, RA = (x, y, z) ∈ A3 exactly two of x, y and z are equal
and cA = 3.
Remark 1.7 The key idea from mathematical logic here is that the symbols
of the vocabulary of a language L are separate from their interpretations in a
structure. It follows that the symbols do not have to be interpreted by their
usual meanings. For example we can make the set N into an Lgp -structure
by interpreting the symbol · as addition and (−)−1 as the identity function, so
x−1 = x for all x ∈ N, and interpreting the constant symbol 1 as the number 2.
However, this is perverse, and if we want an unusual interpretation, we will
choose to use a different symbol.
Given a mathematical problem you are trying to solve, or a statement you
want to understand, it is often a good exercise to work out what structure the
statement might be about. For example, the fundamental theorem of arithmetic
states that every positive integer can be written as a product of primes in a
unique way (up to reordering). An appropriate structure would have domain
the set N+ of positive integers and needs to have the multiplication function;
1 is a special case as the empty product, which is relevant to single out, so
we can regard the fundamental theorem of arithmetic as a statement about the
structure N+mon = N+ ; ·, 1. To actually prove the theorem, we might need more
than that, for example the order to do induction on and also addition.
Example 1.12 The only automorphisms of Zadgp are the identity and the map
x → −x. To see this, note that if π : Z → Z is an Ladgp -embedding, then
π(0) = 0, and if π(1) = n, then for any m ∈ N+ , we have
Exercises 7
Exercises
1.1 Let L = f, c be a language with one unary function symbol and one
constant symbol. Describe all the possible L-structures on the domain
{1, 2}. How many of them are there up to isomorphism (which means
counting isomorphic structures as the same)?
1.2 For each of the following statements, give a structure which they say
something about.
(a) There is no largest integer.
(b) Every integer has an additive inverse.
(c) Square integers are always non-negative.
(d) Every complex number is the sum of a real number and i times a
real number.
(e) The exponential function is strictly increasing on the real numbers.
(f) A real quadratic equation ax2 + bx + c = 0 has real roots if and only
if b2 − 4ac 0.
(g) Euler’s identity eiπ + 1 = 0.
1.3 For each language L in Examples 1.5, say which of the sets from N, Z,
and R is the domain of an L-structure with the symbols interpreted with
their usual meanings. For example, there is no structure Ngp because
N is not closed under multiplicative inverses. Which of your structures
are expansions or reducts of each other? Which are extensions or
substructures?
1.4 What are all the automorphisms of Z< ?
1.5 Show that embeddings of N< into R< correspond to strictly increasing
sequences of real numbers.
1.6 Show that an embedding of L-structures is an isomorphism if and only if
it is surjective.
1.7 Explain what all the embeddings of Zadgp into Radgp are.
1.8 Find an automorphism π of the structure R; < such that π(0) = 1 and
π(1) = 5. Is your π also an automorphism of the structure R; +?
8 1 Structures
9
10 2 Terms
Remarks 2.3 (i) If t is a closed term, then in Definition 2.2 we can take
r = 0. In this case it is best to think of the interpretation tA as an element
of A. We can alternatively think of it as a function A0 → A. Since A0 is a
one-point set, this amounts to the same thing as an element of A.
(ii) Note that terms depend only on the language, but their interpretations
depend on the structure. For example, the term ((x + 1) + x) is interpreted
in the structure Rring as the function
R −→ R
x −→ 2x + 1,
Z −→ Z
x −→ x + 2.
(iv) Where no ambiguity arises, we often do not write all the brackets which
should be there according to the recursive definition.
Exercises 11
(v) In model theory we almost always deal with terms with a given list of
variables. So we will write that t( x̄) is a term, when we really mean that t
is a term and x̄ is a list of variables which includes all the variables
which appear in t.
Exercises
2.1 Write out a recursive definition of Lmon -terms.
2.2 Explain how the Lring -terms (−(x + 1) · y) and (x + x) + (y · −z) are built
up from the recursive definition of L-terms.
12 2 Terms
2.3 In the structure Rring , which elements of R are named by closed Lring -
terms?
2.4 Give three different Lring -terms which are interpreted as the same
polynomial function.
2.5 Define a polynomial function on R to be a function Rn → R of the form
m
d d
p(x1 , . . . , xn ) = ri x1i,1 · · · xni,n
i=1
Terms are certain strings of symbols from the language. As we have seen,
they are interpreted as elements of a structure or as functions on the structure.
Other strings of symbols of the language say something about structures or
about elements of the structure. For example, ((1 + 0) + 1) = 0 is a statement
about numbers (which is false in Zadgp but true in the cyclic group Z/2Z),
∃x[((x · x) + −(1 + 1)) = 0] asserts that there is a square root of 2 (which is
true in Rring but false in Zring ), and (x · x) < 1 is a statement about the number
x (which in Ro-ring will be true for some values of x and false for other values).
The formulas in clauses (i) and (ii) are called atomic formulas, because they
do not contain smaller formulas.
x<1+1
13
14 3 Formulas
says something about the variable x, namely that it is less than 2, whereas the
formula
∃x[0 < x]
says that there is some element which is greater than 0 and the variable x is just
a dummy. The formula has the same meaning as ∃y[0 < y], where x is replaced
by y. The difference is that in the second example, the variable x is quantified
over by the ∃ quantifier.
Definition 3.2 An instance of a variable x in a formula is a quantifier
instance if it occurs immediately after the ∃ symbol. Immediately following
the quantifier ∃x is the scope of the quantifier, which is enclosed in square
brackets [ ]. Any instance of x which occurs within the scope of the quantifier
∃x is called a bound instance of x, and the quantifier ∃x is said to bind it. Any
other instance of a variable is said to be a free instance. The variables which
have free instances in a formula are called its free variables.
For simplicity, we will usually assume that no variable occurs both free and
bound in the same formula. For example, the formula
(x y ∧ ∃x[0 x])
should be rewritten as (x y ∧ ∃z[0 z]).
Formulas with no free variables are particularly important, essentially
because they say something about a structure as a whole rather than about
some elements of it, so they have a special name.
Definition 3.3 A formula with no free variables is called a sentence.
(i) A |= t1 (ā) = t2 (ā) iff t1A (ā) = t2A (ā), that is, iff the functions t1A and t2A
take the same value at ā.
(ii) A |= R(t1 (ā), . . . , tr (ā)) iff (t1A (ā), . . . , trA (ā)) ∈ RA .
(iii) A |= ¬ϕ(ā) iff A |= ϕ(ā), that is, A does not model ϕ(ā).
(iv) A |= (ϕ1 ∧ ϕ2 )(ā) iff A |= ϕ1 (ā) and A |= ϕ2 (ā).
(v) A |= ∃x[ϕ(x, ā)] iff there is some b ∈ A such that A |= ϕ(b, ā).
∃x case: Suppose A |= ∃xϕ(x, ā). Then there is c ∈ A such that A |= ϕ(c, ā).
By induction, B |= ϕ(π(c), π(ā)). So B |= ∃xϕ(x, π(ā)). Conversely, suppose
B |= ∃xϕ(x, π(ā)). Then there is d ∈ B such that B |= ϕ(d, π(ā)). Since π is
an isomorphism, it has an inverse, π−1 . Let c = π−1 (d). Then π(c) = d, so, by
induction, A |= ϕ(c, ā). So A |= ∃xϕ(x, ā).
That completes all the necessary induction steps, one for each part of the
recursive definition of a formula.
3.5 Abbreviations
Our formal language is very restricted. In practice, we adopt many
abbreviations which make it easier to use. We write
Exercises
3.1 Write down an Lring -formula in which the variables x, y, and z appear
free and the variables u and v are bound.
3.2 In the language L with a binary relation symbol < and constant symbols
for 0, 1, 2, 3, 4, 5, 6, write L-sentences expressing the following about the
L-structure on the integers, Z.
(a) a formula ϕ(x) in the language +, · with one free variable such that
for any n ∈ N, N |= ϕ(n) iff n = 2;
(b) a formula ξ(x, y) with two free variables such that for any
n1 , n2 ∈ N, N |= ξ(n1 , n2 ) iff n1 < n2 ;
(c) a formula δ(x, y) with two free variables such that for any
n1 , n2 ∈ N, N |= δ(n1 , n2 ) iff n1 |n2 ;
(d) a formula ψ(x) with one free variable such that for any n ∈ N,
N |= ψ(n) iff n is a prime number;
(e) a sentence stating that there are infinitely many pairs of prime
numbers which differ by 2.
You can use abbreviations, provided you explain what they are.
3.5 Consider the Lring -formula ϕ(x) given by ∃y[(y · y) + 1 = x]. For what
values of x do we have Rring |= ϕ(x)? For what x do we have Zring |= ϕ(x)?
3.6 Express each of the statements in Exercise 1.2 as L-sentences for an
appropriate choice of language L.
3.7 A formula is said to be quantifier-free if it does not use the symbol ∃ (or
the abbreviation ∀).
In this chapter we introduce the main idea of the book, that of a definable set.
(x + 1 = 0) ∨ (x = (1 + 1) + 1),
19
20 4 Definable Sets
Note that if the graph of f is defined by the formula ϕ(x, y), then the domain
of f is defined by ∃y[ϕ(x, y)] and the image is defined by ∃x[ϕ(x, y)].
Example 4.4 In Ro-ring , the absolute value function R → R; x → |x| is defined
by the formula
((x < 0) ∧ (y = −x)) ∨ (¬(x < 0) ∧ (y = x)).
Lemma 4.5 If S 1 , S 2 ⊆ An are definable, then S 1 ∩ S 2 , S 1 ∪ S 2 , and An S 1
are definable. Furthermore, if S ⊆ An+m is definable, then the projection
proj(S ) = ā ∈ An There is some b̄ ∈ Am such that (ā, b̄) ∈ S
is also definable.
Proof Suppose S 1 is defined by ϕ( x̄) and S 2 is defined by ψ( x̄). Then S 1 ∩ S 2
is defined by (ϕ( x̄) ∧ ψ( x̄)) and so on.
Figure 4.1 illustrates why existential quantification corresponds to projec-
tion. In the structure Ro-ring , let ϕ(x, y) be the formula
(x − 4)2 + (y − 3)2 < 4
which defines a disc of radius 2, centred at (4, 3) in the xy-plane. We have
used subtraction and squaring in the formula, although they are not symbols
in the language Lo-ring . Since they are definable functions, we can use them
as abbreviations. The formula ∃y[ϕ(x, y)] defines the projection to the x-axis,
which is the interval (2, 6).
0 1 2 3 4 5 6 7
Exercises
4.1 Complete the proof of Lemma 4.5.
4.2 Show that addition and multiplication are not definable in R< .
4.3 Show that the order < is not definable in Zadgp but is definable in Nadmon .
4.4 Show that the order < is definable in Rring . Deduce that every subset of
Rn which is definable in Ro-ring is also definable in Rring .
4.5 Show that the set N and the order < are definable in Zring . [Hint: Use
Lagrange’s 4-square theorem.]
4.6 Show that negation is a definable function in R; +, 0 and in Z; +, 0
but that multiplication is not definable in either structure.
√
4.7 Show that the square root function R+ → R+ ; x → x is definable in
Ro-ring .
4.8 Give an example of a definable function in Zring which is not defined by
the interpretation of any term.
4.9 Show that the only automorphism of the structure Ns-ring is the identity
map.
4.10 Consider the expansion of the real ordered field Ro-ring by a unary
function f . Write down a formula ϕ(x) such that whatever the function
f is, ϕ(x) defines the set of real numbers at which f is continuous.
Exercises 23
4.11 Find all the subsets of Q which are definable in Qadgp (by a formula with
one free variable) and prove that they are the only ones.
4.12 Sketch a proof of Proposition 4.6 starting from the relevant definitions
and including the statements and sketch proofs of any necessary lemmas.
You should explain what methods of proof are used, what all the key
ideas are, and how they fit together, but you do not need to give all the
details of the inductive proofs.
5
Substructures and Quantifiers
In the previous chapter we showed that every definable set is preserved under
automorphisms. Here we give more subtle preservation theorems which show
that formulas constructed with only certain quantifiers are preserved under
taking substructures or embeddings.
5.1 Substructures
The field of rational numbers, Qring , is a subfield of the field of real numbers,
Rring . Similarly, Zring is a subring of Qring . More generally, recall from
Chapter 1 the notion of a substructure of an L-structure.
24
5.2 Existential and Universal Formulas 25
∀x[0 < x ∨ x = 0]
with a universal quantifier. The second sentence is true in Qring and also in the
extension Rring but false in the substructure Zring . It makes sense, because once
the number (1/2) with this property is there in Q, it is still in any extension of
Q, but it might not be there in a substructure, in this case, Z. We can write it as
∃x[x + x = 1]
(iv) Only a formula constructed by the above rules in finitely many steps is a
quantifier-free formula.
Similarly, we can give recursive definitions of existential formulas and
universal formulas.
Definition 5.3 (Existential formula)
(i) A quantifier-free formula is an existential formula.
(ii) If ϕ is an existential formula and x is a variable, then ∃x[ϕ] is an
existential formula.
(iii) Only a formula constructed by the above rules in finitely many steps is
an existential formula.
Definition 5.4 (Universal formula)
(i) A quantifier-free formula is a universal formula.
(ii) If ϕ is a universal formula and x is a variable, then ∀x[ϕ] is a universal
formula.
(iii) Only a formula constructed by the above rules in finitely many steps is a
universal formula.
So any existential formula has the form ∃y1 · · · yn [ψ] where ψ is a quantifier-
free formula, and any universal formula has the form ∀y1 · · · yn [ψ]. From our
definition of ∀y as an abbreviation for ¬∃y¬, we can write ∀y1 · · · yn [ψ] as
¬∃y1 ¬¬∃y2 ¬ · · · ¬∃yn [¬ψ] and cancelling the double negations it becomes
¬∃y1 · · · yn [¬ψ], which is the negation of an existential formula.
Exercises
5.1 If L is a language with only relation symbols and A is an L-structure,
show that every subset of A is naturally an L-substructure of A.
5.2 If L has function and constant symbols, which subsets of the domain of
an L-structure correspond to L-substructures?
5.4 Write the axiom for a group which states that every element has an
inverse both as an Lgp -sentence and as an Lmon -sentence. Which of the
axioms is a universal sentence? Show that if G is a group considered
as an Lgp -structure, then its Lgp -substructures are its subgroups and its
Lmon -substructures are submonoids.
5.6 Show that there is no universal Lring -sentence which asserts that every
non-zero element of a field has a multiplicative inverse.
5.7 Give a direct proof of Proposition 5.7, not using Proposition 5.6.
In this part of the book we introduce the first part of our programme for
understanding a mathematical structure: finding axioms for the theory of the
structure. The programme is illustrated with the Peano axioms for Ns-ring and
by the axioms for algebraically closed fields and for real-closed fields for Cring
and Ro-ring , respectively. At this stage, we lack the tools to give proofs for
these examples, or indeed for any other examples. We then introduce the most
powerful of the model-theoretic tools, the compactness theorem, together with
the method of changing the language by adding new constant symbols. These
methods are used to construct new models of the theory of an infinite structure.
Further applications of the compactness theorem are given in the context of
axiomatisable classes. A brief discussion of cardinal arithmetic and Henkin’s
proof of the compactness theorem complete Part II.
29
6
Theories and Axioms
In this chapter we move the focus from individual formulas and sentences
to the set of al those sentences which are true in a structure, its theory. To
describe a theory, we need to have a subset of it we can write down, that is, an
axiomatisation.
6.1 Theories
Recall from Definition 3.5 that if A is an L-structure and Σ is a set of
L-sentences, we write A |= Σ, read ‘A models Σ’, to mean that every sentence
σ in Σ is true in A.
For any class of structures C, the theory Th(C) has the property of being
deductively closed, which we now explain.
31
32 6 Theories and Axioms
Some authors use the word theory to mean any set of sentences, and others
require satisfiability but not deductive closedness, or vice versa. In practice it
rarely matters. A minor quirk of our convention is that if C is the empty set of
L-structures, then Th(C) is the set of all L-sentences. So in this case (and only
in this case), Th(C) is not satisfiable and so is not a theory.
Example 6.6 (Axioms for the theory of groups) We can write the following
axioms for groups in the language Lgp = ·, (−)−1 , 1:
The theory of groups is the deductive closure of these three axioms. In other
words, it is the set of all Lgp -sentences which are true of all groups. So, for
example, the sentence
∀xy[x−1 · (x · y) = y]
6.2 Examples of Axioms 33
follows easily from the axioms so is in the theory of groups, but the sentence
∃x[x 1 ∧ x · x = 1]
is true in some groups (for example C2 , the cyclic group of order 2), but not
in other groups (for example C3 , the cyclic group of order 3), so is not in the
theory of groups.
so the theory of abelian groups is the deductive closure of {G1, G2, G3, AG}.
We have written four axioms for abelian groups, but we could write a single
axiom with the same meaning, the conjunction of those four axioms:
G1 ∧ G2 ∧ G3 ∧ AG.
Example 6.8 (Rings) We have the axioms for abelian groups, but now in the
additive language Ladgp = +, −, 0:
Then there are axioms for commutative monoids (the abelian group axioms
except for the inverse) in the language Lmon = ·, 1:
Example 6.9 (Fields) A field is a ring satisfying two additional axioms. First,
an axiom to rule out the zero ring,
F1. 0 1,
34 6 Theories and Axioms
and second an axiom which says that every non-zero element of the field has a
multiplicative inverse:
So the axioms R1–R8, F1, and F2 together axiomatise the theory of fields.
Remark 6.10 Notice that we put −, the additive inverse, as a function symbol
in the language. However, we cannot easily do the same for the multiplicative
inverse, because it is not defined at 0. We could put a unary function symbol for
it in the language, but we would have to define 0−1 somehow arbitrarily, and
then make sure that our axioms describing how (−)−1 works in fields took this
case into account. We follow the usual practice of not introducing a symbol
for it.
and for each L-formula ϕ(x), with one free variable x, the axiom
The last axiom scheme tries to capture the idea of induction. Induction says
that if 0 has a certain property, and whenever n has that property, then so does
n + 1, then every natural number has that property. The axiom scheme says that
for each property which can be expressed as a first-order formula.
6.4 Elementary Equivalence 35
This set of axioms, or its deductive closure, is called the theory of Peano
arithmetic, or PA. It is easy to check each axiom individually to see that
Ns-ring |= PA, and hence that PA ⊆ Th(Ns-ring ). Some of the axioms look
a little strange, for example (P5) is a very limited form of the associativity
axiom, and we could replace it with the full associativity axiom. In fact, the full
associativity of addition can be proved from all the axioms using the induction
scheme. The reason for using the limited form is that it is, at first sight, weaker,
and Peano was trying to write down the weakest set of axioms from which
everything else could be deduced. Can everything else about arithmetic be
deduced from the axioms of PA?
Exercises
6.1 Given a set Σ of L-sentences, let Mod(Σ) be the class of L-structures A
such that A |= Σ. Show that Th(Mod(Σ)) is the deductive closure of Σ.
6.2 Show that a theory T is complete if and only if, whenever A and B are
models of T , then A ≡ B.
6.3 For each of the five structures Ns-ring , Zs-ring , Qs-ring , Rs-ring , Cs-ring , write
down a sentence which is true in that structure but not in any of the other
four structures.
6.4 Show that the theory of fields is not complete.
6.5 Show that there must be a model of Peano arithmetic which is not
isomorphic to the standard model, Ns-ring .
6.6 Show that in any model A of PA, the function +A is associative.
6.7 Let L = R, f, c, where R is a binary relation symbol, f is a binary
function symbol, and c is a constant symbol. Let A be an L-structure
with three elements. Show that there is a single L-sentence σA such that
for any L-structure B, if B |= σA , then B A. How would you change
your proof to work for an arbitrary finite structure in an arbitrary finite
language?
6.8 -formula such that for every n ∈ N, the
Suppose that ϕ(x, y) is an Ls-ring
subset ϕ(Ns-ring , n) = x ∈ N Ns-ring |= ϕ(x, n) of N is non-empty. Let
M |= Th(Ns-ring ), and let a ∈ M. Show that ϕ(M, a) has a least element.
6.9 Can you find two structures which are elementarily equivalent but not
isomorphic? [This is quite difficult without some theory. Later we will
see many ways to answer the question.]
7
The Complex and Real Fields
One of the main problems addressed in this book is to start with a structure A
and to write down a complete axiomatisation of its theory. The general strategy
is simple. To find a candidate set of sentences Σ which might axiomatise
Th(A), start by writing down some sentences capturing properties of A. If
you can find another model B |= Σ and a sentence σ such that A |= σ and
B |= σ, then add σ to Σ to get a better candidate. When you can no longer do
this, you have a plausible candidate for a complete axiomatisation.
Actually proving that a given axiomatisation is complete is, in general,
a difficult problem. Gödel’s First Incompleteness Theorem shows that it is
impossible to give an explicit complete axiomatisation for Th(Ns-ring ). Using
this result, the same can also be shown for Th(Zring ) and Th(Qring ).
In this chapter we will describe complete axiomatisations for the complex
and real fields. In Part III of the book we will develop one method of proving
the completeness of an axiomatisation, the Łos–Vaught test. We will apply this
method to prove that our axiomatisation for the complex field is complete in
Chapter 30. The proof for the real field is similar but more involved and can
be found in the books of Marker [Mar02, Section 3.3] and of Poizat [Poi00,
Section 6.6].
The real field is a good illustration of the limitations of first-order logic.
The obvious axiomatisation is in second-order logic, where quantification over
subsets is allowed. We have to find a different axiomatisation to stay within
first-order logic.
37
38 7 The Complex and Real Fields
+ 1 + ··· + 1 0
1
n
for each n ∈ N+ . Since there are fields with non-zero characteristic, we need
these axioms.
In Lring we can express statements about polynomials. The fundamental
theorem of algebra states that every non-constant polynomial with coefficients
from C has a root in C. This fact can be written as a list of sentences in Lring ,
taking the sentence σn given by
states that y is an upper bound for S . Abbreviating it by UB(S , y), the formula
UB(S , z) ∧ ∀y[UB(S , y) → z y]
states that z is the least upper bound for S . Abbreviating that by LUB(S , z), the
sentence
(∀S ⊆ F) ((S ∅) ∧ ∃y[UB(S , y)]) → ∃z[LUB(S , z)]
expresses the completeness axiom. However, this is not a formula in the
language Lo-ring as we have defined it because we have also used the symbols ∈,
⊆, and ∅, but most importantly, we have a variable S which does not range over
the elements of F but over its subsets, and then we have quantified over that.
This is not allowed in first-order logic, but it is allowed in so-called second-
order logic. While we can make sense of what this axiom means, it is actually
not expressible by any set of first-order sentences. (See Exercise 9.5.) It follows
that there are models of the complete first-order theory of the real ordered field,
Th(Ro-ring ), which are necessarily ordered fields but which are not complete as
ordered sets.
However, it turns out that we can axiomatise the first-order theory
Th(Ro-ring ) in a way closer to the axiomatisation of algebraically closed fields.
Definition 7.7 The axioms for real-closed fields consist of the axioms of
ordered fields together with
RCF1. ∀x[0 x → ∃y[y2 = x]],
RCF2. ∀y0 . . . yn−1 ∃x[xn + yn−1 · xn−1 + · · · + y1 · x + y0 = 0]
for each odd n ∈ N.
In other words, a real-closed field is an ordered field in which every positive
element has a square root and every odd-degree polynomial has a root.
Fact 7.8 The axioms of real-closed fields axiomatise the complete theory RCF
of the real ordered field Ro-ring .
Using the basic ideas of real analysis, it is easy to verify that Ro-ring is a real-
closed field. However, the proof that the theory RCF is complete is beyond the
scope of this book.
Remark 7.9 Often the theory RCF is defined as an Lring -theory rather than
an Lo-ring -theory. The order is definable from the field structure as x < y ↔
∃z[z 0 ∧ x + z2 = y], so it would be possible to translate all the axioms we
have given involving < into Lring -sentences. However, other axiomatisations
are also possible. See [Mar02, Section 3.3] and [Poi00, Section 6.6] for more
details.
Exercises 41
Exercises
7.1 Give an example to show that the axioms of ordered fields do not
axiomatise a complete theory.
7.2 Verify that Ro-ring does satisfy the of axioms for real-closed fields, using
standard theorems of real analysis.
7.3 Prove that in any ordered field F we have 0 < 1 and 1 < 1 + 1 and, more
generally, that N; +, 0, 1, < embeds in F; +, 0, 1, <.
7.4 Let Σ be the set of axioms of ordered fields. Show that Σ ∀x[x · x 0].
7.5 Give a linear order on Cring satisfying axioms O1–O4. Show that there is
no linear order on Cring satisfying axioms O1–O5.
7.6 Suppose that S ⊆ R is non-empty and bounded above, and furthermore
that it is defined by an Lo-ring -formula ϕ(x). Now suppose that R is
another real-closed field, with domain R. Show that the subset ϕ(R) of R
defined by ϕ(x) has a least upper bound in R.
7.7 Is the usual definition of topological spaces given by first-order axioms
or second-order axioms? What about metric spaces?
7.8 [This exercise requires some knowledge of field theory.] A complex
number is algebraic if it is a zero of a non-trivial polynomial with integer
coefficients. Show that the set of algebraic numbers forms a subfield
of Cring which is algebraically closed. Show also that the set of real
algebraic numbers forms a subfield of R which is real-closed.
7.9 Look up the notion of Puiseux series, and find proofs that the field of
Puiseux series over C forms an algebraically closed field and that the
field of Puiseux series over R forms a real-closed field.
8
Compactness and New Constants
42
8.2 The Use of New Constant Symbols 43
but not straightforward. By contrast, the original proof uses the idea of a formal
deduction and so is not self-contained. For those who have seen the notion of
a formal deduction, we give here a short proof of the compactness theorem.
Proof Given a set of L-sentences Σ and another L-sentence ϕ, we can write
Σ d ϕ to mean that there is a formal deduction of ϕ from Σ. A formal deduction
is a finite list of L-formulas, so it only uses finitely many of the sentences
from Σ. So if Σ d ϕ, then there is a finite subset Σ0 of Σ such that Σ0 d ϕ.
The Completeness Theorem of first-order logic states that Σ d ϕ if and only if
Σ ϕ.
We write ⊥ for some contradictory sentence, for example ∃x[x x], which
is not true in any L-structure at all. Now Σ ⊥ means that every model of Σ is
a model of ⊥, and since there are no models of ⊥, it means there are no models
of Σ, that is, Σ is not satisfiable.
Now suppose that Σ is not satisfiable. Then Σ ⊥, so Σ d ⊥, hence there is
a finite subset Σ0 of Σ such that Σ0 d ⊥. Then Σ0 ⊥, so Σ0 is not satisfiable.
Therefore, whenever every finite subset of Σ is satisfiable, Σ itself is satisfiable,
as required.
Th(Ns-ring ) ∪ {c 0, c 1, c 1 + 1, c 1 + 1 + 1, . . .},
which consists of the complete theory of Ns-ring in the language Ls-ring , together
with sentences using the new constant symbol c which say that c is not equal
to any natural number. Now let Σ0 be a finite subset of Σ. Then there is
some number m ∈ N such that the sentence c
1 + 1 + · · · + 1 does not
m
44 8 Compactness and New Constants
Exercises
8.1 Is there a model M of Th(Ns-ring ) with an element m ∈ M satisfying
0 < m < 1?
8.2 Sketch a proof of Proposition 8.3. You should list all the key ideas and
explain how they fit together, without giving all the details.
46 8 Compactness and New Constants
47
48 9 Axiomatisable Classes
Exercises
9.1 Let C be a non-empty class of L-structures. Show that C ⊆ Mod(Th(C))
and that C is axiomatisable iff equality holds.
9.2 Let Σ be a satisfiable set of L-sentences. Show that Σ ⊆ Th(Mod(Σ)) and
that Σ is a theory iff equality holds.
Exercises 51
9.3 Show that the class of groups of size less than 100 is axiomatisable
and that the class of infinite groups is axiomatisable but not finitely
axiomatisable.
9.4 Show using the compactness theorem and the method of new constants
from the previous chapter that if C is an axiomatisable class with either
arbitrarily large finite models or an infinite model, then it has infinite
models of arbitrarily large cardinality.
9.5 Prove that the class of complete ordered fields is not axiomatisable.
[Hint: use Remark 8.5 (i).]
9.6 Is the class of cyclic groups axiomatisable? Is it finitely axiomatisable?
9.7 An abelian group G is said to be n-divisible for some n ∈ N+ if it satisfies
∀x∃y[ny = x], so each element can be divided by n (not necessarily
uniquely). G is divisible if it is n-divisible for all n ∈ N+ . Show that
the class of divisible abelian groups is axiomatisable but not finitely
axiomatisable.
9.8 Show that the group G = C {0}; ·, 1 is divisible but not torsion-free.
9.9 Let DTFAG be the theory of divisible, torsion-free abelian groups. Show
that if V is a Q-vector space considered as an Ladgp -structure, then V |=
DTFAG.
9.10 The characteristic of a field F is the least number n ∈ N+ such that
1 + · · · + 1 = 0, if such an n exists, and 0 otherwise. The characteristic
n
of a field is always 0 or a prime number. Show that the class of fields of a
fixed prime characteristic p is finitely axiomatisable and that the class of
fields of characteristic 0 is axiomatisable but not finitely axiomatisable.
9.11 Show that the class of fields of positive characteristic is not
axiomatisable.
9.12 Suppose that σ is an Lring -sentence which is true in every field of
characteristic 0. Show that there is N ∈ N such that if F is a field of
characteristic p with p > N, then F |= σ.
9.13 A graph G consists of a set of vertices, and between each pair of distinct
vertices, there may or may not be an edge. We can consider a graph
as a structure for the language with one binary relation E. The vertices
of the graph are the elements of the structure, and vertices v, w have
an edge between them if E(v, w) holds. A graph is then a model of the
sentence
∀xy[¬E(x, x) ∧ (E(x, y) → E(y, x))].
52 9 Axiomatisable Classes
The model theory we cover will use very few set-theoretic tools, essentially
only the basics of cardinal arithmetic. We give an intuitive explanation of what
little we need, omitting the proofs. In particular, we avoid the use of ordinals.
The underlying set theory we use is the standard one in mathematics, called
Zermelo–Fraenkel with Choice (ZFC). Details of the definitions and proofs
can be found in the first few pages of Kunen [Kun11] and Jech [Jec03]. For a
more gentle approach, Halmos [Hal74] is also suitable.
10.1 Cardinality
Definition 10.1 Two sets have the same cardinality (size) if and only if there
is a bijection between them. Given a set X, we write |X| for the cardinality of
X. A cardinal is a possible value of |X|.
We define |X| |Y| to mean there is an injective function from X to Y.
We will make use of four basic facts about injective functions, as follows:
Facts 10.2 Let X and Y be sets.
53
54 10 Cardinality Considerations
(iv) For any set X, there is a set Y (e.g., the power set PX) such that there is
an injective function X → Y but no injective function Y → X. (This is
Cantor’s theorem.)
From facts (i) and (ii), we see that is a linear order on cardinals. Fact (iii)
is often useful as an alternative way to show that |X| |Y|. Fact (iv) says there
is no greatest cardinal.
A set is finite precisely when its cardinality is some natural number n ∈
N; otherwise, it is infinite. There is a smallest infinite cardinal, which is |N|,
written ℵ0 . (ℵ, pronounced aleph, is the first letter of the Hebrew alphabet.) A
set is countable precisely when it is either finite or of cardinality ℵ0 ; otherwise,
it is uncountable. It is countably infinite if it is countable and infinite.
From Fact (iv), we see that the power set of the natural numbers, PN, is
uncountable. It is actually in bijection with the set R of real numbers, so R is
also uncountable.
Now Form(L) is a subset of the set of all finite strings of elements of X, and
hence | Form(L)| max(| Symb(L)|, ℵ0 ) by Proposition 10.5. So | Form(L)| =
max(| Symb(L)|, ℵ0 ), as required.
the one or two places it is needed, except in Part VI. Readers of that part of the
book should have no difficulty in learning how to do transfinite induction from
another source.
Some methods in model theory require an understanding of cardinal expo-
nentiation and issues relating to the continuum hypothesis and inaccessible
cardinals. These are briefly touched on in Chapter 27.
Exercises
10.1 What is the cardinality of the set of L-terms, given the vocabulary
Symb(L) of L?
10.2 Assume that for all infinite sets Y, we have |Y × Y| = |Y|. Then, using
Facts 10.2, deduce Facts 10.3 and 10.4.
10.3 Look up the definition of cardinal exponentiation and show that for any
set X, |PX| = 2|X| .
10.4 Prove Fact 10.2(i), the Schröder–Bernstein theorem.
10.5 Suppose that f : PX → X is an injective function. Let A =
{ f (S ) | S ⊆ X and f (S ) S }, and let a = f (A). By considering whether
a ∈ A, prove Fact 10.2(iv).
10.6 Show that Fact 10.2(iii) follows from the Axiom of Choice.
10.7 Using some form of the Axiom of Choice, for example Zorn’s lemma,
prove Fact 10.2 (ii).
11
Constructing Models from Syntax
The goal of this chapter is to give a proof of the compactness theorem which
does not go via the notion of formal deductions.
In mathematical practice, there is a distinction between the language we
use to describe mathematical objects and the objects themselves. Mathematical
logic makes this distinction formal. Syntax is the word describing the formal
language we use, as distinct from the meaning, or semantics, which arises when
we interpret the syntax in mathematical structures. In logic it is important to be
able to distinguish between the two, so for example we can distinguish between
an element of a structure and a constant symbol which names the element.
However, mathematical logic also considers syntax in such a formal way
that we can reason mathematically about it and indeed build mathematical
structures out of it. This is precisely what we do in this chapter, where we
follow Henkin’s method to prove that a set Σ of sentences is satisfiable by
building a model of Σ using the sentences themselves. This proof is extended
in Chapter 24 to prove the omitting types theorem.
57
58 11 Constructing Models from Syntax
Note in particular that if Σ is complete and deductively closed, then for each
L-sentence ϕ, either ϕ ∈ Σ or ¬ϕ ∈ Σ, and if Σ is also finitely satisfiable, then
it cannot contain both ϕ and ¬ϕ.
Lemma 11.2 (Lindenbaum’s lemma) If Σ is a finitely satisfiable set of
L-sentences, then there is a finitely satisfiable, deductively closed and complete
set Σ
of L-sentences such that Σ ⊆ Σ
.
The basic idea of the proof is to keep adding more sentences to Σ
maintaining finite satisfiability until, for every sentence ϕ, either ϕ or ¬ϕ is
included. We leave the details as an exercise.
Σ ⊆ Σ0 ⊆ Σ1 ⊆ Σ2 ⊆ · · · ⊆ Σn ⊆ · · · ,
with each Σn being a finitely satisfiable, deductively closed and complete set
of Ln -sentences. Then L∗ = n∈N Ln and Σ∗ = n∈N Σn will have the desired
properties. With the explanation out of the way, we start the proof.
11.3 Canonical Models 59
The structures Zring and Nsucc are canonical structures, but Ro-ring is not.
If A is an L-structure, then we can name every element of A with a new
constant symbol to get a canonical model in the expanded language LA . In
general, a theory will not have a canonical model unless it has enough closed
terms, which may involve adding new constant symbols. This is precisely what
Henkin theories are for.
60 11 Constructing Models from Syntax
For atomic formulas it holds by definition. The ∧ and ¬ inductive steps are
straightforward (see Exercise 11.4).
Suppose that ϕ( x̄) has the form ∃y[θ(y, x̄)]. Then
Exercises
11.1 Let L be a countable language, and enumerate the set of L-sentences as
(ϕn )n∈N . Let Σ be a finitely satisfiable set of L-sentences, and show that
at least one of Σ ∪ {ϕ0 } or Σ ∪ {¬ϕ0 } is finitely satisfiable. Then build on
this idea to prove Lindenbaum’s lemma in the case that L is countable.
11.2 [For those who know some set theory] Use transfinite induction or
Zorn’s lemma to prove Lindenbaum’s lemma for a language of arbitrary
cardinality.
11.3 Show that the relation ∼ on the set of closed L-terms of a Henkin theory
T given by “t1 ∼ t2 if the sentence t1 = t2 is in T ” is an equivalence
relation.
11.4 Complete the proof of Proposition 11.6 by showing that RA is well
defined and that the ∧ and ¬ steps of the induction on formulas hold.
11.5 Summarise the proof of the compactness theorem; that is, list all of the
key ideas and explain how they fit together, without giving all the details.
Part III
Changing Models
In this third part of the book, we extend the idea that a theory has different
models with the Löwenheim–Skolem theorems. The Downward Löwenheim–
Skolem theorem is proved using induction on formulas and the new idea of
Skolem functions. The Upward Löwenheim–Skolem theorem is proved by
extending the method of new constants to the method of diagrams.
The simplest possible description for the class of models of a theory is that
the models are determined by a single cardinal invariant, which is the case
for vector spaces which are determined by their dimension. In large enough
models, this dimension is equal to the cardinality of the model. A theory like
this with only one model of a certain cardinality is called categorical. The Łos–
Vaught test gives the completeness of an axiomatisation for such categorical
theories. So for several examples we are able to complete the first two parts of
our programme: to give an axiomatisation for the theory of a structure and to
classify the other models of the theory. The important back-and-forth method
is introduced to achieve the first aim for dense linear orders, although it turns
out to be impossible to classify all the models in that case. In the last chapter of
this part, the whole programme is given as an extended exercise for the natural
numbers with the successor function. This includes some investigation of the
definable sets, setting the scene for Part IV.
63
12
Elementary Substructures
We now consider the problem of finding new models of the theory of a given
structure. In this chapter we start with a structure B and find substructures A of
B which are elementarily equivalent to it, and in fact cannot be distinguished
from B even by formulas applied to elements of A. The new model A
is built using Skolem functions, and the method of proof is induction on
the construction of formulas. The Tarski–Vaught test helps to organise the
induction proof efficiently.
65
66 12 Elementary Substructures
π
We say that an embedding of L-structures A −→ B is an elementary
embedding iff π(A) B.
When A B, then A and B are very similar; indeed, they are indistin-
guishable from the point of view of the truth of L-formulas applied to elements
of A. The word elementary is used because the structures look the same in
terms of their elements, that is, in terms of first-order logic.
Separating out formulas into sentences and those with free variables, we
have two easy consequences of being an elementary substructure.
Lemma 12.4 Suppose A B. Then A ≡ B, and for any L-formula
ϕ(x1 , . . . , xn ), we have ϕ(A) = ϕ(B) ∩ An .
Proof Both conclusions are immediate from the definitions.
For ϕ an atomic formula, it is true by Lemma 3.6, because the inclusion map
A → B is an embedding.
There are inductive steps for ∧ , ¬, and ∃. The first two are easy and left as
an exercise. So suppose ϕ( x̄) is ∃yψ( x̄, y) and ā ∈ A. If A |= ∃yψ(ā, y), then
there is d ∈ A such that A |= ψ(ā, d), and so by induction, B |= ψ(ā, d), hence
B |= ∃yψ(ā, y). Conversely, if B |= ∃yψ(ā, y), then there is b ∈ B such that
12.3 The Downward Löwenheim–Skolem Theorem 67
B |= ψ(ā, b). Then, using the condition in the statement of the lemma, there is
d ∈ A such that B |= ψ(ā, d). Then, by induction again, A |= ψ(ā, d), hence
A |= ∃yψ(ā, y). That completes the ∃ inductive step and the whole proof.
Example 12.9 Consider the complex field Cring and the formula ϕ(x, y) given
by x = y · y. Then a Skolem function gϕ : C → C is a square-root function, so
for all x ∈ C we have gϕ (x)2 = x. In particular, we must have gϕ (−1) picking
out one of ±i, say, +i. But complex conjugation z → z is an automorphism of
Cring , and if gϕ were definable, it would be preserved under all automorphisms,
so we would have both gϕ (−1) = +i and gϕ (−1) = +i, that is, gϕ (−1) = −i, a
contradiction. So gϕ is not definable.
Example 12.10 Ns-ring has definable Skolem functions for every formula.
To prove it, we use the fact that every non-empty subset of N has a smallest
element. So for a formula ϕ( x̄, y) we can define a Skolem function by the
formula μϕ ( x̄, z) given by
Exercises
12.1 Prove Lemma 12.4.
12.2 Suppose A B and ϕ(x) is an L-formula. Show that if ϕ(B) is finite,
then ϕ(A) = ϕ(B), and if ϕ(B) is infinite, then ϕ(A) is also infinite.
Exercises 69
12.3 Why does Skolem’s paradox seem paradoxical, and why is it not in fact
contradictory?
12.4 In the real ordered field Ro-ring , write down Skolem functions for the
formulas x1 < y ∧ y < x2 , x1 < y, and y < x2 .
12.5 Suppose S ⊆ R is a finite subset which is definable in Ro-ring . Show that
S has a definable Skolem function. Then show that for every s ∈ S , the
singleton {s} is definable. [Hint: use induction on |S |.]
12.6 Suppose that B is a structure with Skolem functions given by function
symbols in the language. Show that any substructure of B is an elemen-
tary substructure.
12.7 Suppose that A ⊆ B ⊆ D are L-structures such that A D and B D.
Prove that A B.
12.8 Sketch a proof of the Downward Löwenheim–Skolem theorem. You
should give all the key ideas and explain how they fit together, but you
do not need to give all the details.
13
Elementary Extensions
In this chapter we consider the opposite problem to the previous chapter: given
a structure A, how can we find elementary extensions of it? In Chapter 8 we
used the compactness theorem in conjunction with new constant symbols to
find new models of Th(A). Here we combine those ideas with the method of
diagrams to find new models which are elementary extensions of A.
70
13.2 The Upward Löwenheim–Skolem Theorem 71
⎧
⎪
⎪ −1
⎨π (b) if b ∈ π(A),
g(b) = ⎪
⎪
⎩ f (b) otherwise.
because A D and B D. So A B.
Now N |= ∀x x n → ni=0 x = i , so since M ≡ N, we have M |=
∀x x n → ni=0 x = i , so M |= ni=0 a = i, and then a is a standard natural
number, a contradiction.
Proposition 13.8 Let M be any proper elementary extension of Ns-ring . Then
there is a non-standard prime number in M.
Proof Note that the formula ψ(y) given by
∀x[∃z[x · z = y] → (x = 1 ∨ x = y)] ∧ y 1
N |= ∀x∃y[ψ(y) ∧ x < y]
Sketch proof Let ϕ(x) be the formula ψ(x) ∧ ψ(x + 2), where ψ defines the
set of primes as above. If the twin prime conjecture is true, then the subset of
N defined by ϕ(x) is infinite, and a compactness argument shows there is some
M with a non-standard realisation of ϕ(x). If the twin prime conjecture is false,
then we can list all the realisations of ϕ(x) as n1 = 3, n2 = 5, n3 = 11, . . . , nr ,
for some finite r, and we have
⎡ ⎤
⎢⎢⎢
r ⎥⎥
Ns-ring |= ∀x ⎢⎢⎣ϕ(x) → x = ni ⎥⎥⎥⎦ .
i=1
r
But then, whenever M |= Th(Ns-ring ), we have M |= ∀x[ϕ(x) → i=1 x = ni ],
and hence there are no non-standard twin primes.
At the time of writing (2018), the twin prime conjecture is a long-standing
open problem, and we might hope that this reformulation of it would help to
solve it. Unfortunately, it does not, because there is no easy way to construct
explicit non-standard models of Th(Ns-ring ) and study them directly. However,
non-standard models are very useful for other theories where they can be
constructed.
Warning: the notions of finite and infinite non-standard real numbers are
different from the notions of finite and infinite as applied to sets.
Exercises
13.1 Prove Lemma 13.5.
13.2 Show that there is a model A of Th(Z< ) such that Q< embeds in A. Can
the embedding be elementary?
13.3 Let T be a complete theory in a language L of cardinality λ, and suppose
that T has an infinite model. Show that T has models of all cardinalities
greater than or equal to λ and no finite models.
13.4 Complete the proof of Proposition 13.11 by writing down the compact-
ness argument.
13.5 A Mersenne prime is a prime number of the form 2n − 1. Prove that there
are infinitely many Mersenne primes if and only if there is a non-standard
Mersenne prime. [You may assume that f (n) = 2n is a definable function
in Ns-ring . For a more difficult exercise, prove that it is definable.]
13.6 Show that there is a countable model R of Th(Ro-ring ) which is non-
Archimedean. Show that neither of R nor Ro-ring can be embedded in
the other.
13.7 Let R be any proper elementary extension of the ordered field Ro-ring of
real numbers.
(b) Let I be the set consisting of zero and all infinitesimals in R. Prove
that I is closed under addition and multiplication and that if α ∈ I
and r ∈ R, then α · r ∈ I.
(c) Let p(X) ∈ R[X] be a polynomial with standard real coefficients.
Show there is another polynomial q(X) ∈ R[X] such that whenever
x is a standard real and α is infinitesimal, there is β ∈ I such that
p(x + α) − p(x)
= q(x) + β.
α
(d) Explain briefly how we can use the above result to define the
derivative of a polynomial function. How does this method differ
from the usual approach in analysis?
13.8 Sketch a proof of the Upward Löwenheim–Skolem theorem. You should
give all the key ideas and explain how they fit together, but you do not
need to give all the details.
13.9 An elementary chain of L-structures is a chain
A 1 A2 · · · A n · · · .
Let A = n∈N+ An as in Exercise 5.9.
(a) Show that for each n ∈ N we have An A.
(b) Now suppose there is B such that each An B. Prove that A B.
13.10 This exercise uses the method of diagrams and compactness to prove
that an axiomatisable class C is axiomatised by universal sentences if
and only if it is closed under taking substructures. Suppose that C is
axiomatisable and that whenever B ∈ C and A is a substructure of B,
A ∈ C. Let Σ = Th(C), and let Σ∀ = {σ ∈ Σ | σ is a universal sentence }.
Let A |= Σ∀ , and let ϕ1 (c̄a ), . . . , ϕr (c̄a ) ∈ Diag(A).
(a) Show that Σ ∀ x̄ ¬ ri=1 ϕi ( x̄) .
(b) Using this idea, show that Σ ∪ Diag(A) is finitely satisfiable.
(c) Deduce that C = Mod(Σ∀ ).
(d) For the converse direction, prove that if C is axiomatised by a set of
universal sentences, then C is closed under taking substructures.
14
Vector Spaces and Categoricity
Definition 14.1 The theory of K-vector spaces, T K-VS , is the LK-VS -theory
given by the axioms for abelian groups, written additively in the language
Ladgp , together with the following axioms which describe how scalar multi-
plication works:
77
78 14 Vector Spaces and Categoricity
Note that axioms 2, 3, and 4 are not single LK-VS -sentences but families of
sentences. Axiom 2 is really a family of axioms indexed by elements of K,
and axioms 3 and 4 are families of axioms indexed by pairs of elements of K.
These are called axiom schemes. We cannot write these as single axioms in
LK-VS because that would involve a universal quantifier which quantified over
elements of K. However, that cannot exist in our language, which only allows
us to quantify over elements of our structure, which is the vector space, not the
field. (It is also possible to consider a language where some of the elements of
a model are elements of the field and some are elements of the vector space,
but that turns out to be like studying the field rather than studying the vector
space.)
For any field K, there is a 0-dimensional K-vector space with only one
element, 0. If K is a finite field, there are other finite K-vector spaces. Since we
are mostly interested in infinite structures, it is useful to consider the theory of
infinite K-vector spaces as well.
Definition 14.2 The theory of infinite K-vector spaces, T K∞-VS , is the theory
axiomatised by the axioms for K-vector spaces together with sentences saying
that there are at least n distinct elements for each n ∈ N+ .
Definition 14.3 Let V be a K-vector space. (We will use the same letter V for
the vector space and its domain.)
Facts 14.4 (i) Let B be a basis for V, and v ∈ V. Then there are a unique
n ∈ N, unique distinct b1 , . . . , bn ∈ B and unique λ1 , . . . , λn ∈ K {0}
We next show that for any field K, there are K-vector spaces of every
possible cardinal dimension.
Example 14.6 Let X be any set, and let K ⊕X be the set of functions f : X → K
of finite support, that is, such that there are only finitely many x ∈ X with
f (x) 0. We make K ⊕X into a K-vector space by pointwise operations:
n
λi b xi = 0, with the xi distinct. Then for each j = 1, . . . , n, we have f (x j ) =
i=1
i=1 λi b xi (x j ) = λ j . But f is the zero function, so each λ j = 0. So B is linearly
n
This function is surjective because B is a basis, so, using Fact 10.2(iii), we have
|V| |S |. By Proposition 10.5, we have |S | = max(|X|, ℵ0 ), and we also have
|X| = |K| · |B|. At least one of K and B is infinite (since otherwise V would be
finite), and so
14.4 Categoricity
We have seen that the theory of K-vector spaces has exactly one model (up to
isomorphism) of each infinite cardinality κ such that κ > |K|. There is a name
for such theories.
Example 14.14 There is no LR-VS -formula ϕ(x, y) which expresses that two
vectors are linearly independent.
Proof If such a ϕ(x, y) did exist, then we would have R2 |= ∃xy[ϕ(x, y)], but
R1 |= ¬∃xy[ϕ(x, y)], which is impossible, since R1 ≡ R2 .
82 14 Vector Spaces and Categoricity
Exercises
14.1 If K is a finite field and V is a K-vector space of dimension d, show
that |V| = |K|d .
14.2 If K is an infinite field, show that T K∞-VS is axiomatised by the axioms
for K-vector spaces together with the single axiom ∃x[x 0].
14.3 If V is a one-dimensional K-vector space, show that Aut(V) is isomor-
phic to the multiplicative group K × of non-zero elements of K.
14.4 If V is an n-dimensional K-vector space, show that Aut(V) is isomor-
phic to GLn (K), the group of invertible n × n matrices with entries in
K.
14.5 For any field K and any non-zero vector space V, show that there are
exactly four definable subsets of V.
14.6 Show that if a1 , . . . , an and b1 , . . . , bn are each linearly independent n-
tuples from V, then there is an automorphism π of V such that π(ai ) = bi
for each i.
14.7 Write F3 for the field with three elements, and let V be an infinite-
dimensional F3 -vector space. What are all the definable subsets of V
and of V 2 ?
14.8 In the language L= with no relation, function, or constant symbols, let
T be the empty theory, that is, (the deductive closure of) the empty set
of L= -sentences. What is a model of T ? Show that T is κ-categorical
for every cardinal κ.
14.9 Sketch a proof of Corollary 14.13, including the results used to prove
it. You should give all the key ideas and explain how they fit together,
but should not give all the details.
14.10 Suppose that A is a model of the theory DTFAG of divisible torsion-
free abelian groups from Exercise 9.9. Show that for each λ ∈ Q,
there is an Ladgp -formula which defines multiplication by λ on A in
such a way that A becomes a Q-vector space. Deduce that the theory
DTFAG ∪ {∃x[x 0]} is complete.
15
Linear Orders
In this chapter we will look at some theories of linearly ordered sets, aiming
to find complete axiomatisations using the method of categoricity. For dense
linear orders such as R< and Q< we will achieve this using the important back-
and-forth method.
Examples 15.2 The ordered set of real numbers is written R< . Likewise, we
have linearly ordered sets N< , Z< , Q< , and I< , where I is the closed unit interval
I = [0, 1] ⊆ R.
15.1 Endpoints
Both N< and I< have a least element, so they are models of the sentence
∃x∀y[x y],
while R< , Q< , and Z< do not have a least element. Similarly, I< has a greatest
element, so is a model of
∃x∀y[y x],
83
84 15 Linear Orders
while the other four examples are not. Least and greatest elements of a linearly
ordered set are called endpoints, so a linearly ordered set is without endpoints
if it satisfies the sentence
and
∀x[∃w[w > x] → ∃y[y > x ∧ ∀z[z > x → z y]]].
Note that any finite non-empty linearly ordered set is discrete and has
endpoints, and indeed it must be isomorphic to {1, 2, 3, . . . , n}; < for some
n ∈ N+ . On the other hand, R< , Q< , and I< are dense linear orders, captured by
the axiom
∀xy[x < y → ∃z[x < z ∧ z < y]].
Clearly a linearly ordered set cannot be both dense and discrete, although it is
possible to be neither.
We have found sentences to distinguish three of our five examples from
the others, and we will show that it is impossible to distinguish the last
two, R< and Q< , by a first-order sentence. Let DLO be the theory of dense
linear orders without endpoints, as given by the axioms stating transitivity,
irrelexivity, linearity, no endpoints, and density, together with a non-triviality
axiom ∃x[x = x] to rule out the empty linear order. We have Q< |= DLO and
R< |= DLO.
Proof of Theorem 15.3 Suppose A, B |= DLO and both are countable. Since
DLO has no finite models, A and B are both countably infinite. So we can
list A as (an )n∈N and B as (bn )n∈N . We will construct an isomorphism piece
by piece. In fact, for each n ∈ N, we will inductively construct finite subsets
An ⊆ A and Bn ⊆ B and a bijection πn : An → Bn such that:
• for each a, a ∈ An , a < a iff πn (a) < πn (a );
• An ⊆ An+1 , Bn ⊆ Bn+1 , and πn ⊆ πn+1 ; and
• an ∈ A2n+1 and bn ∈ B2n+2 .
In particular, πn is an isomorphism between An ; < and Bn ; <.
We start with A0 = B0 = ∅, and π0 the empty function. Now suppose n is
even, say, n = 2m, and we have constructed An , Bn , and πn . If am ∈ An , then
set An+1 = An , Bn+1 = Bn , and πn+1 = πn . By induction, the above conditions
are satisfied. Otherwise, am An , and we define An+1 = An ∪ {am }. We must
find a suitable element in B to be πn+1 (am ). If n = 0, we choose π1 (a0 ) = b0 .
Otherwise, there are three cases. Either (i) am is less then every element of An
or (ii) am is greater than every element of An or (iii) there are c, d ∈ An with
c < am and am < d, and no elements of An strictly between c and d. In each
case, because B |= DLO, there is b ∈ B such that b is (i) less than every element
of Bn or (ii) greater than every element of Bn or (iii) between πn (c) and πn (d).
To be precise, we choose the br for the smallest possible value of r ∈ N with
the desired property. Then we define Bn+1 = Bn ∪{br } and πn+1 = πn ∪{(am , br )}.
Now suppose that n is odd, say, n = 2m + 1. If bm ∈ Bn , then set An+1 = An ,
Bn+1 = Bn , and πn+1 = πn . Otherwise, let Bn+1 = Bn ∪ {bm }. Then we use the
same process as above to find ar ∈ A.
Now let π = n∈N πn . Our construction ensures that π is defined on all of A
and its image is all of B. It also preserves < (in particular, it is injective), and
so it is an isomorphism from A to B.
86 15 Linear Orders
Exercises
15.1 Give an example of a linearly ordered set which is neither discrete nor
dense.
15.2 Suppose that A is a discrete linear order without endpoints. Show that
the successor function which takes an element to the one immediately
above it is definable.
15.3 Let DLOep be the theory of dense linear orders with least and greatest
endpoints together with the axiom ∃xy[x < y]. Show that DLOep is
ℵ0 -categorical.
15.4 Let a, b ∈ Q. Show that there is an automorphism of Q< taking a to b.
15.5 Let A be a countable linearly ordered set. Show that there is an
embedding of A into Q< . [Hint: use the idea in the back-and-forth
proof, but only going forth, not back.]
15.6 Show that every non-empty finite linearly ordered set is discrete and
has endpoints. [Hint: use induction on the cardinality of the set.]
15.7 Show that the theory of non-empty discrete linear orders without
endpoints is not ℵ0 -categorical.
Exercises 87
15.8 If A and B are two linear orders, their lexicographic product A ×lex B
is the set A × B, linearly ordered by setting (a, b) < (c, d) if and only if
either a < c or (a = c and b < d). Show that any discrete linear order
without endpoints can be written as A ×lex Z< , for some linear order A.
15.9 Show that each singleton {n} is definable in N< . Using this fact and a
compactness argument, show that Th(N< ) is not ℵ0 -categorical.
15.10 Show that ThZ; <, 0 is not ℵ0 -categorical. Hence or otherwise show
that Th(Z< ) is also not ℵ0 -categorical.
16
The Successor Structure
16.1 Axioms
We first observe some basic properties of the successor function:
S1. s is injective;
S2. 0 is not in the image of s; and
S3. every element of N other than 0 is in the image of s.
Slightly less obvious is that there are no ‘cycles’, captured by the following
axiom scheme:
S4n . ∀x[sn (x) x] for n ∈ N+ ,
where s0 (x) = x and sn+1 (x) = s(sn (x)) for each n ∈ N.
Let us write T S for the set of axioms {S1, S2, S3} ∪ {S4n | n ∈ N+ }.
Exercise 16.2 Write down a similar list of axioms that is satisfied by Zsucc =
Z; s, 0.
88
16.2 Models 89
Exercise 16.3 Adapt the lists of axioms to the structures N; s and Z; s
which do not have a constant symbol naming 0.
16.2 Models
By design, Nsucc is a model of T S . By the Upward Löwenheim–Skolem
theorem, there are models of T S of every infinite cardinality. Now we will
investigate what these must look like.
Exercise 16.4 Show that every model of T S has a substructure which is
isomorphic to Nsucc . We will identify this substructure with N for notational
convenience.
Now suppose that M |= T S and M Nsucc . Then there is an element
a ∈ M N.
Exercise 16.5 Show that a lies in a substructure of M; s isomorphic to Z; s.
(We have taken a reduct to forget the constant 0; otherwise, it would not be a
substructure.) So any model M |= T S consists of Nsucc and a set of copies of
Z; s. We can be more precise.
For any set I, define MI = MI ; s, 0 to be the structure with domain MI =
N ∪ (I × Z), the constant symbol 0 naming the zero from N, and with s defined
by s(n) = n + 1 for n ∈ N and s((i, n)) = (i, n + 1) for each (i, n) ∈ I × Z.
Exercise 16.6 Verify that for any set I, MI |= T S .
Exercise 16.7 Show that if M is any model of T S , then there is a set I such
that M is isomorphic to MI .
Exercise 16.8 Show that MI1 MI2 if and only if I1 and I2 have the same
cardinality.
So now we have a classification of all the models of T S , up to isomorphism.
Exercise 16.9 Show that the cardinality of MI is |I| + ℵ0 .
Exercise 16.10 How many models are there of each cardinality, up to isomor-
phism? In which cardinalities is T S categorical?
Exercise 16.12 What changes if we take Zsucc , N; s, or Z, s instead of
Nsucc ?
Exercise 16.13 Show that every finite subset of Nsucc is definable and that
every cofinite subset (that is, the complement of a finite set) is also definable.
Exercise 16.16 Let A be any infinite structure and ϕ(A) ⊆ A and θ(A) ⊆ A
be infinite definable sets. Use a compactness argument to show there is B,
elementarily equivalent to A, such that the subsets ϕ(B) and θ(B) of B are
uncountable.
Exercise 16.17 Now suppose that ϕ(x) is a formula such that both ϕ(Nsucc )
and ¬ϕ(Nsucc ) are infinite. By considering ϕ(MI ) and ¬ϕ(MI ) for an
uncountable set I, find a contradiction. Deduce that the subsets of N which
are definable in Nsucc are exactly the finite and cofinite subsets. (S is cofinite
if its complement N S is finite.)
16.3 Definable Sets 91
Exercise 16.19 Show that no formula can define a linear order on MI , and
deduce that the order < on N is not a definable subset of N2 .
Part IV
In this part of the book we reach the main theme: the study of the definable
sets of a structure. We first introduce the important method of quantifier
elimination. For those structures where it holds, it means that to understand
the definable sets, it is enough to consider the sets defined by formulas without
quantifiers. The basic back-and-forth method suffices to prove quantifier elim-
ination for dense linear orders, and we introduce the method of substructure
completeness, which works for many other examples, including vector spaces
and (in Part VI) algebraically closed fields.
We then show how definable sets form Boolean algebras and relate the
atoms of these Boolean algebras to principal formulas. Finally, we work out
several examples, including the important case of the real field, where the
definable sets are also known as semi-algebraic sets.
93
17
Quantifier Elimination for Dense Linear Orders
and
x3 < x1 ∧ x2 = x4 ∧ (x3 < x5 ∨ x4 = x5 ).
95
96 17 Quantifier Elimination for DLO
$
n−1
% &
xσ(i) i xσ(i+1) ,
i=1
We will show that Ψ( x̄) defines the same subset of Qn as ϕ( x̄). Suppose
Q< |= ϕ(ā). Then ā satisfies some principal DLO formula ψ( x̄), and then ψ ∈ P
by definition of P. Since Q< |= ψ(ā), we have Q< |= Ψ(ā).
Conversely, suppose that Q< |= Ψ(ā). Then there is ψ ∈ P such that Q< |=
ψ(ā), and since ψ ∈ P, there is b̄ ∈ Qn such that Q< |= ϕ(b̄) ∧ ψ(b̄). We have
Q< |= ψ(ā) ∧ ψ(b̄), so by Proposition 17.3, there is an automorphism π of Q<
such that π(ā) = b̄. Since Q< |= ϕ(b̄), by Proposition 3.7, we have Q< |= ϕ(ā).
So Ψ( x̄) and ϕ( x̄) define the same subset of Qn , as required.
Definition 17.5 A structure A is said to have quantifier elimination if and
only if, for every n ∈ N+ , every definable subset of An is defined by a quantifier-
free formula.
Since disjunctions of principal DLO formulas are quantifier-free formulas,
Theorem 17.4 implies that Q< has quantifier elimination.
Exercises
17.1 List all of the principal DLO formulas for n = 3.
17.2 Prove Lemma 17.2.
17.3 Let T =∞ be the theory of infinite sets in the empty language L= . Prove that
T =∞ has quantifier elimination.
17.4 Let A be a finite set considered as an L= -structure. Prove that A has
quantifier elimination.
17.5 Show that the empty L= -theory does not have quantifier elimination.
Observe that, with the previous two exercises, this gives an example of
a theory without quantifier elimination, even though all of its models do
have quantifier elimination.
17.6 For the language consisting of two constant symbols, c and d, show
that the theory T ∞ stating that there are infinitely many elements has
quantifier elimination. By considering the sentence c = d, show that the
theory has exactly two completions.
17.7 Suppose that L is a language without constant symbols and that T is an
L-theory with quantifier elimination. Prove that T is a complete theory.
17.8 Show that the structure I< from Examples 15.2 does not have quantifier
elimination. However, show that it does have quantifier elimination if
we expand the language by adding constant symbols 0 and 1 for the least
and greatest endpoints.
18
Substructure Completeness
In the previous chapter we showed that the theory DLO of dense linear orders
without endpoints has quantifier elimination. The method we used relies on
the fact that every finite tuple from a dense linear order satisifies a special
quantifier-free formula (a principal DLO formula) which we could show
determines all the definable sets the tuple lies in. As we shall see in Chapter 25,
this method only works because DLO is countably categorical. In this chapter
we will give another method for proving quantifier elimination, which also
works for theories which are not countably categorical.
99
100 18 Substructure Completeness
Now to prove (iii) ⇒ (i), assume that T has quantifier elimination. Let M be
a model of T and A a substructure of M. Write MA for the expansion of M by
18.3 Quantifier Elimination and Completeness 101
Exercises
18.1 Show that the structure Z< does not have quantifier elimination.
18.2 Let L be the language with a single unary relation symbol R. Let T ∞
be the L-theory which says there are infinitely many elements, and for
n ∈ N, let T n∞ be the L-theory which also says that there are exactly n
elements in the subset named by R. Show that T ∞ is not substructure
complete but that each T n∞ is.
18.3 Let K be a field. Show that the incomplete theory T K-VS does not have
quantifier elimination but every completion of it does.
18.4 Describe all the finitely generated substructures of models of the theory
T S = Th(Nsucc ) from Chapter 16. Prove that T S is substructure complete.
Deduce that Nsucc has quantifier elimination.
18.5 Let N = N; s be the reduct of Nsucc without the constant symbol for 0.
Show that N does not have quantifier elimination.
18.6 Give two isomorphic subrings of Rring which illustrate that the real field
does not have quantifier elimination in the language Lring .
18.7 Suppose that T is a complete theory with quantifier elimination, that A
and B are models of T , and that π : A → B is an embedding. Show that
π is an elementary embedding.
18.8 An L-theory T is said to be model complete iff, whenever M |= T , the
theory T ∪ Diag(M) is a complete L M -theory.
(a) Show that T is model complete iff whenever M1 , M2 |= T and
M1 ⊆ M2 , then M1 M2 .
(b) Suppose that T ‘eliminates quantifiers to the level of existential
formulas’, that is, for every L-formula ϕ( x̄), there is an existential
L-formula θ( x̄) such that T ∀ x̄[ϕ( x̄) ↔ θ( x̄)]. Show that T is
model complete.
(c) Show that if T is model complete, then it eliminates quantifiers to
the level of existential formulas. [Hint: try to adapt the proof of
Proposition 18.2.]
19
Power Sets and Boolean Algebras
104
19.2 Lattices 105
However, not every partial order arises from a power set, so we need to
consider more properties.
19.2 Lattices
There are natural operations of intersection and union which we can capture.
Given a, b ∈ PX, we usually define a ∩ b as {x ∈ X | x ∈ a ∧ x ∈ b }. However,
this is not a definition by a formula in our chosen language. Nonetheless, there
is a formula which captures the notion of the intersection. We can see that
c = a ∩ b if and only if PX |= ϕ(a, b, c), where ϕ(x1 , x2 , y) is the formula
y ⊆ x1 ∧ y ⊆ x2 ∧ ∀w[(w ⊆ x1 ∧ w ⊆ x2 ) → w ⊆ y],
which says that y is the greatest lower bound of x1 and x2 . So in a power set,
every pair of elements has a greatest lower bound. Similarly, it has a least upper
bound, the union of the two sets. A power set PX also has a least element, ∅,
and a greatest element, X. So we can add the following axioms to the power
set axioms:
GLB ∀x1 x2 ∃y[y ⊆ x1 ∧ y ⊆ x2 ∧ ∀w[(w ⊆ x1 ∧ w ⊆ x2 ) → w ⊆ y]];
LUB ∀x1 x2 ∃y[x1 ⊆ y ∧ x2 ⊆ y ∧ ∀w[(x1 ⊆ w ∧ x2 ⊆ w) → y ⊆ w]];
Least element ∃y∀w[y ⊆ w]; and
Greatest element ∃y∀w[w ⊆ y].
Any partially ordered set satisfying these axioms is called a lattice.
It is convenient to introduce new constant symbols 0 for the least element
and 1 for the greatest element. The formula ϕ(x1 , x2 , y) above defines the
function y = x1 ∩ x2 , so we can use the binary function symbol ∩ as an
abbreviation, without changing which sets are definable. Similarly, we can use
∪ as an abbreviation. Such an expansion of the language, naming a relation,
function, or constant which is already definable, is called an expansion by
definitions.
We could then omit ⊆ from the language, since it is definable from ∩ or
from ∪ (see Exercise 19.3).
We note that ∩ and ∪ are commutative and associative in any lattice, and in
a power set, they also satisfy the following distributive laws:
Distributivity 1 ∀xyz[x ∩ (y ∪ z) = (x ∩ y) ∪ (x ∩ z)]; and
Distributivity 2 ∀xyz[x ∪ (y ∩ z) = (x ∪ y) ∩ (x ∪ z)].
Not all lattices satisfy these laws, but those which do are called distributive
lattices.
106 19 Power Sets and Boolean Algebras
19.4 Atoms
A fundamental property of sets is that they are determined by their elements.
In set theory this is known as the axiom of extension. An element x ∈ X is not
available directly to us, but the singleton set {x} is an element of PX. Singleton
sets are non-empty, but have no non-empty subsets.
Definition 19.2 An element a of a Boolean algebra B is called an atom if
B |= At(a), where At(x) is the formula
x 0 ∧ ∀w[w x → w = 0].
So we can include a version of the axiom of extension in our axioms. In
fact, given the other axioms of a Boolean algebra, it is equivalent to something
simpler.
Lemma 19.3 In any Boolean algebra the following two conditions are
equivalent:
a ⊆ b ∩ dc . But if a ⊆ b, then a ⊆ d, so a ⊆ dc , so a ⊆ b ∩ dc . So b ∩ dc
has no atoms beneath it. By the atomic property, b ∩ dc = 0. Similarly, we can
show that every atom is beneath b ∪ dc . So no atoms are beneath (b ∪ dc )c , so
(b∪dc )c = 0, so b∪dc = 1. So dc satisfies the properties of being a complement
of b, but complements are unique, so dc = bc , and taking complements of both
sides, it follows that d = b. So the extension property holds. The converse
direction is immediate.
Definition 19.4 A Boolean algebra satisfying the equivalent conditions of
Lemma 19.3 is called an atomic Boolean algebra.
Fact 19.5 The axioms for atomic Boolean algebras axiomatise the theory
T pow , and adding axioms saying the structure is infinite gives a complete
∞
axiomatisation of T pow .
∞
The theory T pow is not categorical in any infinite cardinal, so we cannot use
the Łos–Vaught test to prove completeness. The back-and-forth method can be
used as mentioned in Section 18.3. See [Poi00, Section 6.3] for details.
∞
Not every model of T pow is isomorphic to a power set algebra, so the class
of power set algebras is not an axiomatisable class.
Remarks 19.7 (i) We have considered power sets and Boolean algebras in
the language L⊆ = ⊆, and we introduced the constants 0 and 1 and the
function symbols ∩, ∪, and c as abbreviations. However, we could also
use the language LBool = ∩, ∪, c , 0, 1. In this case the axioms for
Boolean algebras will be different. Chapter 2 of Cori and Lascar [CL00]
gives a clear account of this and many other topics on Boolean algebras.
(ii) We have used the symbols ⊆, ∩, and ∪ for the partial order, greatest lower
bound, and least upper bound in a lattice or Boolean algebra, respectively,
even when it is not a power set algebra. It is more conventional to use ,
∧, and ∨, but I have avoided these symbols because the latter two conflict
with our symbols for AND and OR, which sometimes appear in the same
formulas.
108 19 Power Sets and Boolean Algebras
Exercises
19.1 Show that any linearly ordered set with endpoints is a distributive lattice,
but that if it has at least three elements, it is not a Boolean algebra.
19.2 Give examples of a partially ordered set which is not a lattice and a lattice
which is not distributive.
19.3 Show that in a lattice, the partial order ⊆ can be defined just using ∩ or
using ∪.
19.4 A Boolean algebra B is complete if every subset of B (not just the
finite subsets) has a greatest lower bound. Show that a complete atomic
Boolean algebra B is isomorphic to the power set algebra P(At(B)).
19.5 Suppose that B is a finite Boolean algebra. Show that B is complete and
atomic and that if n is the number of atoms of B, then |B| = 2n .
19.6 Show that in the language ∩, ∪, c , 0, 1, the theory of Boolean algebras
can be axiomatised by ∀-sentences. Use Proposition 5.7 to deduce that if
B is a subset of PX containing ∅ and X which is closed under ∩, ∪, and
c
, then B is a Boolean subalgebra of PX.
19.7 A Boolean ring is a ring R; +, ·, −, 0, 1 which satisfies ∀x[x · x = x]. In
a Boolean ring, define x ∩ y = x · y, define x ∪ y = x + y + x · y, and define
xc = 1 + x. Show that R; ∩, ∪, c , 0, 1 is a Boolean algebra. Conversely,
if B is any Boolean algebra, show how to define ·, +, and − to make B
into a Boolean ring.
19.8 An ideal of a Boolean algebra B is a subset I ⊆ B such that 0 ∈ I; if
y ∈ I and x ⊆ y, then x ∈ I; and if x ∈ I and y ∈ I, then x ∪ y ∈ I.
(a) Show that an ideal of a Boolean algebra B is the same thing as an
ideal of B considered as a Boolean ring.
(b) Show that the quotient B/I is also a Boolean ring.
19.9 A Boolean algebra is atomless if it satisfies ¬∃x At(x) and 0 1.
(a) Show that any atomless Boolean algebra is infinite.
(b) Let B be an infinite Boolean algebra, and let Fin(B) be the ideal
generated by At(B). Show that B/Fin(B) is an atomless Boolean
algebra.
(c) Use the back-and-forth method to show that the theory of atomless
Boolean algebras is countably categorical and has quantifier
elimination in the language ∩, ∪, c , 0, 1.
20
The Algebras of Definable Sets
In this chapter we will look more systematically at the definable sets in a model
A of a theory T . The definable subsets of An form a Boolean algebra, and we
study this in the examples of dense linear orders and vector spaces. We show
that the atoms of the Boolean algebras are related to certain formulas, called
principal formulas.
109
110 20 The Algebras of Definable Sets
We leave the proof as an exercise. The algebras Lindn (T ) are called the
Lindenbaum algebras of T .
Lemma 20.3 Let A be an L-structure and T = Th(A). There is an
isomorphism of Boolean algebras between Lindn (T ) and Def n (A) given by
So principal DLO formulas are principal formulas for the theory DLO,
and every principal formula for DLO is ∼DLO -equivalent to a principal DLO
formula.
For any L-structure A, a formula ϕ( x̄) ∈ Formn (L) is a principal formula for
Th(A) if and only if ϕ(A) is an atom of Def n (A). So to understand Def n (A), a
good start is to try to understand all the principal formulas. When there are only
finitely many, and every n-tuple from A satisfies one of them, this is enough to
determine all the definable sets. The following proposition captures the method
we used for DLO.
Proposition 20.5 Suppose ψ1 ( x̄), . . . , ψm ( x̄) are all principal formulas in n
variables for the complete theory T = Th(A), defining different subsets of An ,
and m i=1 ψi (A) = A . Then every definable set in Def n (A) is a union of some
n
are all equivalent under the theory T F∞3 -VS to formulas of the form ni=1 λi xi = 0
for scalars λi ∈ F3 .
For n = 1, this gives us atomic formulas 0 = 0, x1 = 0, and 2x1 = 0. The
latter two both define {0}, which is a singleton, so x1 = 0 is a principal formula
(see Exercise 20.6). The atomic formula 0 = 0 defines all of V and is not a
112 20 The Algebras of Definable Sets
x1 0 ∧ x2 = 0, x1 0 ∧ x2 = x1 , x1 0 ∧ x2 = 2 · x1 ,
which are all principal. If (a1 , a2 ) satisfies one of these formulas, then a1 and a2
are linearly dependent, so there is also the possibility that (a1 , a2 ) is a linearly
independent pair of vectors. We can also capture this situation with a single
formula,
$
λ1 · x1 + λ2 · x2 0,
(λ1 ,λ2 )∈F23 {(0,0)}
Exercises
20.1 Prove Lemma 20.2.
20.2 Prove Lemma 20.3.
20.3 Suppose that T is an incomplete theory and A |= T . Show there is a
surjective homomorphism of Boolean algebras Lindn (T ) → Def n (A)
as in Lemma 20.3, but that it is not injective.
Exercises 113
20.4 Give two examples of principal formulas and two examples of formulas
which are satisfiable but non-principal in the theory of Zring .
20.5 How many definable sets are there in Def n (Q< ) for n = 3 and n = 4?
20.6 Suppose that ϕ(x) is a formula such that T ∃=1 x[ϕ(x)]. Show that
ϕ(x) is a principal formula for T .
20.7 Consider the expansion A of Q< by constant symbols naming 0 and 1.
How many definable sets are there in Def n (A) for n = 1, 2?
20.8 How many definable sets are there in Def n (I< ) for n = 1, 2, where I is
the closed unit interval [0, 1] in the reals?
20.9 Let V be an infinite-dimensional F3 -vector space. Show that any pair
(a1 , a2 ) ∈ V 2 satisfies one of the six principal formulas given before
Definition 20.4.
20.10 How many definable sets are there in Def n (V) for n = 1, 2, 3, where V
is an infinite F4 -vector space?
20.11 Let A = Z; <, 0. Show that for every n ∈ N+ , Def n (A) is an atomic
Boolean algebra which is not complete.
20.12 Since Lindenbaum algebras are Boolean algebras, they satisfy the
distributive laws and de Morgan laws, which allow us to swap the
order of conjunctions, disjunctions, and negations. This allows us to
give normal forms for formulas which can be useful in understanding
definable sets. Let T be any L-theory, for example the empty L-theory.
Let ψ, ϕi , and ϕi j be any L-formulas for i = 1, . . . , r and j = 1, . . . , si .
r si
i=1 j=1 βi j , where each βi j is either an atomic formula or the
negation of an atomic formula.
(d) Show that if ϕ is a positive quantifier-free formula, that is, it is
constructed using ∧ and ∨ , but without implications or negations,
then its conjunctive and disjunctive normal forms also do not use
negation.
21
Real Vector Spaces and Parameters
n
i=1 λi xi = 0 for scalars λi ∈ R. Conjunctions of atomic formulas therefore
define vector subspaces of Rn , and indeed all subspaces of Rn are definable.
Thus Def n (RR-VS ) consists of all the Boolean combinations of subspaces of Rn .
The only subspace of R1 is {0}, so Def 1 (RR-VS ) consists of the four sets ∅,
{0}, R {0}, and R.
The subspaces of R2 are {(0, 0)}, R2 itself, and the one-dimensional
subspaces given by x2 = λx1 for each λ ∈ R, and by x1 = 0.
Lemma 21.1 For each n ∈ N+ , the formula ni=1 xi = 0 defining the origin
0 is a principal formula. If L is any 1-dimensional subspace of Rn , then any
formula defining L {0} is a principal formula.
Proof It is immediate that ni=1 xi = 0 is principal since it defines a singleton
set. Suppose that L is a one-dimensional subspace of Rn and a, b ∈ L{0}. Then
there is λ ∈ R{0} such that b = λa. Multiplication by λ is an automorphism of
115
116 21 Real Vector Spaces and Parameters
RR-VS , so a, b must satisfy the same formulas. So any formula defining L {0}
is principal.
Proposition 21.2 For all n ∈ N+ , Def n (RR-VS ) is an atomic Boolean algebra.
It is not complete if n 2.
Proof Let S ⊆ Rn be definable and non-empty. We must show that there is
an atom of Def n (RR-VS ) contained in S . Let a = (a1 , . . . , an ) ∈ S . If a = 0, then
{0} ⊆ S . Otherwise, there is i such that ai 0. For convenience, assume a1 0.
Then for each j = 2, . . . , n, there is λ j ∈ R such that a j = λ j a1 . Let ϕ( x̄) be the
formula x1 0 ∧ nj=2 x j = λ j x1 . Then ϕ( x̄) is a principal formula by Lemma
21.1, and the set it defines is contained in S . So in either case, S contains an
atom of the Boolean algebra Def n (RR-VS ), so Def n (RR-VS ) is atomic.
If n 2, then the number of atoms in Def n (RR-VS ) is |R|, but the total
number of formulas is also |R|, so |Def n (RR-VS )| = |R|. However, a complete
atomic Boolean algebra with |R| atoms has size |PR|, which is strictly larger
than |R|.
So as in the case of vector spaces over finite fields, principal formulas are an
important starting point in determining the definable sets. However, not every
definable set is a finite disjunction of these sets; indeed, R2 is not. So while
principal formulas are still important, they do not give the whole picture.
Now suppose that V is another model of T R∞-VS , for example V = R3 . For
each n we have Def n (V) Lindn (T R-VS ) Def n (RR-VS ), so the definable
subsets of V n are not Boolean combinations of all the vector subspaces of
V n = R3n but only Boolean combinations of certain subspaces. This is because
the variables xi range over the vectors in V and not over the real numbers. In
the proof of Proposition 21.2, to find the scalars λ, we made essential use of
the fact that we were working in the one-dimensional model RR-VS of T R-VS .
However, the conclusion of the proposition also holds for Def n (V). This is an
example where we get a benefit from working in a particular model of the
theory.
21.2 Parameters
We have seen that definable sets in RR-VS correspond to Boolean combinations
of homogeneous linear equations, that is, equations which state that a linear
combination of the variables is equal to 0. Often in linear algebra, one wishes
to consider systems of inhomogeneous equations, that is, equations of the form
n
i=1 λi xi = a, for some a 0. We can do this by adding a constant symbol to
21.2 Parameters 117
the language for a. In this case, constants representing elements of the structure
are called parameters.
S = {(x1 , . . . , xn ) ∈ M n | M |= ϕ(x1 , . . . , xn , a1 , . . . , am ) } .
In principle, there is nothing very new here. We can expand the language
L to LA and expand the structure M to MA by adding constants naming each
element of A. Then ThLA (MA ) is a complete LA -theory, and the subsets of
M n which are A-definable with respect to the language L and the same as
the subsets which are ∅-definable with respect to the language LA . However,
in practice, it is very useful to consider M and MA not as totally different
structures, because they are much more closely related than the structures
you can get by changing the language in other ways. For example, quantifier
elimination is preserved.
Lemma 21.4 Suppose M is an L-structure with quantifier elimination and
S ⊆ M n is a subset definable with parameters. Then S is defined using the
same parameters by a quantifier-free L-formula.
Proof Suppose S = { x̄ ∈ M n | M |= ϕ( x̄, ā) }. By quantifier elimination for
M, there is a quantifier-free L-formula θ( x̄, ȳ) such that M |= ∀ x̄ȳ[θ( x̄, ȳ) ↔
ϕ( x̄, ȳ)]. So θ( x̄, ā) is a quantifier-free formula defining S with the same
parameters.
Consider now the parametrically definable subsets of R2 with respect to
the structure RR-VS . As well as the origin (0, 0), any point (a, b) in R2 is now
definable by x1 = a ∧ x2 = b. As well as the straight lines through the
origin, formulas of the form λ1 x2 + λ2 x2 = a with λ1 , λ2 , a ∈ R now give
all the straight lines in R2 . So the parametrically definable subsets of R2 are
the Boolean combinations of points and straight lines.
118 21 Real Vector Spaces and Parameters
Exercises
21.1 Let V = R2 , considered as an R-vector space. Then both Def 2 (V) and
Def 4 (RR-VS ) are Boolean algebras of subsets of R4 . Give an example of
a subset S ⊆ R4 which is in Def 4 (RR-VS ) but not in Def 2 (V).
21.2 Let S ∈ Def 2 (RR-VS ). Show that either S or R2 S is defined by a
finite disjunction of principal formulas. Is the same true for every S ∈
Def 3 (RR-VS )?
21.3 Let A be the structure RR-VS expanded by a single constant symbol
naming 1. Find the atoms in the Lindenbaum algebra Def 2 (A).
21.4 Let M be an L-structure, suppose A ⊆ M is a set of parameters,
'
and let n ∈ N. Show that Def n (MA ) = Def n (MA0 ) | A0 is a finite
subset of A}.
21.5 Let M be an infinite set considered as an L= =structure, and let A ⊆ M.
How large is Def n (MA ) for n = 1, 2, when |A| = r, finite, and when
|A| = ℵ0 ?
21.6 Let M be an L-structure and A ⊆ M a subset. Recall that the
substructure of M generated by A is the smallest L-substructure of M
containing A. Write it as A. Show that Def n (MA ) = Def n (MA ).
21.7 The definable closure of a subset A of an L-structure M, written dcl(A),
is the set of all b ∈ M such that the singleton set {b} is definable in M,
with parameters from A. Show that A ⊆ dcl(A) and that Def n (MA ) =
Def n (Mdcl(A) ).
21.8 Suppose that S ⊆ R is parametrically definable with respect to the
structure RR-VS . Show that either S or R S is a finite set. In the latter
case, we say that S is a cofinite subset. Conversely, show that every
finite subset and every cofinite subset of R is parametrically definable
with respect to RR-VS .
21.9 The Lindenbaum algebras of structures are not always atomic. Here
is one example. Let L be the language with unary relation symbols
Dn for n ∈ N+ , and consider the structure R with domain R and with
Dn interpreted as the set of real numbers whose nth decimal digit after
the decimal point is even. Show that R has quantifier elimination by
showing that if r, s ∈ R satisfy the same quantifier-free formulas, then
there is an automorphism of R sending r to s. Then show that Def 1 (R)
is atomless.
21.10 Recall T S = Th(Nsucc ) from Chapter 16. Using the methods of that
chapter or using Exercise 18.4, show that if M is any model of T S , then
every subset of M definable with parameters is finite or cofinite. Show
also that no linear order is definable on M, even using parameters.
22
Semi-algebraic Sets
We consider now the subsets of Rn which are definable with parameters, with
respect to the structure Ro-ring . These subsets are also known as semi-algebraic
sets. As with many structures, the study of the definable sets combines model-
theoretic ideas with ideas from the branch of mathematics whence the structure
naturally comes, which in this case is elementary real analysis. For simplicity,
we will concentrate on the definable subsets of R and R2 , although most of the
ideas needed in higher dimensions are already present here.
22.1 O-Minimality
We will use Fact 18.5, which states that Ro-ring has quantifier elimination in the
ordered ring language. So, as in the previous chapter, we start by considering
the sets defined by atomic formulas, and then by quantifier-free formulas.
Lemma 22.1 Every atomic Lo-ring -formula, with parameters from R, defines
the same subset of Rn as a formula of the form f ( x̄) = 0 or f ( x̄) > 0, where
f ( x̄) is a polynomial with real coefficients.
The proof is left as an exercise.
Lemma 22.2 Every subset of Rn defined by a quantifier-free Lo-ring -formula,
with parameters from R, is a finite union of sets defined by formulas of the form
h( x̄) = 0 ∧ sj=1 g j ( x̄) > 0.
Proof Suppose S is defined by a quantifier-free formula ϕ( x̄). Then ϕ( x̄) is
a Boolean combination of atomic formulas. By the disjunctive normal form
theorem, Exercise 20.12, we can write ϕ( x̄) such that negation is applied only
to atomic formulas. But for any polynomial f ( x̄),
119
120 22 Semi-algebraic Sets
and
ti
Let hi ( x̄) = j=1 hi j ( x̄)2 . Then S is defined by
⎛ ⎞
r ⎜
⎜⎜⎜ $
si ⎟⎟⎟
⎜⎜⎝hi ( x̄) = 0 ∧ gi j ( x̄) > 0⎟⎟⎟⎠ ,
i=1 j=1
–4 –2 0 2
–2
The functions h(x, y) are then those appearing in the formula in Example
22.5. Note that f is not differentiable at x = −3, so is not analytic, and this
corresponds to the function h(x, y) = (y + 1)3 − x − 3 having ∂h
∂y (−3, −1) = 0.
am < am+1 = b. Now we claim that each interval Ik := (ak , ak+1 ) is contained in
one of the Dh . By definition, if c, c ∈ Ik and h ∈ H, then either both or neither
of c and c lie in Zh . From the formula defining f , for some i = 1, . . . , r, we
have Ik ⊆ Zhi . If Ik ⊆ Dhi , then we replace hi by ∂h
∂y and repeat if necessary. If
i
∂d hi
d is the degree of hi (x, y) as a polynomial in y, then ∂yd
is constant in y and
∂d hi
non-zero, so ∂yd
(x, f (x)) is a non-zero polynomial in x which cannot vanish on
the interval Ik . So at some stage we stop and find an h ∈ H such that Ik ⊆ Dh .
Thus we have shown that f is a piecewise Nash function, as required.
It is also true, and fairly easy to prove, that every piecewise Nash function
f : (a, b) → R is a semi-algebraic function, provided we use the definition
given above that piecewise means split into only finitely many pieces.
22.4 Cells
The definable subsets of R2 can be built from Nash functions as follows.
or
a < x ∧ x < b ∧ y = f (x),
where a < b are as above and f and g are Nash functions on (a, b) such that, for
all x ∈ (a, b), we have f (x) < g(x), except that f may be the constant function
with value −∞ and g may be the constant function with value +∞.
0-cells
1-cells 0 5
–5
There are notions of Nash m-cells in Rn for all m and n ∈ N+ , and the
results analogous to Propositions 22.10 and 22.12 can be proved together by
an induction on n.
If we replace Nash functions by arbitrary continuous definable functions
in Definition 22.11, we get a more general notion of cells (continuous cells).
Then the graph of the function f in Example 22.5 is a single 1-cell, whereas it
is the union of seven Nash cells.
Remarkably, a generalisation of Proposition 22.12 to Mn for arbitrary n ∈
+
N , called the cell decomposition theorem, is true in any o-minimal structure
M when we consider continuous cells.
The study of o-minimal structures is an important branch of model theory.
The book [vdD98] by van den Dries is an excellent introduction to the
subject, and Chapter 2 treats the case of semi-algebraic sets in detail for
the continuous cells. Semi-algebraic sets are studied in detail from a more
geometric viewpoint in [BCR98]. More information about the model theory of
Ro-ring can also be found in Section 3.3 of Marker’s book [Mar02] and in the
first chapter of [MMP06].
126 22 Semi-algebraic Sets
Exercises
22.1 Prove Lemma 22.1.
22.2 Show that the singleton set {a} ⊆ R is definable in Ro-ring without
parameters if and only if a is a real algebraic number, that is, it is the
zero of a non-constant polynomial with integer coefficients.
22.3 Sketch a proof of Proposition 22.3, including any results which are
needed for the proof.
22.4 Let S ⊆ R2 be defined by y + xy = y2 + x ∧ 2y 1 + x. Show that S is
the graph of a function f : R → R, and give a decomposition of f as a
piecewise Nash function.
22.5 Show that R2 can be partitioned into 21 Nash cells such that the graph
of the function f from example 22.5 is the union of 7 of those cells.
22.6 Show how the closed unit circle (x, y) ∈ R2 x2 + y2 1 can be
written as a union of cells. How many cells are needed?
22.7 The definition of a cell in R2 depends on the order of the variables x
and y. Give examples of cells C1 , C2 ⊆ R2 such that if we exchange the
roles of x and y, then C1 is still a cell, but C2 is not.
22.8 Show that the proof of Proposition 22.3 generalises to prove that any
real-closed field is o-minimal.
22.9 Use the completeness of RCF to show that the conclusions of Lemma
22.7 and Proposition 22.6 hold for any real-closed field.
22.10 Find a proof of Proposition 22.12.
22.11 [Uniform finiteness for semi-algebraic sets] Let ϕ( x̄, y) be an Lo-ring -
formula. For each ā ∈ Rn , write Dā for the subset of R defined by
ϕ(ā, y). Show that Dā is infinite if and only if it contains an open
interval. Deduce that the set of ā such that Dā is infinite is definable.
Further deduce that there is N ∈ N such that for any ā ∈ Rn , either Dā
is infinite or |Dā | N.
22.12 Consider Ro-R-VS , the real line as an ordered R-vector space, in
the language LR-VS ∪ {<}. Characterise the subsets of R2 which are
parametrically definable by quantifier-free formulas in this structure.
[This structure actually has quantifier elimination, and the definable
sets are known as semi-linear sets. See [vdD98, pp25–28] for more
details.]
22.13 Prove that (x, y) ∈ R2 y = x2 is not definable in R , nor even in
<
Ro-R-VS .
Part V
Types
Types are a central concept in model theory. In this part of the book we start
by explaining how types generalise elements or tuples from a structure: they
are like potential elements which exist in elementary extensions. We then
explain how types also generalise definable sets. A key tool is the omitting
types theorem, which is proved by extending the method of Henkin that
we previously used to prove the compactness theorem. The first application
of types is the Ryll–Nardzewski theorem, which characterises the countably
categorical structures as those structures A such that An has only finitely
many definable subsets for each n ∈ N. The ideas from the proof of that
theorem naturally lead to an analysis of the countable models of other theories,
including the notions of prime, atomic, universal, and ℵ0 -saturated models.
Finally, we extend the idea of saturation to uncountable models and give a
method for proving the completeness of a theory which, unlike the Łos-Vaught
test, does not require the theory to be categorical in any cardinal. Here we need
more set theory than elsewhere in the book, and some ideas are only sketched.
127
23
Realising Types
23.1 Types
Recall that Formn (L) is the set of all L-formulas with free variables from
x1 , . . . , xn only.
For example, we can consider the 2-type in the theory of infinite Q-vector
spaces consisting of all the formulas λ1 · v1 + λ2 · v2 0 such that (λ1 , λ2 ) ∈
Q2 {(0, 0)}. This is the type of a linearly independent pair of vectors.
We should check that the type of a tuple really is a type, according to our
definition.
Lemma 23.3 Let M |= T and ā ∈ M n . Then tpM (ā) is a complete n-type of T .
129
130 23 Realising Types
Proof The set of formulas tpM (ā) is finitely satisfiable, because it is satisfied
by ā. For any ϕ( x̄) ∈ Formn (L), either M |= ϕ(ā) or M |= ¬ϕ(ā), so tpM (ā) is
complete.
The type of a tuple is preserved under elementary extensions and auto-
morphisms.
Proposition 23.4 (i) Let π : M → N be an elementary embedding, and let
ā ∈ M n . Then tpM (ā) = tpN (π(ā)).
(ii) If π ∈ Aut(M) and ā ∈ M n , then tpM (ā) = tpM (π(ā)).
Proof For (i), we have ϕ( x̄) ∈ tpM (ā) iff M |= ϕ(ā) iff N |= ϕ(π(ā)) by
definition of an elementary embedding, and this is iff ϕ( x̄) ∈ tpN (π(ā)). Now
note that (ii) is a special case of (i).
Usually we are only considering one model, or elementary extensions or
elementary submodels of a given model, so then, by the proposition, the type
of tuple does not depend on the particular model M. So usually we write just
tp(ā) without the subscript M.
Proposition 23.7 Let P be any set of types of a complete theory T , and let
M |= T . Then there is an elementary extension of M which realises all the
types in P.
We leave the proof as an exercise for the reader.
Exercises
23.1 Suppose A is a substructure of B. Show that A B if and only if, for
every finite tuple ā from A, tpA (ā) = tpB (ā).
23.2 Prove Proposition 23.7.
23.3 Show that there is a 1-type of Th(Ns-ring ) of a number whose only prime
factor is 5 but which is divisible by 5n for all n ∈ N. Show there is another
1-type of Th(Ns-ring ) of a non-standard number which is divisible by 3 but
not by 9 or by any other standard natural number greater than 3.
23.4 Suppose ā, b̄ ∈ Qn with a1 < a2 < · · · < an and b1 < b2 < · · · < bn . By
considering automorphisms of Q< , show that tpQ< (ā) = tpQ< (b̄). Deduce
that there are only finitely many complete n-types in DLO, for each n ∈
N+ .
∞
23.5 Show there are exactly two complete 1-types in T K-VS for any field K.
23.6 Let p( x̄) be an n-type of a complete L-theory T . Let L = L ∪ {c1 , . . . , cn },
with the ci being new constant symbols, and let T be the deductive
closure of {ϕ(c̄) | ϕ( x̄) ∈ p( x̄) }. Show that T is an L -theory and that p is
a complete type if and only if T is a complete L -theory.
23.7 Recall that RCF = Th(Ro-ring ), and let p+∞ (x) = {x > n | n ∈ N }. Show
that p+∞ is a 1-type of RCF. For every polynomial f (x) ∈ Z[x], show
that exactly one of the formulas f (x) = 0, f (x) < 0, or f (x) > 0 is in (the
deductive closure of) p+∞ . Using quantifier elimination for RCF, deduce
that p+∞ is a complete type of RCF.
23.8 Recall from Exercise 18.4 that T S = Th(Nsucc ) has quantifier elimination.
Use this fact to determine all of the complete n-types in T S for n ∈ N+ .
24
Omitting Types
In the previous chapter we saw that any type of a theory T can be realised in
some model of T . In this chapter we consider which types are realised in all
models of T and which types can be omitted. First we explain how types can
be considered as a generalisation of definable sets.
for each (λ1 , λ2 ) ∈ Q2 {(0, 0)}. Then the intersection of the sets S λ1 ,λ2 is the
set of linearly independent pairs of vectors in the model V.
More generally, we can consider the intersection of any set {ϕi ( x̄) | i ∈ I }
of definable subsets of M n . The condition that the ϕi ( x̄) are finitely satisfiable,
and so are actually a type, corresponds to the condition that any intersection of
finitely many of the sets ϕi (M) is non-empty.
The intersection p(M) may be empty, and this corresponds to the type p
being omitted by the model M. For example, in the case of vector spaces
above, the intersection S λ1 ,λ2 (λ1 , λ2 ) ∈ Q2 {(0, 0)} is empty if V is a
one-dimensional Q-vector space but non-empty if dim V 2.
So we cannot necessary refer to the set of realisations in a particular model
as the type. However, by Proposition 23.7, there is a model M of T which
133
134 24 Omitting Types
realises all the n-types of T , for all n ∈ N+ . In this case, if p( x̄) and q( x̄) are
different n-types, then p(M) and q(M) are different subsets of Mn . If M is
such a model, then we refer to sets of the form p(M) as type-definable subsets
of M n .
Exercises
24.1 Let p( x̄) be an n-type of Th(M). Show that p is principal if and only if
there is a non-empty definable set S ⊆ M n such that S ⊆ p(M).
24.2 In Th(Ns-ring ), give an example of a complete principal 1-type and an
incomplete non-principal 1-type.
24.3 Show that if p( x̄) is a complete principal type, then there is a principal
formula ψ( x̄) in p( x̄). Find an example of an incomplete principal type
which does not contain a principal formula.
24.4 In Ro-ring , show that the family of intervals {(0, 1 + 1/n) | n ∈ N+ } is a
principal 1-type and the family of intervals {(1, 1 + 1/n) | n ∈ N+ } is a
non-principal 1-type.
24.5 Let r ∈ R be a real algebraic number, that is, a root of a non-zero
polynomial f (x) ∈ Z[x]. Show that tpRo-ring (r) is a principal type. Using
quantifier elimination for Ro-ring , show that if r ∈ R is a transcendental
number, then tpRo-ring (r) is non-principal.
∞
24.6 Let K be a field and let V |= T K-VS . Suppose (a1 , . . . , an ) ∈ V n is linearly
independent and (b1 , . . . , bn ) ∈ V is also linearly independent.
n
24.8 Sketch a proof of the omitting types theorem, including any lemmas
which are needed for its proof. Give all the key ideas and explain how
they fit together, without giving all the details.
24.9 Prove Theorem 24.4.
25
Countable Categoricity
In Chapter 15 we saw that the theory DLO of dense linear orders without
endpoints is countably categorical, that is, up to isomorphism, it has exactly
one countably infinite model, which is Q< . Then, in Chapter 17, we saw that
for each n ∈ N+ , only finitely many subsets of Qn are definable in Q< . In
the terminology of Chapter 20, the Lindenbaum algebras Lindn (DLO) are all
finite.
In this chapter we show that this finiteness property characterises countably
categorical theories. The proof uses types, and there are two more equivalent
properties involving types.
138
25.2 The Ryll–Nardzewski Theorem 139
Proof (i) ⇒ (ii): Suppose every type in S n (T ) is principal, but suppose for
a contradiction that S n (T ) is infinite, say S n (T ) = {pi | i ∈ I }. Let ψi be a
principal formula for pi . Let q = {¬ψi | i ∈ I }. We claim that q is finitely
satisfiable. So let ¬ψi1 , . . . , ¬ψir be a finite subset of q. Since I is infinite, there
is i ∈ I {i1 , . . . , ir }. Let ā be an n-tuple in some model M such that tp(ā) = pi .
Then M |= rj=1 ¬ψi j (ā). So q is finitely satisfiable and hence is a type. By
Lemma 25.1, there is a complete type q containing q. But q cannot be any of
the pi for i ∈ I, which is a contradiction. So S n (T ) is finite.
(ii) ⇒ (i): Suppose S n (T ) is finite, say, S n (T ) = {p1 , . . . , pr }. For each i, j ∈
{1, . . . , r} with i j, there is a formula ϕi j ( x̄) such that ϕi j ( x̄) ∈ pi and ¬ϕi j ( x̄) ∈
p j . Let ψi = rj=1, ji ϕi j . Then T ∃ x̄ψi ( x̄) because pi is a type and so finitely
satisfiable. Now suppose M |= T and ā ∈ M n with M |= ψi (ā). Then, for each
j i, M |= ϕi j (ā), so tpM (ā) p j . Thus tpM (ā) = pi . In particular, ψi is a
principal formula for pi . So every p ∈ S n (T ) is principal.
(iii) ⇒ (ii): Each type in S n (T ) corresponds to a subset of Lindn (T ), and
different types correspond to different subsets. There are 2|Lindn (T )| subsets of
Lindn (T ), so |S n (T )| 2|Lindn (T )| . Thus, if Lindn (T ) is finite, so is S n (T ).
(ii) ⇒ (iii): Suppose S n (T ) is finite. Let r = |S n (T )|. Then, by (ii)
⇒ (i), every type in S n (T ) is principal. Say the principal formulas are
ψ ( x̄), . . . , ψr ( x̄). Then, for each subset J of {1, . . . , r}, the formula ϕ J ( x̄) =
1
j∈J ψ j ( x̄) defines a different subset of M . But if S is a definable subset of
n
n
M , and p is a type, then either every realisation of p is in S or no realisation
of p is in S , so S must be defined by one of the formulas ϕ J ( x̄). Hence
|Lindn (T )| = 2|S n (T )| , so |Lindn (T )| is finite.
Proof Conditions (ii), (iii), and (iv) are all equivalent by Proposition 25.3.
(i) ⇒ (ii): Suppose that T is countably categorical but, for a contradiction,
assume there is a non-principal type p ∈ S n (T ) for some n ∈ N+ . By the
omitting types theorem, Theorem 24.3, there is a countable model A of T
which omits p. By Lemma 23.6, there is a countable model B of T and ā ∈ Bn
such that tp(ā) = p. Since T is countably categorical, there is an isomorphism
π : B → A. Then, by Proposition 23.4, we have tpA (π(ā)) = tpB (ā) = p.
But A omits p, so we have a contradiction. So every complete type of T is
principal.
(ii) ⇒ (i): This part of the proof uses the back-and-forth method and is very
similar to the proof that DLO is ℵ0 -categorical. Firstly, since the language is
countable and T has infinite models, by the strong compactness theorem, there
is at least one model of cardinality ℵ0 .
Suppose A and B are both models of T of cardinality ℵ0 . Enumerate A as
(an )n∈N+ and B as (bn )n∈N+ . We will construct new enumerations (αn )n∈N+ of A
and (βn )n∈N+ of B such that for every n ∈ N and every L-formula ϕ(x1 , . . . , xn ),
we have
Exercises
25.1 Let T be any complete theory. Show that a formula ψ( x̄) is a principal
formula for T if and only if [ψ( x̄)] is an atom of the Boolean algebra
Lindn (T ).
25.2 Use the idea from the proof of Lemma 20.6 to show that if Lindn (T ) is
finite, then every type in S n (T ) is principal.
25.3 Suppose that every complete n-type of a complete theory T is principal.
Show that every incomplete n-type of T is also principal.
25.4 Show that the theories ACF0 = Th(Cring ) and RCF = Th(Ro-ring ) are not
ℵ0 -categorical.
25.5 List all of the complete 2-types in the theory T F∞3 -VS . How many complete
3-types are there?
25.6 Sketch a proof of the Ryll–Nardzewski theorem. Explain all the key ideas
in the proof and how they fit together, without writing out all the details.
25.7 Suppose that T = Th(A), that |A| = ℵ0 , and that every finite tuple ā from
A realises a principal type. By adapting the last part of the proof of the
Ryll-Nardzewski theorem, show that for any model B |= T , there is an
elementary embedding π : A → B.
25.8 Countably categorical theories can also be characterised in terms of
permutation groups. This exercise and the next one briefly explain the
idea. Suppose A is a countable L-structure whose theory is countably
categorical. Let ā, b̄ ∈ An have the same type. Use the back-and-forth
method to construct π ∈ Aut(A) such that π(ā) = b̄.
25.9 Using the Ryll–Nardzewski theorem, we can deduce that the permutation
action of Aut(A) on An has only finitely many orbits, for each n ∈ N+ . A
group G acting on an infinite set A such that the induced action on An has
only finitely many orbits is called an oligomorphic permutation group.
Let G be an oligomorphic permutation group on a countably infinite
set A. Name each G-orbit O of An by an n-ary relation symbol RO , to
make a structure A in a language L. Show that every quantifier-free
definable subset of An is a finite union of orbits and that the projection
of such a set to An−1 is still quantifier-free definable, so A has quantifier
elimination. Show that A is countably categorical.
26
Large and Small Countable Models
Definition 26.2 A structure A is atomic if, for every finite tuple ā from A,
the type tpA (ā) is a principal type.
Warning The word atomic is related to the principal formulas which are
atoms in the Boolean algebras Lindn (T ); it has nothing to do with atomic
formulas.
142
26.2 Saturated and Universal Models 143
Analogously to the situation for small models, we also consider the property
of a model realising as many types as possible. However, there is a subtlety
here in that we need to consider types over parameters, that is, types in
expansions of T by constant symbols.
A 1 A2 A3 · · · A r · · ·
Exercises
26.1 For which K and d is a K-vector space of dimension d an atomic LK-VS -
structure? For which K and d is it prime, universal, or ℵ0 -saturated?
26.2 Suppose that T is a complete theory in a countable language and T has
an uncountable atomic model A. Show that T has a prime model.
26.3 Show that a complete theory T is countably categorical if and only if
every model of T is atomic.
26.4 Suppose that for every expansion A of A by finitely many constant
symbols, every 1-type of Th(A ) is realised in A . Show that A is ℵ0 -
saturated.
26.5 Complete the proofs of all the theorems in this chapter.
26.6 A structure A is strongly ℵ0 -homogeneous if, whenever ā, b̄ are n-
tuples of A and tpA (ā) = tpA (b̄), then there is an automorphism π ∈
Aut(A) such that π(ā) = b̄. Using the back-and-forth method, show
that countable atomic models and countable ℵ0 -saturated models are
strongly ℵ0 -homogeneous.
26.7 Suppose that A and B are countable, strongly ℵ0 -homogeneous models
of a complete theory T and they realise the same sets of n-types for all
n ∈ N+ . Show that A B.
26.8 Suppose that A is countable, universal, and strongly ℵ0 -homogeneous.
Show that A is ℵ0 -saturated. Give an example of a countable universal
structure which is not ℵ0 -saturated.
26.9 Let P be the set of all prime numbers in N. Given any subset Q of P,
show there is a 1-type of Ns-ring of an element which is divisible by all
the primes in Q but no other primes in P. Deduce that S 1 (Ns-ring ) is
uncountable.
26.10 Suppose that M is countable and ℵ0 -saturated and that S ⊆ M n . Show
that S is preserved under all automorphisms of M if and only if S is a
union of type-definable sets.
27
Saturated Models
The only method we have used in this book to prove that a given axiomatisation
of a theory is complete is the Łos–Vaught test: a theory with no finite models
which is categorical in some infinite cardinality is complete. In Chapter 18
we briefly discussed how the back-and-forth method can be adapted to give a
second method. In this chapter we give a third method using saturated models
and apply it to the theory of discrete linear orders without endpoints. This
works in the same spirit as the Łos–Vaught test, but we need to use more set
theory than before: at least transfinite induction, and for some theories, more.
27.1 Saturation
Theorem 26.9 is suggestive. It states that countable ℵ0 -saturated models of a
complete theory are unique up to isomorphism. Suppose a theory T has no
finite models and we can prove that any two countable ℵ0 -saturated models of
T are isomorphic. Then we want to conclude that T is complete. The problem
is that T might not have any countable ℵ0 -saturated model or that it might have
a completion with no countable ℵ0 -saturated model. So we would still need to
prove that every completion of T is 0-stable to deduce that T is complete. We
can address this problem by generalising the notion of ℵ0 -saturation.
147
148 27 Saturated Models
If we use the same back-and-forth proof as for Theorem 26.9, but with
transfinite induction in place of induction on natural numbers, we get the
following.
Theorem 27.2 Suppose A, B are saturated models of the same complete
theory T , of the same cardinality. Then A B.
27.2 Stability
We still have the problem of the existence of these saturated models. As in
the countable case, the only obstacle is that there may be too many types to
fit into a model, without making the model too large. There is an analogue of
0-stability.
27.5 Discussion
Note that the proof above of Theorem 27.8 is almost entirely about under-
standing the models of the theory, in fact, countable parts of models, and
relating them to something we already understand (countable parts of models
of DLO). The set theory behind the saturated models is not visible. Any
proof that DiscLO is complete needs to use at least some comparable level of
understanding of the models. In practice, this is exactly how saturated models
are used to simplify proofs, which could in principle be done by working
entirely inside small, often countable, models.
We have focused on proving completeness of theories here, but another
advantage of saturated models is that they have a lot of automorphisms, so
the methods we have used for quantifier elimination and for understanding
definable sets or types more generally can be extended easily.
One minor disadvantage to the method of saturated models, at least for
unstable theories, is the requirement to work with strongly inaccessible
cardinals. Under the usual set theoretic axioms (ZFC), you cannot prove that
strongly inaccessible cardinals do or do not exist. There are a number of
different ways to get around this. You can just work in this slightly stronger
set theory with strongly inaccessible cardinals or assume the generalised
continuum hypothesis, which gives another reason for saturated models to
exist. Then you can use set-theoretic methods to show that the theorems you
prove with these extra assumptions could also be proven in ZFC. Chang and
Keisler [CK90] use special models, which are similar to saturated models but
do always exist, and (for countable recursive theories) they also use recursively
Exercises 151
saturated models. Tent and Ziegler [TZ12] and Hodges [Hod93] take different
approaches again.
Exercises
27.1 Show that R< is not a saturated model of DLO.
27.2 Show that DiscLO is 0-stable. What is its countable saturated model?
27.3 Let M |= DLO and let A be a substructure with domain A. Using
quantifier elimination for DLO, show that 1-types of M over A
correspond to cuts in the order of A, that is, subsets C ⊆ A such that if
c ∈ C and a ∈ A with a < c, then a ∈ C.
27.4 Sketch a proof of Theorem 27.8, including any theorems and lemmas
which are used.
27.5 Show that, for each n ∈ Z, the function fn given by x → x + n is
definable in Z< , and hence in any model of DiscLO. Then show that
Z; <, ( fn )n∈Z has quantifier elimination.
27.6 Characterise the models of the theory of infinite discrete linear orders
with endpoints, and show the theory is complete.
27.7 Suppose we alter Definition 27.3 to say that T is κ-stable if over any
set of at most κ parameters there are at most κ + ℵ0 types, and we
remove the condition that κ be infinite. Show that the new definition
is equivalent to the old one when κ is infinite and that for any n ∈ N
the newly defined notion of n-stable is equivalent to Definition 26.10
of 0-stable.
27.8 This exercise, analogous to Exercise 26.6 in the countable case, indi-
cates how saturated structures have a lot of automorphisms. A structure
A is strongly κ-homogeneous if, whenever ā and b̄ are potentially
infinite tuples of length strictly less than κ such that tp(ā) = tp(b̄),
there is an automorphism π of A such that π(ā) = b̄. Make sense of
this definition, and use transfinite induction to prove that a saturated
structure of cardinalty κ is strongly κ-homogeneous.
27.9 Referring to another source, such as [Poi00], [Mar02], or [TZ12],
use the back-and-forth method to give another proof that DiscLO is
complete.
27.10 Assuming the generalised continuum hypothesis, show that every
theory has saturated models.
Part VI
153
28
Fields and Their Extensions
∀xy[x · y = 0 → (x = 0 ∨ y = 0)].
Every field is a domain, and since the ring axioms and the property of being
a domain are given by universal sentences, every Lring -substructure of a field is
a domain. The converse is also true: every domain is a substructure of a field,
in particular its field of fractions. The following lemma captures the property
we need.
Lemma 28.2 If R is a domain, then it has a field of fractions, which is a field
FR ⊇ R such that any embedding π : R → F of R into a field F extends
uniquely to an embedding FR → F.
Examples 28.3 We write R[x1 , . . . , xn ] for the ring of polynomials in the
variables x1 , . . . , xn , with coefficients from a ring R. If R is a domain, so is
R[x1 , . . . , xn ]. If R is a field F, the field of fractions of F[x1 , . . . , xn ] is written as
155
156 28 Fields and Their Extensions
√ √
Examples 28.14 Suppose √ F 2= Q and b = 2 ∈ Q(√ 2) ⊆ C. Then the
minimal√polynomial of 2 is x − 2. The same √ field Q( 2) is also generated
by c = 2 + 1. The minimal polynomial of 2 + 1 is x2 − 2x − 1.
The number π is transcendental, that is, it does not satisfy any polynomial
equations with coefficients from Q. So its minimal polynomial over Q is the
zero polynomial, and the ideal Iπ is the zero ideal {0}. Then the quotient map
evπ : Q[x] → Q(π) is injective, and the field Q(π) is isomorphic to the field
Q(x) of rational functions in one variable over Q.
n ∈ N. For n > 1, these are not always generated by a single polynomial, but
we have the next best thing.
Theorem 28.15 (Hilbert’s basis theorem) For any ideal I of F[x1 , . . . , xn ],
there is a finite set of polynomials which generates I.
Definition 28.16 If F ⊆ K is a field extension and b ∈ K, then b is said to be
algebraic over F if b satisfies some non-zero polynomial over F. Otherwise, it
is transcendental over F. If every element of K is algebraic over F, then K is
said to be an algebraic extension of F.
Finitely generated algebraic extensions have a special form.
Proposition 28.17 If K = F(b̄) is a finitely generated algebraic extension of
F, then there is a single element a which generates K as an extension of F.
Furthermore, the ring F[a] is actually all of K.
Finally, we give two useful lemmas.
Lemma 28.18 If F ⊆ K ⊆ L is a tower of field extensions, L is algebraic over
K, and K is algebraic over F, then L is algebraic over F.
A zero of a polynomial f (x) is a solution to the equation f (x) = 0.
Lemma 28.19 Let F be a field and f (x) ∈ F[x] a polynomial in one variable,
of degree d. Then there are at most d zeros of f in F.
This chapter is intended as a reminder or reference, but it covers the material
rather quickly to learn it from. Thus there are no exercises, other than to read
up on any parts of the chapter you are unfamiliar with from a suitable reference
and to do the exercises from there.
29
Algebraic Closures of Fields
For example, aclR (Q) is the field of real algebraic numbers. It is not an
algebraically closed field because it is a subfield of R and so, for example, the
polynomial x2 + 1 has no zero in aclR (Q).
Lemma 29.2 For any extension F ⊆ K of fields, aclK (F) is a subfield of K
of cardinality |F| | aclK (F)| max{|F|, ℵ0 }. In particular, if F is an infinite
field, then | aclK (F)| = |F|.
Proof We leave the proof that aclK (F) is a subfield as an exercise. For the
cardinality result, note that each element of aclK (F) is a zero of a polynomial
f (x) ∈ F[x], and f has at most deg( f ) zeros, a finite number. So | aclK (F)|
|F[x]| · ℵ0 . But |F[x]| = max{|F|, ℵ0 }, so | aclK (F)| max{|F|, ℵ0 }. Also F ⊆
aclK (F), so |F| | aclK (F)|.
159
160 29 Algebraic Closures of Fields
F = K0 ⊆ K1 ⊆ K2 ⊆ · · · ⊆ Kn ⊆ · · ·
for n ∈ N such that every non-constant f ∈ Kn [x] has a zero in Kn+1 . Let
K = n∈N Kn . Then K is an algebraically closed field extension of F.
Now we come to the second notion of algebraic closure of F. Unlike the
relative algebraic closure, it is defined without reference to a previously given
extension field K.
Putting together the previous proposition with the relative algebraic closure,
we can show the existence of an algebraic closure of a field F. With some more
work, we can also show uniqueness of the algebraic closure.
29.2 (Absolute) Algebraic Closure 161
Theorem 29.5 Every field F has an algebraic closure. If K and L are both
algebraic closures of F, then there is an isomorphism K L which restricts to
the identity on F.
Proof Let F be any field. By Proposition 29.3, there is an algebraically closed
field extension K of F. Take K0 = aclK (F). Suppose that f (x) is a non-constant
polynomial in K0 [x]. Then since K is algebraically closed, there is b ∈ K
such that f (b) = 0. Then b is algebraic over K0 , which is algebraic over F,
so, by Lemma 28.18, b is algebraic over F, and hence b ∈ K0 . So K0 is an
algebraically closed field which is an algebraic extension of F. So we have
shown that F has at least one algebraic closure.
Now suppose that K and L are both algebraic closures of F. We must find an
isomorphism π : K → L fixing F pointwise. We give a proof using transfinite
induction.
List K as (aα )α<λ for some ordinal λ. (If K is countable, then just take the
α to be natural numbers.) We define subfields Kα of K and embeddings πα :
Kα → L for α λ as follows:
Exercises
29.1 Show that if F is an algebraically closed field and f ∈ F[x] is a non-
zero irreducible polynomial, then f has the form f (x) = x − a for some
a ∈ F. Deduce that an algebraically closed field has no proper algebraic
extensions.
29.2 Show that for any field F, there is no algebraically closed proper subfield
of F alg which contains F.
29.3 Let F ⊆ K be an extension of fields. Explain how K can be regarded as
an F-vector space. Let α ∈ K. Show that α ∈ aclK (F) if and only if the
field F(α) is finite-dimensional as an F-vector space.
alg
29.4 For p prime, show that F p is the union of its finite subfields.
29.5 Let F ⊆ K be an extension of fields. Prove that aclK (F) is a subfield of
K.
29.6 The use of the compactness theorem in the proof of Proposition 29.3 is
actually hiding a use of the axiom of choice or transfinite induction. Give
a proof not using compactness when the field F is countable. Where is
the axiom of choice used in the proof of the compactness theorem?
29.7 Give another proof of the uniqueness part of Theorem 29.5 using the
back-and-forth method, avoiding a separate proof that the function π is
surjective.
30
Categoricity and Completeness
163
164 30 Categoricity and Completeness
30.2 Categoricity
Recall from Chapter 7 that we write ACF p for the theory of algebraically
closed fields of characteristic p, axiomatised by the axioms for ACF and either
1 + · · · + 1 = 0 or, if p = 0, the set of sentences
the sentence χ p given by
p
¬χq | q ∈ N+ .
Theorem 30.6
(i) For each p, prime or 0, the theory ACF p is categorical in all uncountable
cardinals.
(ii) For any field F, the theory Diag(F) ∪ ACF is categorical in all
uncountable cardinals λ such that λ > |F|.
Proof First we deduce (i) from (ii). For p prime, K |= Diag(F p ) ∪ ACF if
and only if K is an algebraically closed field of characteristic p, with constant
symbols naming 0, 1, 2, . . . , p − 1, if and only if K (without the extra constant
symbols) is a model of ACF p . For p = 0, the same applies with Q in place of
F p . So (i) follows from (ii).
Exercises 165
Now we prove (ii). Suppose that K and L are both models of Diag(F) ∪
ACF of the same uncountable cardinality λ, with λ > |F|. Then K and L are
both algebraically closed field extensions of F, and by Proposition 30.3, the
transcendence degrees of K and L as extensions of F are both λ. So let B
be a transcendence base for F ⊆ K, and let B be a transcendence base for
F ⊆ L. Then there is an isomorphism π between the subfields F(B) of K and
F(B ) of L, restricting to the identity on F, since by Lemma 30.2, they are both
isomorphic to the field of rational functions in λ variables. Then, by Theorem
29.5, this isomorphism π extends to an isomorphism π : K → L. So the theory
Diag(F) ∪ ACF is categorical in λ.
Corollary 30.7 For each p, prime or 0, the theory ACF p is complete and has
quantifier elimination.
Proof By the Łos–Vaught test, Lemma 14.11, it follows from part (i) of
Theorem 30.6 that the theories ACF p are complete.
Applying the Łos–Vaught test to part (ii) of the same theorem, we deduce
that ACF is substructure complete. By Proposition 18.2, it has quantifier
elimination, and thus so does each completion ACF p .
Putting together results from this chapter, we have the following classifica-
tion of algebraically closed fields.
Theorem 30.8 For each cardinal λ and each p, either a prime number or 0, up
to isomorphism, there is exactly one algebraically closed field of characteristic
p and transcendence degree λ.
Exercises
30.1 Prove that the characteristic of any field is either 0 or a prime number.
Deduce
that ACF0 is axiomatised by the axioms for ACF together with
¬χ p p is prime .
30.2 Use the compactness theorem to deduce that if σ is any Lring -sentence,
then ACF0 σ if and only if there is N ∈ N such that for all primes
p > N, ACF p σ.
30.3 Given a set X, a function cl : PX → PX is a closure operator if, for all
A, B ⊆ X and all a, b ∈ X: if A ⊆ B, then cl(A) ⊆ cl(B), A ⊆ cl(A), and
cl(cl(A)) = cl(A).
A closure operator cl has finite character if, whenever a ∈ cl(A), then
there is a finite subset A0 ⊆ A such that a ∈ cl(A0 ).
166 30 Categoricity and Completeness
31.1 Varieties
Quantifier-free formulas are, by definition, Boolean combinations of atomic
formulas. The language Lring has no relation symbols, so the only atomic
formulas are of the form t1 ( x̄) = t2 ( x̄), where t1 and t2 are terms. Lring -terms
are interpreted in K as polynomials f ( x̄) ∈ Z[ x̄]. If we allow parameters
from a subfield F of K, that is, constant symbols naming the elements of
F, then Lring (F)-terms are interpreted as polynomials in F[ x̄]. So atomic
formulas are of the form f1 ( x̄) = f2 ( x̄), for polynomials f1 and f2 . Setting
f ( x̄) = f1 ( x̄) − f2 ( x̄), the atomic formulas are all equivalent to formulas of the
form f ( x̄) = 0.
Before moving to arbitrary Boolean combinations of these equations,
we consider the positive Boolean combinations, that is, those built using
conjunctions and disjunctions but not negations.
By the conjunctive normal form theorem (see Exercise 20.12), a positive
Boolean combination of equations is equivalent to a formula of the form
$
r
si
fi j ( x̄) = 0.
i=1 j=1
167
168 31 Definable Sets and Varieties
i
Since K is a field, it has no zero divisors, so sj=1 f ( x̄) = 0 if and only if
+ si + si ij
f
j=1 i j ( x̄) = 0. So writing f i ( x̄) for the product j=1 fi j ( x̄), every positive
quantifier-free formula is equivalent to a finite conjunction of polynomial
equations ri=1 fi ( x̄) = 0.
The subsets of K n defined by these systems of polynomial equations are
known as varieties.
Definition 31.1 Let P be a set of polynomials from K[x1 , . . . , xn ]. The zero-
set of P is V(P) = {ā ∈ K n | for all f ( x̄) ∈ P, f (ā) = 0 }. The subset V(P) ⊆ K n
is called an affine algebraic variety, which we will abbreviate to variety. It is
also called a Zariski-closed subset of K n .
Remark 31.2 In algebraic geometry, the word variety is sometimes reserved
for a Zariski-closed subset which is irreducible. See Exercise 31.3. Apart from
affine varieties, there are also projective varieties, quasi-projective varieties,
and abstract varieties. They can also be treated as definable sets, but we will
keep to affine varieties.
In the definition of V(P), the set P of polynomials does not need to be
finite. So it appears that varieties are more general than positive quantifier-free
definable sets. We will show that in fact they are the same thing.
Varieties are closely related to ideals of the polynomial ring. Given a subset
P ⊆ K[ x̄], we have defined the variety V(P) ⊆ K n . We can also define an
operation in the opposite direction.
Definition 31.3 Given any subset S ⊆ K n , let I(S ) be the set of polynomials
in K[x1 , . . . , xn ] which vanish at all points in S . That is,
I(S ) = { f ( x̄) ∈ K[ x̄] | for all ā ∈ S , f (ā) = 0 } .
Lemma 31.4 For all S , S 1 , S 2 ⊆ K n and all P, P1 , P2 ⊆ K[x1 , . . . , xn ], the
following hold:
(i) I(S ) is an ideal in K[ x̄].
(ii) If S 1 ⊆ S 2 ⊆ K n , then I(S 1 ) ⊇ I(S 2 ).
(iii) If P1 ⊆ P2 ⊆ K[x1 , . . . , xn ], then V(P1 ) ⊇ V(P2 ).
(iv) V(I(S )) ⊇ S .
(v) I(V(P)) ⊇ P.
(vi) I(V(I(S ))) = I(S ).
(vii) V(I(V(P))) = V(P).
(viii) If I is the ideal generated by P, then V(I) = V(P).
The proof is left as an exercise. The characterisation of exactly which ideals
are I(S ) for some S is given by Hilbert’s Nullstellensatz, which is the subject
31.2 Constructible Sets 169
of Chapter 32. With this relation between varieties and ideals, we can apply
Hilbert’s basis theorem.
Proposition 31.5 Every variety V ⊆ K n is the zero set of a finite set of
polynomials.
Proof Suppose V = V(P). Then, by Lemma 31.4, V = V(I(V(P))). By
Theorem 28.15, there is a finite set { f1 , . . . , fr } of polynomials which generates
I(V(P)). Using the lemma again, V = V( f1 , . . . , fr ).
The following corollary summarises what we have proved.
Corollary 31.6 Let K be an algebraically closed field and n ∈ N+ . The
varieties V ⊆ K n are exactly the subsets of K n which are defined by positive
quantifier-free formulas (using parameters from K).
for some natural numbers r, si , ti and some polynomials fi j ( x̄) and gi j ( x̄). For
+i
each i, let gi ( x̄) be the product tj=1 gi j ( x̄), let Vi be the variety defined by
si i
f i j ( x̄) = 0, and let Wi be the variety defined by sj=1 fi j ( x̄) = 0 ∧ gi ( x̄) = 0.
j=1 r
Then the set defined by the formula above is i=1 (Vi Wi ). Thus we have
proved the following.
Proposition 31.7 Let K be an algebraically closed field and n ∈ N+ . Every
subset of K n which is Lring -definable with parameters from K is a finite union
of sets of the form V W, where V and W are varieties in K n .
It is generally much easier to deal with systems of equations than to
deal with negations of equations as well. The Rabinowitsch trick, introduced
170 31 Definable Sets and Varieties
Take Y to be defined by
⎛ s ⎞
r ⎜$
⎜⎜⎜ i ⎟⎟⎟
⎜⎝⎜ fi j (x1 , . . . , xn ) = 0 ∧ xn+i gi (x1 , . . . , xn ) − 1 = 0⎟⎟⎟⎠ .
i=1 j=1
polynomials fi .
Exercises
31.1 Suppose that I1 ⊆ I2 ⊆ I3 ⊆ · · · ⊆ Ir ⊆ · · · is an ascending chain of
ideals of F[ x̄]. Using the Hilbert basis theorem, show there is s ∈ N+
such that for all t > s, It = I s . [We say that F[ x̄] has the ascending
chain condition for ideals.]
31.2 Show that the collection of varieties in K n satisfies the descending
chain condition, that is, if
V1 ⊇ V2 ⊇ V3 ⊇ · · · ⊇ Vr ⊇ · · ·
173
174 32 Hilbert’s Nullstellensatz
capture the system with an Lring -formula ϕ( x̄, c̄) where ϕ( x̄, ȳ) has the form
$
r $
s
fi ( x̄, ȳ) = 0 ∧ gi ( x̄, ȳ) 0
i=1 i=1
By Theorem 32.1, K |= ∃ x̄ ri=1 fi ( x̄) = 0. Let ā ∈ K n be a witness, so
ā ∈ V(I). So V(I) ∅, as required.
Exercises
32.1 Let K be an algebraically closed field, and let I ⊆ K[ x̄] be an ideal.
Show that I = I(V(I)) if and only if I is a radical ideal. Give an example
to show that this fails if K is not algebraically closed.
32.2 Show that an ideal I ⊆ K alg [ x̄] is maximal if and only if it is generated
by polynomials of the form x1 − a1 , . . . , xn − an . Give an example to show
that this fails if K is not algebraically closed.
32.3 Give a complete proof of Hilbert’s Nullstellensatz along the lines of the
proof of Theorem 32.2, not using the Rabinowitsch trick.
32.4 Give a sketch proof of Hilbert’s Nullstellensatz. Explain what all the key
ideas in the proof are, how they fit together, and how they depend on
ideas from earlier in the book.
Bibliography
177
178 Bibliography
179
180 Index
L-structure, 3 of terms, 11
language, 3 of types, 130
lattice, 105 of universal formulas, 27
least upper bound, 105 prime model, 142
lexicographic product, 87, 149 prime subfield, 156
Lindenbaum algebra, 110, 116, 139 principal DLO formula, 95, 110
Lindenbaum’s lemma, 58 principal formula, 110, 115
linear order, 83, 148 principal ideal domain, 157
linearly independent, 78, 133, 136 principal type, 142
logical consequence, 31
quantifier elimination, 97, 100, 117, 150
Łos–Vaught test, 81, 85, 101, 147, 149, 165
for Nsucc , 103
Mersenne prime, 75 for Q< , 97
method of diagrams, 70, 72, 76, 160 for T =∞ , 98
method of new constants, 43–45, 71, 130, 134 for ACF, 165, 169, 172, 174
method of preservation under automorphisms, for atomless Boolean algebras, 108
21, 90, 97, 130, 146, 150 for DLO, 98, 150
minimal polynomial, 157, 161 for real-closed fields, 102, 132, 136
model, 15 for structures, 97
model completeness, 103 for theories, 97
for vector spaces, 101
n-type, 129 quotient ring, 156
Nash function, 122
piecewise Nash function, 123 Rabinowitsch trick, 169, 176
non-standard rational functions, 156
analysis, 75 real algebraic number, 136
model, 72 real field, 38, 45, 74, 176
natural number, 72, 131 real-closed field, 40, 102, 132
real number, 75 realise a type, 130
realising types, 139
o-minimal, 120 recursive definition
oligomorphic permutation group, 141 of existential formulas, 26
omitting types, 130, 139 of formulas, 13
omitting types theorem, 134 of quantifier-free formulas, 25
of Vaught, 136 of terms, 9
Order Property, 148 of universal formulas, 26
parameters, 117, 144 reduct, 6
parametrically definable, see definable with relation symbols, 3
parameters relative algebraic closure, 159
partial orders, 104 ring, 155
Ryll–Nardzewski theorem, 139, 143, 144
partial type, 134
Peano arithmetic, 35 satisfiable, 32
polynomials, 155, 167 formula with respect to a theory, 110
power set, 104 saturated, 147
prefix notation, 10 ℵ0 -saturated, 144
pregeometry, 166 κ-saturated, 147
preservation Schröder–Bernstein theorem, 53
of atomic formulas, 15 second-order logic, 37
of definable sets, 21 second-order logic (comparison with
of existential formulas, 26 first-order), 40
of formulas, 15 semantics, 57
of quantifier-free formulas, 18, 26 semi-algebraic sets, 21, 119
182 Index