• Nu S-Au Găsit Rezultate

AN INTRODUCTION TO SET THEORY

N/A
N/A
Protected

Academic year: 2022

Share "AN INTRODUCTION TO SET THEORY"

Copied!
119
0
0

Text complet

(1)

AN INTRODUCTION TO SET THEORY

Professor William A. R. Weiss

October 2, 2008

(2)

2

(3)

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

3

(4)

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

(5)

CONTENTS 5 Preface

These notes for a graduate course in set theory are on their way to be- coming a book. They originated as handwritten notes in a course at the University of Toronto given by Prof. William Weiss. Cynthia Church pro- duced the first electronic copy in December 2002. James Talmage Adams produced the copy here in February 2005. Chapters 1 to 9 are close to fi- nal 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)

6 CONTENTS

(7)

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 mathemati- cians, 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 intoX.

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 dif- 7

(8)

8 CHAPTER 0. INTRODUCTION ficult 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 never- theless 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 bein the set. But it can’t be in the set. That’s

(9)

9 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)

10 CHAPTER 0. INTRODUCTION

(11)

Chapter 1 LOST

We construct a language suitable for describing sets.

The symbols:

variables v0, v1, v2, . . . equality symbol =

membership symbol ∈

logical connectives ∧,∨,¬,→,↔ quantifiers ∀,∃

parentheses (,)

The atomic formulas are strings of symbols of the form:

(vi ∈vj) or (vi =vj)

The collection of 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.

11

(12)

12 CHAPTER 1. LOST 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 vi is a variable, then (∀vi)Φ is also a formula.

8. If Φ is a formula and vi is a variable, then (∃vi)Φ 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 completeness theorem (due to K. G¨odel) 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 ((Φ →Ψ)∧(Ψ →Φ));

(∃vi)Φ is equivalent to (¬(∀vi)(¬Φ)); and, (Φ↔Ψ) is equivalent to (Ψ↔Φ).

The complete collection of subformulas of a formula Φ is defined as fol- lows:

1. Φ is a subformula of Φ;

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

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

(13)

13 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 (∀vi)Ψ is a subformula of Φ andviis a variable, then Ψ is a subformula of Φ; and,

8. If (∃vi)Ψ is a subformula of Φ andviis 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 vi occurs bound in a formula Φ means one of the following two conditions holds:

1. For some subformula Ψ of Φ, (∀vi)Ψ is a subformula of Φ; or, 2. For some subformula Ψ of Φ, (∃vi)Ψ is a subformula of Φ.

