AN INTRODUCTION TO SET THEORY

Professor William A. R. Weiss October 2, 2008

2

Contents

0 Introduction 7 1 LOST 11 2 FOUND 19 3 The Axioms of Set Theory 23 4 The Natural Numbers 31 5 The Ordinal Numbers 41 6 Relations and Orderings 53 7 Cardinality 59 8 There Is Nothing Real About The Real Numbers 65 9 The Universe 73 4 CONTENTS 10 Reflection 79 11 Elementary Submodels 89 12 Constructibility 101 13 Appendices 117

.1 The Axioms of ZFC . . . . . . . . . . . . . . . . . . . . . . . . 117 .2 Tentative Axioms . . . . . . . . . . . . . . . . . . . . . . . . . 118 Preface

These notes for a graduate course in set theory are on their way to becoming a book. They originated as handwritten notes in a course at the University of Toronto given by Prof. William Weiss. Cynthia Church produced the first electronic copy in December 2002. James Talmage Adams produced the copy here in February 2005. Chapters 1 to 9 are close to final form. Chapters 10, 11, and 12 are quite readable, but should not be considered as a final draft. One more chapter will be added.

6 CONTENTS

Chapter 0

Introduction

Set Theory is the true study of infinity. This alone assures the subject of a place prominent in human culture. But even more, Set Theory is the milieu in which mathematics takes place today. As such, it is expected to provide a firm foundation for the rest of mathematics. And it does—up to a point; we will prove theorems shedding light on this issue.

Because the fundamentals of Set Theory are known to all mathematicians, basic problems in the subject seem elementary. Here are three simple statements about sets and functions. They look like they could appear on a homework assignment in an undergraduate course.

1. For any two sets X and Y, either there is a one-to-one function from X into Y or a one-to-one function from Y into X.

2. If there is a one-to-one function from X into Y and also a one-to-one function from Y into X, then there is a one-to-one function from X onto Y.

3. If X is a subset of the real numbers, then either there is a one-to-one function from the set of real numbers into X or there is a one-to-one function from X into the set of rational numbers.

They won’t appear on an assignment, however, because they are quite difficult to prove. Statement (2) is true; it is called the Schroder-Bernstein Theorem. The proof, if you haven’t seen it before, is quite tricky but nevertheless uses only standard ideas from the nineteenth century. Statement (1) is also true, but its proof needed a new concept from the twentieth century, a new axiom called the Axiom of Choice.

Statement (3) actually was on a homework assignment of sorts. It was the first problem in a tremendously influential list of twenty-three problems posed by David Hilbert to the 1900 meeting of the International Congress of Mathematicians. Statement (3) is a reformulation of the famous Continuum Hypothesis. We don’t know if it is true or not, but there is hope that the twenty-first century will bring a solution. We do know, however, that another new axiom will be needed here. All these statements will be discussed later in the book.

Although Elementary Set Theory is well-known and straightforward, the modern subject, Axiomatic Set Theory, is both conceptually more difficult and more interesting. Complex issues arise in Set Theory more than any other area of pure mathematics; in particular, Mathematical Logic is used in a fundamental way. Although the necessary logic is presented in this book, it would be beneficial for the reader to have taken a prior course in logic under the auspices of mathematics, computer science or philosophy. In fact, it would be beneficial for everyone to have had a course in logic, but most people seem to make their way in the world without one.

In order to introduce one of the thorny issues, let’s consider the set of all those numbers which can be easily described, say in fewer then twenty English words. This leads to something called Richard’s Paradox. The set

{x : x is a number which can be described in fewer than twenty English words}

must be finite since there are only finitely many English words. Now, there are infinitely many counting numbers (i.e., the natural numbers) and so there must be some counting number (in fact infinitely many of them) which are not in our set. So there is a smallest counting number which is not in the set. This number can be uniquely described as “the smallest counting number which cannot be described in fewer than twenty English words”. Count them—14 words. So the number must be in the set. But it can’t be in the set. That’s a contradiction. What is wrong here?

Our naive intuition about sets is wrong here. Not every collection of numbers with a description is a set. In fact it would be better to stay away from using languages like English to describe sets. Our first task will be to build a new language for describing sets, one in which such contradictions cannot arise.

We also need to clarify exactly what is meant by “set”. What is a set? We do not know the complete answer to this question. Many problems are still unsolved simply because we do not know whether or not certain objects constitute a set or not. Most of the proposed new axioms for Set Theory are of this nature. Nevertheless, there is much that we do know about sets and this book is the beginning of the story.

10 CHAPTER 0. INTRODUCTION

LOST

We construct a language suitable for describing sets.

The \underline{symbols}:

variables v_{0}, v_{1}, v_{2}, …
equality symbol =
membership symbol ∈
logical connectives ∧, ∨, ¬, →, ↔
quantifiers ∀, ∃
parentheses (,)

The \underline{atomic formulas} are strings of symbols of the form: (v_{i} ∈ v_{j}) or (v_{i} = v_{j})

The collection of \underline{formulas of set theory} is defined as follows:

1. An atomic formula is a formula.

2. If Φ is any formula, then (¬Φ) is also a formula.

3. If Φ and Ψ are formulas, then (Φ ∧ Ψ) is also a formula.

4. If Φ and Ψ are formulas, then (Φ ∨ Ψ) is also a formula.

5. If Φ and Ψ are formulas, then (Φ → Ψ) is also a formula.

6. If Φ and Ψ are formulas, then (Φ ↔ Ψ) is also a formula.

7. If Φ is a formula and v_{i} is a variable, then (∀v_{i})Φ is also a formula.

8. If Φ is a formula and v_{i} is a variable, then (∃v_{i})Φ is also a formula.

Furthermore, any formula is built up this way from atomic formulas and a finite number of applications of the inferences 2 through 8.

Now that we have specified a language of set theory, we could specify a proof system. We will not do this here—see n different logic books for n different proof systems. However, these are essentially all the same— satisfying the \underline{completeness theorem} (due to K. Gödel) which essentially says that any formula either has a proof or it has an interpretation in which it is false (but not both!). In all these proof systems we have the usual logical equivalences which are common to everyday mathematics. For example:

For any formulas Φ and Ψ:

(¬(¬(Φ))) is equivalent to Φ;
(Φ ∧ Ψ) is equivalent to ¬((¬Φ) ∨ (¬Ψ));
(Φ → Ψ) is equivalent to ((¬Φ) ∨ Ψ);
(Φ ↔ Ψ) is equivalent to ((Φ → Ψ) ∧ (Ψ → Φ));
(∃v_{i})Φ is equivalent to (¬(∀v_{i})(¬Φ)); and,
(Φ ↔ Ψ) is equivalent to (Ψ ↔ Φ).

The complete collection of \underline{subformulas} of a formula Φ is defined as follows:

1. Φ is a subformula of Φ;

2. If (¬Ψ) is a subformula of Φ, then so is Ψ;

3. If (Θ ∧ Ψ) is a subformula of Φ, then so are Θ and Ψ; 4. If (Θ ∨ Ψ) is a subformula of Φ, then so are Θ and Ψ;

5. If (Θ → Ψ) is a subformula of Φ, then so are Θ and Ψ;

6. If (Θ ↔ Ψ) is a subformula of Φ, then so are Θ and Ψ;

7. If (∀v_{i})Ψ is a subformula of Φ and v_{i} is a variable, then Ψ is a subformula of Φ; and,

8. If (∃v_{i})Ψ is a subformula of Φ and v_{i} is a variable, then Ψ is a subformula of Φ.

Note that the subformulas of Φ are those formulas used in the construction of Φ.

To say that a variable v_{i} \underline{occurs bound} in a formula Φ means one of the following two conditions holds:

1. For some subformula Ψ of Φ, (∀v_{i})Ψ is a subformula of Φ; or,

2. For some subformula Ψ of Φ, (∃v_{i})Ψ is a subformula of Φ.

The result, Φ^{∗}, of \underline{substituting} the variable v_{j} for each \underline{bound occurrence} of the variable v_{i} in the formula Φ is defined by constructing a Ψ^{∗} for each subformula Ψ of Φ as follows:

1. If Ψ is atomic, then Ψ^{∗} is Ψ;

2. If Ψ is (¬Θ) for some formula Θ, then Ψ^{∗} is (¬Θ^{∗});

3. If Ψ is (Γ ∧ Θ) for some formula Θ, then Ψ^{∗} is (Γ^{∗} ∧ Θ^{∗});

4. If Ψ is (Γ ∨ Θ) for some formula Θ, then Ψ^{∗} is (Γ^{∗} ∨ Θ^{∗});

5. If Ψ is (Γ → Θ) for some formula Θ, then Ψ^{∗} is (Γ^{∗} → Θ^{∗});

6. If Ψ is (Γ ↔ Θ) for some formula Θ, then Ψ^{∗} is (Γ^{∗} ↔ Θ^{∗});

7. If Ψ is (∀v_{k})Θ for some formula Θ then Ψ^{∗} is just (∀v_{k})Θ^{∗} if k ≠ i, but if k = i then Ψ^{∗} is (∀v_{j})Γ where Γ is the result of substituting v_{j} for each occurrence of v_{i} in Θ; and, 8. If Ψ is (∃v_{k})Θ for some formula Θ then Ψ^{∗} is just (∃v_{k})Θ^{∗} if k ≠ i, but

if k = i then Ψ^{∗} is (∃v_{j})Γ where Γ is the result of substituting v_{j} for each occurrence of v_{i} in Θ.

That a variable v_{i} \underline{occurs free} in a formula Φ means that at least one of the following is true:

1. Φ is an atomic formula and v_{i} occurs in Φ;

2. Φ is (¬Ψ), Ψ is a formula and v_{i} occurs free in Ψ;

3. (Θ ∧ Ψ), Θ and Ψ are formulas and v_{i} occurs free in Θ or occurs free in Ψ;

4. Φ is (Θ ∨ Ψ), Θ and Ψ are formulas and v_{i} occurs free in Θ or occurs free in Ψ;

5. Φ is (Θ → Ψ), Θ and Ψ are formulas and v_{i} occurs free in Θ or occurs free in Ψ;

6. Φ is (Θ ↔ Ψ), Θ and Ψ are formulas and v_{i} occurs free in Θ or occurs free in Ψ;

7. Φ is (∀v_{j})Ψ and Ψ is a formula and v_{i} occurs free in Ψ and i ≠ j; or,

8. Φ is (∃v_{j})Ψ and Ψ is a formula and v_{i} occurs free in Ψ and i ≠ j.

As in the example below, a variable can occur both free and bound in a formula. However, notice that if a variable occurs in a formula at all it must occur either free, or bound, or both (but not at the same occurrence).

We define the important notion of the \underline{substitution of a variable} v_{j} for each free occurrence of the variable v_{i} in the formula Φ. This procedure is as follows.

1. Substitute a new variable v_{l} for all bound occurrences of v_{i} in Φ.

2. Substitute another new variable v_{k} for all bound occurrences of v_{j} in the result of (1).

3. Directly substitute v_{j} for each occurrence of v_{i} in the result of (2).

Example. Let us substitute v_{2} for all free occurrences of v_{1} in the formula

((∀v_{1})((v_{1} = v_{2}) → (v_{1} ∈ v_{0})) ∧ (∃v_{2})(v_{2} ∈ v_{1}))

The steps are as follows.

1. ((∀v_{1})((v_{1} = v_{2}) → (v_{1} ∈ v_{0})) ∧ (∃v_{2})(v_{2} ∈ v_{1}))

2. ((∀v_{3})((v_{3} = v_{2}) → (v_{3} ∈ v_{0})) ∧ (∃v_{2})(v_{2} ∈ v_{1}))

3. ((∀v_{3})((v_{3} = v_{2}) → (v_{3} ∈ v_{0})) ∧ (∃v_{4})(v_{4} ∈ v_{1}))

4. ((∀v_{3})((v_{3} = v_{2}) → (v_{3} ∈ v_{0})) ∧ (∃v_{4})(v_{4} ∈ v_{2}))

For the reader who is new to this abstract game of formal logic, step (2) in the substitution proceedure may appear to be unnecessary. It is indeed necessary, but the reason is not obvious until we look again at the example to see what would happen if step (2) were omitted. This step essentially changes (∃v_{2})(v_{2} ∈ v_{1}) to (∃v_{4})(v_{4} ∈ v_{1}). We can agree that each of these means the same thing, namely, “v_{1} is non-empty”. However, when v_{2} is directly substituted into each we get something different: (∃v_{2})(v_{2} ∈ v_{2}) and (∃v_{4})(v_{4} ∈ v_{2}). The latter says that “v_{2} is non-empty” and this is, of course what we would hope would be the result of substituting v_{2} for v_{1} in “v_{1} is non-empty”. But the former statement, (∃v_{2})(v_{2} ∈ v_{2}), seems quite different, making the strange assertion that “v_{2} is an element of itself”, and this is not what we have in mind. What caused this problem? An occurrence of the variable v_{2} became bound as a result of being substituted for v_{1}. We will not allow this to happen. When we substitute v_{2} for the free v_{1} we must ensure that this freedom is preserved for v_{2}.

For a formula Φ and variables v_{i} and v_{j}, let Φ(v_{i}|v_{j}) denote the formula which results from substituting v_{j} for each free occurance of v_{i}. In order to make Φ(v_{i}|v_{j}) well defined, we insist that in steps (1) and (2) of the substitution process, the first new variable available is used. Of course, the use of any other new variable gives an equivalent formula. In the example, if Φ is the formula on the first line, then Φ(v_{1}|v_{2}) is the formula on the fourth line.

As a simple application we can show how to express “there exists a unique element”. For any formula Φ of the language of set theory we denote by (∃!v_{j})Φ the formula

((∃v_{j})Φ ∧ (∀v_{j})(∀v_{l})((Φ ∧ Φ(v_{j}|v_{l})) → (v_{j} = v_{l})))

where v_{l} is the first available variable which does not occur in Φ. The expression (∃!v_{j}) can be considered as an abbreviation in the language of set theory, that is, an expression which is not actually part of the language. However, whenever we have a formula containing this expression, we can quickly convert it to a proper formula of the language of set theory.

A \underline{class} is just a string of symbols of the form \{v_{i} : Φ\} where v_{i} is a variable and Φ is a formula. Two important and well-known examples are:

{v_{0} : (¬(v_{0} = v_{0}))}

which is called the empty set and is usually denoted by ∅, and

{v_{0} : (v_{0} = v_{0})}

which is called the universe and is usually denoted by 𝕍.

A \underline{term} is defined to be either a class or a variable. Terms are the names for what the language of set theory talks about. A grammatical analogy is that terms correspond to nouns and pronouns—classes to nouns and variables to pronouns. Continuing the analogy, the predicates, or verbs, are = and ∈. The atomic formulas are the basic relationships among the predicates and the variables.

We can incorporate classes into the language of set theory by showing how the predicates relate to them. Let Ψ and Θ be formulas of the language of set theory and let v_{j}, v_{k} and v_{l} be variables. We write:

v_{k} ∈ {v_{j} : Ψ} instead of Ψ(v_{j}|v_{k})
v_{k} = {v_{j} : Ψ} instead of (∀v_{l})((v_{l} ∈ v_{k}) ↔ Ψ(v_{j}|v_{l}))
{v_{j} : Ψ} = v_{k} instead of (∀v_{l})(Ψ(v_{j}|v_{l}) ↔ (v_{l} ∈ v_{k}))
{v_{j} : Ψ} = {v_{k} : Θ} instead of (∀v_{l})(Ψ(v_{j}|v_{l}) ↔ Θ(v_{k}|v_{l}))
{v_{j} : Ψ} ∈ v_{k} instead of (∃v_{l})((v_{l} ∈ v_{k}) ∧ (∀v_{j})((v_{j} ∈ v_{l}) ↔ Ψ))
{v_{j} : Ψ} ∈ {v_{k} : Θ} instead of (∃v_{l})(Θ(v_{k}|v_{l}) ∧ (∀v_{j})((v_{j} ∈ v_{l}) ↔ Ψ))

whenever v_{l} is neither v_{j} nor v_{k} and occurs in neither Ψ nor Θ.

We can now show how to express, as a proper formula of set theory, the \underline{substitution of a term} t for each free occurrence of the variable v_{i} in the formula Φ. We denote the resulting formula of set theory by Φ(v_{i}|t). The case when t is a variable v_{j} has already been discussed. Now we turn our attention to the case when t is a class {v_{j} : Ψ} and carry out a proceedure similar to the variable case.

1. Substitute the first available new variable for all bound occurrences of v_{i} in Φ.

2. In the result of (1), substitute, in turn, the first available new variable for all bound occurrences of each variable which occurs free in Ψ.

3. In the result of (2), directly substitute {v_{j} : Ψ} for v_{i} into each atomic subformula in turn, using the table above.

For example, the atomic subformula (v_{i} ∈ v_{k}) is replaced by the new subformula

(∃v_{l})((v_{l} ∈ v_{k}) ∧ (∀v_{j})((v_{j} ∈ v_{l}) ↔ Ψ))

where v_{l} is the first available new variable. Likewise, the atomic subformula (v_{i} = v_{i}) is replaced by the new subformula

(∀v_{l})(Ψ(v_{j}|v_{l}) ↔ Ψ(v_{j}|v_{l}))

where v_{l} is the first available new variable (although it is not important to change from v_{j} to v_{l} in this particular instance).

18 CHAPTER 1. LOST

FOUND

The language of set theory is very precise, but it is extremely difficult for us to read mathematical formulas in that language. We need to find a way to make these formulas more intelligible.

In order to avoid the inconsistencies associated with Richard’s paradox, we must ensure that the formula Φ in the class {v_{j} : Φ} is indeed a proper formula of the language of set theory—or, at least, can be converted to a proper formula once the abbreviations are eliminated. It is not so important that we actually write classes using proper formulas, but what is important is that whatever formula we write down can be converted into a proper formula by eliminating abbreviations and slang.

We can now relax our formalism if we keep the previous paragraph in mind. Let’s adopt these conventions.

1. We can use any letters that we like for variables, not just v_{0}, v_{1}, v_{2}, . . ..