The result, Φ, of substituting the variable vj for each bound occurrence of the variable vi 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 (∀vk)Θ for some formula Θ then Ψ is just (∀vk ifk 6=i, but if k = i then Ψ is (∀vj)Γ where Γ is the result of substituting vj for each occurrence of vi in Θ; and,

(14)

14 CHAPTER 1. LOST 8. If Ψ is (∃vk)Θ for some formula Θ then Ψ is just (∃vk ifk 6=i, but if k = i then Ψ is (∃vj)Γ where Γ is the result of substituting vj for each occurrence ofvi in Θ.

That a variable vi occurs free in a formula Φ means that at least one of the following is true:

1. Φ is an atomic formula and vi occurs in Φ;

2. Φ is (¬Ψ), Ψ is a formula andvi occurs free in Ψ;

3. (Θ∧Ψ), Θ and Ψ are formulas and vi occurs free in Θ or occurs free in Ψ;

4. Φ is (Θ∨Ψ), Θ and Ψ are formulas and vi occurs free in Θ or occurs free in Ψ;

5. Φ is (Θ→Ψ), Θ and Ψ are formulas and vi occurs free in Θ or occurs free in Ψ;

6. Φ is (Θ↔Ψ), Θ and Ψ are formulas and vi occurs free in Θ or occurs free in Ψ;

7. Φ is (∀vj)Ψ and Ψ is a formula andvi occurs free in Ψ and i6=j; or, 8. Φ is (∃vj)Ψ and Ψ is a formula andvi occurs free in Ψ and i6=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 substitution of a variable vj for each free occurrence of the variablevi in the formula Φ. This procedure is as follows.

1. Substitute a new variable vl for all bound occurrences of vi in Φ.

2. Substitute another new variable vk for all bound occurrences of vj in the result of (1).

(15)

15 3. Directly substitute vj for each occurrence of vi in the result of (2).

Example. Let us substitute v2 for all free occurrences of v1 in the formula ((∀v1)((v1 =v2)→(v1 ∈v0))∧(∃v2)(v2 ∈v1))

The steps are as follows.

1. ((∀v1)((v1 =v2)→(v1 ∈v0))∧(∃v2)(v2 ∈v1)) 2. ((∀v3)((v3 =v2)→(v3 ∈v0))∧(∃v2)(v2 ∈v1)) 3. ((∀v3)((v3 =v2)→(v3 ∈v0))∧(∃v4)(v4 ∈v1)) 4. ((∀v3)((v3 =v2)→(v3 ∈v0))∧(∃v4)(v4 ∈v2))

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 (∃v2)(v2 ∈ v1) to (∃v4)(v4 ∈ v1). We can agree that each of these means the same thing, namely, “v1 is non-empty”. However, when v2 is directly substituted into each we get something different: (∃v2)(v2 ∈v2) and (∃v4)(v4 ∈v2). The latter says that “v2 is non-empty” and this is, of course what we would hope would be the result of substituting v2 for v1 in “v1 is non-empty”. But the former statement, (∃v2)(v2 ∈v2), seems quite different, making the strange assertion that “v2 is an element of itself”, and this is not what we have in mind. What caused this problem? An occurrence of the variable v2 became bound as a result of being substituted forv1. We will not allow this to happen. When we substitute v2 for the free v1 we must ensure that this freedom is preserved for v2.

For a formula Φ and variables vi and vj, let Φ(vi|vj) denote the formula which results from substituting vj for each free occurance of vi. In order to make Φ(vi|vj) 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 Φ(v1|v2) is the formula on the fourth line.

(16)

16 CHAPTER 1. LOST 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 (∃!vj)Φ the formula

((∃vj)Φ∧(∀vj)(∀vl)((Φ∧Φ(vj|vl))→(vj =vl)))

where vl is the first available variable which does not occur in Φ. The ex- pression (∃!vj) 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 class is just a string of symbols of the form {vi : Φ} where vi is a variable and Φ is a formula. Two important and well-known examples are:

{v0 : (¬(v0 =v0))}

which is called the empty set and is usually denoted by∅, and {v0 : (v0 =v0)}

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

A 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 vj,vk and vl be variables. We write:

vk ∈ {vj : Ψ} instead of Ψ(vj|vk)

vk={vj : Ψ} instead of (∀vl)((vl ∈vk)↔Ψ(vj|vl)) {vj : Ψ}=vk instead of (∀vl)(Ψ(vj|vl)↔(vl∈vk)) {vj : Ψ}={vk : Θ} instead of (∀vl)(Ψ(vj|vl)↔Θ(vk|vl))

{vj : Ψ} ∈vk instead of (∃vl)((vl ∈vk)∧(∀vj)((vj ∈vl)↔Ψ)) {vj : Ψ} ∈ {vk : Θ} instead of (∃vl)(Θ(vk|vl)∧(∀vj)((vj ∈vl)↔Ψ))

(17)

17 whenever vl is neither vj nor vk and occurs in neither Ψ nor Θ.

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

1. Substitute the first available new variable for all bound occurrences of vi 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 {vj : Ψ} forvi into each atomic subformula in turn, using the table above.

For example, the atomic subformula (vi ∈vk) is replaced by the new subfor- mula

(∃vl)((vl ∈vk)∧(∀vj)((vj ∈vl)↔Ψ))

where vl is the first available new variable. Likewise, the atomic subformula (vi =vi) is replaced by the new subformula

(∀vl)(Ψ(vj|vl)↔Ψ(vj|vl))

where vl is the first available new variable (although it is not important to change from vj tovl in this particular instance).

(18)

18 CHAPTER 1. LOST

(19)

Chapter 2 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 {vj : Φ} 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 whatisimportant is that whatever formula we write downcan 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 justv0, v1, v2, . . .. 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 expres- sions for the logical connectives and quantifiers.

19

(20)

20 CHAPTER 2. FOUND 4. We will use the notation Φ(x, y, w1, . . . , wk) to indicate that all free variables of Φ lie among x, y, w1, . . . , wk. When the context is clear we use the notation Φ(x, t, w1, . . . , wk) for the result of substituting the termt for each free occurrence of the variabley 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 termsr,s, andt, we make the following abbreviations of formulas.

(∀x∈t)Φ for (∀x)(x∈t →Φ) (∃x∈t)Φ for (∃x)(x∈t∧Φ)

s /∈t for ¬(s∈t) s6=t for ¬(s=t)

s⊆t for (∀x)(x∈s →x∈t)

Whenever we have a finite number of terms t1, t2, . . . , tn the notation {t1, t2, . . . , tn} is used as an abbreviation for the class:

{x:x=t1∨x=t2∨ · · · ∨x=tn}.

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 s4t for (s\t)∪(t\s) Ordered Pair hs, ti for {{s},{s, t}}

Cartesian Product s×t for {p:∃x ∃y (x∈s∧y∈t∧p=hx, yi)}

Domain dom(f) for {x:∃y hx, yi ∈f}

Range rng(f) for {y:∃x hx, yi ∈f}

(21)

21 Image fA for {y:∃x∈A hx, yi ∈f}

Inverse Image fB for {x:∃y ∈B hx, yi ∈f}

Restriction f|A for {p:p∈f∧ ∃x∈A ∃y p=hx, yi}

Inverse f−1 for {p:∃x ∃y hx, yi ∈f ∧ hy, xi=p}

These latter abbreviations are most often used when f is a function. We write

f is a function for

∀p∈f ∃x ∃y p=hx, yi ∧ (∀x)(∃y hx, yi ∈f → ∃!y hx, yi ∈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 hx, yi ∈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}=V

(22)

22 CHAPTER 2. FOUND and so Russell’s paradox leads to:

¬∃z z =V.

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 =V” 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 = V” 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 theZFCAxiom System. We will begin to study it in the next chapter.

(23)

Chapter 3

The Axioms of Set Theory

We will explore the ZFC 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¨odel. 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 ZFC 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.

23

(24)

24 CHAPTER 3. THE AXIOMS OF SET THEORY 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 =hx, yi.

5. ∀u ∀v ∀x ∀y [hu, vi=hx, yi ↔(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 how- ever, 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 [x6=∅ → ∃z z ={w: (∃y∈x)(w∈y)}]

The class {w : (∃y ∈ x)(w ∈ y)} is abbreviated as S

x and called the “big union”.

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

The class {w : (∀y ∈ x)(w ∈ y)} is abbreviated as T

x and called the “big intersection”.

The Axiom of Foundation ∀x[x6=∅ → (∃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 6= ∅). For anyz1 ∈xwe would be able to getz2 ∈z1∩x.

Since z2 ∈ x we would be able to get z3 ∈ z2 ∩x. The process continues forever:

· · · ∈z4 ∈z3 ∈z2 ∈z1 ∈x

(25)

25 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.

Letf(x) denote the classS

{y:hx, yi ∈f}.

Exercise 3. Suppose f is a function and x∈dom(f). Prove that hx, yi ∈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 uis 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 uis 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 xand 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 in- finitely many—one axiom for each formula of the language of set theory.

Such a system is called an axiom scheme.

(26)

26 CHAPTER 3. THE AXIOMS OF SET THEORY The Replacement Axiom Scheme

For each formula Φ(x, u, v, w1, . . . , wn) of the language of set theory, we have the axiom:

∀w1. . .∀wn ∀x [∀u∈x ∃!v Φ→ ∃z z={v :∃u∈x Φ}]

Note that we have allowed Φ to have w1, . . . , wn 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 allt ∈y we get

∀u∈x ∃!v v =hu, ti.

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

∃q q ={v :∃u∈x v =hu, ti}.

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

We again use Replacement, this time with the formula Φ(y, t, q, x) as

“q ={v :∃u∈x v =hu, ti}”; here xis a parameter. We obtain:

∃r r ={q:∃t∈y q ={v :∃u∈x v =hu, ti}}

By the Union Axiom∃z z =S

r and so we have:

z ={p:∃q [q∈r∧p∈q]}

={p:∃q [(∃t∈y) q={v :∃u∈x v =hu, ti} ∧p∈q]}

={p: (∃t∈y)(∃q)[q={v :∃u∈x v =hu, ti} ∧p∈q]}

={p: (∃t∈y)p∈ {v :∃u∈x v=hu, ti}}

={p: (∃t∈y)(∃u∈x)p=hu, ti}

=x×y

(27)

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

It is natural to believe that for any setx, the collection of those elements y ∈xwhich 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, w1, . . . , wn) of the language of set theory, we have the statement:

∀w1. . .∀wn ∀x∃z z ={y:y∈x∧Φ(x, y, w1, . . . , wn)}

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, w1, . . . , wn) of the language of set theory we have:

Theorem 4. Φ

∀w1. . .∀wn ∀x ∃z z ={u:u∈x∧Φ}.

Proof. Apply Replacement with the formula Ψ(x, u, v, w1, . . . , wn) given by:

(Φ(x, u, w1, . . . , wn)→v ={u})∧(¬Φ(x, u, w1, . . . , wn)→v =∅) to obtain:

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

(28)

28 CHAPTER 3. THE AXIOMS OF SET THEORY Note that{{u}: Φ(x, u, w1, . . . , wn)} ⊆yand the only other possible element of y is∅. Now let z =S

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∩y6=∅))→ ∃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 setszwhich satisfy the axiom and we are given no formula which would single out any one particularz.

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 anX, 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∩(S

Y). Thenf: X →S

X and each f(x)∈x.

(29)

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

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

We denote{y:y⊆x}byP(x), called the 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 ZFC Axiom System with one exception to come later—higher analogues of the Axiom of Existence.

(30)

30 CHAPTER 3. THE AXIOMS OF SET THEORY

(31)

Chapter 4

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:

N for {n:n is a natural number}

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

31

(32)

32 CHAPTER 4. THE NATURAL NUMBERS We now begin to develop the basic properties of the natural numbers by introducing an important concept. We say that a term t is transitive whenever we have (∀x∈t)(x⊆t).

Theorem 6.

1. Each natural number is transitive.

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

Proof. Suppose that (1) were false; i.e., somen∈Nis not transitive, so that:

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

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; supposen ∈N with {m :m ∈n and m /∈N} 6=∅.

By Comprehension∃x x={m ∈n:m /∈N} 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 ∈ N. But then y = succ(l) ∈ N, contradicting that y∈x.

Theorem 7. (Trichotomy of Natural Numbers)

Let m, n∈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.

(33)

33 Lemma. Let m, n∈N.

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

2. If m /∈n, thenn ⊆m.

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

{x∈N: (∃y∈N)(y⊆x and y6=x and y /∈x)}.

It will suffice to prove thatS =∅. We use an indirect proof—pick some n1 ∈S. Ifn1∩S 6=∅, Foundation gives usn2 ∈n1∩S withn2∩(n1∩S) =∅.

By transitivity, n2 ⊆ n1 so that n2 ∩S = ∅. Thus, we always have some n ∈S such that n∩S=∅.

For just such ann, choose m∈Nwith m⊆n,m6=n, andm /∈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 6= m since l ∈ n and m /∈ n.

Therefore we conclude that m\l 6=∅.

Using Foundation, pickk ∈ 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 ∈N 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 Njust 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.

(34)

34 CHAPTER 4. THE NATURAL NUMBERS The next theorem scheme justifies ordinary mathematical induction. For brevity let us writew~ for w1, . . . , wn.

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

Theorem 8. Φ For all w, if~

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

then

∀n∈N Φ(n, ~w).

Proof. We will assume that the theorem is false and derive a contradiction.

We havew~ and a fixed l ∈N such that¬Φ(l, ~w).

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

The statement ∀m ∈ n Φ(m, ~w) in Theorem 8 Φ is usually called the inductive hypothesis.

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

∀w~ [(∀n∈N)((∀m > n Φ(m, ~w))→Φ(n, ~w))→ ∀n ∈N Φ(n, ~w)].

Recursion on N is a way of defining new terms (in particular, functions with domainN). Roughly speaking, values of a functionF at larger numbers are defined in terms of the values ofF 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 numbern. We have set out a short recursive procedure which gives a way to calculateF(n) for any n ∈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?

(35)

35 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 ex- ample. There is an implicit formula for the calculation of y = F(x) which is

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

However the formula involvesF, 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 numbernless thanx, notF(x) itself. In fact, you might say that the formula doesn’t really involve F at all; it just involvesF|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 ={h0,3i}, f ={h0,3i,h1,4i} or

f ={h0,3i,h1,4i,h2,5i},

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

{hx, yi: (∃n ∈N)(∃f)[f: n→V∧f(x) = y∧ ∀m∈n Φ(m, f|m, f(m))]}.

But in order to justify this we will need to notice that (∀x∈N)(∀f)[(f: x→V)→ ∃!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(Φ,N, ~w) the class

{hx, yi: (∃n∈N)(∃f)[f: n→V∧f(x) = y∧ ∀m ∈n Φ(m, f|m, f(m), ~w)]}.

(36)

36 CHAPTER 4. THE NATURAL NUMBERS We will show, under the appropriate hypothesis, that REC(Φ,N, ~w) is the unique function onNwhich 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∈N)(∀f)[(f: x→V)→ ∃!y Φ(x, f, y, ~w)].

Then, letting F denote REC(Φ,N, ~w), we have:

1. F: N→V;

2. ∀m∈N Φ(m, F|m, F(m), ~w);

and, furthermore, for anyn∈Nand any functionHwithn ∈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∈N)(∀y1)(∀y2)[(hx, y1i ∈F ∧ hx, y2i ∈F →y1 =y2]

Proof of Claim. By definition of F we have, for i = 1,2, functions fi with domainsni ∈N such that fi(x) = yi and

(∀m∈ni) Φ(m, fi|m, fi(m), ~w).

It suffices to prove that

(∀m∈N)(m ∈x∪ {x} →f1(m) = f2(m)),

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

(∀j ∈m)(j ∈x∪ {x} →f1(j) =f2(j))

(37)

37 with intent to show that

m ∈x∪ {x} →f1(m) = f2(m).

To do this suppose m∈ x∪ {x}. Since x ∈n1 ∩n2 we have m ∈n1∩n2 so that we have both

Φ(m, f1|m, f1(m), ~w) and Φ(m, f2|m, f2(m), ~w).

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

In order to verify (1), it suffices to show that (∀x∈N)(∃y) [hx, yi ∈F] by induction. To this end, we assume that

(∀j ∈x)(∃y) [hj, yi ∈F]

with intent to show that ∃y hx, yi ∈F. For each j ∈x there is nj ∈ N and fj:nj →V such that

(∀m ∈nj) Φ(m, fj|m, fj(m), ~w).

If x ∈ nj for some j, then hx, fj(x)i ∈ F and we are done; so assume that nj ≤x for allj. Let g =S

{fj :j ∈x}. By the claim, thefj’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 uniquey such that Φ(x, g, y, ~w). Define f to be the function f =g∪ {hx, yi}. It is straightfor- ward to verify that f witnesses thathx, yi ∈F.

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

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

(38)

38 CHAPTER 4. THE NATURAL NUMBERS 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 toH|n=F|n we get H(n) =F(n).

By applying this theorem to our specific example we see thatREC(Φ,N, ~w) does indeed give us a function F. Since F is defined by recursion on N, we use induction on N to verify the properties of F. For example, it is easy to use induction to check that F(n)∈N for all n∈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 N by the formulas

a+ 0 =a

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

for eacha ∈N. Here a is a parameter which is allowed by the inclusion ofw~ in our analysis. The same trick can be used for multiplicaton:

a·0 = 0

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

(39)

39 for each a ∈ N, 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:

a0 = 1 asucc(b) =ab·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 N. You may like to see for yourself some of what this entails by proving that multiplication is commutative.

A setX is said to be finite provided that there is a natural numbern and a bijection f:n →X. In this case n is said to be the size ofX. Otherwise, X is said to be infinite.

Exercise 6. Use induction to prove the ”pigeon-hole principle”: for n ∈ N there is no injection f: (n+ 1)→n. Conclude that a setX 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∈N that ifa∈Nand b∈N and max (a, b) = n, then a = b. If n = 0 then a = 0 = b. Assume the inductive hypothesis for n and let a∈N and b∈N 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)

40 CHAPTER 4. THE NATURAL NUMBERS

(41)

Chapter 5

The Ordinal Numbers

The natural number system can be extended to the system of ordinal num- bers.

An 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 ON.

From Theorem 6 we see immediately that N⊆ON. Theorem 10.

1. ON is transitive.

2. ¬(∃z)(z =ON).

Proof.

1. Let α ∈ ON; we must prove that α ⊆ ON. Let x ∈ α; we must prove that

41

(42)

42 CHAPTER 5. THE ORDINAL NUMBERS (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∈α; hencey is transitive.

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

Theorem 11. (Trichotomy of Ordinals)

(∀α∈ON)(∀β ∈ON)(α∈β∨β ∈α∨α =β).

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

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

Since N ⊆ ON, it is natural to wonder whether N = ON. In fact, we know that “N= ON” 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 “N=ON” to our axiom system, or we can add “N6=ON”.

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

The Axiom of Infinity N6=ON

(43)

43 As a consequence, there is a set of all natural numbers; in fact, N∈ON. Theorem 12. (∃z)(z ∈ON∧z =N).

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

The lower case Greek letter ω is reserved for the set N considered as an ordinal; i.e., ω =N. 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. ∀α ∈ON ∃β ∈ON β =succ(α).

2. ∀S [S ⊆ON→ ∃β ∈ON β =S S].

Exercise 7. Prove this lemma.

ForS ⊆ON we write supS for the least element of {β ∈ON: (∀α∈S)(α ≤β)}

if such an element exists.

Lemma. ∀S [S ⊆ON→S

S = supS]

Exercise 8. Prove this lemma.

An ordinalαis called a successor ordinal whenever∃β ∈ONα =succ(β).

If α= sup α, then α is called a limit ordinal.

(44)

44 CHAPTER 5. THE ORDINAL NUMBERS 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 transfinite induction. In order to justify transfinite induction we need a the- orem scheme.

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

Theorem 13. Φ For all w, if~

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

then

∀n∈ON Φ(n, ~w).

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

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

{hx, yi: (∃n ∈ON)(∃f)[f :n→V∧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∈ON)(∀f)[(f :x→V)→ ∃!y Φ(x, f, y, ~w)].

Then, letting F denote REC(Φ,ON, ~w), we have:

(45)

45 1. F :ON→V;

2. ∀x∈ON Φ(x, F|x, F(x), ~w);

and, furthermore, for any n ∈ ON 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 “N” with “ON” in the proof of Theorem Scheme 9.

When applying transfinite recursion on ON we often have three sepa- rate cases to specify, rather than just two as with recursion on N. This is illustrated by the recursive definitions of the arithmetic operations on 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 fromN to all of ON. The following theorem shows that these operations behave somewhat similarly on Nand ON.

(46)

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. α+ supS = sup {α+η:η∈S};

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

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

6. 0·α = 0;

7. 1·α =α;

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

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

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

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

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

13. 1α = 1;

14. If 1< α and β < δ then αβ < αδ; 15. αsupS = sup {αη :η∈S};

16. α(β+δ)β ·αδ; 17. (αβ)δβ·δ; and, 18. If α < β then αδ ≤βδ.

Exercise 10. Build your transfinite induction skills by proving two parts of this theorem.

(47)

47 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 +ω6=ω+ 1 3. 1·ω = 2·ω 4. 2·ω 6=ω·2 5. 2ω = 4ω

6. (2·2)ω 6= 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 epsilon numbers (The smallest such ordinal α=ωα is called 0.)

Lemma. ∀α∈ON ∀β ∈α ∃!γ ∈ON α=β+γ.

Exercise 13. Prove this lemma.

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

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

(48)

48 CHAPTER 5. THE ORDINAL NUMBERS Proof. Let’s use an indirect proof. Supposex⊆ω is infinite andf: x→ON such that if n < m then f(n) > f(m). Let X = {f(n) : n ∈ x}. By Foundation there isy∈X such that y∩X =∅; i.e., there isn ∈xsuch that f(n)∩X =∅. However, if m∈ x and m > nthen f(m) ∈f(n), which is a contradiction.

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

n

X

i=0

s(i) is defined by recursion as follows.

0

X

i=0

s(i) = s(0); and,

m+1

X

i=0

s(i) =

m

X

i=0

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 m0, . . . , mn of positive natural numbers and β0, . . . , βn of ordinals which sat- isfy β0 > β1 >· · ·> βn such that

α=ωβ0m0β1m1+· · ·+ωβnmn. Proof. Using the penultimate lemma, let

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

and then let

m0 = max {m ∈ω:ωβ0m≤α}

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

(49)

49 By the previous lemma, there is someα0 ∈ONsuch that

α =ωβ0m00

where the maximality of m0 ensures that α0 < ωβ0. Now let β1 = max {β :ωβ ≤α0}

so that β1 < β0. Proceed to get

m1 = max {m∈ω:ωβ1m≤α0}

and α1 < ωβ1 such that α0 = ωβ1m11. 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 α∈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 m0, . . . , mk < ω, and α0, . . . , αk< β, then

m0·ωα0 +· · ·+mk·ωα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 The- ory. Pick a number—say x = 54. We have 54 = 25+ 24+ 22+ 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, {xn}.

It begins with n= 2 and is constructed as follows.

x2 = 54 = 2(22+1)+ 222 + 22+ 2.

(50)

50 CHAPTER 5. THE ORDINAL NUMBERS Subtract 1.

x2−1 = 2(22+1)+ 222 + 22+ 1.

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

x3 = 3(33+1)+ 333 + 33+ 1.

Subtract 1.

x3−1 = 3(33+1)+ 333 + 33. Change all 3’s to 4’s, leaving any 1’s or 2’s alone.

x4 = 4(44+1)+ 444 + 44. Subtract 1.

x4 −1 = 4(44+1)+ 444 + 3·43+ 3·42+ 3·4 + 3.

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

x5 = 5(55+1)+ 555 + 3·53+ 3·52+ 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

n→∞lim xn. What is your guess? The answer is surprising.

Theorem 18. (Goodstein)

For any initial choice of x there is some n such that xn= 0.

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

g2ω+1)ω)ω+ω, g3ω+1)ω)ω+ 1, g4ω+1)ω)ω,