2. We can freely omit parentheses and sometimes use brackets ] and [ instead.

3. We can write out “and” for “∧”, “or” for “∨”, “implies” for “→” and use the “if...then...” format as well as other common English expressions for the logical connectives and quantifiers.

4. We will use the notation Φ(x, y, w_{1}, …, w_{k}) to indicate that all free variables of Φ lie among x, y, w_{1}, …, w_{k}. When the context is clear we use the notation Φ(x, t, w_{1}, …, w_{k}) for the result of substituting the term t for each free occurrence of the variable y in Φ, i.e., Φ(y|t).

5. We can write out formulas, including statements of theorems, in any way easily seen to be convertible to a proper formula in the language of set theory.

For any terms r, s, and t, we make the following abbreviations of formulas.

(∀x ∈ t)Φ for (∀x)(x ∈ t → Φ)
(∃x ∈ t)Φ for (∃x)(x ∈ t ∧ Φ)
s ∉ t for ¬(s ∈ t)
s ≠ t for ¬(s = t)
s ⊆ t for (∀x)(x ∈ s → x ∈ t)

Whenever we have a finite number of terms t_{1}, t_{2}, …, t_{n} the notation {t_{1}, t_{2}, …, t_{n}} is used as an abbreviation for the class:

{x : x = t_{1} ∨ x = t_{2} ∨ ⋯ ∨ x = t_{n}}.

Furthermore, {t : Φ} will stand for {x : x = t ∧ Φ}, while {x ∈ t : Φ} will represent {x : x ∈ t ∧ Φ}.

We also abbreviate the following important classes.

Union s ∪ t for {x : x ∈ s ∨ x ∈ t}
Intersection s ∩ t for {x : x ∈ s ∧ x ∈ t}
Difference s \ t for {x : x ∈ s ∧ x ∉ t}
Symmetric Difference s△t for (s \ t) ∪ (t \ s)
Ordered Pair ⟨s, t⟩ for {{s}, {s, t}}
Cartesian Product s × t for {p : ∃x ∃y (x ∈ s ∧ y ∈ t ∧ p = ⟨x, y⟩)}
Domain dom(f) for {x : ∃y ⟨x, y⟩ ∈ f}
Range rng(f) for {y : ∃x ⟨x, y⟩ ∈ f}

Image f^{→}A for {y : ∃x ∈ A ⟨x, y⟩ ∈ f}
Inverse Image f^{←}B for {x : ∃y ∈ B ⟨x, y⟩ ∈ f}
Restriction f|A for {p : p ∈ f ∧ ∃x ∈ A ∃y p = ⟨x, y⟩}
Inverse f^{−1} for {p : ∃x ∃y ⟨x, y⟩ ∈ f ∧ ⟨y, x⟩ = p}

These latter abbreviations are most often used when f is a \underline{function}. We write

f is a function

for

∀p ∈ f ∃x ∃y p = ⟨x, y⟩ ∧ (∀x)(∃y ⟨x, y⟩ ∈ f → ∃!y ⟨x, y⟩ ∈ f)

and we write

f: X → Y for f is a function ∧ dom(f) = X ∧ rng(f) ⊆ Y
f is one − to − one for ∀y ∈ rng(f) ∃!x ⟨x, y⟩ ∈ f
f is onto Y for Y = rng(f)

We also use the terms injection (for a one-to-one function), surjection (for an onto function), and bijection (for both properties together).

Russell’s Paradox

The following is a theorem.

¬∃z z = {x : x ∉ x}.

The proof of this is simple. Just ask whether or not z ∈ z.

The paradox is only for the naive, not for us. {x : x ∉ x} is a class—just a description in the language of set theory. There is no reason why what it describes should exist. In everyday life we describe many things which don’t exist, fictional characters for example. Bertrand Russell did exist and Peter Pan did not, although they each have descriptions in English. Although Peter Pan does not exist, we still find it worthwhile to speak about him. The same is true in mathematics.

Upon reflection, you might say that in fact, nothing is an element of itself so that

{x : x ∉ x} = {x : x = x} = 𝕍

and so Russell’s paradox leads to:

¬∃z z = 𝕍.

It seems we have proved that the universe does not exists. A pity!

The mathematical universe fails to have a mathematical existence in the same way that the physical universe fails to have a physical existence. The things that have a physical existence are exactly the things in the universe, but the universe itself is not an object in the universe. This does bring up an important point—do any of the usual mathematical objects exist? What about the other things we described as classes? What about ∅? Can we prove that ∅ exists?

Actually, we can’t; at least not yet. You can’t prove very much, if you don’t assume something to start. We could prove Russell’s Paradox because, amazingly, it only required the basic rules of logic and required nothing mathematical—that is, nothing about the “real meaning” of ∈. Continuing from Russell’s Paradox to “¬∃z z = 𝕍” required us to assume that “∀x x ∉ x”—not an unreasonable assumption by any means, but a mathematical assumption none the less. The existence of the empty set “∃z z = ∅” may well be another necessary assumption.

Generally set theorists, and indeed all mathematicians, are quite willing to assume anything which is obviously true. It is, after all, only the things which are not obviously true which need some form of proof. The problem, of course, is that we must somehow know what is “obviously true”. Naively, “∃z z = 𝕍” would seem to be true, but it is not and if it or any other false statement is assumed, all our proofs become infected with the virus of inconsistency and all of our theorems become suspect.

Historically, considerable thought has been given to the construction of the basic assumptions for set theory. All of mathematics is based on these assumptions; they are the foundation upon which everything else is built. These assumptions are called axioms and this system is called the 𝒵ℱ𝒞 Axiom System. We will begin to study it in the next chapter.

The Axioms of Set Theory

We will explore the 𝒵ℱ𝒞 Axiom System. Each axiom should be “obviously true” in the context of those things that we desire to call sets. Because we cannot give a mathematical proof of a basic assumption, we must rely on intuition to determine truth, even if this feels uncomfortable. Beyond the issue of truth is the question of consistency. Since we are unable to prove that our assumptions are true, can we at least show that together they will not lead to a contradiction? Unfortunately, we cannot even do this—it is ruled out by the famous incompleteness theorems of K. Gödel. Intuition is our only guide. We begin.

We have the following axioms:

The Axiom of Equality ∀x ∀y [x = y → ∀z (x ∈ z ↔ y ∈ z)]
The Axiom of Extensionality ∀x ∀y [x = y ↔ ∀u (u ∈ x ↔ u ∈ y)]
The Axiom of Existence ∃z z = ∅
The Axiom of Pairing ∀x ∀y ∃z z = {x, y}

Different authors give slightly different formulations of the 𝒵ℱ𝒞 axioms. All formulations are equivalent. Some authors omit the Axiom of Equality and Axiom of Existence because they are consequences of the usual logical background to all mathematics. We include them for emphasis. Redundancy is not a bad thing and there is considerable redundancy in this system.

The following theorem gives some results that we would be quite willing to assume outright, were they not to follow from the axioms. The first three parts are immediate consequences of the Axiom of Extensionality.

Theorem 1.

1. ∀x x = x.

2. ∀x ∀y x = y → y = x.

3. ∀x ∀y ∀z [(x = y ∧ y = z) → x = z].

4. ∀x ∀y ∃z z = ⟨x, y⟩.

5. ∀u ∀v ∀x ∀y [⟨u, v⟩ = ⟨x, y⟩ ↔ (u = x ∧ v = y)].

Exercise 1. Prove parts (4) and (5) of Theorem 1

We now assert the existence of unions and intersections. No doubt the reader has experienced a symmetry between these two concepts. Here however, while the Union Axiom is used extensively, the Intersection Axiom is redundant and is omitted in most developments of the subject. We include it here because it has some educational value (see Exercise 4).

The Union Axiom  ∀x [x ≠ ∅ → ∃z z = {w : (∃y ∈ x)(w ∈ y)}]

The class {w : (∃y ∈ x)(w ∈ y)} is abbreviated as ⋃ x and called the “big union”.

The Intersection Axiom  ∀x [x ≠ ∅ → ∃z z = {w : (∀y ∈ x)(w ∈ y)}]

The class {w : (∀y ∈ x)(w ∈ y)} is abbreviated as ⋂ x and called the “big intersection”.

The Axiom of Foundation  ∀x [x ≠ ∅ → (∃y ∈ x)(x ∩ y = ∅)]

This axiom, while it may be “obviously true”, is not certainly obvious. Let’s investigate what it says: suppose there were a non-empty x such that (∀ y ∈ x) (x ∩ y ≠ ∅). For any z_{1} ∈ x we would be able to get z_{2} ∈ z_{1} ∩ x. Since z_{2} ∈ x we would be able to get z_{3} ∈ z_{2} ∩ x. The process continues forever:

⋯ ∈ z_{4} ∈ z_{3} ∈ z_{2} ∈ z_{1} ∈ x

We wish to rule out such an infinite regress. We want our sets to be founded: each such sequence should eventually end with the empty set. Hence the name of the axiom, which is also known as the Axiom of Regularity. It is nevertheless best understood by its consequences.

Theorem 2.

1. ∀x ∀y ∃z z = x ∪ y.

2. ∀x ∀y ∃z z = x ∩ y.

3. ∀x ∀y x ∈ y → y ∉ x.

4. ∀x x ∉ x.

Exercise 2. Prove Theorem 2.

Let f(x) denote the class ⋃{y : ⟨x, y⟩ ∈ f}.

Exercise 3. Suppose f is a function and x ∈ dom(f). Prove that

⟨x, y⟩ ∈ f iff y = f(x).

Suppose that x is a set and that there is some way of removing each element u ∈ x and replacing u with some element v. Would the result be a set? Well, of course—provided there are no tricks here. That is, there should be a well defined replacement procedure which ensures that each u is replaced by only one v. This well defined procedure should be described by a formula, Φ, in the language of set theory. We can guarantee that each u is replaced by exactly one v by insisting that ∀u ∈ x ∃!v Φ(x, u, v).

We would like to obtain an axiom, written in the language of set theory stating that for each set x and each such formula Φ we get a set z. However, this is impossible. We cannot express “for each formula” in the language of set theory—in fact this formal language was designed for the express purpose of avoiding such expressions which bring us perilously close to Richard’s Paradox.

The answer to this conundrum is to utilise not just one axiom, but infinitely many—one axiom for each formula of the language of set theory. Such a system is called an axiom scheme.

The Replacement Axiom Scheme

For each formula Φ(x, u, v, w_{1}, …, w_{n}) of the language of set theory, we have the axiom:

∀w_{1} … ∀w_{n} ∀x [∀u ∈ x ∃!v Φ → ∃z z = {v : ∃u ∈ x Φ}]

Note that we have allowed Φ to have w_{1}, …, w_{n} as parameters, that is, free variables which may be used to specify various procedures in various contexts within a mathematical proof. This is illustrated by the following theorem.

Theorem 3. ∀x ∀y ∃z z = x × y.

Proof. From Theorem 1 parts (4) and (5), for all t ∈ y we get

∀u ∈ x ∃!v v = ⟨u, t⟩.

We now use Replacement with the formula “Φ(x, u, v, t)” as “v = ⟨u, t⟩”; t is a parameter. We obtain, for each t ∈ y:

∃q q = {v : ∃u ∈ x v = ⟨u, t⟩}.

By Extensionality, in fact ∀t ∈ y ∃!q q = {v : ∃u ∈ x v = ⟨u, t⟩}.

We again use Replacement, this time with the formula Φ(y, t, q, x) as “q = {v : ∃u ∈ x v = ⟨u, t⟩}”; here x is a parameter. We obtain:

∃r r = {q : ∃t ∈ y q = {v : ∃u ∈ x v = ⟨u, t⟩}}

By the Union Axiom ∃z z = ⋃ r and so we have:

z = {p : ∃q [q ∈ r ∧ p ∈ q]}
= {p : ∃q [(∃t ∈ y) q = {v : ∃u ∈ x v = ⟨u, t⟩} ∧ p ∈ q]}
= {p : (∃t ∈ y)(∃q)[q = {v : ∃u ∈ x v = ⟨u, t⟩} ∧ p ∈ q]}
= {p : (∃t ∈ y)p ∈ {v : ∃u ∈ x v = ⟨u, t⟩}}
= {p : (∃t ∈ y)(∃u ∈ x) p = ⟨u, t⟩}
= x × y

Exercise 4. Show that the Intersection Axiom is indeed redundant.

It is natural to believe that for any set x, the collection of those elements y ∈ x which satisfy some particular property should also be a set. Again, no tricks—the property should be specified by a formula of the language of set theory. Since this should hold for any formula, we are again led to a scheme.

The Comprehension Scheme

For each formula Φ(x, y, w_{1}, …, w_{n}) of the language of set theory, we have the statement:

∀w_{1} … ∀w_{n} ∀x ∃z z = {y : y ∈ x ∧ Φ(x, y, w_{1}, …, w_{n})}

This scheme could be another axiom scheme (and often is treated as such). However, this would be unnecessary, since the Comprehension Scheme follows from what we have already assumed. It is, in fact, a theorem scheme—that is, infinitely many theorems, one for each formula of the language of set theory. Of course we cannot write down infinitely many proofs, so how can we prove this theorem scheme?

We give a uniform method for proving each instance of the scheme. So to be certain that any given instance of the theorem scheme is true, we consider the uniform method applied to that particular instance. We give this general method below.

For each formula Φ(x, u, w_{1}, …, w_{n}) of the language of set theory we have:

Theorem 4. Φ

∀w_{1} … ∀w_{n} ∀x ∃z z = {u : u ∈ x ∧ Φ}.

Proof. Apply Replacement with the formula Ψ(x, u, v, w_{1}, …, w_{n}) given by:

(Φ(x, u, w_{1}, …, w_{n}) → v = {u}) ∧ (¬Φ(x, u, w_{1}, …, w_{n}) → v = ∅)

to obtain:

∃y y = {v : (∃u ∈ x)[(Φ → v = {u}) ∧ (¬Φ → v = ∅)]}.

Note that {{u} : Φ(x, u, w_{1}, …, w_{n})} ⊆ y and the only other possible element of y is ∅. Now let z = ⋃ y to finish the proof.

Theorem 4 Φ can be thought of as infinitely many theorems, one for each Φ. The proof of any one of those theorems can be done in a finite number of steps, which invoke only a finite number of theorems or axioms. A proof cannot have infinite length, nor invoke infinitely many axioms or lemmas.

We state the last of the “set behavior” axioms.

The Axiom of Choice

∀X [(∀x ∈ X ∀y ∈ X (x = y ↔ x ∩ y ≠ ∅)) → ∃z (∀x ∈ X ∃!y y ∈ x ∩ z)]

In human language, the Axiom of Choice says that if you have a collection X of pairwise disjoint non-empty sets, then you get a set z which contains one element from each set in the collection. Although the axiom gives the existence of some “choice set” z, there is no mention of uniqueness—there are quite likely many possible sets z which satisfy the axiom and we are given no formula which would single out any one particular z.

The Axiom of Choice can be viewed as a kind of replacement, in which each set in the collection is replaced by one of its elements. This leads to the following useful reformulation which will be used in Theorem 22.

Theorem 5. There is a choice function on any set of non-empty sets; i.e.,

∀X [∅ ∉ X → (∃f)(f: X → ⋃ X ∧ (∀x ∈ X)(f(x) ∈ x))].

Proof. Given such an X, by Replacement there is a set

Y = {{x} × x : x ∈ X}

which satisfies the hypothesis of the Axiom of Choice. So, ∃z ∀y ∈ Y ∃!p p ∈ y ∩ z. Let f = z ∩ (⋃ Y). Then f: X → ⋃ X and each f(x) ∈ x.

We state the last of the “set creation” axioms.

The Power Set Axiom ∀x ∃z z = {y : y ⊆ x}

We denote \{y : y ⊆ x\} by P(x), called the \underline{power set} of x. For reasons to be understood later, it is important to know explicitly when the Power Set Axiom is used. This completes the list of the 𝒵ℱ𝒞 Axiom System with one exception to come later—higher analogues of the Axiom of Existence.

30 CHAPTER 3. THE AXIOMS OF SET THEORY

The Natural Numbers

We now construct the natural numbers. That is, we will represent the natural numbers in our universe of set theory. We will construct a number system which behaves mathematically exactly like the natural numbers, with exactly the same arithmetic and order properties. We will not claim that what we construct are the actual natural numbers—whatever they are made of. But we will take the liberty of calling our constructs “the natural numbers”. We begin by taking 0 as the empty set ∅. We write

1 for {0}
2 for {0, 1}
3 for {0, 1, 2}
succ(x) for x ∪ {x}

We write “n is a natural number” for

[n = ∅ ∨ (∃l ∈ n)(n = succ(l))] ∧ (∀m ∈ n)[m = ∅ ∨ (∃l ∈ n)(m = succ(l))]

and write:

ℕ for {n : n is a natural number}

The reader can gain some familiarity with these definitions by checking that succ(n) ∈ ℕ for all n ∈ ℕ.

We now begin to develop the basic properties of the natural numbers by introducing an important concept. We say that a term t is \underline{transitive} whenever we have (∀x ∈ t)(x ⊆ t).

Theorem 6.

1. Each natural number is transitive.

2. ℕ is transitive; i.e., every element of a natural number is a natural number.

Proof. Suppose that (1) were false; i.e., some n ∈ ℕ is not transitive, so that:

{k : k ∈ n and ¬(k ⊆ n)} ≠ ∅.

By Comprehension ∃x x = {k ∈ n : ¬(k ⊆ n)} and so by Foundation there is y ∈ x such that y ∩ x = ∅. Note that since ∅ ∉ x and y ∈ n we have that y = succ(l) for some l ∈ n. But since l ∈ y, l ∉ x and so l ⊆ n. Hence y = l ∪ {l} ⊆ n, contradicting that y ∈ x.

We also prove (2) indirectly; suppose n ∈ ℕ with

{m : m ∈ n and m ∉ ℕ} ≠ ∅.

By Comprehension ∃x x = {m ∈ n : m ∉ ℕ} and so Foundation gives y ∈ x such that y ∩ x = ∅. Since y ∈ n, we have y = succ(l) for some l ∈ n. Since l ∈ y and y ∩ x = ∅ we must have l ∈ ℕ. But then y = succ(l) ∈ ℕ, contradicting that y ∈ x.

Theorem 7. (Trichotomy of Natural Numbers)

Let m, n ∈ ℕ. Exactly one of three situations occurs:

m ∈ n, n ∈ m, m = n.

Proof. That at most one occurs follows from Theorem 2. That at least one occurs follows from this lemma.

Lemma. Let m, n ∈ ℕ.

1. If m ⊆ n, then either m = n or m ∈ n.

2. If m ∉ n, then n ⊆ m.

Proof. We begin the proof of (1) by letting S denote

{x ∈ ℕ : (∃y ∈ ℕ)(y ⊆ x and y ≠ x and y ∉ x)}.

It will suffice to prove that S = ∅. We use an indirect proof—pick some n_{1} ∈ S. If n_{1} ∩S ≠ ∅, Foundation gives us n_{2} ∈ n_{1} ∩S with n_{2} ∩(n_{1} ∩S) = ∅. By transitivity, n_{2} ⊆ n_{1} so that n_{2} ∩ S = ∅. Thus, we always have some n ∈ S such that n ∩ S = ∅.

For just such an n, choose m ∈ ℕ with m ⊆ n, m ≠ n, and m ∉ n. Using Foundation, choose l ∈ n \ m such that l ∩ (n \ m) = ∅. Transitivity gives l ⊆ n, so we must have l ⊆ m. We have l ≠ m since l ∈ n and m ∉ n. Therefore we conclude that m \ l ≠ ∅.

Using Foundation, pick k ∈ m \ l such that k ∩ (m \ l) = ∅. Transitivity of m gives k ⊆ m and so we have k ⊆ l. Now, because l ∈ n we have l ∈ ℕ and l ∉ S so that either k = l or k ∈ l. However, k = l contradicts l ∉ m and k ∈ l contradicts k ∈ m \ l.

We prove the contrapositive of (2). Suppose that n is not a subset of m; using Foundation pick l ∈ n \ m such that l ∩ (n \ m) = ∅. By transitivity, l ⊆ n and hence l ⊆ m. Now by (1) applied to l and m, we conclude that l = m. Hence m ∈ n.

These theorems show that “∈” behaves on ℕ just like the usual ordering “<” on the natural numbers. In fact, we often use “<” for “∈” when writing about the natural numbers. We also use the relation symbols ≤, >, and ≥ in their usual sense.

The next theorem scheme justifies ordinary mathematical \underline{induction}. For brevity let us write w⃗ for w_{1}, …, w_{n}.

For each formula Φ(v, w⃗) of the language of set theory we have:

Theorem 8. Φ

For all w⃗, if

∀n ∈ ℕ [(∀m ∈ n Φ(m, w⃗)) → Φ(n, w⃗)]

then

∀n ∈ ℕ Φ(n, w⃗).

Proof. We will assume that the theorem is false and derive a contradiction. We have w⃗ and a fixed l ∈ ℕ such that ¬Φ(l, w⃗).

Let t be any transitive subset of ℕ containing l (e.g., t = l ∪ {l}). By Comprehension, ∃s s = {n ∈ t : ¬Φ(n, w⃗)}. By Foundation, we get y ∈ s such that y ∩s = ∅. Transitivity of t guarantees that (∀n ∈ y) Φ(n, w⃗). This, in turn, contradicts that y ∈ s.

The statement ∀m ∈ n Φ(m, w⃗) in Theorem 8 Φ is usually called the \underline{inductive hypothesis}.

Exercise 5. Prove or disprove that for each formula Φ(v, w⃗) we have

∀w⃗ [(∀n ∈ ℕ)((∀m > n Φ(m, w⃗)) → Φ(n, w⃗)) → ∀n ∈ ℕ Φ(n, w⃗)].

\underline{Recursion} on ℕ is a way of defining new terms (in particular, functions with domain ℕ). Roughly speaking, values of a function F at larger numbers are defined in terms of the values of F at smaller numbers.

We begin with the example of a function F, where we set F (0) = 3 and F (succ(n)) = succ(F (n)) for each natural number n. We have set out a short recursive procedure which gives a way to calculate F (n) for any n ∈ ℕ. The reader may carry out this procedure a few steps and recognise this function F as F (n) = 3 + n. However, all this is a little vague. What exactly is F?

In particular, is there a formula for calculating F? How do we verify that F behaves like we think it should?

In order to give some answers to these questions, let us analyse the example. There is an implicit formula for the calculation of y = F (x) which is

[x = 0 → y = 3] ∧ (∀n ∈ ℕ)[x = succ(n) → y = succ(F (n))]

However the formula involves F, the very thing that we are trying to describe. Is this a vicious circle? No — the formula only involves the value of F at a number n less than x, not F (x) itself. In fact, you might say that the formula doesn’t really involve F at all; it just involves F |x. Let’s rewrite the formula as

[x = 0 → y = 3] ∧ (∀n)[x = succ(n) → y = succ(f(n))]

and denote it by Φ(x, f, y). Our recursive procedure is then described by

Φ(x, F |x, F (x)).

In order to describe F we use functions f which approximate F on initial parts of its domain, for example f = {⟨0, 3⟩}, f = {⟨0, 3⟩, ⟨1, 4⟩} or

f = {⟨0, 3⟩, ⟨1, 4⟩, ⟨2, 5⟩},

where each such f satisfies Φ(x, f|x, f(x)) for the appropriate x’s. We will obtain F as the amalgamation of all these little f’s. F is

{⟨x, y⟩ : (∃n ∈ ℕ)(∃f)[f: n → 𝕍 ∧ f(x) = y ∧ ∀m ∈ n Φ(m, f|m, f(m))]}.

But in order to justify this we will need to notice that

(∀x ∈ ℕ)(∀f)[(f: x → 𝕍) → ∃!y Φ(x, f, y)],

which simply states that we have a well defined procedure given by Φ.

Let us now go to the general context in which the above example will be a special case. For any formula Φ(x, f, y, w⃗) of the language of set theory, we denote by REC(Φ, ℕ, w⃗) the class

{⟨x, y⟩ : (∃n ∈ ℕ)(∃f)[f: n → 𝕍 ∧ f(x) = y ∧ ∀m ∈ n Φ(m, f|m, f(m), w⃗)]}.

We will show, under the appropriate hypothesis, that REC(Φ, ℕ, w⃗) is the unique function on ℕ which satisfies the procedure given by Φ. This requires a theorem scheme.

For each formula Φ(x, f, y, w⃗) of the language of set theory we have:

Theorem 9. Φ

For all w⃗, suppose that we have

(∀x ∈ ℕ)(∀f)[(f: x → 𝕍) → ∃!y Φ(x, f, y, w⃗)].

Then, letting F denote REC(Φ, ℕ, w⃗), we have:

1. F: ℕ → 𝕍;

2. ∀m ∈ ℕ Φ(m, F |m, F (m), w⃗);

and, furthermore, for any n ∈ ℕ and any function H with n ∈ dom(H), we have:

3. If Φ(m, H|m, H(m), w⃗) for all m ∈ n ∪ {n}, then H(n) = F (n).

Proof. We first prove the following claim. Claim.

(∀x ∈ ℕ)(∀y_{1})(∀y_{2})[(⟨x, y_{1}⟩ ∈ F ∧ ⟨x, y_{2}⟩ ∈ F → y_{1} = y_{2}]

Proof of Claim. By definition of F we have, for i = 1, 2, functions f_{i} with domains n_{i} ∈ ℕ such that f_{i}(x) = y_{i} and

(∀m ∈ n_{i}) Φ(m, f_{i}|m, f_{i}(m), w⃗).

It suffices to prove that

(∀m ∈ ℕ)(m ∈ x ∪ {x} → f_{1}(m) = f_{2}(m)),

which we do by induction on m ∈ ℕ. To this end, we assume that m ∈ ℕ and

(∀j ∈ m)(j ∈ x ∪ {x} → f_{1}(j) = f_{2}(j))

with intent to show that

m ∈ x ∪ {x} → f_{1}(m) = f_{2}(m).

To do this suppose m ∈ x ∪ {x}. Since x ∈ n_{1} ∩ n_{2} we have m ∈ n_{1} ∩ n_{2} so that we have both

Φ(m, f_{1}|m, f_{1}(m), w⃗) and Φ(m, f_{2}|m, f_{2}(m), w⃗).

By transitivity j ∈ x ∪ {x} for all j ∈ m and so by the inductive hypothesis f_{1}|m = f_{2}|m. Now by the hypothesis of this theorem with f = f_{1}|m = f_{2}|m we deduce that f_{1}(m) = f_{2}(m). This concludes the proof of the claim.

In order to verify (1), it suffices to show that

(∀x ∈ ℕ)(∃y) [⟨x, y⟩ ∈ F]

by induction. To this end, we assume that

(∀j ∈ x)(∃y) [⟨j, y⟩ ∈ F]

with intent to show that ∃y ⟨x, y⟩ ∈ F. For each j ∈ x there is n_{j} ∈ ℕ and f_{j}: n_{j} → 𝕍 such that

(∀m ∈ n_{j}) Φ(m, f_{j}|m, f_{j}(m), w⃗).

If x ∈ n_{j} for some j, then ⟨x, f_{j}(x)⟩ ∈ F and we are done; so assume that n_{j} ≤ x for all j. Let g = ⋃{f_{j} : j ∈ x}. By the claim, the f_{j}’s agree on their common domains, so that g is a function with domain x and

(∀m ∈ x) Φ(m, g|m, g(m), w⃗).

By the hypothesis of the theorem applied to g there is a unique y such that Φ(x, g, y, w⃗). Define f to be the function f = g ∪ {⟨x, y⟩}. It is straightforward to verify that f witnesses that ⟨x, y⟩ ∈ F.

To prove (2), note that, by (1), for each x ∈ ℕ there is n ∈ ℕ and f: n → 𝕍 such that F (x) = f(x) and, in fact, F |n = f. Hence,

(∀m ∈ n) Φ(m, f|m, f(m), w⃗).

We prove (3) by induction. Assume that

(∀m ∈ n) H(m) = F (m)

with intent to show that H(n) = F (n). We assume Φ(n, H|n, H(n), w⃗) and by (2) we have Φ(n, F |n, F (n), w⃗). By the hypothesis of the theorem applied to H|n = F |n we get H(n) = F (n).

By applying this theorem to our specific example we see that REC(Φ, ℕ, w⃗) does indeed give us a function F. Since F is defined by recursion on ℕ, we use induction on ℕ to verify the properties of F. For example, it is easy to use induction to check that F (n) ∈ ℕ for all n ∈ ℕ.

We do not often explicitly state the formula Φ in a definition by recursion. The definition of F would be more often given by:

F (0) = 3
F (succ(n)) = succ(F (n))

This is just how the example started; nevertheless, this allows us to construct the formula Φ immediately, should we wish. Of course, in this particular example we can use the plus symbol and give the definition by recursion by the following formulas.

3 + 0 = 3
3 + succ(n) = succ(3 + n)

Now, let’s use definition by recursion in other examples. We can define general addition on ℕ by the formulas

a + 0 = a
a + succ(b) = succ(a + b)

for each a ∈ ℕ. Here a is a parameter which is allowed by the inclusion of w⃗ in our analysis. The same trick can be used for multiplicaton:

a · 0 = 0
a · (succ(b)) = a · b + a

for each a ∈ ℕ, using the previously defined notion of addition. In each example there are two cases to specify—the zero case and the successor case. Exponentiation is defined similarly:

a^{0} = 1
a^{succ(b)} = a^{b} · a

The reader is invited to construct, in each case, the appropriate formula Φ, with a as a parameter, and to check that the hypothesis of the previous theorem is satisfied.

G. Peano developed the properties of the natural numbers from zero, the successor operation and induction on ℕ. You may like to see for yourself some of what this entails by proving that multiplication is commutative.

A set X is said to be \underline{finite} provided that there is a natural number n and a bijection f: n → X. In this case n is said to be the \underline{size} of X. Otherwise, X is said to be \underline{infinite}.

Exercise 6. Use induction to prove the ”pigeon-hole principle”: for n ∈ ℕ there is no injection f: (n + 1) → n. Conclude that a set X cannot have two different sizes.

Do not believe this next result:

Proposition. All natural numbers are equal.

Proof. It is sufficient to show by induction on n ∈ ℕ that if a ∈ ℕ and b ∈ ℕ and max (a, b) = n, then a = b. If n = 0 then a = 0 = b. Assume the inductive hypothesis for n and let a ∈ ℕ and b ∈ ℕ be such that

max (a, b) = n + 1.

Then max (a − 1, b − 1) = n and so a − 1 = b − 1 and consequently a = b.

40 CHAPTER 4. THE NATURAL NUMBERS

The Ordinal Numbers

The natural number system can be extended to the system of ordinal numbers.

An \underline{ordinal} is a transitive set of transitive sets. More formally: for any term t, “t is an ordinal” is an abbreviation for

(t is transitive) ∧ (∀x ∈ t)(x is transitive).

We often use lower case Greek letters to denote ordinals. We denote {α : α is an ordinal} by 𝕆ℕ.

From Theorem 6 we see immediately that ℕ ⊆ 𝕆ℕ.

Theorem 10.

1. 𝕆ℕ is transitive.

2. ¬(∃z)(z = 𝕆ℕ).

Proof.

1. Let α ∈ 𝕆ℕ; we must prove that α ⊆ 𝕆ℕ. Let x ∈ α; we must prove that (a) x is transitive; and,

(b) (∀y ∈ x)(y is transitive).

Clearly (a) follows from the definition of ordinal. To prove (b), let y ∈ x; by transitivity of α we have y ∈ α; hence y is transitive.

2. Assume (∃z)(z = 𝕆ℕ). From (1) we have that 𝕆ℕ is a transitive set of transitive sets, i.e., an ordinal. This leads to the contradiction 𝕆ℕ ∈ 𝕆ℕ.

Theorem 11. (Trichotomy of Ordinals)

(∀α ∈ 𝕆ℕ)(∀β ∈ 𝕆ℕ)(α ∈ β ∨ β ∈ α ∨ α = β).

Proof. The reader may check that a proof of this theorem can be obtained by replacing “ℕ” with “𝕆ℕ” in the proof of Theorem 7.

Because of this theorem, when α and β are ordinals, we often write α < β for α ∈ β.

Since ℕ ⊆ 𝕆ℕ, it is natural to wonder whether ℕ = 𝕆ℕ. In fact, we know that “ℕ = 𝕆ℕ” can be neither proved nor disproved from the axioms that we have stated (provided, of course, that those axioms are actually consistent). We find ourselves at a crossroads in Set Theory. We can either add “ℕ = 𝕆ℕ” to our axiom system, or we can add “ℕ ≠ 𝕆ℕ”.

As we shall see, the axiom “ℕ = 𝕆ℕ” essentially says that there are no infinite sets and the axiom “ℕ ≠ 𝕆ℕ” essentially says that there are indeed infinite sets. Of course, we go for the infinite!

The Axiom of Infinity ℕ ≠ 𝕆ℕ

As a consequence, there is a set of all natural numbers; in fact, ℕ ∈ 𝕆ℕ.

Theorem 12. (∃z)(z ∈ 𝕆ℕ ∧ z = ℕ).

Proof. Since ℕ ⊆ 𝕆ℕ and ℕ ≠ 𝕆ℕ, pick α ∈ 𝕆ℕ\ℕ. We claim that for each n ∈ ℕ we have n ∈ α; in fact, this follows immediately from the trichotomy of ordinals and the transitivity of ℕ. Thus ℕ = {x ∈ α : x ∈ ℕ} and by Comprehension ∃z z = {x ∈ α : x ∈ ℕ}. The fact that ℕ ∈ 𝕆ℕ now follows immediately from Theorem 6.

The lower case Greek letter ω is reserved for the set ℕ considered as an ordinal; i.e., ω = ℕ. Theorems 6 and 12 now show that the natural numbers are the smallest ordinals, which are immediately succeeded by ω, after which the rest follow. The other ordinals are generated by two processes illustrated by the next lemma.

Lemma.

1. ∀α ∈ 𝕆ℕ ∃β ∈ 𝕆ℕ β = succ(α).

2. ∀S [S ⊆ 𝕆ℕ → ∃β ∈ 𝕆ℕ β = ⋃ S].

Exercise 7. Prove this lemma.

For S ⊆ 𝕆ℕ we write sup S for the least element of

{β ∈ 𝕆ℕ : (∀α ∈ S)(α ≤ β)}

if such an element exists.

Lemma. ∀S [S ⊆ 𝕆ℕ → ⋃ S = sup S]

Exercise 8. Prove this lemma.

An ordinal α is called a \underline{successor ordinal} whenever ∃β ∈ 𝕆ℕ α = succ(β). If α = sup α, then α is called a \underline{limit ordinal}.

Lemma. Each ordinal is either a successor ordinal or a limit ordinal, but not both.

Exercise 9. Prove this lemma.

We can perform induction on the ordinals via a process called \underline{transfinite induction}. In order to justify transfinite induction we need a theorem scheme.

For each formula Φ(v, w⃗) of the language of set theory we have:

Theorem 13. Φ

For all w⃗, if

∀n ∈ 𝕆ℕ [(∀m ∈ n Φ(m, w⃗)) → Φ(n, w⃗)]

then

∀n ∈ 𝕆ℕ Φ(n, w⃗).

Proof. The reader may check that a proof of this theorem scheme can be obtained by replacing “ℕ” with “𝕆ℕ” in the proof of Theorem Scheme 8.

We can also carry out recursive definitions on 𝕆ℕ. This process is called \underline{transfinite recursion}. For any formula Φ(x, f, y, w⃗) of the language of set theory, we denote by REC(Φ, 𝕆ℕ, w⃗) the class

{⟨x, y⟩ : (∃n ∈ 𝕆ℕ)(∃f)[f : n → 𝕍∧f(x) = y∧∀m ∈ n Φ(m, f|m, f(m), w⃗)]}.

Transfinite recursion is justified by the following theorem scheme.

For each formula Φ(x, f, y, w⃗) of the language of set theory we have:

Theorem 14. Φ

For all w⃗, suppose that we have

(∀x ∈ 𝕆ℕ)(∀f)[(f : x → 𝕍) → ∃!y Φ(x, f, y, w⃗)].

Then, letting F denote REC(Φ, 𝕆ℕ, w⃗), we have:

1. F : 𝕆ℕ → 𝕍;

2. ∀x ∈ 𝕆ℕ Φ(x, F |x, F (x), w⃗);

and, furthermore, for any n ∈ 𝕆ℕ and any function H with n ∈ dom(H) we have:

3. If Φ(x, H|x, H(x), w⃗) for all x ∈ n ∪ {n} then H(n) = F (n).

Proof. The reader may check that a proof of this theorem scheme can be obtained by replacing “ℕ” with “𝕆ℕ” in the proof of Theorem Scheme 9.

When applying transfinite recursion on 𝕆ℕ we often have three separate cases to specify, rather than just two as with recursion on ℕ. This is illustrated by the recursive definitions of the arithmetic operations on 𝕆ℕ.

Addition:

α + 0 = α;
α + succ(β) = succ(α + β);
α + δ = sup {α + η : η ∈ δ}, for a limit ordinal δ.

Multiplication:

α · 0 = 0;
α · succ(β) = (α · β) + α;
α · δ = sup {α · η : η ∈ δ}, for a limit ordinal δ.

Exponentiation:

α^{0} = 1;
α^{succ(β)} = (α^{β}) · α;
α^{δ} = sup {α^{η} : η ∈ δ}, for a limit ordinal δ.

Note that, in each case, we are extending the operation from ℕ to all of 𝕆ℕ. The following theorem shows that these operations behave somewhat similarly on ℕ and 𝕆ℕ.

46 CHAPTER 5. THE ORDINAL NUMBERS Theorem 15. Let α, β, and δ be ordinals and S be a non-empty set of ordinals. We have,

1. 0 + α = α;

2. If β < δ then α + β < α + δ;

3. α + sup S = sup {α + η : η ∈ S};

4. α + (β + δ) = (α + β) + δ;

5. If α < β then α + δ ≤ β + δ;

6. 0 · α = 0;

7. 1 · α = α;

8. If 0 < α and β < δ then α · β < α · δ;

9. α · sup S = sup {α · η : η ∈ S};

10. α · (β + δ) = (α · β) + (α · δ);

11. α · (β · δ) = (α · β) · δ;

12. If α < β then α · δ ≤ β · δ;

13. 1^{α} = 1;

14. If 1 < α and β < δ then α^{β} < α^{δ};

15. α^{sup S} = sup {α^{η} : η ∈ S};

16. α^{(β+δ)} = α^{β} · α^{δ};

17. (α^{β})^{δ} = α^{β·δ}; and,

18. If α < β then α^{δ} ≤ β^{δ}. Exercise 10. Build your transfinite induction skills by proving two parts of this theorem.

However, ordinal addition and multiplication are not commutative. This is illustrated by the following examples, which are easy to verify from the basic definitions.

Examples.

1. 1 + ω = 2 + ω

2. 1 + ω ≠ ω + 1

3. 1 · ω = 2 · ω

4. 2 · ω ≠ ω · 2

5. 2^{ω} = 4^{ω}

6. (2 · 2)^{ω} ≠ 2^{ω} · 2^{ω}

Lemma. If β is a non-zero ordinal then ω^{β} is a limit ordinal.

Exercise 11. Prove this lemma.

Lemma. If α is a non-zero ordinal, then there is a largest ordinal β such that ω^{β} ≤ α.

Exercise 12. Prove this lemma. Show that the β ≤ α and that there are cases in which β = α. Such ordinals β are called \underline{epsilon numbers} (The smallest such ordinal α = ω^{α} is called ϵ_{0}.)

Lemma. ∀α ∈ 𝕆ℕ ∀β ∈ α ∃!γ ∈ 𝕆ℕ α = β + γ.

Exercise 13. Prove this lemma.

Commonly, any function f with dom(f) ⊆ ω is called a \underline{sequence}. If dom(f) ⊆ n + 1 for some n ∈ ω, we say that f is a \underline{finite sequence}; otherwise f is an \underline{infinite sequence}. As usual, we denote the sequence f by \{f_{n}\}, where each f_{n} = f(n).

Theorem 16. There is no infinite descending sequence of ordinals.

Proof. Let’s use an indirect proof. Suppose x ⊆ ω is infinite and f: x → 𝕆ℕ such that if n < m then f(n) > f(m). Let X = {f(n) : n ∈ x}. By Foundation there is y ∈ X such that y ∩ X = ∅; i.e., there is n ∈ x such that f(n) ∩ X = ∅. However, if m ∈ x and m > n then f(m) ∈ f(n), which is a contradiction.

If n ∈ ω and s: (n + 1) → 𝕆ℕ is a finite sequence of ordinals, then the

sum ∑_{i=0}^{n} s(i) is defined by recursion as follows.

∑_{i=0}^{0} s(i) = s(0); and,

∑_{i=0}^{m+1} s(i) = ∑_{i=0}^{m} s(i) + s(m + 1), for m < n.

This shows that statements like the following theorem can be written precisely in the language of set theory.

Theorem 17. (Cantor Normal Form)

For each non-zero ordinal α there is a unique n ∈ ω and finite sequences m_{0}, …, m_{n} of positive natural numbers and β_{0}, …, β_{n} of ordinals which satisfy β_{0} > β_{1} > ⋯ > β_{n} such that

α = ω^{β_{0}}m_{0} + ω^{β_{1}}m_{1} + ⋯ + ω^{β_{n}}m_{n}.

Proof. Using the penultimate lemma, let

β_{0} = max {β : ω^{β} ≤ α}

and then let

m_{0} = max {m ∈ ω : ω^{β_{0}}m ≤ α}

which must exist since ω^{β_{0}}m ≤ α for all m ∈ ω would imply that ω^{β_{0}+1} ≤ α.

By the previous lemma, there is some α_{0} ∈ 𝕆ℕ such that

α = ω^{β_{0}}m_{0} + α_{0}

where the maximality of m_{0} ensures that α_{0} < ω^{β_{0}}. Now let

β_{1} = max {β : ω^{β} ≤ α_{0}}

so that β_{1} < β_{0}. Proceed to get

m_{1} = max {m ∈ ω : ω^{β_{1}}m ≤ α_{0}}

and α_{1} < ω^{β_{1}} such that α_{0} = ω^{β_{1}}m_{1} + α_{1}. We continue in this manner as long as possible. We must have to stop after a finite number of steps or else β_{0} > β_{1} > β_{2} > … would be an infinite decreasing sequence of ordinals. The only way we could stop would be if some α_{n} = 0. This proves the existence of the sum. Uniqueness follows by induction on α ∈ 𝕆ℕ.

Exercise 14. Verify the last statement of this proof.

Lemma.

1. If 0 < m < ω and α is a non-zero ordinal, then m · ω^{α} = ω^{α}.

2. If k ∈ ω, and m_{0}, …, m_{k} < ω, and α_{0}, …, α_{k} < β, then

m_{0} · ω^{α_{0}} + ⋯ + m_{k} · ω^{α_{k}} < ω^{β}.

Exercise 15. Prove this lemma and note that it implies that m · δ = δ for each positive integer m and each limit ordinal δ.

There is an interesting application of ordinal arithmetic to Number Theory. Pick a number—say x = 54. We have 54 = 2^{5} + 2^{4} + 2^{2} + 2 when it is written as the simplest sum of powers of 2. In fact, we can write out 54 using only the the arithmetic operations and the numbers 1 and 2. This will be the first step in a recursively defined sequence of natural numbers, {x_{n}}. It begins with n = 2 and is constructed as follows.

x_{2} = 54 = 2^{(2^{2}+1)} + 2^{2^{2}} + 2^{2} + 2.

Subtract 1.

x_{2} − 1 = 2^{(2^{2}+1)} + 2^{2^{2}} + 2^{2} + 1.

Change all 2’s to 3’s, leaving the 1’s alone.

x_{3} = 3^{(3^{3}+1)} + 3^{3^{3}} + 3^{3} + 1.

Subtract 1.

x_{3} − 1 = 3^{(3^{3}+1)} + 3^{3^{3}} + 3^{3}.

Change all 3’s to 4’s, leaving any 1’s or 2’s alone.

x_{4} = 4^{(4^{4}+1)} + 4^{4^{4}} + 4^{4}.

Subtract 1.

x_{4} − 1 = 4^{(4^{4}+1)} + 4^{4^{4}} + 3 · 4^{3} + 3 · 4^{2} + 3 · 4 + 3.

Change all 4’s to 5’s, leaving any 1’s, 2’s or 3’s alone.

x_{5} = 5^{(5^{5}+1)} + 5^{5^{5}} + 3 · 5^{3} + 3 · 5^{2} + 3 · 5 + 3.

Subtract 1 and continue, changing 5’s to 6’s, subtracting 1, changing 6’s to 7’s and so on. One may ask the value of the limit

lim_{n→∞} x_{n}.

What is your guess? The answer is surprising.

Theorem 18. (Goodstein)

For any initial choice of x there is some n such that x_{n} = 0.

Proof. We use an indirect proof; suppose x ∈ ℕ and for all n ≥ 2 we have x_{n} ≠ 0. From this sequence, we construct another sequence. For each n ≥ 2 we let g_{n} be the result of replacing each occurrence of n in x_{n} by ω. So, in the example above we would get:

g_{2} = ω^{(ω^{ω}+1)} + ω^{(ω^{ω})} + ω^{ω} + ω,
g_{3} = ω^{(ω^{ω}+1)} + ω^{(ω^{ω})} + ω^{ω} + 1,
g_{4} = ω^{(ω^{ω}+1)} + ω^{(ω^{ω})} + ω^{ω},
g_{5} = ω^{(ω^{ω}+1)} + ω^{(ω^{ω})} + 3 · ω^{3} + 3 · ω^{2} + 3 · ω + 3,
g_{6} = ω^{(ω^{ω}+1)} + ω^{(ω^{ω})} + 3 · ω^{3} + 3 · ω^{2} + 3 · ω + 2,

etc. The previous lemma can now be used to show that {g_{n}} would be an infinite decreasing sequence of ordinals.

It is interesting that, although the statement of the theorem does not mention infinity in any way, we used the Axiom of Infinity in its proof. We do not need the Axiom of Infinity in order to verify the theorem for any one particular value of x—we just need to carry out the arithmetic. The reader can do this for x = 4; however, finishing our example x = 54 would be tedious. Moreover, the calculations are somewhat different for different values of x. Mathematical logicians have proved that, in fact, there is no uniform method of finitary calculations which will give a proof of the theorem for all x. The Axiom of Infinity is necessary for the proof.

52 CHAPTER 5. THE ORDINAL NUMBERS

Relations and Orderings

In the following definitions, R and C are terms.

1. We say R is a \underline{relation} on C whenever R ⊆ C × C.

2. We say a relation R is \underline{irreflexive} on C whenever ∀x ∈ C ⟨x, x⟩ ∉ R.

3. We say a relation R is \underline{transitive} on C whenever ∀x ∀y ∀z [(⟨x, y⟩ ∈ R ∧ ⟨y, z⟩ ∈ R) → ⟨x, z⟩ ∈ R.]

4. We say a relation R is \underline{well founded} on C whenever

∀X [(X ⊆ C ∧ X ≠ ∅) → (∃x ∈ X ∀y ∈ X ⟨y, x⟩ ∉ R)]. Such an x is called \underline{minimal} for X.

5. We say a relation R is \underline{total} on C whenever ∀x ∈ C ∀y ∈ C [⟨x, y⟩ ∈ R ∨ ⟨y, x⟩ ∈ R ∨ x = y].

6. We say R is \underline{extensional} on C whenever ∀x ∈ C ∀y ∈ C [x = y ↔ ∀z ∈ C (⟨z, x⟩ ∈ R ↔ ⟨z, y⟩ ∈ R)].

An example of a relation R on an ordinal is given by the membership relation:

⟨x, y⟩ ∈ R iff x ∈ y.

R satisfies all the above properties. On the other hand, if α ∉ ω, the reverse relation R′ given by

⟨x, y⟩ ∈ R′ iff y ∈ x

is not well founded but nevertheless has all the other properties.

Any well founded relation is irreflexive. Any total relation is extensional. Any relation which is both well founded and total is also transitive.

Exercise 16. Prove that a transitive set α is an ordinal iff the membership relation is total on α.

Suppose δ is an ordinal and f : X → δ. A relation R on X with the property that f(x) < f(y) whenever ⟨x, y⟩ ∈ R must be a well founded relation. In fact, this turns out to be a characterisation.

Theorem 19. Let R be a relation on a set X. R is well founded iff there is an ordinal δ and a surjection f : X → δ such that f(x) < f(y) whenever ⟨x, y⟩ ∈ R.

Proof. We treat only the forward implication. Using recursion on 𝕆ℕ we define g : 𝕆ℕ → P(X) by

g(β) = {x : x is a minimal element of X \ ⋃{g(α) : α < β}} .

From g we obtain f : X → 𝕆ℕ by

f(x) = \begin{cases}the unique α ∈ 𝕆ℕ with x ∈ g(α), & if possible; \\ 0, & otherwise. \end{cases}

By Theorem 10 and the Axiom of Replacement there must be some least δ ∈ 𝕆ℕ such that δ ∉ rng(f). This means that g(δ) = ∅, and since R is well founded we must have

X = ⋃{g(α) : α < δ}.

To finish the proof suppose ⟨x, y⟩ ∈ R and f(y) = β. We have y ∈ g(β) so that y is a minimal element of

X \ ⋃{g(α) : α < β},

and hence we have that

x ∉ X \ ⋃{g(α : α < β}.

In other words x ∈ g(α) for some α < β and so f(x) = α < β = f(y).

A relation R on a set A is said to be \underline{isomorphic} to a relation S on a set B provided that there is a bijection f : A → B, called an \underline{isomorphism}, such that for all x and y in A we have

⟨x, y⟩ ∈ R iff ⟨f(x), f(y)⟩ ∈ S.

Exercise 17. Prove that any isomorphism between transitive sets is the identity. Of course, the relation on the transitive set is the membership relation, which is extensional and well founded.

This unexpected result leads to the important Mostowski Collapsing Theorem.

Theorem 20. Let R be a well founded extensional relation on a set X. There is a unique transitive set M and a unique isomorphism h : X → M.

Proof. Obtain f : X → δ directly from the previous theorem. By recursion on the ordinals we define for each β < δ a function h_{β} : f^{←}{β} → 𝕍 such that

h_{β}(y) = {h_{α}(x) : α < β and ⟨x, y⟩ ∈ R}.

Let h = ⋃{h_{β} : β < δ}. Clearly h is a function with domain X.

Note that if y ∈ f^{←}{β} and ⟨x, y⟩ ∈ R then x ∈ f^{←}{α} for some α < β, so that in fact

h_{β}(y) = {h_{α}(x) : α < δ and ⟨x, y⟩ ∈ R},

and hence we have

h(y) = {h(x) : ⟨x, y⟩ ∈ R}.

Since R is extensional, h is an injection. Letting M = rng(h), it is now straightforward to use the previous exercise to complete the proof.

Exercise 18. Verify the last two sentences in this proof.

We say that a relation R is a \underline{partial ordering} or \underline{partial order} whenever it is both irrefexive and transitive; if in addition it is total, then it is called a \underline{linear ordering} or \underline{linear order}; furthermore, if in addition it is well founded, then it is called a \underline{well ordering} or \underline{well order}. For those orderings we usually write < instead of R and we write x < y for ⟨x, y⟩ ∈ R.

Whenever

∃z z = ⟨X, <⟩ and < is a partial ordering on X,

we say that ⟨X, <⟩ is a \underline{parially ordered set}. We similarly have the concepts of \underline{linearly ordered set} and \underline{well ordered set}.

The study of partially ordered sets continues to be a major theme in contemporary Set Theory and the construction of elaborate partial orders is of great technical importance. In contrast, well orders have been thoroughly analysed and we shall now classify all well ordered sets.

Theorem 21. Each well ordered set is isomorphic to a unique ordinal.

Proof. Since well orders are extensional and well founded we can use the Mostowski Collapsing Theorem. By Exercise 16 the resulting transitive set is an ordinal.

The unique ordinal given by this theorem is called the \underline{order type} of the well ordered set. We denote the order type of ⟨X, <⟩ by type⟨X, <⟩.

We now come to the \underline{Well Ordering Principle}, which is the fundamental theorem of Set Theory due to E. Zermelo. In order to prove it we use the Axiom of Choice and, for the first time, the Power Set Axiom.

Theorem 22. (∀X)(∃ <) [⟨X, <⟩ is a well ordered set].

Proof. We begin by using Theorem 5 to obtain a choice function

f : P(X) \ {∅} → X

such that for each nonempty A ⊆ X we have f(A) ∈ A.

By recursion on 𝕆ℕ we define g : 𝕆ℕ → X ∪ {X} as:

g(β) = \begin{cases}f(X \ \{g(α) : α < β\}), & if X \ \{g(α) : α < β\} ≠ ∅; \\ X, & otherwise. \end{cases}  (6.1)

Now replace each x ∈ X ∩ran(g) by the unique ordinal β such that g(β) = x. The Axiom of Replacement gives the resulting set S ⊆ 𝕆ℕ, where

S = {β ∈ 𝕆ℕ : g(β) ∈ X}.

By Theorem 10 there is a δ ∈ 𝕆ℕ \ S. Choosing any such, we must have g(δ) ∉ X; that is, g(δ) = X and so X ⊆ {g(α) : α < δ}. It is now straightforward to verify that

{⟨x, y⟩ ∈ X × X : x = g(α) and y = g(β) for some α < β < δ}

is a well ordering of X, which completes the proof.

This Well Ordering Principle is used frequently in modern Set Theory. In fact, most uses of the Axiom of Choice are via the Well Ordering Principle. The Power Set Axiom, first used in this proof, will now also be used frequently without special mention.

58 CHAPTER 6. RELATIONS AND ORDERINGS

Cardinality

In this chapter, we investigate a concept which aims to translate our intuitive notion of size into formal language. By Zermelo’s Well Ordering Principle (Theorem 22) every set can be well ordered. By Theorem 21, every well ordered set is isomorphic to an ordinal. Therefore, for any set x there is some ordinal κ ∈ 𝕆ℕ and a bijection f: x → κ.

We define the \underline{cardinality} of x, |x|, to be the least κ ∈ 𝕆ℕ such that there is some bijection f : x → κ. Every set has a cardinality.

Those ordinals which are |x| for some x are called \underline{cardinals}.

Exercise 19. Prove that each n ∈ ω is a cardinal and that ω is a cardinal. Show that ω + 1 is not a cardinal and that, in fact, each other cardinal is a limit ordinal.

Theorem 23. The following are equivalent.

1. κ is a cardinal.

2. (∀α < κ)(¬∃ bijection f: κ → α); i.e., |κ| = κ.

3. (∀α < κ)(¬∃ injection f: κ → α).

60 CHAPTER 7. CARDINALITY

Proof. We prove the negations of each are equivalent:

¬(1) (∀x)[(∃ bijection g: x → κ) → (∃α < κ)(∃ bijection h: x → α)]
¬(2) ∃α < κ ∃ bijection f: κ → α
¬(3) ∃α < κ ∃ injection f: κ → α

¬(2) ⇒ ¬(1) Just take h = f ∘ g. ¬(1) ⇒ ¬(3) Just consider x = κ. ¬(3) ⇒ ¬(2) Suppose α < κ and f: κ → α is an injection. By Theorem

21, there is an isomorphism g: β → f^{→}κ for some β ∈ 𝕆ℕ. Since g is order preserving, we must have γ ≤ g(γ) for each γ ∈ β and hence β ≤ α. Now g^{−1} ∘ f: κ → β is the desired bijection.

The following exercises are applications of the theorem. The first two statements relate to the questions raised in the introduction. Exercise 20. Prove the following:

1. |x| = |y| iff ∃ bijection f: x → y.

2. |x| ≤ |y| iff ∃ injection f: x → y.

3. |x| ≥ |y| iff ∃ surjection f: x → y. Assume here that y ≠ ∅. Theorem 24. (G. Cantor)

∀x |x| < |P(x)|.

Proof. First note that if |x| ≥ |P(x)|, then there would be a surjection

g: x → P(x).

But this cannot happen, since {a ∈ x : a ∉ g(a)} ∉ g^{→}(x).

For any ordinal α, we denote by α^{+} the least cardinal greater than α. This is well defined by Theorem 24.

Exercise 21. Prove the following:

1. The supremum of a set of cardinals is a cardinal.

2. ¬∃z z = {κ : κ is a cardinal}.

Theorem 25. For any infinite cardinal κ, |κ × κ| = κ.

Proof. Let κ be an infinite cardinal. The formulas |κ| = |κ × {0}| and |κ × {0}| ≤ |κ × κ| imply that κ ≤ |κ × κ|. We now show that |κ × κ| ≤ κ. We use induction and assume that |λ × λ| = λ for each infinite cardinal λ < κ.

We define an ordering on κ × κ by:

⟨α_{0}, β_{0}⟩ < ⟨α_{1}, β_{1}⟩ iff \begin{cases}max \{α_{0}, β_{0}\} < max \{α_{1}, β_{1}\}; \\ max \{α_{0}, β_{0}\} = max \{α_{1}, β_{1}\} ∧ α_{0} < α_{1}; or, \\ max \{α_{0}, β_{0}\} = max \{α_{1}, β_{1}\} ∧ α_{0} = α_{1} ∧ β_{0} < β_{1}. \end{cases}

It is easy to check that < well orders κ × κ.

Let θ = type ⟨κ × κ, <⟩. It suffices to show that θ ≤ κ. And for this it suffices to show that for all ⟨α, β⟩ ∈ κ × κ,

type ⟨<^{←} {⟨α, β⟩}, <⟩ < κ.

To this end, pick ⟨α, β⟩ ∈ κ×κ. Let δ ∈ κ be such that <^{←} {⟨α, β⟩} ⊆ δ ×δ. This is possible since κ is a limit ordinal. It now suffices to prove that

type ⟨<^{←} {⟨δ, δ⟩}, <⟩ < κ.

By Theorem 23 it suffices to prove that |<^{←} {⟨δ, δ⟩}| < κ and so it suffices to prove that |δ × δ| < κ.

Since |δ × δ| = ||δ| × |δ||, it suffices to prove that |λ × λ| < κ for all cardinals λ < κ. If λ is infinite, this is true by inductive hypothesis. If λ is finite, then |λ × λ| < ω ≤ κ.

Corollary. If X is infinite, then |X × Y | = max {|X|, |Y |}.

Theorem 26. For any X we have | ⋃ X| ≤ max {|X|, sup {|a| : a ∈ X}}, provided that at least one element of X ∪ {X} is infinite.

Proof. Let κ = sup {|a| : a ∈ X}. Using Exercise 20, for each a ∈ X there is a surjection f_{a}: κ → a. Define a surjection f: X × κ → ⋃ X by

f(⟨a, α⟩) = f_{a}(α).

Using Exercise 20 and the previous corollary, the result follows.

Define ^{B}A as {f : f: B → A} and [A]^{κ} as {x : x ⊆ A ∧ |x| = κ}.

Lemma. If κ is an infinite cardinal, then |^{κ}κ| = |[κ]^{κ}| = |P(κ)|.

Proof. We have,

κ2 ⊆ ^{κ}κ ⊆ [κ × κ]^{κ} ⊆ P(κ × κ).

Using characteristic functions it is easily proved that |^{κ}2| = |P(κ)|. Since |κ × κ| = κ we have the result.

Lemma. If κ ≤ λ and λ is an infinite cardinal, then |^{κ}λ| = |[λ]^{κ}|.

Proof. For each x ∈ [λ]^{κ} there is a bijection f_{x}: κ → x. Since f_{x} ∈ ^{κ}λ, we have an injection from [λ]^{κ} into ^{κ}λ, so |[λ]^{κ}| ≤ |^{κ}λ|.

Now ^{κ}λ ⊆ [κ × λ]^{κ}. Thus, |^{κ}λ| ≤ |[λ]^{κ}|.

A subset S of a limit ordinal α is said to be \underline{cofinal} whenever sup S = α. A function f : δ → α is said to be \underline{cofinal} whenever rng(f) is cofinal in α. The \underline{cofinality}, cf(α), of a limit ordinal α is the least δ ∈ 𝕆ℕ such that there is a cofinal f : δ → α.

A cardinal κ is said to be \underline{regular} whenever cf(κ) = κ. Otherwise, κ is said to be \underline{singular}. These notions are of interest when κ is an infinite cardinal. In particular, ω is regular.

Lemma.

1. For each limit ordinal κ, cf(κ) is a regular cardinal.

2. For each limit ordinal κ, κ^{+} is a regular cardinal.

3. Each infinite singular cardinal contains a cofinal subset of regular cardinals.

Exercise 22. Prove this lemma.

Theorem 27. (König’s Theorem)

For each infinite cardinal κ, |^{cf(κ)}κ| > κ.

Proof. We show that there is no surjection g: κ → ^{δ}κ, where δ = cf(κ). Let f: δ → κ witness that cf(κ) = δ. Define h: δ → κ such that each h(α) ∉ {g(β)(α) : β < f(α)}. Then h ∉ g^{→}(κ), since otherwise h = g(β) for some β < κ; pick α ∈ δ such that f(α) > β.

Corollary. For each infinite cardinal κ, cf(|P(κ)|) > κ.

Proof. Let λ = |P(κ)|. Suppose cf(λ) ≤ κ. Then

λ = |P(κ)| = |^{κ}2| = |^{(κ×κ)}2| = |^{κ}(^{κ}2)| = |^{κ}λ| ≥ |^{cf(λ)}λ| > λ.

Cantor’s Theorem guarantees that for each ordinal α there is a set, P(α), which has cardinality greater than α. However, it does not imply, for example, that ω^{+} = |P(ω)|. This statement is called the Continuum Hypothesis, and is equivalent to the third question in the introduction.

The \underline{aleph function} ℵ: 𝕆ℕ → 𝕆ℕ is defined as follows:

ℵ(0) = ω
ℵ(α) = sup {ℵ(β)^{+} : β ∈ α}.

We write ℵ_{α} for ℵ(α). We also sometimes write ω_{α} for ℵ(α).

The \underline{beth function} ℶ: 𝕆ℕ → 𝕆ℕ is defined as follows:

ℶ(0) = ω
ℶ(α) = sup {|P(ℶ(β))| : β ∈ α}.

We write ℶ_{β} for ℶ(β).

It is apparent that ℵ_{1} ≤ ℶ_{1}. The \underline{continuum hypothesis} is the statement ℵ_{1} = ℶ_{1}; this is abbreviated as CH. The \underline{generalised continuum hypothesis}, GCH, is the statement ∀α ∈ 𝕆ℕ ℵ_{α} = ℶ_{α}. Exercise 23. Prove that

∀κ [κ is an infinite cardinal → (∃α ∈ 𝕆ℕ(κ = ℵ_{α})].

A cardinal κ is said to be \underline{inaccessible} whenever both κ is regular and

∀λ < κ |P(λ)| < κ.

An inaccessible cardinal is sometimes said to be strongly inaccessible, and the term weakly inaccesible is given to a regular cardinal κ such that

∀λ < κ λ^{+} < κ.

Under the GCH these two notions are equivalent.

Axiom of Inaccessibles ∃κ κ > ω and κ is an inaccessible cardinal

This axiom is a stronger version of the Axiom of Infinity, but the mathematical community is not quite ready to replace the Axiom of Infinity with it just yet. In fact, the Axiom of Inacessibles is not included in the basic 𝒵ℱ𝒞 axiom system and is therefore always explicitly stated whenever it is used. Exercise 24. Are the following two statements true? What if κ is assumed to be a regular cardinal?

1. κ is weakly inaccessible iff κ = ℵ_{κ}.

2. κ is strongly inaccesssible iff κ = ℶ_{κ}.

There Is Nothing Real About The Real Numbers

We now formulate three familiar number systems in the language of set theory. From the natural numbers we shall construct the integers; from the integers we shall construct the decimal numbers and the real numbers.

For each n ∈ ℕ let −n = \{\{m\} : m ∈ n\}. The \underline{integers}, denoted by ℤ, are defined as

ℤ = ℕ ∪ {−n : n ∈ ℕ}.

For each n ∈ ℕ \ {∅} we denote {n} by −n.

We can extend the ordering < on ℕ to ℤ by letting x < y iff one of the following holds:

1. x ∈ ℕ ∧ y ∈ ℕ ∧ x < y;

2. x ∉ ℕ ∧ y ∈ ℕ; or,

3. x ∉ ℕ ∧ y ∉ ℕ ∧ ⋃ y < ⋃ x.

To form the reals, first let

F = {f : f ∈ ^{ω}ℤ}.

66CHAPTER 8. THERE IS NOTHING REAL ABOUT THE REAL NUMBERS

We pose a few restrictions on such functions as follows. Let us write:

A(f) for (∀n > 0)(−9 ≤ f(n) ≤ 9);
B(f) for (∀n ∈ ω)(f(n) ≥ 0) ∨ (∀n ∈ ω)(f(n) ≤ 0);
C(f) for (∀m ∈ ω)(∃n ∈ ω \ m)(f(n) ∉ {9, −9}); and,
D(f) for (∃m ∈ ω)(∀n ∈ ω \ m)(f(n) = 0).

Finally, let

ℝ = {f : f ∈ F and A(f) and B(f) ∧ C(f)}

to obtain the \underline{real numbers} and let

𝔻 = {f : f ∈ ℝ and D(f)}

to obtain the \underline{decimal numbers}.

We now order ℝ as follows: let f < g iff

(∃n ∈ ω) [f(n) < g(n) ∧ (∀m ∈ n)(f(m) = g(m))].

This ordering clearly extends our ordering on ℕ and ℤ, and restricts to 𝔻.

In light of these definitions, the operations of addition, multiplication and exponentiation defined in Chapter 4 can be formally extended from ℕ to ℤ, 𝔻 and ℝ in a natural—if cumbersome—fashion.

Lemma.

1. |𝔻| = ℵ_{0}.

2. ℝ is uncountable.

3. < is a linear order on 𝔻.

4. (∀p ∈ ℝ)(∀q ∈ ℝ) [p < q → ∃d ∈ 𝔻 p < d < q].

I.e., 𝔻 is a countable \underline{dense} subset of ℝ.

5. < is complete; i.e., bounded subsets have suprema and infima.

Exercise 25. Prove this lemma.

Theorem 28. Any two countable dense linear orders without endpoints are isomorphic.

Proof. This method of proof, the back-and-forth argument, is due to G.Cantor. The idea is to define an isomorphism recursively in ω steps, such that at each step we have an order-preserving finite function; at even steps f(x_{i}) is defined and at odd steps f^{−1}(y_{j}) is defined.

Precisely, if X = {x_{i} : i ∈ ω} and Y = {y_{j} : j ∈ ω} are two countable dense linear orders we define f: X → Y by the formulas

f_{0} = {⟨x_{0}, y_{0}⟩}
f_{n+1} = f_{n} ∪ {⟨x_{i}, y_{j}⟩}

where

1. if n is even, i = min {k ∈ ω : x_{k} ∉ dom(f_{n})} and j is chosen so that f_{n} ∪ {⟨x_{i}, y_{j}⟩} is order-preserving; and,

2. if n is odd, j = min {k ∈ ω : y_{k} ∉ rng(f_{n})} and i is chosen so that f_{n} ∪ {⟨x_{i}, y_{j}⟩} is order-preserving.

We then check that for each n ∈ ω, there is indeed a choice of j in (1) and i in (2) and that f = ⋃{f_{n} : n ∈ ω} is an isomorphism.

Any complete dense linear order without endpoints and with a countable dense subset is isomorphic to ⟨ℝ, <⟩. Can “with a countable dense subset” be replaced by “in which every collection of disjoint intervals is countable”?. The affirmation of this is called the Suslin Hypothesis. It is the second most important problem in Set Theory. It too requires new axioms for its solution.

We have begun with ℕ, extended to ℤ, then extended again to ℝ. We now extend once more to ^{∗}ℝ. This is the set of hyperreals. In order to do this, we introduce the important notion of an ultrafilter.

A collection of subsets U ⊆ P(S) is a \underline{filter} provided that it satisfies the first three of the following conditions:

1. S ∈ U and ∅ ∉ U.

68CHAPTER 8. THERE IS NOTHING REAL ABOUT THE REAL NUMBERS 2. If A ∈ U and B ∈ U, then A ∩ B ∈ U.

3. If A ∈ U and A ⊆ B, then B ∈ U.

4. A ∈ U or B ∈ U whenever A ∪ B = S.

5. ∀x ∈ S {x} ∉ U.

If a filter U obeys condition (4) it is called an \underline{ultrafilter}, and if U satisfies conditions (1) through (5) it is said to be a \underline{free} or \underline{non-principal} ultrafilter.

An ultrafilter is a maximal filter under inclusion. Every filter can be extended to an ultrafilter. (We can recursively define it.) There is a free ultrafilter over ω. Theorem 29. (Ramsey)

If P: [ω]^{2} → {0, 1}, then there is H ∈ [ω]^{ω} such that |P′′[H]^{2}| = 1.

Proof. Let U be a free ultrafilter over ω. Either:

1. {α ∈ ω : {β ∈ ω : P ({α, β}) = 0} ∈ U} ∈ U; or,

2. {α ∈ ω : {β ∈ ω : P ({α, β}) = 1} ∈ U} ∈ U.

As such, the proof breaks into two similar cases. We address case (1).

Let S = {α ∈ ω : {β ∈ ω : P ({α, β}) = 0} ∈ U}. Pick α_{0} ∈ S and let

S_{0} = {β ∈ ω : P ({α_{0}, β}) = 0}.

Pick α_{1} ∈ S ∩ S_{0} and let

S_{1} = {β ∈ ω : P ({α_{1}, β}) = 0}.

In general, recursively choose {α_{n} : n < ω} such that for each n α_{n+1} ∈ S ∩ S_{0} ∩ ⋯ ∩ S_{n}, where

S_{n} = {β ∈ ω : P ({α_{n}, β}) = 0}.

Then H = {α_{n} : n < ω} exhibits the desired property.

Theorem 30. (Sierpinski)

There is a function P: [ω_{1}]^{2} → {0, 1} such that there is no H ∈ [ω_{1}]^{ω_{1}} with |P′′[H]^{2}| = 1.

Proof. Let f: ω_{1} → ℝ be an injection. Define P as follows: for α < β, let

P (\{α, β\}) = \begin{cases}0, & if f(α) < f(β); \\ 1, & if f(α) > f(β). \end{cases}  (8.1)

The following exercise finishes the proof.

Exercise 26. There is no subset of ℝ with order type ω_{1}.

Let U be a free ultrafilter over ω. Form an equivalence relation ∼ on ^{ω}ℝ by the rule:

f ∼ g whenever {n ∈ ω : f(n) = g(n)} ∈ U.

The equivalence class of f is denoted by

[f] = {g ∈ ^{ω}ℝ : g ∼ f}.

The set of equivalence classes of ∼ is called the \underline{ultrapower} of ℝ with respect to U. The elements of^{ω}ℝ are often called the \underline{hyperreal numbers} and denoted ∗ℝ.

There is a \underline{natural embedding} of ℝ into ^{∗}ℝ given by

x ↦ [f_{x}]

where f_{x}: ω → ℝ is the constant function; i.e., f_{x}(n) = x for all n ∈ ω; we identify ℝ with its image under the natural embedding.

70CHAPTER 8. THERE IS NOTHING REAL ABOUT THE REAL NUMBERS

We can define an ordering ^{∗} < on ^{∗}ℝ by the rule:

a <^{∗} b whenever ∃f ∈ a ∃g ∈ b {n ∈ ω : f(n) < g(n)} ∈ U. Lemma. ^{∗} < is a linear ordering on ^{∗}ℝ which extends the usual ordering of ℝ. Exercise 27. Prove this lemma.

We usually omit the asterisk, writing < for ^{∗} <. Exercise 28. There is a subset of ^{∗}ℝ of order type ω_{1}.

For each function F: ℝ^{n} → ℝ there is a \underline{natural extension}

∗F: (^{∗}ℝ)^{n} → ^{∗}ℝ

given by

∗F (a⃗) = [F ∘ s⃗]

where a⃗ = ⟨a_{0}, …, a_{n−1}⟩ ∈ (^{∗}ℝ)^{n} and s⃗: ω → ℝ^{n} such that for each j ∈ ω

s⃗(j) = ⟨s_{0}(j), …, s_{n−1}(j)⟩

and s_{i} ∈ a_{i} for each i. Theorem 31. (The Leibniz Transfer Principle)

Suppose F: ℝ^{n} → ℝ and G: ℝ^{n} → ℝ.

1. ∀a⃗ ∈ ℝ^{n} F (a⃗) = G(a⃗) iff ∀a⃗ ∈ (^{∗}ℝ)^{n} ^{∗}F (a⃗) = ^{∗}G(a⃗).

2. ∀a⃗ ∈ ℝ^{n} F (a⃗) < G(a⃗) iff ∀a⃗ ∈ (^{∗}ℝ)^{n} ^{∗}F (a⃗) < ^{∗}G(a⃗). Exercise 29. Prove the above theorem. This includes verifying that ^{∗}F is a function.

As a consequence of this theorem, we can extend + and × to ^{∗}ℝ. For example, a + b = c means that

∃f ∈ a ∃g ∈ b ∃h ∈ c {n ∈ ω : f(n) + g(n) = h(n)} ∈ U.

Indeed, the natural embedding embeds ℝ as an ordered subfield of ^{∗}ℝ.

In order to do elementary calculus we consider the \underline{infinitesimal} elements of ^{∗}ℝ. Note that ℝ ≠ ^{∗}ℝ; consider

α = [⟨1, 1/2, 1/3, …, 1/n, … ⟩].

Then α > 0 but α < r for each positive r ∈ ℝ; a member of ^{∗}ℝ with this property is called a \underline{positive infinitesimal}. There are negative infinitesimals; 0 is an infinitesimal. Since ^{∗}ℝ is a field 1/α exists and 1/α > r for any real number r; it is an example of a \underline{positive infinite} number.

A hyperreal number a is said to be \underline{finite} whenever |a| < r for some real r. Two hyperreal numbers a and b are said to be \underline{infinitely close} whenever a − b is infinitesimal. We write a ≈ b.

Lemma. Each finite hyperreal number is infinitely close to a unique real number.

Proof. Let a be finite. Let s = sup {r ∈ ℝ : r < a}. Then a ≈ s. If we also have another real t such that a ≈ t, then we have s ≈ t and so s = t.

If a is finite, the \underline{standard part} of a, st(a), is defined to be the unique real number which is infinitely close to a.

It is easy to check that for finite a and b,

st(a + b) = st(a) + st(b); and,
st(a × b) = st(a) × st(b).

For a function F: ℝ → ℝ we define the \underline{derivative}, F′(x), of F (x) to be

st (\frac{F (x + △x) − F (x)}{△x})

provided this exists and is the same for each non-zero infinitesimal △x.

The fact that F′(x) exists implies that for each infinitesimal △x there is an infinitesimal ϵ such that F (x + △x) = F (x) + F′(x)△x + ϵ△x. That is, for any △x ≈ 0 there is some ϵ ≈ 0 such that

△y = F′(x)△x + ϵ△x

where △y = F (x + △x) − F (x).

Theorem 32. (The Chain Rule)

Suppose y = F (x) and x = G(t) are differentiable functions. Then y = F (G(t)) is differentiable and has derivative F′(G(t)) · G′(t).

Proof. Let △t be any non-zero infinitesimal. Let △x = G(t + △t) − G(t). Since G′(x) exists, △x is infinitesimal. Let △y = F (x + △x) − F (x). We wish to calculate st(\frac{△y}{△x}), which will be the derivative of y = F (G(t)). We consider two cases.

Case 0: △x = 0 △y = 0, st(\frac{△y}{△t}) = 0, and G′(t) = st(\frac{△x}{△t}) = 0.

So st(\frac{△y}{△t}) = F′(G(t)) · G′(t).

Case 1: △x ≠ 0 \frac{△y}{△t} = \frac{△y}{△x} · \frac{△x}{△t}. So st(\frac{△y}{△t}) = st(\frac{△y}{△x}) · st(\frac{△x}{△t}), and again,

st(\frac{△y}{△t}) = F′(x) · G′(t) = F′(G(t)) · G′(t).

The Universe

In this chapter we shall discuss two methods of measuring the complexity of a set, as well as their corresponding gradations of the universe. For this discussion it will be helpful to develop both a new induction and a new recursion procedure, this time on the whole universe. Each of these will depend upon the fact that every set is contained in a transitive set, which we now prove.

By recursion on ℕ, we define:

⋃^{0}X = X; and,
⋃^{n+1}X = ⋃(⋃^{n}X).

We define the \underline{transitive closure} of X as,

trcl(X) = ⋃{⋃^{n}X : n ∈ ω}.

Theorem 33.

1. ∀X trcl(X) is the smallest transitive set containing X.

2. ∀x trcl(x) = x ∪ ⋃{trcl(y) : y ∈ x}.

Proof. Note that Y is transitive iff ⋃ Y ⊆ Y, so trcl(X) is transitive.

1. If Y is transitive and X ⊆ Y then for each n ∈ ℕ, ⋃^{n}X ⊆ ⋃^{n}Y ⊆ Y. So trcl(X) ⊆ Y.

2. To prove that trcl(x) ⊇ x ∪ ⋃{trcl(y) : y ∈ x}, notice first that since ∀y ∈ x y ⊆ ⋃ x, we have that ∀n ∈ ω ⋃^{n}y ⊆ ⋃^{n+1}x. Hence trcl(y) ⊆ trcl(x). For the opposite containment, we prove by induction that ∀n ∈ ω ⋃^{n}x ⊆ x ∪ ⋃{trcl(y) : y ∈ x}.

As with ℕ and 𝕆ℕ, we can perform induction on the universe, called \underline{∈ −induction}, as illustrated by the following theorem scheme.

For each formula Φ(v, w⃗) of the language of set theory we have:

Theorem 34. Φ

For all w⃗, if

∀n [(∀m ∈ n Φ(m, w⃗)) → Φ(n, w⃗)]

then

∀n Φ(n, w⃗).

Proof. We shall assume that the theorem is false and derive a contradiction. We have w⃗ and a fixed l such that ¬Φ(l, w⃗).

Let t be any transitive set containing l. Thanks to the previous theorem, we can let t = trcl(l ∪ {l}). The proof now proceeds verbatim as the proofs of Theorems 8 and 13.

We can also carry out recursive definitions on 𝕍; this is called \underline{∈ −recursion}. For any formula Φ(x, f, y, w⃗) of the language of set theory, we denote by REC(Φ, 𝕍) the class

{⟨x, y⟩ : (∃n)(∃f) [f: n → 𝕍 ∧ f(x) = y ∧ ∀m ∈ n Φ(m, f|m, f(m), w⃗)]}.

∈ −recursion is justified by the next theorem scheme.

For each formula Φ(x, f, y, w⃗) of the language of set theory we have: Theorem 35. Φ For all w⃗, suppose that we have

(∀x)(∀f) [(f: x → 𝕍) → ∃!y Φ(x, f, y, w⃗)].

Then, letting F denote REC(Φ, 𝕍), we have:

1. F: 𝕍 → 𝕍;

2. ∀x Φ(x, F |x, F (x), w⃗); and furthermore for any n and any function H with n ∈ dom(H) we have,

3. Φ(x, H|x, H(x), w⃗) for all x ∈ n ∪ {n} then H(n) = F (n).

Proof. The proof is similar to that of Theorems 9 and 14.

Our first new measure of the size of a set is given by the \underline{rank} function. This associates, to each set x, an ordinal rank(x) by the following rule:

rank(x) = sup {rank(y) + 1 : y ∈ x}

Observe that ∀α ∈ 𝕆ℕ rank(α) = α.

By recursion on 𝕆ℕ we define the \underline{cumulative hierarchy}, an ordinal-gradation on 𝕍, as follows.

R(0) = ∅;
R(α + 1) = P(R(α)); and,
R(δ) = ⋃{R(α) : α < δ} if δ is a limit ordinal.

Sometimes we write R_{α} or 𝕍_{α} for R(α). The next theorem connects and lists some useful properties of the cumulative hierarchy and the rank function. Theorem 36.

76 CHAPTER 9. THE UNIVERSE

1. ∀α ∈ 𝕆ℕ R(α) is transitive.

2. ∀α ∈ 𝕆ℕ ∀β ∈ 𝕆ℕ (β < α → R(β) ⊆ R(α).

3. ∀x ∀α ∈ 𝕆ℕ (x ∈ R(α) ↔ ∃β ∈ α x ⊆ R(β)).

4. ∀x ∀α ∈ 𝕆ℕ (x ∈ R(α + 1) \ R(α) ↔ rank(x) = α).

5. ∀x ∃α ∈ 𝕆ℕ x ∈ R(α); i.e., 𝕍 = ⋃{R(α) : α ∈ 𝕆ℕ}.

Proof.

1. This is an easy induction on α ∈ 𝕆ℕ.

2. Apply induction on α, using (1).

3. (→) Note that if γ is least ordinal such that x ∈ R(γ), then γ is a

successor ordinal, so choose β such that γ = β + 1; (←) This uses (2).

4. First show by induction on α that rank(x) < α implies x ∈ R(α).

5. This follows from ∀x ∃α ∈ 𝕆ℕ rank(x) = α.

We have discussed cardinality as a way of measuring the size of a set. However, if our set is not transitive, the cardinality function does not tell the whole story since it cannot distinguish the elements of the set. For example, although ℕ ∈ {ℕ}, |ℕ| = ℵ_{0} while |{ℕ}| = 1. Intuitively, we think of {ℕ} as no smaller than ℕ. As such, we define the \underline{hereditary cardinality}, hcard(x), of a set x, as the cardinality of its transitive closure:

hcard(x) = |trcl(x)|

The corresponding cardinal-gradation is defined as follows.

For each cardinal κ,

H(κ) = {x : |trcl(x) < κ}.

The members of H(ω) are called the \underline{hereditarily finite sets} and the members of H(ω_{1}) are called the \underline{hereditarily countable sets}. The next theorem lists some important properties of H. Theorem 37.

1. For any infinite cardinal κ, H(κ) is transitive.

2. For any infinite cardinal κ, ∀x hcard(x) < κ → rank(x) < κ.

3. For any infinite cardinal κ, H(κ) ⊆ R(κ).

4. For any infinite cardinal κ, ∃z z = H(κ).

5. ∀x ∃κ (κ is a cardinal and x ∈ H(κ)); i.e, 𝕍 = ⋃{H(κ) : κ is a cardinal}.

Proof.

1. Apply part (2) of Theorem 33.

2. Case 1: κ is regular.

The proof is by ∈-induction on 𝕍, noting that if rank(y) < κ for each y ∈ x and |x| < κ, then rank(x) < κ.

Case 2: κ is singular.

There is a regular cardinal λ such that hcard(x) < λ < κ; now use Case 1.

3. This follows from (2) and Theorem 36.

4. Apply (3) and Comprehension.

5. This follows since ∀x ∃κ hcard(x) = κ.

Theorem 38. If κ is an inaccessible cardinal, then H(κ) = R(κ).

Proof. From Theorem 37 we have H(κ) ⊆ R(κ).

For the reverse containment, let x ∈ R(κ). By Theorem 36, ∃α < κ such that x ∈ R(α + 1) \ R(α). So x ⊆ R(α). Since R(α) is transitive, trcl(x) ⊆ R(α).

It suffices to prove by induction that ∀α < κ |R(α)| < κ. For successor α = β + 1, we note that |P(λ)| < κ, where λ = |R(β)|; for limit α we apply Theorem 36, observing that κ is regular.

Reflection

There is a generalisation of the Equality Axiom, called the \underline{Equality Principle}, which states that for any formula Φ we have x = y implying that Φ holds at x iff Φ holds at y. The proof requires a new technique, called induction on complexity of the formula.

We make this precise. For each formula Φ of set theory all of whose free variables lie among v_{0}, …, v_{n} we write Φ(v_{0}, …, v_{n}) and for each i and j with 0 ≤ i ≤ n, we denote by Φ(v_{0}, …, v_{i}/v_{j}, …, v_{n}) the result of substituting v_{j} for each free occurance of v_{i}.

For each formula Φ(v_{0}, …, v_{n}) and each i and j with 0 ≤ i ≤ n we have:

Theorem 39. Φ, i, j

∀v_{0} … ∀v_{i} … ∀v_{n}∀v_{j}[v_{i} = v_{j} → (Φ(v_{0}, …, v_{n}) ↔ (Φ(v_{0}, …, v_{i}/v_{j}, …, v_{n}))]

This is a scheme of theorems, one for each appropriate Φ, i, j.

Proof. The proof will come in two steps.

1. We first prove this for atomic formulas Φ.

Case 1 Φ is v_{i} ∈ v_{k} where i ≠ k This is true by Axiom of Equality.

Case 2 Φ is v_{k} ∈ v_{i} where i ≠ k This is true by Axiom of Extensionality.

Case 3 Φ is v_{i} ∈ v_{i} This is true since by Theorem 2 both v_{i} ∈ v_{j} and v_{j} ∈ v_{i} are false.

Case 4 Φ is v_{k} ∈ v_{k} where i ≠ k This is true since both Φ(v_{0}, …, v_{n}) and Φ(v_{0}, …, v_{i}/v_{j}, …, v_{n}) are the same.

Case 5 Φ is v_{i} = v_{k} where i ≠ k This is true by Theorem 1.

Case 6 Φ is v_{k} = v_{i} where i ≠ k This is similar to case 5.

Case 7 Φ is v_{i} = v_{i} This is true since by Theorem 1 both v_{i} = v_{i} and v_{j} = v_{j} are true.

Case 8 Φ is v_{k} = v_{k} where i ≠ k This is similar to case 4.

2. We now show that for any subformula Ω of Φ, if the theorem is true for all proper subformulas of Ω then it is true for Ω. Here Θ and Ψ are subformulas of Ω and Ω is expressed in parentheses for each case according to how Ω is built.

Case 1 (¬Θ)

This is true since if

Θ(v_{0}, …, v_{n}) ↔ Θ(v_{0}, …, v_{i}/v_{j}, …, v_{n})

then

¬Θ(v_{0}, …, v_{n}) ↔ ¬Θ(v_{0}, …, v_{i}/v_{j}, …, v_{n})

Case 2 (Θ ∧ Ψ)

From the hypothesis that

Θ(v_{0}, …, v_{n}) ↔ Θ(v_{0}, …, v_{i}/v_{j}, …, v_{n})

and

Ψ(v_{0}, …, v_{n}) ↔ Ψ(v_{0}, …, v_{i}/v_{j}, …, v_{n})

we obain

Θ(v_{0}, …, v_{n}) ∧ Ψ(v_{0}, …, v_{n})

iff

Θ(v_{0}, …, v_{i}/v_{j}, …, v_{n}) ∧ Ψ(v_{0}, …, v_{i}/v_{j}, …, v_{n}).

Cases 3 through 5 result from Cases 1 and 2. Case 3 (Θ ∨ Ψ) Case 4 (Θ → Ψ) Case 5 (Θ ↔ Ψ) Case 6 (∀v_{k} Θ) and i ≠ k

We have

∀v_{0} … ∀v_{n} ∀v_{j} [v_{i} = v_{j} → Θ(v_{0}, …, v_{n})
↔ Θ(v_{0}, …, v_{i}/v_{j}, …, v_{n})].

If v_{k} is not free in Θ, then Θ ↔ ∀v_{k} Θ and we are done. If v_{k} is free in Θ, then since 0 ≤ k ≤ n we have

∀v_{0} … ∀v_{n} ∀v_{j} ∀v_{k} [v_{i} = v_{j} → Θ(v_{0}, …, v_{n})
↔ Θ(v_{0}, …, v_{i}/v_{j}, …, v_{n})]

and so

∀v_{0} … ∀v_{n} ∀v_{j} [v_{i} = v_{j} → (∀v_{k})(Θ(v_{0}, …, v_{n})
↔ Θ(v_{0}, …, v_{i}/v_{j}, …, v_{n}))]

and so

∀v_{0} … ∀v_{n} ∀v_{j} [v_{i} = v_{j} → (∀v_{k})Θ(v_{0}, …, v_{n})
↔ (∀v_{k})Θ(v_{0}, …, v_{i}/v_{j}, …, v_{n}))].

Case 7 (∃v_{k}) Θ) and i ≠ k

This follows from Cases 1 and 6. Case 8 (∀v_{i} Θ)

This is true since v_{i} is not free in Φ, hence Φ(v_{0}, …, v_{i}/v_{j}, …, v_{n}) is Φ(v_{0}, …, v_{n}).

82 CHAPTER 10. REFLECTION

Case 9 (∃v_{i}) Θ) This is similar to case 8.

We conclude that the theorem scheme holds for all appropriate Φ, i, j.

Let M be a term and Φ any formula of the language of set theory. We define the \underline{relativisation} of Φ to M, denoted by Φ^{M}, as follows:

1. If Φ is atomic then Φ^{M} is Φ;

2. If Φ is ¬Ψ then Φ^{M} is ¬Ψ^{M};

3. If Φ is (Ψ_{1} ∧ Ψ_{2}) then Φ^{M} is (Ψ_{1}^{M} ∧ Ψ_{2}^{M});

4. If Φ is (Ψ_{1} ∨ Ψ_{2}) then Φ^{M} is (Ψ_{1}^{M} ∨ Ψ_{2}^{M});

5. If Φ is (Ψ_{1} → Ψ_{2}) then Φ^{M} is (Ψ_{1}^{M} → Ψ_{2}^{M});

6. If Φ is (Ψ_{1} ↔ Ψ_{2}); then Φ^{M} is (Ψ_{1}^{M} ↔ Ψ_{2}^{M});

7. If Φ is (∀v_{i})Ψ then Φ^{M} is (∀v_{i} ∈ M)Ψ^{M}; and,

8. If Φ is (∃v_{i})Ψ then Φ^{M} is (∃v_{i} ∈ M)Ψ^{M}.

We write M ⊧ Φ for Φ^{M} and moreover whenever Φ has no free variables we say that M is a \underline{model} of Φ.

We denote by 𝒵ℱ𝒞 the collection of axioms which include: Equality, Extensionality, Existence, Pairing, Foundation, Union, Intersection, the Replacement Scheme, Power Set, Choice and Infinity.

For each axiom Φ of 𝒵ℱ𝒞, except for the Axiom of Infinity, we have: Lemma. Φ R(ω) ⊧ Φ.

Lemma. If M is transitive, then M models Equality, Extensionality, Existence and Foundation.

For each axiom Φ of 𝒵ℱ𝒞, except for those in the Replacement Scheme, we have:

Theorem 40. For each uncountable κ, R(κ) ⊧ Φ.

Exercise 30. Prove the above theorem scheme. Use the fact that 𝕍 ⊧ Φ.

For each axiom Φ of 𝒵ℱ𝒞, except for Power Set, we have:

Theorem 41. For each uncountable regular cardinal κ, H(κ) ⊧ Φ.

Exercise 31. Prove the above theorem scheme.

If κ is an inaccessible cardinal, then R(κ) = H(κ) ⊧ Φ, for each axiom Φ of 𝒵ℱ𝒞.

Lemma. If κ is the least inaccessible cardinal, then

H(κ) ⊧ ¬∃ an inaccessible cardinal.

From this lemma we can infer that there is no proof, from 𝒵ℱ𝒞, that there is an inaccessible cardinal. Suppose Θ is the conjuction of all the (finitely many) axioms used in such a proof. Then from Θ we can derive (∃λ)(λ is an inaccessible). Let κ be the least inaccessible cardinal. Then H(κ) ⊧ Θ so

H(κ) ⊧ (∃λ)(λ is an inaccessible).

This assumes that our proof system is sound; i.e., if from Θ_{1} we can derive Θ_{2} and M ⊧ Θ_{1}, then M ⊧ Θ_{2}. We conclude that 𝒵ℱ𝒞 plus “¬∃ an inaccessible” is consistent.

We can also infer that 𝒵ℱ𝒞 minus “Infinity” plus “¬(∃z)(z = ℕ)” is consistent. Suppose not. Suppose Θ is the conjuction of the finitely many axioms of 𝒵ℱ𝒞 − Inf needed to prove (∃z)(z = N). Then H(ω) ⊧ Θ, so H(ω) ⊧ (∃z)(z = ℕ), which is a contradiction.

In fact, given any collection of formulas without free variables and a class M such that for each Φ in the collection M ⊧ Φ, we can then conclude that the collection is consistent.

For example, 𝒵ℱ𝒞 minus “Power Set” plus “(∀x)(x is countable)” is consistent:

Lemma. H(ω_{1}) ⊧ (∀x)(x is countable).

If Φ(v_{0}, …, v_{k}) is a formula of the language of set theory and M = {x : χ_{M}(x, v⃗)} and C = {x : χ_{C}(x, v⃗)} are classes, then we say Φ is \underline{absolute between M and C} whenever

(∀v_{0} ∈ M ∩ C) … (∀v_{k} ∈ M ∩ C) [Φ^{M} ↔ Φ^{C}].

This concept is most often used when M ⊆ C. When C = 𝕍, we say that Φ is \underline{absolute} for M.

For classes M = {x : χ_{M}(x, v⃗)} and C = {x : χ_{C}(x, v⃗)} with M ⊆ C and a list Φ_{0}, …, Φ_{m} of formulas of set theory such that for each i ≤ m every subformula of Φ_{i} is contained in the list, we have:

Lemma. χ_{M}, χ_{C}, Φ_{1}, …, Φ_{m}

The following are equivalent:

1. Each of Φ_{1}, …, Φ_{m} are absolute between M and C.

2. Whenever Φ_{i} is ∃x Φ_{j}(x, v⃗) for i, j ≤ m we have

(∀v_{1} ∈ M … ∀v_{k} ∈ M)(∃x ∈ C Φ_{j}^{C}(x, v⃗) → ∃x ∈ M Φ_{j}^{C}(x, v⃗)).

The latter statement is called the \underline{Tarski-Vaught Condition}.

Proof. ((1) ⇒ (2))

Let v_{0} ∈ M, …, v_{k} ∈ M and suppose ∃x ∈ C Φ_{j}^{C}(x, v_{0}, …, v_{k}). Then Φ_{i}^{C}(v_{0}, …, v_{k}) holds. By absoluteness Φ_{i}^{M}(v_{0}, …, v_{k}) holds; i.e., ∃x ∈ M Φ_{j}^{M}(x, v_{0}, …, v_{k}), so by absoluteness of Φ_{j}(x, v_{0}, …, v_{k}) for x ∈ M we have ∃x ∈ M Φ_{j}^{C}(x, v_{0}, …, v_{k}).

(2) ⇒ (1)

This is proved by induction on complexity of Φ_{i}, noting that each subformula appears in the list. There is no problem with the atomic formula step since atomic formulas are always absolute. Similarly, the negation and connective steps are easy. Now if Φ_{i} is ∃x Φ_{j} and each of v_{1}, …, v_{k} is in M we have

Φ_{i}^{M}(v_{1}, …, v_{k}) ⇔ ∃x ∈ M Φ_{j}^{M}(x, v_{1}, …, v_{k})
⇔ ∃x ∈ M Φ_{j}^{C}(x, v_{1}, …, v_{k})
⇔ ∃x ∈ C Φ_{j}^{C}(x, v_{1}, …, v_{k})
⇔ Φ_{i}^{C}(v_{1}, …, v_{k})

where the second implication is due to the inductive hypothesis and the third implication is by part (2).

The next theorem scheme is called the \underline{Levy Reflection Principle}.

For each formula Φ of the language of set theory, we have:

Theorem 42. Φ

∀α ∈ 𝕆ℕ ∃β ∈ 𝕆ℕ [β > α and Φ is absolute for R(β)].

If, in addition, Φ has no free variables then Φ implies R(β) ⊧ Φ. This is interpreted as the truth of Φ being reflected to R(β).

Proof. Form a collection Φ_{1}, …, Φ_{m} of all the subformulas of Φ. We will use the Tarski-Vaught Condition for Φ_{1}, …, Φ_{m} to get absoluteness between R(β) and 𝕍; but first we must find β.

For each i = 1, …, m such that Φ_{i} is ∃x Ψ for some formula Ψ we define f_{i} such that f_{i}: 𝕍 → 𝕆ℕ by setting

f_{i}(⟨y_{1}, …, y_{l_{i}}⟩) = min {γ : γ ∈ 𝕆ℕ ∧ ∃x ∈ R(γ) Ψ(x, y_{1}, …, y_{l_{i}})}

if such an ordinal exists, and f_{i}(⟨y_{1}, …, y_{l_{i}}⟩) = α otherwise.

Now define h: ω → 𝕆ℕ by recursion by the formulas

h(0) = α
h(n + 1) = sup {f_{i}(⟨y_{1}, …, y_{l_{i}}⟩) : 1 ≤ i < m and each y_{j} ∈ R(h(n))}

and then let β = sup {h(n) : n ∈ ω}. This β works.

The analogous theorem scheme can be proven for the H(κ) hierarchy as well.

We can now argue that 𝒵ℱ𝒞 cannot be finitely axiomatised. That is, there is no one formula without free variables which implies all axioms of 𝒵ℱ𝒞 and is, in turn, implied by 𝒵ℱ𝒞. Suppose such a Φ exists. By the Levy Reflection Principle, choose the least β ∈ 𝕆ℕ such that Φ^{R(β)}. We have R(β) ⊧ Φ. Hence R(β) ⊧ ∃α ∈ 𝕆ℕ Φ^{R(α)}, since this instance of the theorem follows from 𝒵ℱ𝒞. Thus,

(∃α ∈ 𝕆ℕ Φ^{R(α)})^{R(β)}.

That is,

∃α ∈ (𝕆ℕ ∩ R(β)) Φ^{R(α)∩R(β)}.

But 𝕆ℕ ∩ R(β) = β, the ordinals of rank < β. So, α < β and we have ∃α < β Φ^{R(α)}, contradicting the minimality of β.

For any formula Φ of the language of set theory with no free variables and classes M = {v : χ_{M}(v)}, C = {v : χ_{C}(v)}, and F = {v : χ_{F} (v)} we have:

Lemma. Φ, χ_{M}, χ_{C}, χ_{F}

If F: M → C is an isomorphism then Φ is absolute between M and C. That is, M ⊧ Φ iff C ⊧ Φ.

Proof. It is easy to show by induction on the complexity of Φ that

Ψ(x_{1}, …, x_{k}) ⇔ Ψ(F (x_{1}), …, F (x_{k}))

for each subformula Ψ of Φ.

A \underline{bounded formula} (also called a \underline{△_{0} formula}) is one which is built up as usual with respect to atomic formulas and connectives, but where each ∃x Φ clause is replaced by ∃x ∈ y Φ, and the ∀x Φ clause is replaced by ∀x ∈ y Φ.

△_{0} formulas are absolute for transitive models. That is, for each △_{0} formula Φ(v_{0}, …, v_{k}, w⃗) and for each class M = {x : χ_{M}(x, w⃗)} we have:

Theorem 43. Φ, χ_{M}

∀w⃗ if M is transitive, then

(∀v_{0} ∈ M) … (∀v_{k} ∈ M) [Φ^{M}(v_{0}, …, v_{k}, w⃗) ↔ Φ(v_{0}, …, v_{k}, w⃗)]

Proof. We use induction on the complexity of Φ. We only show the ∃ step. Suppose [(∀v_{0} ∈ M) … (∀v_{k} ∈ M) Φ^{M}(v_{0}, …, v_{k}, w⃗)] ↔ Φ(v_{0}, …, v_{k}, w⃗). We wish to consider (∃v_{i} ∈ v_{j}) Φ(v_{0}, …, v_{k}, w⃗).

Fix any v_{0}, …, v_{k} ∈ M, but not v_{i}; however, v_{j} is fixed in M. Now

(∃v_{i} ∈ v_{j} Φ(v_{0}, …, v_{k}, w⃗))^{M} → (∃v_{i} ∈ v_{j} Φ(v_{0}, …, v_{k}, w⃗))

since Φ^{M}(v⃗, w⃗) → Φ(v⃗, w⃗). Also,

(∃v_{i} ∈ v_{j}) Φ(v⃗, w⃗)
→(∃v_{i} ∈ v_{j}) Φ^{M}(v⃗, w⃗) since Φ(v⃗, w⃗)
→Φ^{M}(v⃗, w⃗)
→∃v_{i} ∈ (v_{j} ∩ M) Φ^{M}(v⃗, w⃗) since v_{j} ∈ M implies v_{j} ⊆ M
→((∃v_{i} ∈ v_{j}) Φ(v⃗, w⃗))^{M}

A formula Φ(w⃗) is said to be △_{1}^{T}, where T is a subcollection of 𝒵ℱ𝒞, whenever there are △_{0} formulas Φ_{1}(v⃗, w⃗) and Φ_{2}(v⃗, w⃗) such that using only the axioms from T we can prove that both:

(∀w⃗)(Φ_{1}(w⃗) ↔ ∃v_{0} … ∃v_{k} Φ_{1}(v⃗, w⃗))
(∀w⃗)(Φ_{2}(w⃗) ↔ ∀v_{0} … ∀v_{k} Φ_{2}(v⃗, w⃗)).

We can now use the above theorem to show that if Φ(w⃗) is a △_{1}^{T} formula and M ⊧ Θ for each Θ in T, then Φ(w⃗) is absolute for M, whenever M is transitive. We do so as follows, letting Ψ play the role of Ψ_{1} above:

Φ(w⃗) ⇔ ∃v_{0} … ∃v_{k} Ψ(v⃗, w⃗)
⇔ (∃v_{0} ∈ M) … (∃v_{k} ∈ M) [Ψ(v⃗, w⃗)]
⇔ ∃v_{0} … ∃v_{k} Ψ(v⃗, w⃗)^{M}
⇔ Φ(w⃗)^{M}

The first and third implications accrue from Φ(w⃗) being △_{1}^{T}; the second from the fact that Ψ is △_{0} and M is transitive and models the axioms of T.

This is often used with T as 𝒵ℱ𝒞 without Power Set and M = H(κ).

Elementary Submodels

In this chapter we shall first introduce a collection of set operations proposed by Kurt Gödel which are used to build sets. We shall then discuss the new concept of elementary submodel.

We now define the ordered \underline{n−tuple} with the following infinitely many formulas, thereby extending the notion of ordered pair.

⟨x⟩ = x
⟨x, y⟩ = {{x}, {x, y}}
⟨x, y, z⟩ = ⟨⟨x, y⟩, z⟩
⟨x_{1}, …, x_{n}⟩ = ⟨⟨x_{1}, …, x_{n−1}⟩, x_{n}⟩

The following operations shuffle the components of such tuples in a set S.

F_{0}(S) = {⟨⟨u, v⟩, w⟩ : ⟨u, ⟨v, w⟩⟩ ∈ S}
F_{1}(S) = {⟨u, ⟨v, w⟩⟩ : ⟨⟨u, v⟩, w⟩ ∈ S}
F_{2}(S) = {⟨v, u⟩ : ⟨u, v⟩ ∈ S}
F_{3}(S) = {⟨v, u, w⟩ : ⟨u, v, w⟩ ∈ S}
F_{4}(S) = {⟨t, v, u, w⟩ : ⟨t, u, v, w⟩ ∈ S}

Lemma. (Shuffle Lemma Scheme)

For any m ∈ ℕ and any permutation σ: m → m, there is a composition of the operations F_{0}, F_{1}, F_{2}, F_{3}, F_{4} such that for any S,

F_{σ}(S) = {⟨x_{σ(0)}, …, x_{σ(m−1)}⟩ : ⟨x_{0}, …, x_{m−1}⟩ ∈ S}.

Proof. Since binary exchanges generate the symmetric group, noting that the identity permutation is given by F_{2} ∘ F_{2}, it suffices to consider only σ such that for some l ≤ m,

σ(i) = \begin{cases}i + 1, & if i = l; \\ i − 1, & if i = l + 1; \\ i, & otherwise. \end{cases}

For convenience, let F_{i}^{n} denote the n−fold composition of F_{i}. There are several cases.

Case 1: m = 2 F_{σ} = F_{2}

Case 2: m = 3, l = 1 F_{σ} = F_{3}

Case 3: m = 3, l = 2 F_{σ} = F_{0} ∘ F_{2} ∘ F_{3} ∘ F_{2} ∘ F_{1}

Case 4: m ≥ 4, l = 1 F_{σ} = F_{0}^{m−3} ∘ F_{3} ∘ F_{1}^{m−3}

Case 5: m ≥ 4, 1 ≤ l ≤ m − 1 F_{σ} = F_{0}^{m−l−2} ∘ F_{4} ∘ F_{1}^{m−l−2}

Case 6: m ≥ 4, l = m − 1 F σ = F_{0} ∘ F_{2} ∘ F_{3} ∘ F_{2} ∘ F_{1}

The \underline{Gödel Operations} are as follows:

G_{1}(X, Y) = {X, Y }
G_{2}(X, Y) = X \ Y
G_{3}(X, Y) = {⟨u, v⟩ : u ∈ X ∧ v ∈ Y }; i.e., X × Y
G_{4}(X, Y) = {⟨u, v⟩ : u ∈ X ∧ v ∈ Y ∧ u = v}
G_{5}(X, Y) = {⟨u, v⟩ : u ∈ X ∧ v ∈ Y ∧ u ∈ v}
G_{6}(X, Y) = {⟨u, v⟩ : u ∈ X ∧ v ∈ Y ∧ v ∈ u}
G_{7}(X, R) = {u : ∃x ∈ X ⟨u, x⟩ ∈ R}
G_{8}(X, R) = {u : ∀x ∈ X ⟨u, x⟩ ∈ R}
G_{9}(X, R) = F_{0}(R)
G_{10}(X, R) = F_{1}(R)
G_{11}(X, R) = F_{2}(R)
G_{12}(X, R) = F_{3}(R)
G_{13}(X, R) = F_{4}(R)

G_{9} through G_{13} are defined as binary operations for conformity.

We now construct a function which, when coupled with recursion on 𝕆ℕ, will enumerate all possible compositions of Gödel operations. G: ℕ×𝕍 → 𝕍 is given by the following rule. For each k ∈ ω and each s⃗: k → 𝕍, we define G|_{ℕ×s⃗} by recursion on ℕ as follows:

G(n, s⃗) = \begin{cases}s⃗(i), & if n = 17^{i}, 0 ≤ i ≤ k; \\ G_{m}(G(i, s⃗), G(j, s⃗)), & if n = m · 19^{i+1}23^{j+1}, 1 ≤ m ≤ 13; \\ ∅, & otherwise. \end{cases}

—

Now G enumerates all compositions of Gödel operations.

We wish to prove that sets defined by △_{0} formulas can be obtained through a composition of Gödel operations. First we need a lemma.

Lemma. Each of the following sets is equal to a composition of Gödel operations on X, w⃗.

92 CHAPTER 11. ELEMENTARY SUBMODELS 1. {⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X ∧ w_{i} = w_{j}}

2. {⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X ∧ w_{i} ∈ w_{j}}

3. {⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X ∧ w_{i} = x_{j}}

4. {⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X ∧ w_{i} ∈ x_{j}}

5. {⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X ∧ x_{i} ∈ w_{j}}

6. {⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X ∧ x_{i} = x_{j}}

7. {⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X ∧ x_{i} ∈ x_{j}}

Proof. First note that {⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X} = G_{3}(G_{3} … (G_{3}(X, X), … X), X) where G_{3} is composed (m − 1)−fold; i.e., (… ((X × X) × X) × ⋯ × X). Now call this set P_{m}(X), the m^{th} power of X. Let us now examine each of the seven cases individually.

1. This is either P_{m}(X) or ∅ depending upon whether or not w_{i} = w_{j}.

2. This is either P_{m}(X) or ∅ depending upon whether or not w_{i} ∈ w_{j}.

3. If m = 1, then this set is ⟨w_{i}⟩ = w_{i}. For m > 1, we may, thanks to the Shuffle Lemma, without loss of generality assume that j = m. The set is equal to

G_{3}(P_{m−1}(X), w_{i})

if w_{i} ∈ X and ∅ otherwise.

4. Again, without loss of generality, we assume j = m. This set is equal

to

G_{3}(P_{m−1}(X), G_{7}(X, G_{6}(X, {w_{i}}))).

5. Again, assume j = m. This set is given by G_{3}(P_{m−1}(X), G_{7}(X, G_{5}(X, {w_{i}}))).

6. This time, assume i = m − 1 and j = m. This set is

G_{3}(P_{m−2}(X), G_{4}(X, X)).

7. We assume again that i = m − 1 and j = m. This set becomes

G_{3}(P_{m−2}(X), G_{5}(X, X)).

For each formula Φ(x, w⃗) of the language of set theory we have:

Theorem 44. Φ

(∀w⃗)(∀X)(∃n ∈ ω) [{x ∈ X : Φ^{X}(x, w⃗)} = G(n, s⃗)]

where s⃗(i) = w_{i} for i < k and s(k) = X.

Proof. We prove by induction on the complexity of Φ that for all m ∈ ω and Φ

(∀w⃗)(∃n ∈ ω)[{⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X
and Φ^{X}(x_{1}, …, x_{m}, w⃗)} = G(n, s⃗)]

The proof of the theorem for any given Φ will assume the corresponding result for a finite number of simpler formulas, the proper subformulas of Φ.

We begin by looking at atomic formulas Φ. This step is covered by the previous lemma.

Now we proceed by induction on complexity. Suppose that

{⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X and Φ_{1}^{X}(x_{1}, …, x_{m}, w⃗)} = G(n_{1}, s⃗)

and

{⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m} ∈ X and Φ_{2}^{X}(x_{1}, …, x_{m}, w⃗)} = G(n_{2}, s⃗).

Then

{⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X … x_{m} ∈ X and ¬Φ_{1}^{X}(x_{1}, …, x_{m}, w⃗)}
= P_{m}(X) \ G(n_{1}, s⃗) = G_{2}(P_{m}(X), G(n_{1}, s⃗))

and

{⟨x_{1}, …, x_{m}⟩ : x_{1} ∈ X … x_{m} ∈ X and Φ_{1}^{X} ∧ Φ_{2}^{X}(x_{1}, …, x_{m}, w⃗)}

= G(n_{1}, s⃗) ∩ G(n_{2}, s⃗).

The other connectives can be formed from ¬ and ∧; as such, ∀x_{l} is ¬∃x_{l}, so it only remains to do the Φ = ∃x_{l} Φ_{1} step. Thanks again to the last lemma, we may assume that l = m. Then Φ is ∃x_{m} Φ_{1} and

{⟨x_{1} … x_{m−1}⟩ : x_{1} ∈ X ∧ ⋯ ∧ x_{m−1} ∈ X and Φ^{X}(x_{1}, …, x_{m−1}, w⃗)}

= G_{7}(G(n_{1}, s⃗))

Let’s write G(n, X, y⃗) for G(n, s⃗), where s⃗(0) = X and s⃗(k + 1) = y⃗(k) for all k ∈ dom(y⃗) = dom(s⃗) − 1.

M is said to be an \underline{elementary submodel} of N whenever

1. M ⊆ N; and,

2. ∀k ∈ ω ∀y⃗ ∈ ^{k}M ∀n ∈ ω G(n, N, y⃗) ∩ N ≠ ∅ ⇔ G(n, N, y⃗) ∩ M ≠ ∅.

We write M ≺ N.

Justification of the terminology comes from the following theorem scheme. For each formula Φ of the language of set theory we have:

Theorem 45. Φ

Suppose M ≺ N. Then Φ is absolute between M and N.

Proof. We will use the Tarski-Vaught criterion. Let Φ_{0}, …, Φ_{m} enumerate Φ and each of its subformulas. Suppose Φ_{i} is ∃x Φ_{j}(x, y_{0}, …, y_{k}) with y_{0}, …, y_{k} ∈ M in a sequence y⃗.

Let n ∈ ω so that by Theorem 44 we can find n ∈ ω such that

G(n, N, y⃗) = {x ∈ N : Φ_{j}^{N}(x, y_{0}, …, y_{k})}.

Then

∃x ∈ N Φ_{j}^{N}(x, y_{0}, …, y_{k}) ↔ G(n, N, y⃗) ∩ N ≠ ∅
↔ G(n, N, y⃗) ∩ M ≠ ∅
↔ ∃x ∈ M Φ_{j}^{N}(x, y_{0}, …, y_{k}).

The following is sometimes called the Lowenheim-Skolem-Tarski theorem.

Theorem 46. Suppose X ⊆ N. Then there is an M such that

1. M ≺ N;

2. X ⊆ M; and,

3. |M| ≤ max{ω, |X|}.

Proof. Define F: ω × ⋃{^{k}N : k ∈ ω} → N by choice:

F (n, s⃗) = \begin{cases}some element of G(n, N, s⃗) & if G(n, N, s⃗) ≠ ∅ \\ any element of ℕ & otherwise \end{cases}

Now define {X_{n}}_{n∈ω} by recursion on ℕ as follows:

X_{0} = X
X_{m+1} = X_{m} ∪ F′′(ω × ⋃{^{k}(X_{m}) : k ∈ ω})

96 CHAPTER 11. ELEMENTARY SUBMODELS Let M = ⋃_{m∈ω} X_{m}. As such, (2) and (3) are clearly satisfied. To check (1), let y⃗ ∈ ^{k}(X_{m}). If G(n, N, y⃗) ∩ N ≠ ∅, then F (n, y⃗) ∈ X_{m+1} ⊆ M and G(n, N, y⃗) ∩ M ≠ ∅.

The use of elementary submodels of the H(θ) can be illustrated. Theorem 47. (Pressing Down Lemma)

Let f: ω_{1} \ {0} → ω_{1} be regressive; i.e., f(α) < α for all α.

Then ∃β ∈ ω_{1} such that f^{←}{β} is uncountable. Theorem 48. (Delta System Lemma)

Let A be an uncountable collection of finite sets.

Then ∃D ⊆ A ∃R such that

1. D is uncountable, and

2. ∀D_{1}, D_{2} ∈ D D_{1} ∩ D_{2} = R.

We need some lemmas. Assume M ≺ H(θ) where θ is an uncountable regular cardinal. For each △_{0} formula Φ(v_{0}, …, v_{k}) we have: Lemma. Φ

(∀y_{0} ∈ M) … (∀y_{k} ∈ M) [M ⊧ Φ(y_{0}, …, y_{k}) ⇔ Φ(y_{0}, …, y_{k})].

Proof.

M ⊧ Φ(y_{0}, …, y_{k}) ⇔ H(θ) ⊧ Φ(y_{0}, …, y_{k}) by elementarity,
⇔ Φ(y_{0}, …, y_{k}) since H(θ) is transitive.

Remark. The same is true for △_{1}^{T} formulas where T is 𝒵ℱ𝒞 without Power Set.

For any formula Φ(v_{0}, …, v_{k}) of LOST, we have: Lemma. Φ

∀y_{0} ∈ M ∀y_{2} ∈ M … ∀y_{k} ∈ M ∀x ∈ H(θ)
[H(θ) ⊧ z = {x : Φ(x, y_{0}, …, y_{k})} → z ∈ M].

Proof. Let y_{0}, …, y_{k} ∈ M and z ∈ H(θ) be given such that

H(θ) ⊧ z = {x : Φ(x, y_{0}, …, y_{k})}.

Then,

H(θ) ⊧ ∃u u = {x : Φ(x, y_{0}, …, y_{k})}
⇒M ⊧ ∃u u = {x : Φ(x, y_{0}, …, y_{k})}
⇒∃p ∈ M [M ⊧ p = {x : Φ(x, y_{0}, …, y_{k})}]
⇒H(θ) ⊧ p = {x : Φ(x, y_{0}, …, y_{k})}
⇒H(θ) ⊧ p = z.

H(θ) is transitive; therefore, p = z and hence z ∈ M.

Corollaries. 1. If M ≺ H(θ), then (a) ∅ ∈ M;

(b) ω ∈ M; and,

(c) ω ⊆ M.

2. If also θ > ω_{1}, then ω_{1} ∈ M. Proof. ∅ and ω are direct. For ω ⊆ M show that y ∈ M ⇒ y ∪ {y} ∈ M.

Lemma. Suppose M ≺ H(θ) where θ is regular and uncountable. Suppose p is countable and p ∈ M. Then p ⊆ M.

Proof. Let q ∈ p; we must show that q ∈ M. Let f_{0} : ω → p be a surjection. Since {ω, p} ⊂ H(θ) we must have f_{0} ∈ H(θ). Since the formula “f: ω → p and p is surjective” is a △_{0} formula and {f_{0}, ω, p} ⊂ H(θ), we have H(θ) ⊧ (f_{0} : ω → p and p is surjective). So

H(θ) ⊧ (∃f)(f: ω → and p is surjective).

Since {ω, p} ⊂ M we have,

M ⊧ (∃f)(f: ω → p and p is surjective).

That is, (∃f_{p} ∈ M)(f_{p}: ω → p and p is surjective).

Pick n ∈ ω such that f_{p}(n) = q, and again use the first lemma as follows. Since {p, f_{p}, n} ⊂ M and (∃!x)(x ∈ p and f_{p}(n) = x) is a △_{0} formula

M ⊧ (∃!x)(x ∈ p and f_{p}(n) = x).

That is, (∃!x)(x ∈ p ∩ M and f_{p}(n) = x). Since x is unique, x = q and thus q ∈ M.

Corollary. ω_{1} ∩ M ∈ ω_{1}.

Proof. It is enough to show that ω_{1} ∩ M is a countable initial segment of ω_{1}. If α ∈ ω_{1} ∩ M, then by the above lemma, α ⊆ M.

Proof of Pressing Down Lemma

Let M ≺ H(ω_{2}) such that M is countable and f ∈ M. Let δ = ω_{1} ∩ M and let β = f(δ) < δ. Then,

(∀α < δ)(∃x ∈ ω_{1}) [x > α ∧ f(x) = β].

So ∀α < δ H(ω_{2}) ⊧ (∃x ∈ ω_{1})(x > α ∧ f(x) = β), since everything relevant is in H(ω_{2}). Hence,

∀α < δ M ⊧ (∃x ∈ ω_{1})(x > α ∧ f(α) = β)

since {α, β, ω_{1}, f} ⊂ M. Now, since δ = ω_{1} ∩ M we have,

M ⊧ (∀α ∈ ω_{1})(∃x ∈ ω_{1}) [x > α ∧ f(α) = β].

So H(ω_{2}) ⊧ (∀α ∈ ω_{1})(∃x ∈ ω_{1}) [x > α ∧ f(α) = β]. Thus we have

H(ω_{2}) ⊧ f^{←}{β} is uncountable.

Again, since everything relevant is in H(ω_{2}) we conclude that f^{←}{β} is uncountable.

□

Proof of the Delta System Lemma

Let A be as given. We may, without loss of generosity, let

A = {a(α) : α < ω_{1}}

where a: ω_{1} → 𝕍. We may also assume that a: ω_{1} → P(ω_{1}).

Let M be countable with {A, ⊣} ⊆ M and M ≺ H(ω_{2}). Let δ = ω_{1} ∩ M. Let R = a(δ) ∩ δ. Since R ⊆ M, we know R ∈ M by the second lemma. So,

∀α < δ ∃β > α a(β) ∩ β = R
⇒H(ω_{2}) ⊧ (∀α < δ)(∃β > α) [a(β) ∩ β = R]
⇒(∀α < δ) [H(ω_{2}) ⊧ (∃β > α)(a(β) ∩ β = R)]
⇒(∀α < δ) [M ⊧ (∃β > α)(a(β) ∩ β = R)]
⇒M ⊧ (∀α < ω_{1})(∃β > α) [a(β) ∩ β = R]
⇒(∀α < ω_{1})(∃β > α) [a(β) ∩ β = R].

Now recursively define D: ω_{1} → A as follows:

D(α) = a(0);
D(γ) = a(β)

100 CHAPTER 11. ELEMENTARY SUBMODELS where β is the least ordinal such that

β > sup {D(γ) : γ < α} and a(β) ∩ β = R.

Now if γ_{1} < γ_{2} < ω_{1}, then D(γ_{1}) ⊆ γ_{2}. So,

R ⊆ D(γ_{1}) ∩ D(γ_{2}) ⊆ γ_{2} ∩ D(γ_{2}) = R.

Thus we let D = {D(α) : α < ω_{1}}.

□

Theorem 49. (Elementary Chain Theorem)

Suppose that δ is a limit ordinal and {M_{α} : α < δ} is a set of elementary submodels of H(θ) such that

∀α ∀α′ (α < α′ < δ → M_{α} ⊂ M_{α′}).

Let

M_{δ} = ⋃{M_{α} : α < δ}.

Then M_{δ} ≺ H(θ). Proof. Let k ∈ ω, let y⃗ ∈ ^{k}M_{δ}, and let n ∈ ω. We need to show that

G(n, H(θ), y⃗) ∩ H(θ) ≠ ∅ ⇒ G(n, H(θ), y⃗) ∩ M_{δ} ≠ ∅.

But this is easy since y⃗ ∈ ^{k}M_{α} for some α < δ.

Constructibility

The Gödel closure of a set X is denoted by

cl(X) = {X ∩ G(n, y⃗) : n ∈ ω and ∃k ∈ ω y⃗ ∈ ^{k}(X)}.

The constructible sets are obtained by first defining a function

𝕃: 𝕆ℕ → 𝕍

by recursion as follows:

L(0) = ∅
L(α + 1) = cl(L(α) ∪ {L(α)})
L(δ) = ⋃{L(α) : α < δ} for a limit ordinal δ

We denote by 𝕃 the class ⋃{L(α) : α ∈ 𝕆ℕ}. Sets in 𝕃 are said to be \underline{constructible}.

Lemma. For each ordinal α, L(α) ⊆ R(α).

Proof. This is proved by induction. L(0) = ∅ = R(0) and for each α ∈ 𝕆ℕ we have, by definition,

L(α + 1) ⊆ P(L(α))

⊆ R(α + 1)

Lemma.

1. ∀X X ⊆ cl(X).

2. If X is transitive, then cl(X) is transitive.

3. For each ordinal α, L(α) is transitive.

Proof.

1. For any w ∈ X, w = G(1, s⃗), where s⃗(0) = w.

2. Now, if z ∈ cl(X) then z ⊆ X so z ⊆ cl(X).

3. This follows from (1) by induction on 𝕆ℕ.

Lemma.

1. For all ordinals α < β, L(α) ∈ L(β).

2. For all ordinals α < β, L(α) ⊆ L(β).

Proof.

1. For each α, L(α) ∈ L(α + 1) by Part (1) of the previous lemma. We then apply induction on β.

2. This follows from (1) by transitivity of L(β).

Lemma.

1. For each ordinal β, β ∉ L(β).

2. For each ordinal β, β ∈ L(β + 1).

Proof.

1. This is proved by induction on β. The case β = 0 is easy. If β = α + 1 then β ∈ L(α + 1) would imply that β ⊆ L(α) and hence

α ∈ β ⊆ L(α)

contradicting the inductive hypothesis. If β is a limit ordinal and β ∈ L(β) then β ∈ L(α) for some α ∈ β and hence α ∈ β ∈ L(α), again a contradiction.

2. We employ induction on β. The β = 0 case is given by 0 ∈ {0}. We do the sucessor and limit cases uniformly. Assume that

∀α ∈ β α ∈ L(α + 1).

Claim 1. β = L(β) ∩ 𝕆ℕ.

Proof of Claim 1. If α ∈ β, then α ∈ L(α + 1) ⊆ L(β). If α ∈ L(β), then α ∈ β because otherwise α = β or β ∈ α, which contradicts β ∉ L(β) from (1).

Claim 2. ∀x x ∈ 𝕆ℕ iff

[(∀u ∈ x ∀v ∈ u v ∈ x) ∧ (∀u ∈ x ∀v ∈ x (u ∈ v ∨ v ∈ u ∨ u = v)) ∧(∀u ∈ x ∀v ∈ x ∀w ∈ x (u ∈ v ∧ v ∈ w → u ∈ w))].

Proof of Claim 2. The statement says that x is an ordinal iff x is a transitive set and the ordering ∈ on x is transitive and satisfies trichotomy. This is true since ∈ is automatically well founded.

The importance of this claim is that this latter formula, call it Φ(x), is △_{0} and hence absolute for transitive sets.

We have:

β = L(β) ∩ 𝕆ℕ = {x ∈ L(β) : x is an ordinal}

= {x ∈ L(β) : Φ(x)}

= {x ∈ L(β) : Φ^{L(β+1)}(α)} ∈ cl(L(β)) using Theorem 44 = L(β + 1).

Lemma.

1. For each ordinal β, β = L(β) ∩ 𝕆ℕ.

2. 𝕆ℕ ⊆ 𝕃.

Proof. This is easy from the previous lemmas.

Lemma.

1. If W is a finite subset of X then W ∈ cl(X).

2. If W is a finite subset of L(β) then W ∈ L(β + 1).

Proof.

1. We apply Theorem 44 to the formula “x = w_{0} ∨ ⋯ ∨ x = w_{n}”, where W = {w_{1}, w_{2}, …, w_{n}}.

2. This follows immediately from (1).

Lemma.

1. If X is infinite then |cl(X)| = |X|.

2. α ≥ ω then |L(α)| = |α|.

Proof.

1. By Theorem 44 we can construct an injection cl(X) → ω ×⋃{^{k}X : k ∈ ω}. Hence, |X| ≤ |cl(X)| ≤ max (ℵ_{0}, |{^{k}X : k ∈ ω}|) = |X|.

2. We proceed by induction, beginning with the case α = ω. We first note that from the previous lemma, we have L(n) = R(n) for each n ∈ ω. Therefore,

|L(ω)| = | ⋃{L(n) : n ∈ ω}|
= max (ℵ_{0}, sup {|L(n)| : n ∈ ω})
= max (ℵ_{0}, sup {|R(n)| : n ∈ ω})
= ℵ_{0}.

For the successor case,

|L(β + 1)| = |L(β)| by (1)

= |β| by inductive hypothesis = |β + 1| since β is infinite .

And if δ is a limit ordinal then

|L(δ)| = | ⋃{L(β) : β ∈ δ}|

= max (|δ|, sup {|L(β)| : β ∈ δ})

= max (|δ|, sup {|(β)| : β ∈ δ}) by inductive hypothesis = |δ|.

Lemma. (∀x) [x ⊆ 𝕃 → (∃y ∈ 𝕃)(x ⊆ y)].

Proof. x ⊆ 𝕃 means that ∀u ∈ x ∃α ∈ 𝕆ℕ x ∈ L(α). By the Axiom of Replacement,

∃z z = {α : (∃u ∈ x)(α is the least ordinal such that u ∈ L(α))}.

Let β = sup z; then β ∈ 𝕆ℕ and for each u ∈ x, there is α ≤ β such that u ∈ L(α) ⊆ L(β). Since L(β) ∈ L(β + 1) ⊆ 𝕃, we can take y = L(β).

Remark. The above lemma is usually quoted as “𝕃 is almost universal”.

Lemma. 𝕃 ⊧ 𝕍 = 𝕃.

Proof. This is not the trivial statement

∀x ∈ 𝕃 x ∈ 𝕃

but rather

∀x ∈ 𝕃 (x ∈ 𝕃)^{𝕃}

which is equivalent to (∀x ∈ 𝕃)(∃α ∈ 𝕆ℕ x ∈ L(α))^{𝕃}; which is, in turn, since 𝕆ℕ ⊆ 𝕃, equivalent to (∀x ∈ 𝕃)(∃α ∈ 𝕆ℕ)(x ∈ L(α))^{𝕃}.

This latter statement is true since “x ∈ L(α)” is a △_{0} formula when written out in full in LOST, and since 𝕃 is transitive.

For each Axiom Φ of 𝒵ℱ𝒞 we have:

Theorem 50. Φ

𝕃 ⊧ Φ.

Proof. Transitivity of 𝕃 automatically gives Equality, Extensionality, Existence and Foundation. We get Infinity since ω ∈ 𝕃 and “z = ℕ” is a △_{0} formula.

For Comprehension, let Φ be any formula of LOST; we wish to prove

∀y ∈ 𝕃 ∀w_{0} ∈ 𝕃 … ∀w_{n} ∈ 𝕃 ∃z ∈ 𝕃 z = {x ∈ y : Φ^{𝕃}(x, y, w_{0}, …, w_{n})}

since 𝕃 is transitive.

Fix y, w_{0}, …, w_{n} and α ∈ 𝕆ℕ such that {y, w⃗} ⊆ L(α). By the Levy Reflection Principle, there is some β > α such that Φ is absolute between 𝕃 and L(β).

By Theorem 44, there is an n ∈ ω such that

G(n, L(β), y, w⃗) = {x ∈ L(β) : Φ^{L(β)}(x, y, w⃗)}.

and so by definition, {x ∈ L(β) : Φ^{L(β)}(x, y, w⃗)} ∈ L(β + 1). Now by absoluteness, {x ∈ L(β) : Φ^{L(β)}(x)} = {x ∈ L(β)Φ^{𝕃}(x)}. So we have

{x ∈ L(β) : Φ^{𝕃}(x, y, w⃗)} ∈ L(β + 1).

Moreover, since y ∈ L(β + 1),

{x ∈ y : Φ^{𝕃}(x, y, w⃗)} = y ∩ {x ∈ L(β + 1) : Φ^{𝕃}(x, y, w⃗)}
∈ L(β + 2)

and since L(β + 2) ⊆ 𝕃 we are done.

For the Power Set Axiom, we must prove that (∀x ∃z z = {y : y ⊆ x})^{𝕃}. That is, ∀x ∈ 𝕃 ∃z ∈ 𝕃 z = {y : y ∈ 𝕃 and y ⊆ x}. Fix x ∈ 𝕃; by the Power Set Axiom and the Axiom of Comprehension we get

∃z′ z′ = {y ∈ P(x) : y ∈ 𝕃 ∧ y ⊆ x} = {y : y ∈ 𝕃 ∧ y ⊆ x}.

By the previous lemma 𝕃 is almost universal and z′ ⊆ 𝕃 so

∃z′′ ∈ 𝕃 z′ ⊆ z′′.

So z′ = z′ ∩ z′′ = {y ∈ z′′ : y ∈ 𝕃 ∩ y ⊆ x}. By the fact that the Axiom of Comprehension holds relativised to 𝕃 we get

(∃z z = {y ∈ z′′ : y ⊆ x})^{𝕃};

i.e.,

∃z ∈ 𝕃 z = {y ∈ z′′ : y ∈ 𝕃 ∧ y ⊆ x}
= {y : y ∈ 𝕃 ∧ y ⊆ x}

The Union Axiom and the Replacement Scheme are treated similarly. To prove (the Axiom of Choice)^{𝕃}, we will show that the Axiom of Choice follows from the other axioms of 𝒵ℱ𝒞 with the additional assumption that 𝕍 = 𝕃.

It suffices to prove that for each α ∈ 𝕆ℕ there is a β ∈ 𝕆ℕ and a surjection f_{α}: b_{α} → L(α).

To do this we define f_{α} recursively. Of course f_{0} = β_{0} = ∅ = L(0). If α is a limit ordinal, then we let

β_{α} = ∑{β_{ϵ} : ϵ < α}

and f_{α}(σ) = f_{δ}(τ) where σ = ∑{β_{ϵ} : ϵ < δ} + τ and τ < β_{δ}.

If α = γ + 1 is a successor ordinal, use f_{γ} to generate a well ordering of L(γ) and use this well ordering to generate a lexicographic well ordering of ⋃{^{k}(L(γ)) : k ∈ ω} and use this to obtain an ordinal β̄_{α} and a surjection

f̄_{γ}: β̄_{γ} → ⋃{^{k}(L(γ)) : k ∈ ω}.

Now let β_{α} = β_{γ+1} = β̄_{γ} × ω and let

f_{α}: β_{α} → L(α) = {G(n, L(α), y⃗) : n ∈ ω and ∃k ∈ ω y⃗ ∈^{k} L(γ)}

be defined by f_{α}(σ) = G(n, L(γ), f̄_{γ}(τ)) where σ = β̄_{γ} × n + τ, τ < β̄_{γ}.

This completes the proof of Theorem 50 Φ and motivates calling “𝕍 = 𝕃” the \underline{Axiom of Constructibility}.

Remark. 𝕍 = 𝕃 is consistent with 𝒵ℱ𝒞 in the sense that no finite subcollection of 𝒵ℱ𝒞 can possibly prove 𝕍 ≠ 𝕃; To see this, suppose

{Ψ_{0}, …, Ψ_{n}} ⊢ 𝕍 ≠ 𝕃.

Then

Ψ_{0}^{𝕃}, …, Ψ_{n}^{𝕃}} ⊢ (𝕍 ≠ 𝕃)^{𝕃}.

by Theorem 50. This contradicts the preceding lemma.

Remark. Assuming 𝕍 = 𝕃 we actually can find a formula Ψ(x, y) which gives a well ordering of the universe.

We denote by Φ_{𝕃} the conjunction of a finite number of axioms of 𝒵ℱ𝒞 conjoined with “𝕍 = 𝕃” such that Φ_{𝕃} implies all our lemmas and theorems about ordinals and ensures that x ∈ L(α) is equivalent to some △_{0} formula (but I think we have already defined it to be △_{0}). In particular, x ∈ 𝕆ℕ will be equivalent to a △_{0} formula.

Furthermore, we explicitly want Φ_{𝕃} to imply that ∀α ∈ 𝕆ℕ ∃z z = L(α) and that there is no largest ordinal.

We shall use the abbreviation o(M) = 𝕆ℕ ∩ M.

Lemma. ∀M(M is transitive and Φ_{𝕃}^{M} → M = L(o(M))).

Proof. Let M be transitive such that M ⊧ Φ_{𝕃}. Note that o(M) ∈ 𝕆ℕ. We have M ⊧ ∀α ∈ 𝕆ℕ ∃z z = L(α). So,

∀α ∈ o(M) M ⊧ ∃z z = L(α)
⇒∀α ∈ o(M) ∃z ∈ M M ⊧ z = L(α)
⇒∀α ∈ o(M) ∃z ∈ M z = L(α)
⇒∀α ∈ o(M) L(α) ∈ M
⇒∀α ∈ o(M) L(α) ⊆ M.

Since M ⊧ Φ_{𝕃}, o(M) is a limit ordinal and hence

L(o(M)) = ⋃{L(α) : α ∈ o(M)} ⊆ M.

Now let a ∈ M. Since M ⊧ 𝕍 = 𝕃 we have

M ⊧ ∀x ∃y ∈ 𝕆ℕ x ∈ L(y)
⇒M ⊧ ∃y ∈ 𝕆ℕ a ∈ L(y)
⇒∃α ∈ o(M) M ⊧ a ∈ L(α)
⇒∃α ∈ o(M) a ∈ L(α)
⇒a ∈ L(o(M)).

Lemma. χ_{C}

If 𝕆ℕ ⊆ C, C is transitive, and Φ_{𝕃}^{C}, then C = 𝕃.

Proof. The proof is similar to that of the previous lemma.

Theorem 51. (K. Gödel)

If 𝕍 = 𝕃 then GCH holds.

Proof. We first prove the following: Claim. ∀α ∈ 𝕆ℕ P(L(α)) ⊆ L(α^{+}). Proof of Claim. This is easy for finite α, since L(n) = R(n) for each n ∈ ω.

Let’s prove the claim for infinite α ∈ 𝕆ℕ. Let X ∈ P(L(α)); we will show that X ∈ L(α^{+}).

Let A = L(α) ∪ {X}. A is transitive and |A| = |α|.

By the Levy Reflection Principle, there is a β ∈ 𝕆ℕ such that both A ⊆ L(β) and L(β) ⊧ Φ_{𝕃}, where Φ_{𝕃} is the formula introduced earlier.

Now use the Lowenheim-Skolem-Tarski Theorem to obtain an elementary submodel K ≺ L(β) such that A ⊆ K and |K| = |A| = |α| so by elementarily we have K ⊧ Φ_{𝕃}.

Now use the Mostowski Collapsing Theorem to get a transitive M such that K ≅ M. Since A is transitive, the isomorphism is the indentity on A and hence A ⊆ M. We also get M ⊧ Φ_{𝕃} and |M| = |α|.

Now we use the penultimate lemma to infer that M = L(o(M)). Since |M| = |α| we have |o(M)| = |α| so that o(M) < |α^{+}|.

Hence A ⊆ M = L(o(M)) ⊆ L(α^{+}), so that X ∈ L(α^{+}).

We now see that the GCH follows from the claim. For each cardinal κ we have κ ⊆ L(κ) so that |P(κ)| ≤ |P(L(κ))| ≤ |L(κ^{+}).

Since |L(κ^{+})| = κ^{+} we have |P (κ)| = κ^{+}.

We now turn our attention to whether 𝕍 = 𝕃 is true.

Let μ be a cardinal and let U be an ultrafilter over μ. Recalling that μ𝕍 = {f : f: μ → 𝕍}, let ∼_{U} be a binary relation on ^{μ}𝕍 defined by

f ∼_{U} g iff {α ∈ μ : f(α) = g(α)} ∈ U.

It is easy to check that ∼_{U} is an equivalence relation.

For each f ∈ ^{μ}𝕍 let ρ(f) be the least element of

{α ∈ 𝕆ℕ : rank(g) = α ∧ f ∼_{U} g}.

Let [f] = {g ∈ R(ρ(f) + 1) : g ∼_{U} f} and let ULT_{U} 𝕍 = {[f] : f ∈ ^{μ}𝕍}.

Define a relation ∈_{U} on ULT_{U} 𝕍 by

[f] ∈_{U} [g] iff {α ∈ μ : f(α) ∈ g(α)} ∈ U.

It is easy to check that ∈_{U} is well defined.

For each cardinal κ, we use the abbreviation

[X]^{<κ} = {Y ⊆ X : |Y | < κ}.

Given an uncountable cardinal κ, an ultrafilter U is said to be \underline{κ−complete} if ∀X ∈ [U]^{<κ} ⋂ X ∈ U.

An uncountable cardinal κ is said to be \underline{measurable} whenever there exists a κ−complete free ultrafilter over κ.

Lemma. If U is a countably complete ultrafilter (in particular if U is a μ−complete ultrafilter) then ∈_{U} is set-like, extensional and well founded.

Proof. To see that ∈_{U} is set-like, just note that

{[g] : [g] ∈_{U} [f]} ⊆ R(ρ(f) + 2).

For extentionality, suppose [f] ≠ [g]; i.e., {α ∈ μ : f(α) = g(α)} ∉ U. Then either {α ∈ μ : ¬f(α) ⊆ g(α)} ∈ U or {α ∈ μ : ¬g(α) ⊆ f(α)} ∈ U. This leads to two similar cases; we address the first.

Pick any h ∈ ^{μ}𝕍 such that h(α) ∈ f(α) \ g(α) whenever ¬f(α) ⊆ g(α). Then [h] ∈_{U} [f] and [h] ∈_{U} [g].

To see that ∈_{U} is well founded, suppose ∃{f_{n}}_{n∈ω} such that

∀n ∈ ω [f_{n+1}] ∈_{U} [f_{n}].

Let

A = ⋂{{α ∈ μ : f_{n+1}(α) ∈ f_{n}(α)} : n ∈ ω} ∈ U.

A ∈ U by the countable completeness of U, so that A ≠ ∅. Pick any β ∈ A. Then F_{n+1}(β) ∈ f_{n}(β) for each n ∈ ω, which is a contradiction.

We now create a Mostowski collapse of ULT_{U} 𝕍

h_{U}: ULT_{U} 𝕍 → M_{U}

given by the recursion

h_{U}([f]) = {h_{U}([g]) : [g] ∈_{U} [f]}

As per the Mostowski Theorem, h is an isomorphism and M_{U} is transitive.

The natural embedding i_{U}: 𝕍 → ULT_{U} 𝕍 is given by i_{U}(x) = [f_{x}] where f_{x}: μ → 𝕍 such that f_{x}(α) = x for all α ∈ μ.

This natural embedding i_{U} combines with the unique isomorphism h_{U} to give

j_{U}: 𝕍 → M_{U}

given by j_{U}(x) = h_{U}(i_{U}(x)).

j_{U} is called the \underline{elementary embedding} generated by U, since for all formulas Φ(v_{0}, …, v_{n}) of LOST we have:

Lemma. ∀v_{0} … ∀v_{n} Φ(v_{0}, …, v_{n}) ↔ Φ^{M_{U}} (j_{U}(v_{0}), …, j_{U}(v_{n})).

Proof. This follows from two claims, each proved by induction on the complexity of Φ.

Claim 1. ∀v_{0} … ∀v_{n} Φ(v_{0}, …, v_{n}) ↔ Φ̄(i_{U}(v_{0}), …, i_{U}(v_{n})). Claim 2. ∀v_{0} … ∀v_{n} Φ̄(i_{U}(v_{0}), …, i_{U}(v_{n})) ↔ Φ^{M_{U}} (j_{U}(v_{0}), …, j_{U}(v_{n})), where Φ̄ is Φ with ∈ replaced by ∈_{U} and all quantifiers restricted to ULT_{U} 𝕍.

We leave the proofs to the reader.

Theorem 52. Every measurable cardinal is inaccessible.

Proof. We first prove that κ is regular. If cf(κ) = λ < κ, then κ is the union of λ sets each smaller than κ. This contradicts the existence of a κ−complete free ultrafilter over κ.

We now prove that if λ < κ, then |P(λ)| < κ. Suppose not; then there is X ∈ [P(λ)]^{κ} and a κ−complete free ultrafilter U over X. Now, for each α ∈ λ let A_{α} = {x ∈ X : α ∈ x} and B_{α} = {x ∈ X : α ∉ x}. Let I = {α ∈ λ : A_{α} ∈ U} and J = {α ∈ λ : B_{α} ∈ U}. Since U is an ultrafilter, I ∪ J = λ. Since U is κ−complete and λ < κ we have

⋂{A_{α} : α ∈ I} ∩ ⋂{B_{α} : α ∈ J} ∈ U.

But this intersection is equal to X ∪{I}, which is either empty or a singleton, contradicting that U is a free filter.

Lemma. Let U be a μ−complete ultrafilter over an measurable cardinal μ. Let M = M_{U}, h = h_{U}, i = i_{U} and j = j_{U} as above. Then for each β ∈ 𝕆ℕ we have j(β) ∈ 𝕆ℕ and j(β) ≥ β. Furthermore, if β < μ then j(β) = β and j(μ) > μ.

Proof. For each β ∈ 𝕆ℕ we get, by the elementary embedding property of j, that M ⊧ j(β) ∈ 𝕆ℕ; since M is transitive, j(β) ∈ 𝕆ℕ.

Let β be the least ordinal such that j(β) ∈ β. Then M ⊧ j(j(β)) ∈ j(β) by elementarity, and j(j(β)) ∈ j(β) by transitivity of M. This contradicts the minimality of β.

Now let’s prove that j(β) = β for all β < μ by induction on β. Suppose that j(γ) = γ for all γ < β < μ. We have

j(β) = h(i(β))

= {h([g]) : [g] ∈_{U} i(β)} = {h([g]) : [g] ∈_{U} [f_{β}]} where f_{β}(α) = β for all α ∈ μ = {h([g]) : {α ∈ μ : g(α) ∈ f_{β}(α)} ∈ U} = {h([g]) : {α ∈ μ : g(α) ∈ β} ∈ U} = {h([g]) : ∃γ ∈ β {α ∈ μ : g(α) = γ} ∈ U} by μ − completeness of U = {h([g]) : ∃γ ∈ β [g] = [f_{γ}]} where f_{γ}(α) = γ for all α ∈ μ = {h([f_{γ}]) : γ ∈ β} = {h(i(γ)) : γ ∈ β} = {j(γ) : γ ∈ β} = {γ : γ ∈ β} by inductive hypothesis

Hence j(β) = β.

We now show that j(μ) > μ. Let g: μ → 𝕆ℕ such that g(α) = α for each α. We will show that β ∈ h([g]) for each β ∈ μ and that h([g]) ∈ j(μ).

Let β ∈ μ.

{α ∈ μ : f_{β}(α) ∈ g(α)} = {α ∈ μ : β ∈ α}
= μ \ (β + 1)
∈ U

Hence [f_{β}] ∈_{U} [g] and so h([f_{β}]) ∈ h([g]). But since β ∈ μ,

β = j(β)
= h(i(β))
= h([f(β)])

Hence β ∈ h([g]).

Now, {α ∈ μ : g(α) ∈ f_{μ}(α)} = {α ∈ μ : α ∈ μ} = μ ∈ U. Hence [g] ∈_{U} [f_{μ}] and so h[g] ∈ h([f_{μ}]) = h(i(μ)) = j(μ).

Theorem 53. (D. Scott)

If 𝕍 = 𝕃 then there are no measurable cardinals.

Proof. Assume that 𝕍 = 𝕃 and that μ is the least measurable cardinal; we derive a contradiction. Let U be a μ−complete ultrafilter over μ and consider j = j_{U} and M = M_{U} as above.

Since 𝕍 = 𝕃 we have Φ_{𝕃} and by elementarity of j we have Φ_{𝕃}^{M}. Note that Φ_{𝕃} is a \underline{sentence}; i.e., it has no free variables.

Since M is transitive, 𝕆ℕ ⊆ M by the previous lemma. So, by an earlier lemma M = 𝕃. So we have

𝕃 = 𝕍 ⊧ (μ is the least measurable cardinal)

and 𝕃 = M ⊧ (j(μ) is the least measurable cardinal).

Thus 𝕃 ⊧ j(μ) = μ; i.e., j(μ) = μ, contradicting the previous theorem.

Remark. We have demonstrated the existence of an elementary embedding j: 𝕍 → M. K. Kunen has shown that there is no elementary j: 𝕍 → 𝕍.

Large cardinal axioms are often formulated as embedding axioms. For example, κ is said to be \underline{supercompact} whenever

∀λ ∃j [j: 𝕍 → M and j(κ) > λ and j|_{R(λ)} = id|_{R(λ)} and ^{λ}M ⊆ M].

116 CHAPTER 12. CONSTRUCTIBILITY

Chapter 13 Appendices

.1 The Axioms of ZFC

Zermelo-Frankel (with Choice) Set Theory, abbreviated to 𝒵ℱ𝒞, is constituted by the following axioms.

1. Axiom of Equality ∀x ∀y [x = y → ∀z (x ∈ z ↔ y ∈ z)]

2. Axiom of Extensionality ∀x ∀y [x = y ↔ ∀u (u ∈ x ↔ u ∈ y)]

3. Axiom of Existence

∃z z = ∅

4. Axiom of Pairing

∀x ∀y ∃z z = {x, y}

5. Union Axiom ∀x [x ≠ ∅ → ∃z z = {w : (∃y ∈ x)(w ∈ y)] 118 CHAPTER 13. APPENDICES

6. Intersection Axiom ∀x [x ≠ ∅ → ∃z z = {w : (∀y ∈ x)(w ∈ y)]

7. Axiom of Foundation ∀x [x ≠ ∅ → (∃y ∈ x)(x ∩ y = ∅)]

8. Replacement Axiom Scheme

For each formula Φ(x, u, v, w_{1}, …, w_{n}) of the language of set theory,

∀w_{1} … ∀w_{n} ∀x [∀u ∈ x ∃!v Φ → ∃z z = {v : ∃u ∈ x Φ}]

9. Axiom of Choice ∀X [(∀x ∈ X ∀y ∈ X (x = y ↔ x∩y ≠ ∅)) → ∃z (∀x ∈ X ∃!y y ∈ x∩z)]

10. Power Set Axiom

∀x ∃z z = {y : y ⊆ x}

11. Axiom of Infinity

ℕ ≠ 𝕆ℕ

.2 Tentative Axioms

Here is a summary of potential axioms which we have discussed but which lie outside of 𝒵ℱ𝒞.

1. Axiom of Inaccessibles ∃κ κ > ω and κ is an inaccessible cardinal

2. Continuum Hypothesis

|P(ω)| = ω_{1}

3. Generalised Continuum Hypothesis

∀κ [κ is a cardinal → |P(κ)| = κ^{+}

4. Suslin Hypothesis Suppose that R is a complete dense linear order without endpoints in which every collection of disjoint intervals is countable. Then R ≅ ℝ.

5. Axiom of Constructibility

𝕍 = 𝕃