g5ω+1)ω)+ 3·ω3+ 3·ω2+ 3·ω+ 3, g6ω+1)ω)+ 3·ω3+ 3·ω2+ 3·ω+ 2,

(51)

51 etc. The previous lemma can now be used to show that {gn} 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 forx= 4; however, finishing our examplex= 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)

52 CHAPTER 5. THE ORDINAL NUMBERS

(53)

Chapter 6

Relations and Orderings

In the following definitions, R and C are terms.

1. We say R is a relation on C whenever R ⊆C×C.

2. We say a relation R is irreflexive on C whenever ∀x∈C hx, xi∈/ R.

3. We say a relation R is transitive on C whenever

∀x ∀y ∀z [(hx, yi ∈R∧ hy, zi ∈R)→ hx, zi ∈R.]

4. We say a relation R is well founded on C whenever

∀X [(X ⊆C∧X 6=∅)→(∃x∈X ∀y∈X hy, xi∈/ R)].

Such an x is called minimal forX.

5. We say a relation R is total on C whenever

∀x∈C ∀y∈C [hx, yi ∈R∨ hy, xi ∈R∨x=y].

6. We say R is extensional on C whenever

∀x∈C ∀y∈C [x=y↔ ∀z ∈C (hz, xi ∈R ↔ hz, yi ∈R)].

53

Referințe

DOCUMENTE SIMILARE

The notion of local superconvergence is used when on a set of interiorpoints Z* (orZ*¡ the approximate solution has a convergence order greater than the global

Rhetoric is included in the reconstructive sciences having as object the limits of the modal axiom common to the intellectual techniques: it is possible to change beliefs, values

On the other hands, there are many challenges facing the nanomaterials which are the shape and size, to overcome these problems it is better to prepare

As it can be seen in table 3, subjects’ serum Iron mean concentration in the first stage and before the Bruce Protocol physical activity was found to be 1.007 nano grams per

For instance the zero dimensional subsets of the non-orientable manifolds are neither vanishing sets of the top differentiable forms, nor critical sets of any differentiable

We consider, in this paper, mappings with a contractive iterate at a point, which are not contractions, and prove some uniqueness and existence results in the case of b−metric

Without becoming too formal, this chapter carefully examines a number of theories and their models, including the theory of partially ordered sets, in order to provide a background

– Monitoring - there is a wide set of contexts in which monitoring allows decision- making: if system business functions are exposed you need to monitor them, if you want to