Set Theory Lecture Notes
Set Theory Lecture Notes
Set Theory Lecture Notes
Set Theory
(only a draft)
Ali Nesin
Mathematics Department
Istanbul Bilgi University
Kuştepe Şişli
Istanbul Turkey
anesin@bilgi.edu.tr
3 Functions 31
3.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 More On Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Binary Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Operations with Functions . . . . . . . . . . . . . . . . . . . . . . 37
3.5 Injections, Surjections, Bijections . . . . . . . . . . . . . . . . . . 38
3.5.1 Injections . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.2 Surjections . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5.3 Bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.6 Sym(X) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.7 Families, Sequences and Cartesian Products . . . . . . . . . . . . 44
4 Relations 47
4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 Total Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5 Induction 57
3
4 CONTENTS
6 Bijections, revisited 61
6.1 Schröder-Bernstein’s Theorem . . . . . . . . . . . . . . . . . . . . 61
6.2 Examples of Sets in Bijection . . . . . . . . . . . . . . . . . . . . 61
8 Formulae 69
9 Miscellaneous Exercises 71
11 Natural Numbers 87
11.1 Definition and Basic Properties . . . . . . . . . . . . . . . . . . . 87
11.2 Well-ordering on ω . . . . . . . . . . . . . . . . . . . . . . . . . . 88
11.3 Peano’s Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
11.4 Addition of Natural Numbers . . . . . . . . . . . . . . . . . . . . 90
11.5 Multiplication of Natural Numbers . . . . . . . . . . . . . . . . . 92
11.6 Well-Ordering of Natural Numbers . . . . . . . . . . . . . . . . . 94
11.7 Finite and Infinite Sets . . . . . . . . . . . . . . . . . . . . . . . . 96
11.8 Functions Defined by Induction . . . . . . . . . . . . . . . . . . . 96
11.9 Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
11.10Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
11.11Uniqueness of N . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
12 Integers 101
12.1 Definition of The Set Z of Integers . . . . . . . . . . . . . . . . . 101
12.2 Operations +, − and × on Z . . . . . . . . . . . . . . . . . . . . 102
12.3 Ordering on Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
12.4 Embedding of (N, +, ×, <) in (Z, +, ×, <) . . . . . . . . . . . . . 106
12.5 Additive Structure of Z . . . . . . . . . . . . . . . . . . . . . . . 107
12.6 Multiplicative Structure of Z . . . . . . . . . . . . . . . . . . . . 108
12.7 Ordering on Z, Revisited . . . . . . . . . . . . . . . . . . . . . . . 108
CONTENTS 5
16 Ordinals 125
16.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
16.2 Axiom of Replacement . . . . . . . . . . . . . . . . . . . . . . . . 126
16.3 Classification of Well-Ordered Sets . . . . . . . . . . . . . . . . . 126
16.4 Addition of Ordinals . . . . . . . . . . . . . . . . . . . . . . . . . 127
16.5 Multiplication of Ordinals . . . . . . . . . . . . . . . . . . . . . . 127
17 Cardinals 129
17.1 Addition of Cardinals . . . . . . . . . . . . . . . . . . . . . . . . 129
17.2 Multiplication of Cardinals . . . . . . . . . . . . . . . . . . . . . 129
17.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
17.4 Final Exam of Math 112, May 2003 . . . . . . . . . . . . . . . . 129
20 V = L 135
26 Exams 147
26.1 First Semester Midterm, November 2002 . . . . . . . . . . . . . . 147
26.2 First Semester Final, January 2003 . . . . . . . . . . . . . . . . . 152
26.3 First Semester, Resit, January 2004 . . . . . . . . . . . . . . . . 153
26.4 First Semester, February 2003 . . . . . . . . . . . . . . . . . . . . 158
26.5 First Semester Final and Its Correction, January 2004 . . . . . . 160
26.6 Second Semester, Midterm, May 2003 . . . . . . . . . . . . . . . 163
Part I
7
9
This part is about naive set theory, as opposed to axiomatic set theory that
will be the subject of the next part. Naive set theory does not care so much
about the definition or the existence of a set; on the contrary, in the axiomatic
set theory our primary concern will be the existence of a set.
Here, in this part, we will accept the concept of a “set” without defining
it; further we will assume that any collection of mathematical objects is a set,
whatever this means. Going even further, we will assume that the natural
numbers such as 0, 1, 2, integers such as √ −2, −4, rational numbers such as
3/5, −6/5 and the real numbers such as 2, π, π π exist and that the reader is
familiar with the basic operations of + and × performed with them. In other
words we assume all that has been taught in elementary school, mid-school and
high school.
In the next part we will define all mathematical objects carefully (this means
mathematically). We will prove that all the mathematical objects that are
defined are in fact sets. To prove that these objects are sets, we will use axioms
of set theory, that we will define. But for the moment we are away from this
realm and we work intuitively, without asking the question of existence.
10
Chapter 1
11
12 CHAPTER 1. BASIC CONCEPTS AND EXAMPLES
two sets are equal if they have the same elements, i.e. if an element of one of
them is an element of the other and vice versa.
If x ⊆ y and x 6= y, then we write x ⊂ y. For example, {0, 3} ⊂ {0, 2, 3, π}.
If the set x is not a subset of the set y, we write x 6⊆ y. For example,
{π} 6⊆ {3.14, 3.14159, 22/7}.
The statement of our first theorem must be well known by the reader, but
its proof may not be so well known. In fact the proof is very interesting and we
urge the reader to digest it well.
Proof: Let ∅ be a set with no elements4 . Let x be any set. Assume ∅ is not
a subset of x. We will obtain a contradiction, proving that ∅ is a subset of x.
Since ∅ is not a subset of x, by the very definition of the concept of “subset”,
there is an element in ∅ which is not in x. But ∅ has no elements. Thus ∅ cannot
have an element which is not in x. Hence ∅ ⊆ x. ¤
Proof: Let ∅1 and ∅2 be two sets with no elements. By the theorem above,
∅1 ⊆ ∅2 and ∅2 ⊆ ∅1 . Hence ∅1 = ∅2 . ¤
A set that has no elements at all is called emptyset and is denoted by ∅.
As we have seen in the Corollary above there is only one set with no elements5 .
Here we list all the subsets of the set {0, 1, 2}:
∅
{0}
{1}
{2}
{0, 1}
{0, 2}
{1, 2}
{0, 1, 2}
The set of subsets of a set X is denoted by ℘(X). Thus the set ℘({0, 1, 2})
has the eight elements listed above.
there is such a set. In the next part one of our axioms will state that there is a set with
no elements. This fact cannot be proven, so either the existence of such a set or a statement
implying its existence must be accepted as an axiom.
14 CHAPTER 1. BASIC CONCEPTS AND EXAMPLES
Exercises.
xii. Can you find a set X 6= ∅ such that for every x ∈ X, x is a subset of X?
xv. Show that for any set X, {∅} ∈ ℘(X) if and only if ∅ ∈ X.
becomes
∀z (z ∈ x ⇒ z ∈ y).
Finally, the definition of “subset” can be written as
x ⊆ y ⇔ ∀z (z ∈ x ⇒ z ∈ y).
What we have above is really a short cut for the English sentence “x is a subset
of y if and only if every element of x is an element of y”, it is some kind of steno, a
shorthand, as useful as “TGIF”. Although it is convenient, we will refrain from
using such abbreviations without any apparent reason, and we advice the young
reader not to use such symbolism in their papers, unless they are asked to do
so.
Since the above definition is for all sets x and y, we can write,
∀x ∀y (x ⊆ y ⇔ ∀z (z ∈ x ⇒ z ∈ y)).
The fact that every set is a subset of itself is formalized by ∀x x ⊆ x.
Let us formalize the equality of two sets. As we know, two sets x and y are
equal if and only if x ⊆ y and y ⊆ x. Thus
x = y ⇔ (x ⊆ y and y ⊆ x).
(The reader should note the need of parentheses). Instead of the word “and”
we will write ∧, thus we now have
x = y ⇔ (x ⊆ y ∧ y ⊆ x).
We can continue and replace x ⊆ y with ∀z (z ∈ x ⇒ z ∈ y) and y ⊆ x with
∀z (z ∈ y ⇒ z ∈ x). Thus
x = y ⇔ ((∀z (z ∈ x ⇒ z ∈ y) ∧ (∀z (z ∈ y ⇒ z ∈ x))).
A moment of thought will convince the reader that
(∀z (z ∈ x ⇒ z ∈ y) ∧ (∀z (z ∈ y ⇒ z ∈ x))
is equivalent to
∀z ((z ∈ x ⇒ z ∈ y) ∧ (z ∈ y ⇒ z ∈ x)),
and that this one is equivalent to
∀z (z ∈ x ⇔ z ∈ y).
Thus
x = y ⇔ ∀z (z ∈ x ⇔ z ∈ y).
Since this is true for all sets x and y, we have
∀x ∀y (x = y ⇔ ∀z (z ∈ x ⇔ z ∈ y)).
Let us look at the meaning of x 6= y. By definition, x 6= y if it is not true
that x = y, i.e. if there is an element in one of the sets which is not in the
other. Thus, x 6= y if and only if
1.3. NUMBER SETS 17
∃z(z ∈ x ∧ z 6∈ y).
Now x 6= y is formalized by
either ∃z(z ∈ x ∧ z 6∈ y) or ∃z(z ∈ y ∧ z 6∈ x).
Finally, the ”either ... or ...” part is shortened by . . .∨. . ., so that x 6= y becomes
equivalent to
(∃z(z ∈ x ∧ z 6∈ y)) ∨ (∃z(z ∈ y ∧ z 6∈ x)).
A moment of reflection will show that this is equivalent to
{0, 1, 2, 3, 4, 5, . . .}
N = {0, 1, 2, 3, . . .}.
We can add and multiply two natural numbers to obtain a third natural
number, i.e. “N is closed under addition and multiplication”. On the other
hand substraction is not well-defined in N, because for example 2 − 5 is not a
natural number. To subtract one natural number from another we need the
negative of natural numbers as well.
Any natural number is an integer, as well as −3, −2, −1, which are not
natural numbers. The set of integers is denoted by Z. Thus
Now in the set Q we can add, multiply, subtract any two numbers. We can
also divide one rational number to another nonzero rational number. Thus Q
is closed under addition, multiplication, substraction, and division by nonzero
elements.
By taking b = 1, we see that Z ⊂ Q.
Although the set of rational numbers looks like a perfect set to work with,
it is not, because, there are “holes” in Q, for example, one cannot solve the
equation x2 = 2 in Q as the next lemma shows:
in fact ancient Greeks had some considerable difficulty before they became aware
and recognized irrational numbers. In fact even after the Greeks became aware
of the irrational numbers, they had a hard time to admit their existence, for
example the Pythogarian school forbid its members from revealing it. Later on
in this book, we will define each one of these concepts mathematically. Loosely
speaking, we will obtain the set of real numbers by filling the “gaps” in Q. But
for the moment only an intuitive feeling is enough. The following may help the
reader to gain further intuition: A positive real number can be regarded (or
defined) as a distance on a straight line.
Although we know it is not and cannot be the case for most of our readers,
in this part we assume that the reader is familiar with the set R of real numbers
and the four operations performed with these numbers.
In R we can take √ any power of a nonnegative
√ number.√ Unlike in Q, there
2
is a number, called 2, in R such that 2 > 0 and ( 2) = 2. We also
√ √2 π
have real numbers of the form 2 and π . These operations will be defined
mathematically in the next part.
We of course have, N ⊂ Z ⊂ Q ⊂ R.
In between Z and R there are other number sets closed under addition,
substraction and multiplication. For example, the set
√ √
Z[ 2] := {a + b 2 : a, b ∈ Z}
is √
closed under addition, substraction and multiplication. On the other hand
Z[ 2] is not closed under division (by a nonzero element). But the set
√ √
Q[ 2] := {a + b 2 : a, b ∈ Q}
i. Show that between any two rational numbers there is a rational number.
iii. Show that there are positive irrational numbers α and β such that αβ
√ √2
is rational. (Hint: If 2 is rational, we are done. Otherwise consider
√ √2 √2
[ 2 ] .)
iv. Let ² > 0 and α > 0 be rational numbers. Show that there is an n ∈ N
such that n² > α.
v. Show that any nonempty subset of Z closed under substraction is the set
of multiples of a given natural number n.
20 CHAPTER 1. BASIC CONCEPTS AND EXAMPLES
{x ∈ X : P (x)}.
For example, in the example above, the set of even natural numbers we obtained
is written by
{x ∈ N : x is even}.
We may denote the same set as
{2x : x ∈ N}.
We will abbreviate this set as 2N. Similarly, 2Z will denote the set of even
integers. For r ∈ R, the definitions of the sets rN, rZ, rQ should be clear. For
example,
{s ∈ R : s > a}.
This set is denoted by (a, ∞). Similarly for two real numbers a and b we define
the following sets:
These sets are called intervals6 . We also denote the intervals (0, ∞) and [0, ∞)
by R>0 and R≥0 respectively.
6 The reader should be aware that we did not define an object called “infinity” or ∞ here.
We just denoted some subsets with the help of the symbol ∞. We did not use the symbol ∞
in the definition of these subsets, we just used it in the names of the subsets as a meaningless
symbol.
1.5. SETS OF SETS 21
Exercises.
ii. Find the elements of the set {x ∈ R : x > n for all n ∈ N}.
Examples.
i. The collection of all sets of the form (r, ∞) for r ∈ R is a set. We denote
it as {(r, ∞) : r ∈ R}. Naming X this set, we have
(5, ∞) ∈ X
7 6∈ X
7 ∈ (5, ∞) ∈ X
∅ 6∈ X
R 6∈ X
[5, ∞) 6∈ X
A0 = {0}
A1 = {1, 2}
A2 = {2, 3, 4}
A3 = {3, 4, 5, 6}
Consider the set whose elements are all these sets A0 , A1 , A2 , A3 , . . . This
set is denoted as
{An : n ∈ N}.
iii. We may consider the set of subsets X of R such that (−², ²) ⊆ X for some
² ∈ R>0 . This set will be written as
Exercises.
i. Let X be a finite set with n elements. Find the number of elements of the
set {A ∈ ℘(X) : |A| = n − 1}.
ii. Let X be a finite set with n elements. Find the number of elements of the
set {A ∈ ℘(X) : |A| is even}.
iii. Let X be a finite set with n elements. Find the number of elements of the
set {A ∈ ℘(X) : |A| is divisible by 3}.
iv. Let U be the set of subsets X of R such that for some ² ∈ R>0 , (−², ²) ⊆ X.
Let V be the set of subsets X of R such that for some ² ∈ R>0 , [−², ²] ⊆ X.
Let W be the set of subsets X of R such that for some ² ∈ Q>0 , (−², ²) ⊆
X.
Show that U = V = W .
v. A subset U of R is called open if for any x ∈ U there is an ² ∈ R>0 such
that (x − ², x + ²) ⊆ U .
Show that a subset U of R is open if for any x ∈ U there is an ² ∈ R>0
such that [x − ², x + ²] ⊆ U .
Show that ∅ is open.
Show that the intersection7 of two open subsets is open.
Show that if U 6= ∅, R is open, then {x ∈ R : x 6∈ U is not open.
vi. A subset U of Q is called open if it is the intersection with Q of an open
subset of R. Show that Q can be written as the union of two disjoint
nonempty open subsets. Try to convince yourself that R does not have
this property.
2.1 Difference
Let X and Y be two sets. We want to consider the set of elements of X which
are not in Y , i.e. we want to consider the set {x ∈ X : x 6∈ Y }. This is the set
of elements x of X with the property that x 6∈ Y . We denote this set by X \ Y .
For example {0, 2, 3, 5} \ {2, 5, 7, 8} = {0, 3} and N \ 2N is the set of odd
natural numbers.
Clearly, for all sets x and y,
i. x\x=∅
ii. x \ y ⊆ x
iii. x \ ∅ = x
iv. x \ y = ∅ if and only if x ⊆ y
If a set X is fixed once for all, for a subset Y of X, we write Y c for X \ Y .
Whenever we use the notation Y c , we assume that the superset X is clear from
the context. The set Y c is called the complement of Y (in X).
Given a superset X, it is again clear that
i. (Y c )c = Y
ii. X c = ∅
iii. ∅c = X
2.2 Intersection
Given two sets X and Y we may want to consider the set of common elements
of X and Y . This new set is called the intersection of X and Y and is
denoted X ∩ Y . For example if X = {0, 1, 2, 5, 8} and Y = {1, 3, 5, 6} then
X ∩ Y = {1, 5}.
Two sets that intersect in emptyset are called disjoint.
The following properties are well-known and we leave the proofs to the
reader:
25
26 CHAPTER 2. OPERATIONS WITH SETS
i. x∩x=x
ii. x∩y ⊆x
iii. x∩y =y∩x
iv. x ∩ y = x if and only if x ⊆ y
v. (x ∩ y) ∩ z = x ∩ (y ∩ z)
vi. x∩∅=∅
vii. (x \ y) ∩ (y \ x) = ∅
For reasons that will be clear in the next part, ∩∅ is left undefined for the
moment. The reader should only note for the moment that if in the definition
and, since the statement on the right hand side holds for all y, every y is in ∩∅.
(See also Exercise viii, page 28).
2.3. UNION 27
Exercises.
i. Show that for any set X, ∩℘(X) = ∅.
ii. Show that x \ y = x if and only if x ∩ y = ∅ and that x \ y = ∅ if and only
if x ⊆ y.
T∞
iii. Show that n=1 (−1/n, 1 + 1/n) = [0, 1].
T
iv. Show that r<1 and 2<s (r, s) = [1, 2].
T T
v. Show that ²>0 (−², ²) = ²>0 [−², ²] = {0}.
2.3 Union
Given two sets x and y we may want to consider the set of elements which
are either in x or in y. This new set is called the union of x and y and is
denoted x ∪ y. For example if x = {0, 1, 2, 5, 8} and y = {1, 3, 5, 6} then
x ∪ y = {0, 1, 2, 3, 5, 6, 8}.
We leave the proof of the following well-known properties to the reader:
i. x∪x=x
ii. x⊆x∪y
iii. x∪y =y∪x
iv. x∪y =x⇔y ⊆x
v. (x ∪ y) ∪ z = x ∪ (y ∪ z)
vi. x∪∅=x
Property (v) says that the parentheses are not needed when intersecting several
sets. For example the sets x ∪ (y ∪ (z ∪ t)) and (x ∪ y) ∪ (y ∪ t) are equal and
they may be denoted by x ∪ y ∪ y ∪ t.
There are two famous relationships between ∩ and ∪ called De Morgan laws:
vii. x ∩ (y ∪ z) = (x ∩ y) ∪ (x ∩ z)
viii. x ∪ (y ∩ z) = (x ∪ y) ∩ (x ∪ z)
We can also take the union of infinitely many subsets. For example, we may
want to consider all the common Selements of the intervals (1/n,
S∞1 − 1/n) for n =
1, 2, 3, . . . We denote this set as n=1,2,... (1/n, 1−1/n) or as n=1 (1/n, 1−1/n);
it is the union of all the sets of the form (1/n, 1−1/n) for some nonzero natural
number n. The reader should prove that
∞
[
(1/n, 1 − 1/n) = (0, 1).
n=1
Similarly S∞
Sn=1 [1/n, 1 − 1/n) = (0, 1)
∞
Sn=1 [1/n, 1 − 1/n] = (0, 1)
∞
Sn=1 [1/n, ∞) = (0, ∞)
∞
n=1 (1/n, ∞) = (0, ∞)
28 CHAPTER 2. OPERATIONS WITH SETS
Similarly, we may want to take S the union of all theS sets of form (r, ∞) for
r ∈ R>0 . We denote this set as r∈R S >0 (r, ∞) or by r>0 (r, ∞) if there is no
room for confusion. It is clear that r>0 (r, ∞) = (0, ∞).
In general if X = {Ai : i ∈ I} is a set indexed by the indexSset I and if each
Ai is a set, then the union of all the sets in X is denoted by i∈I Ai .
If the set X is not given
S by an index set as above, we denote the union of
all the elements of X by x∈X x or sometimes by ∪X. Thus we have
Lemma 2.3.1 ∪∅ = ∅.
Exercises.
i. For subsets A and B of a superset X, show that (A \ B)c = Ac ∪ B.
ii. Show that for any sets x, y, z,
y ∩ (x \ y) = ∅
(x ∩ y) \ z = (x \ z) ∩ (y \ z)
(x \ y) \ z = x \ (y ∪ z)
Show that this coincides with the earlier definition if X 6= ∅ and that with
the new definition, ∩∅ = ∅.
S
ix. Show that r>0 [r, ∞) = (0, ∞).
S S
x. Show that for any set A and for any set X of sets, ( x∈X x)\A = x∈X (x\
A).
2.4. CARTESIAN PRODUCT OF TWO SETS 29
xii. Symmetric Difference. For two sets X and Y define the symmetric
difference of X and Y as follows: X∆Y = (X \ Y ) ∪ (Y \ X). Show that
for all sets X, Y, Z,
a) X∆(Y ∆Z) = (X∆Y )∆Z.
b) X∆Y = Y ∆X.
c) X∆∅ = ∅∆X = X.
d) X∆X = ∅.
Accordingly, we would like to define the pair (x, y) in such a way that the above
property holds.
The set {{x}, {x, y}} has this property, i.e.,
Given three sets x, y and z, we can form (x, y) and (y, z) and then ((x, y), z)
and (x, (y, z)). Unfortunately these two sets are not necessarily equal. We let
(x, y, z) denote the first one of these. Later we will give a better definition of
(x, y) and (x, y, z).
Exercises.
iv. Find ∩(x, y), ∪(x, y), ∩ ∩ (x, y), ∩ ∪ (x, y), ∪ ∩ (x, y), ∪ ∪ (x, y).
v. Find ((∪ ∪ (x, y)) \ (∪ ∩ (x, y))) ∪ (∩ ∪ (x, y)).
vi. What is X × ∅?
Functions
3.1 Functions
Loosely and naively speaking, a function or a map f from a set X into a set
Y is a “rule” that assigns to each element x of X a unique element f (x) of Y .
Note that we highlighted the words “each” and “unique”.
For example, the rule that assigns to a real number its square root is not
a function because a negative number does not have a square root. The rule
that assigns the elements x and −x to an element x ∈ R is not a function either
because a function must assign a unique element to each element.
On the other hand, a function may assign the same element of the set of
arrival to two different elements of the domain. For example, to a real number
x we can assign its square x2 and get a function from R into R. Although
the element 1 is assigned to the elements 1 and −1, this does not prevent the
squaring from being a function. As this example also shows, an element of the
set of arrival is not necessarily assigned to an element of the domain, e.g. in this
example, the element −1 is not assigned, since it is not a square.
The set X is called the domain of the function f , and the set Y is called
the arrival set of f .
If f is a function from X into Y , very often we denote this fact as f : X −→
Y . The “rule” f may be made explicit by the notation x 7→ f (x).
If A ⊆ X and f : X −→ Y is a function, we let
f (A) = {f (x) : x ∈ A}
and we call this set the image or the range of A under f . The set f (X) is
called the image or the range of f
Given a function f : X −→ Y and a set Y1 that contains f (X) as a subset,
we can define another function f1 : X −→ Y1 by the rule used to define f . For
each x ∈ X we then have f (x) = f1 (x) by the very definition of f1 . Although
the two functions take the same values with the same input, i.e. although they
are defined by the same rule, their arrival sets are distinct. (But their images
31
32 CHAPTER 3. FUNCTIONS
are the same set f (X)). We will differentiate f and f1 and consider them as
two different functions (but we may denote them by the same letter f ). In other
words, a function is more than a rule; the domain X and the arrival set Y are
also parts of the definition of a function.
Two functions are equal if they have the same domain, the same arrival
set and if they take the same value on any element of the domain. Thus two
functions f : X −→ Y and g : X1 −→ Y1 are equal if and only if X = X1 , Y = Y1
and f (x) = g(x) for all x ∈ X. In particular, two functions f, g : X −→ Y are
equal if and only if f (x) = g(x) for √
all x ∈ X. For example the functions f and
g from R into R defined by f (x) = x2 and g(x) = |x| are equal.
The set of functions from X into Y will be denoted by Func(X, Y ).
ii. Let X and Y be two sets. For a fixed element b ∈ Y , the function that
sends each element x of X to the element b of Y is called the constant b
function.
f (0) = 5
f (1) = 6
f ({0, 1}) = 7
i. How many functions are there from a set of n elements into a set of m
elements?
ii. What can you say about the relationship between f (A \ B) and f (A) \
f (B)?
v. Let f : X −→ Y be a function.
i. Show that if (Bi )i is a family of subsets of Y , then
[ [
f −1 ( Bi ) = f −1 (Bi ),
i i
and \ \
f −1 ( Bi ) = f −1 (Bi )
i i
−1 c −1 c
and if B ⊆ Y then f (B ) = f (B) .
S S
Show thatTif (Ai )i is a family of subsets of X, then f ( i Ai ) = i f (Ai ),
ii. T
f ( i Ai ) ⊆ i f (Ai ).
iii. Find an example where the last inclusion fails to be an equality.
iv. If A ⊆ X what is the relationship between f (Ac ) and f (A)c ?
vii. Let X and Y be two sets. Find a set Z such that the map f : ℘(X) ×
℘(Y ) −→ Z defined by f (A, B) = A × B is a function. (One may just take
Z := {A × B : A ∈ ℘(X), B ∈ ℘(Y )}. But we want something better. Try
to define Z in terms of X and Y using only the set theoretic operations
like ∪, ∩, ℘).
3.2. MORE ON FUNCTIONS 35
Exercises.
i. With the new definition of a function given above, given two functions
(X, Y, F ) and (Y, Z, G) define their composite (X, Y, F ) ◦ (Y, Z, G).
ii. Let (X, Y, F ) be a function. Show that the set X is uniquely determined
by Y and F . In other words if (X, Y, F ) and (X1 , Y, F ) are functions,
then X = X1 . This exercise shows that a function may be defined only
as a pair (Y, F ) such that for every x there is a unique y ∈ Y such that
(x, y) ∈ F .
Examples.
v. X = N, Z, Q, R for + and ×.
vii. X = 2Z for +.
xii. X = R and x ? y = x − y.
vii. We can generalize even further the above example. Let I be an index set.
Let (fi : Xi −→ Yi )i∈I be a family of functions indexed by I. Assume
that for all i, j ∈ I and all x ∈ Xi ∩ Xj , fi (x) = fj (x). Then we can
define the function ∪i∈I fi : ∪i∈I Xi −→ ∪i∈I Yi by the following rule: For
all x ∈ ∪i∈I Xi ,
(∪i∈I fi )(x) = fi (x)
if x ∈ Xi .
Exercises.
Further Examples.
3.5.2 Surjections
A function f : X −→ Y is called onto or a surjection if for all y ∈ Y there is
an x ∈ X such that f (x) = y, i.e. if f (X) = Y . That means that if f : X −→ Y
is an surjection, then every elements of Y is “attained” by an element of X
under f . For example the function f : R −→ R defined by f (x) = x2 is not
onto because -1 is not attained. But the function f : R −→ R≥0 defined by the
same rule f (x) = x2 is onto. These examples show that “to be surjective” is a
property that has to do more with the arrival set than with the domain.
Further Examples.
i. If X and Y are nonempty sets, then the projection maps π1 : X ×Y −→ X
and π2 : X ×Y −→ Y are surjections. The map π1 is not one to one unless
|Y | = 1.
ii. The map f : N −→ N defined by f (n) = [n/2] where [x] stands for the
integer part of x is onto (but not one to one).
iii. The map f : N −→ N defined by
½ n
2 if n is even
f (n) = n−1
2 if n is odd
is onto.
iv. If f1 : X1 −→ Y1 and f2 : X2 −→ Y2 are onto then the function f1 × f2 :
X1 × X2 −→ Y1 × Y2 defined by (f1 × f2 )(x1 , x2 ) = (f1 (x1 ), f2 (x2 )) is also
onto.
3.5.3 Bijections
A function f : X −→ Y is called bijection if it is one-to-one and onto. Two
sets X and Y for which there is such a bijection are said to be in one-to-one
correspondence or in bijection.
f −1 (y) = x ⇐⇒ f (x) = y.
We have
f ◦ f −1 = IdY and f −1 ◦ f = IdX .
Furthermore if g : Y −→ X satisfies
f ◦ g = IdY or g ◦ f = IdX
Exercises.
i. Find all bijections from {0, 1, 2} into {0, 1, 2}. Find all bijections from
{0, 1, 2, 3} into {0, 1, 2, 3}. Find all injections from the set {0, 1, 2} into
the set {0, 1, 2, 3}. Find all surjections from {0, 1, 2, 3} into {0, 1, 2}.
3.6. SYM(X) 41
iii. Let X be a set. The set of functions from X into {0, 1} is denoted by X 2.
The purpose of this exercise is to show that there is a bijection between
the sets ℘(X) and X 2.
a) For a subset A of X, define fA : X −→ {0, 1} by the rule
½
1 if x ∈ A
fA (x) =
0 if x 6∈ A
X
Thus fA ∈ 2. (The function fA is called the characteristic function
of A).
b) Show that the rule A 7→ φ(A) := fA defines a function φ from ℘(X)
into X 2.
c) Let f ∈ X 2 be a function. Let Xf := {x ∈ X : f (x) = 1}. Show that
the rule f 7→ ψ(f ) = Xf defines a function ψ from X 2 into ℘(X).
e) For A ∈ ℘(X), show that ψ(φ(A)) = A.
A
f) For f ∈ 2, show that ψ(φ(f )) = f .
g) Conclude that the functions A 7→ φ(A) and f 7→ ψ(f ) are bijections
and that they are inverses of each other.
iv. Let X be a set. The set of functions from {0, 1} into X is denoted by 2 X.
Show that there is a bijection between the sets X × X and 2 X.
3.6 Sym(X)
Let X be any set and G = Sym(X), the set of all bijections from X into X.
Consider the composition operation ◦ on Sym(X). The triple (Sym(X), ◦, IdX )
has the following properties:
Let us first get acquainted with the groups of the form Sym(n) for n ∈ N.
We consider the following element g of Sym(7):
g(1) = 2
g(2) = 5
g(3) = 3
g(4) = 7
g(5) = 1
g(6) = 6
g(7) = 4
where we put the domain on the first line, and the image of the elements of the
domain just below it. We can represent this element also as (1, 2, 5)(3)(4, 7)(6) or
as (1, 2, 5)(4, 7). We will prefer the last representation. The last representation
can be read as follows: “1 goes to 2, 2 goes to 5, 5 goes back to 1; 4 goes to 7,
7 goes back to 4; the rest of the numbers (3 and 6) are fixed”.
Written this way, the element g = (1, 2, 5)(4, 7) may be seen as an element of
Sym(7) as well as an element of Sym(8). If one is careful enough when needed,
this never causes a problem.
It is impossible to represent IdSym(6) with the representation we adopted, so
we will write simply IdSym(6) or just 1 (by abuse of language).
Such a representation is called the cyclic representation of the bijection.
The elements such as (1, 2, 5), (3) and (4, 7) of a cyclic representation are called
cycles. The cycle (1, 2, 3) is a 3-cycle. The cycle (4, 7) is a 2-cycle. The element
(1, 2, 5)(4, 7) of Sym(7) has four cycles, namely (1, 2, 5), (3), (4, 7) and (6). On
the other hand, the element (1, 2, 5)(4, 7) of Sym(8) has five cycles, namely
(1, 2, 5), (3), (4, 7), (6) and (8). The element IdSym(6) or 1 of Sym(6) has six
cycles. But the element 1 of Sym(8) has eight cycles.
Clearly (1, 2, 3) = (2, 3, 1) = (3, 1, 2) 6= (1, 3, 2).
The multiplication (more precisely, the composition) of disjoint cycles is very
simple: One just juxtaposes them, e.g. the multiplication of (1, 2, 5) and (4, 7)
is just (1, 2, 5)(4, 7), or (4, 7)(1, 2, 5). Similarly, the product of the two elements
(1, 5, 7)(3, 4) and (2, 6)(8, 9) is just (1, 5, 7)(2, 6)(3, 4)(8, 9).
If the cycles are not disjoint, then the multiplication (i.e. the product or the
composition) of elements is slightly more complicated. For example to compute
(1, 2, 3)(1, 2, 4, 3, 5) we start from the right and see where 1 goes to: 1 first goes
to 2 (the right cycle) and the left cycle takes 2 to 3. Thus the product starts
as (1, 3, . . .. Now we restart the same procedure with 3. As a result we obtain
(1, 2, 3)(1, 2, 4, 3, 5) = (1, 3, 5, 2, 4). As an exercise the reader should check that
(1, 2, 3)(4, 5), (1, 3, 2)(4, 5), (1, 2, 4)(3, 5), (1, 4, 2)(3, 5), (1, 2, 5)(3, 4),
(1, 5, 2)(3, 4), (1, 3, 4)(2, 5), (1, 4, 3)(2, 5), (1, 3, 5)(2, 4), (1, 5, 3)(2, 4),
(1, 4, 5)(2, 3), (1, 5, 4)(2, 3), (2, 3, 4)(1, 5), (2, 4, 3)(1, 5), (2, 3, 5)(1, 4),
(2, 5, 3)(1, 4), (2, 4, 5)(1, 3), (2, 5, 4)(1, 3), (3, 4, 5)(1, 2), (3, 5, 4)(1, 2).
Exercises.
iv. How many types of elements are there in Sym(9) whose square is 1?
of Sym(n) both ways. Are they equal? How many cycles do the products
have?
viii. Show that it is not true that for every g ∈ Sym(N) there is an h ∈ Sym(N)
such that h2 = g.
∗∗
ix. Is it true that every element of Sym(N) is a product of finitely many
squares?
∗∗
x. Let p be an integer. Is it true that every element of Sym(N) is a product
of finitely many p-th powers?
xi. For an element g ∈ Sym(X), define o(g) to be the least positive natural
number m such that g m = IdX if there is such an m, otherwise define
o(g) = ∞. Thus o(g) = IdX if and only if g = IdX .
Let G = Sym(N). Show that
o(1, 2, 3) = 3
o(1, 2, 3, 4) = 4
o((1, 2, 3)(4, 5)) = 6
o(. . . , 7, 5, 3, 1, 2, 4, 6, 8, . . .) = ∞
with the concept we have defined here when I has just two elements. But
thisQ
is not true. The set X1 × X2 defined in chapter 2.4 is not equal to the
set i∈{1,2} Xi that we have defined above. Nevertheless there is a bijection
between them.
Q
Lemma 3.7.1 There is a bijection between X1 × X2 and i∈{1,2} Xi .
Relations
4.1 Definitions
Let X be a set. A binary relation R of X is just a subset of X × X. For
x, y ∈ X, rather than writing (x, y) ∈ R, one often writes xRy. The usual
symbols for relations are <, ≤, ≺, ¹, ¿, ⊂, ⊆, v, ∼, ', ≈, ≡, ⊥, k, C, E etc.
Examples.
< = {(0, 1), (0, 2), (1, 2), (0, 3), (1, 3), (2, 3)}.
Then < is a relation. It is the order relation that we are familiar with.
v. Let U be any set. Let X be the set of finite subsets of U . Then {(A, B) ∈
X × X : |A| = |B|} is a relation on X.
is a relation on X.
47
48 CHAPTER 4. RELATIONS
is a relation on X.
Exercises.
ii. The relation R defined by xRy for all x, y on any set is an equivalence
relation.
x ≡n y ⇐⇒ n divides x − y
is an equivalence relation.
x ≡ y ⇐⇒ |x| = |y|
is an equivalence relation.
is an equivalence relation on X.
50 CHAPTER 4. RELATIONS
Examples.
i. The set {{0, 3}, {1, 2, 4}} is a partition of {0, 1, 2, 3, 4}.
ii. The sets (n, n + 1] for n ∈ Z partition R, meaning that {(n, n + 1] : n ∈ Z}
is a partition of R.
Lemma 4.2.1 Let ≡ be an equivalence relation on a set X. Then the set {x :
x ∈ X} is a partition of X. Conversely, any partition P of X gives rise to an
equivalence relation on X via
x ≡ y if and only if there exists A ∈ P such that x ∈ A and y ∈ A.
Thus there is a one-to-one correspondence between the set of partitions on X
and the set of equivalence relations on X.
Proof: Let ≡ be an equivalence relation on X. Since x ≡ x for all x ∈ X, we
have x ∈ x. It follows that ∪{x : x ∈ X} = X. Now we prove that for any
x, y ∈ X, either x = y or x ∩ y = ∅. We proceed to show that if x ∩ y 6= ∅, then
x = y. Let z ∈ x ∩ y. Thus z ≡ x and z ≡ y. Let t ∈ x. Thus t ≡ x. Since ≡ is
symmetric we have
t≡x
x≡z
z≡y
By transitivity we get t ≡ y, i.e. t ∈ y. We proved that any element t of x is an
element of y. The other direction holds as well. Thus x = y. Thus {x : x ∈ X}
is a partition of X.
Conversely, let P be a partition of X and define the relation ≡ as follows:
x ≡ y if and only if there exists A ∈ P such that x ∈ A and y ∈ A.
It is a matter of triviality to check that this is an equivalence relation. ¤
Examples
i. Consider the equality as an equivalence relation on the set X. Then the
quotient set is {{x} : x ∈ X} and it is in one to one correspondence with
X.
ii. On any set X consider the equivalence relation defined by x ≡ y for all
x, y ∈ X. Then |X/ ≡ | = 1.
iii. On R consider the equivalence relation defined by xRy ⇐⇒ x2 = y 2 .
Then, for each x ∈ R, x = {x, −x}. Thus there is a natural one to one
correspondence between R/ ≡ and R≥0 given by r 7→ |r|.
iv. Let n > 0 be any natural number. On Z, consider the equivalence relation
≡n defined by
x ≡n y ⇐⇒ n divides x − y.
Then for each i ∈ Z, i = nZ + i = Z + j where j = 0, 1, . . . , n − 1
is the remainder when we divide i by n. Therefore we have Z/ ≡n =
{0, 1, . . . , n − 1} and |Z/ ≡n | = n.
v. On the set R, consider the equivalence relation ≡ defined by x ≡ y if and
only if x − y ∈ Z. Then for each r ∈ R, r = r + Z = s + Z for some unique
s ∈ [0, 1). Therefore R/ ≡ is in a natural one to one correspondence with
the interval [0, 1).
vi. On the set R, consider the relation ≡ defined by x ≡ y if and only if
x − y ∈ Q. Then for each r ∈ R, r = r + Q. In this case, we cannot find a
well-known set with which R/ ≡ is in a one-to-one correspondence1 .
vii. Let X and Y be two sets. Let a ∈ X. Consider the equivalence relation
≡a defined on Func(X, Y ) by
f ≡ g ⇐⇒ f|A = g|A .
Given f ∈ Func(X, Y ), f = {g ∈ Func(X, Y ) : f (a) = g(a)}. There
is a one to one correspondence between Func(X, Y ) ≡ and Y given by
f 7→ f (a). There is also a correspondence between Func(X, Y ) ≡ and the
set of constant functions from X into Y .
viii. On X := R × R × R, consider the equivalence relation ≡ defined by
(x, y, z) ≡ (x1 , y1 , z1 ) by 2(x − x1 ) + 3(y − y1 ) − (z − z1 ) = 0. Then
(x, y, z) = {(x1 , y1 , z1 ) : 2x + 3y − z = 2x1 + 3y1 − z1 }.
There is a (not so natural) correspondence between R3 / ≡ and R2 given
by (x, y, z) 7→ (x, y).
ix. On C, consider the equivalence relation defined by x ≡ y ⇐⇒ |x| = |y|.
Then x = {y ∈ C : |x| = |y|} and there is a natural one to one correspon-
dence between C/ ≡ and R≥0 given by x 7→ |x|. Each equivalence class x
is the circle of center 0 and radius |x|.
1 But there is such a set as we will see later in the second part of the book.
52 CHAPTER 4. RELATIONS
Exercises.
i. Let X be a set.
a) For i ∈ I (index set), let Ri be an equivalence relation on X. Thus
Ri ⊆ X × X for each i ∈ I. Show that ∩i∈I Ri is an equivalence relation.
b) Conclude that for any relation R on X there is a smallest equivalence
relation containing R. This equivalence relation is called the equivalence
relation generated by R.
c) Let X = ∪n∈N {(x, y) ∈ R : 2n + 1 ≤ x2 + y 2 ≤ 2n + 2}. Define R on
X as follows: For A, B ∈ X, A R B if and only the line segment AB is
in X. Show that this is not an equivalence relation. Find the equivalence
relation generated by this relation. Find its set of equivalence classes.
ii. Let X be the set of functions from R into R. Let a ∈ R. Define the
following relation on X: f ≡ g if and only if there is an ² > 0 such that
f (x) = g(x) for all x ∈ (a − ², a + ²). Show that this is an equivalence
relation. Show that the functions induced by two distinct polynomials are
not equivalent.
iii. Let X be a set. For two subsets A and B of X define
X ≡ Y ⇐⇒ There is a bijection f : X −→ Y.
Show that this is an equivalence relation on ℘(X).
iv. Let X be a set. For two subsets A and B of X define
X ≡ Y ⇐⇒ X∆Y is finite.
Show that this is an equivalence relation on ℘(X).
v. Let a ∈ R be fixed. We will say that two functions f and g from R into R
have the same germ around a, and we write f 'a g, if there is an ² ∈ R>0
such that f (x) = g(x) for all x ∈ (a − ², a + ²).
a. Show that 'a is an equivalence relation on the set X := R R of all
functions from R into R. For f ∈ X, let [f ] denote the equivalence class
of f with respect to this equivalence relation.
4.3. PARTIAL ORDERS 53
vi. Let X be a set. For two subsets A and B of X, define the relation A ≡ B
by the condition “A∆B is finite”.
a) Show that this is an equivalence relation on ℘(X).
b) Show that ℘(X)/ ≡ has only one element if X is finite.
c) Conversely show that if ℘(X)/ ≡ has only one element then X is finite.
d) Show that ℘(N)/ ≡ is infinite.
Now let A, B, A1 , B1 ⊆ X be such that A ≡ A1 and B ≡ B1 , then
e) A ∩ B ≡ A1 ∩ B1 .
f) A ∪ B ≡ A1 ∪ B1 .
g) Ac ≡ Ac1 .
h) A \ B ≡ A1 \ B1 .
i) A∆B ≡ A1 ∆B1 .
Examples.
i. Let < be a partial order on a set X and let A ⊆ X. Then the partial order
restricted to A, i.e. the binary relation < ∩(A × A), is a partial order on
A.
A < B ⇐⇒ A ⊆ B and A 6= B.
iv. On Z define
x ≺ y ⇐⇒ y < x.
This is a partial order. In general, the inverse of a partial order is a partial
order.
v. On R define
x < y ⇐⇒ |x| < |y|.
This is a partial order.
vi. On Z define
x ≤ y ⇐⇒ x < y or x = y.
x < y ⇐⇒ x ≤ y and x 6= y
is irreflexive and transitive, i.e. is a partial order. Thus there is no much differ-
ence between irreflexive and transitive binary relation (i.e. partial orders) and
reflexive and transitive binary relations. For this reason, sometimes we will de-
fine a partial order as a reflexive and transitive binary relation, in which case,
we use a notation of the form ≤, ¹, ⊆, v, E.
If < is a binary relation on a set X, we define x ≥ y by y ≤ x and “x > y or
x = y” and “y < x or y = x” respectively. Given a binary relation ≤, we could
also define < by “x ≤ y and x 6= y”. It is easy to show that given a partial
order < on X, the relation ≤ defined on X is reflexive, transitive and satisfies
∀x ∀y ((x ≤ y ∧ y ≤ x) → x = y).
Exercises.
i. Let < and ≺ be two partial orders on two sets X and Y respectively.
Define the partial order on X × Y via
ii. Let (Y, <) be a poset. Let f : X −→ Y be any function. Show that the
relation < on X defined by
is a partial order on X.
iii. Let (Y, <) be a poset, X a set and A ⊆ X. For two functions f and g
from X into Y define
x < y, x = y, y < x
holds.
Lemma 4.4.1 Let < be a total order on a set X. For x, y ∈ X only one of
x < y, x = y, y < x
holds.
Induction
What we have here is not a precise mathematical proof, but only a heuristic argument why
φ(x) should hold for all x ∈ N. In the next part, we will prove that steps (1) and (2), do
indeed proof “φ(x) for all x ∈ N”.
57
58 CHAPTER 5. INDUCTION
Exercises.
i. Show that for any natural number n and for any real number x ∈ [0, 1],
n(n − 1) 2
(1 − x)n ≤ 1 − nx + x .
2
iv. Show that if 0 < x < 1 and n > 0 is a natural number, then (1 − x)n ≤
1 − nx + n(n−1)
2 x2 .
viii. Given a set X and a natural number n, define ℘n (X) as follows by induc-
tion on n: ℘0 (X) = X and ℘n+1 (X) = ℘(℘n (X)). Find all n such that
for any set X, {{∅}, {{X}}} ∈ ℘n (X).
µ ¶ µ ¶
n n
ix. Show that = .
k n−k
µ ¶ µ ¶
n n
x. Show that = = 1.
0 n
µ ¶
n
xi. Show that = n.
1
µ ¶ µ ¶ µ ¶
n+1 n n
xii. Show that = + .
k+1 k k+1
µ ¶
n
xiii. Deduce that ∈ N. (Hint: By induction on n).
k
µ ¶
n
xiv. Show that for n ∈ N and 0 ≤ k ≤ n, a set with n elements has
k
subsets with k elements.
xv. Show
µ ¶that for n ∈ N and k ∈ N with k ≤ n, a set with n elements has
n
subsets with k elements.
k
60 CHAPTER 5. INDUCTION
xxiv. Find and prove (by induction) formulas for the sums
3 5 2n + 1
+ 2 2 + ··· + 2
12 ·2 2 2 ·3 n · (n + 1)2
and
1 + 9 + 25 + · · · + (2n + 1)2 .
xxv. Prove by induction that for all real numbers a and b and natural number
n,
Bijections, revisited
We will prove this theorem in the next part. But we can prove the following
results – although naively.
61
62 CHAPTER 6. BIJECTIONS, REVISITED
We will give a naive proof of this result later on in this part. Now we will
find some bijections between unexpected sets. If there is a bijection between
two sets X and Y , we will represent this fact as X ∼ Y . Note that
X∼X
If X ∼ Y then Y ∼ X
If X ∼ Y andY ∼ Z then Y ∼ X
Chapter 7
Some Automorphism
Groups
Exercises.
i. Show that the set Aut(Γ) of all automorphisms of a binary unirelational
structure Γ is is closed under composition and inversion.
ii. Show that the automorphism groups of a binary unirelational structure
and of its dual are equal.
iii. Let (X, R) and (Y, S) be two binary unirelational structures. Let φ be an
isomorphism from (X, R) onto (Y, S). Show that
Aut(Y, S) = φ Aut(X, R)φ−1 .
63
64 CHAPTER 7. SOME AUTOMORPHISM GROUPS
Exercises.
ii. Let us find all graph structures on the set X = {1, 2, 3}. For any two
distinct points x and y we know that if x − y then y − x, so to shorten our
writing, we will write only one of the two relations.
Γ∅ : no relations at all
Γ3 : only 1 − 2 (and 2 − 1 of course)
Γ2 : only 1 − 3
Γ1 : only 2 − 3
Γ13 : only 1 − 2 and 2 − 3
Γ12 : only 1 − 3 and 2 − 3
Γ23 : only 1 − 2 and 1 − 3
Γ123 : all possible relations 1 − 2, 2 − 3 and 1 − 3
iii. ¶ Show that Γ1 , Γ2 and Γ3 are isomorphic. Show that Γ13 , Γ12 and Γ3
are isomorphic. Show that G1 and G23 are duals of each other.
Thus on X there are only fundamentally different (i.e. nonisomorphic)
graph structures, Γ∅ , Γ1 , Γ23 and Γ123 .
iv. Let X be a set. Let Γ be the set of subsets of X with two elements. On
Γ define the relation αRβ if and only if |α ∩ β| = 1. Then Γ becomes a
graph with this relation.
a) Calculate Aut(Γ) when |X| = 4.
b) Draw the dual of Γ when |X| = 5.
c) Show that for any α, β ∈ Γ there is an automorphism φ ∈ Aut(Γ) such
that φ(α) = β.
d) Calculate Aut(Γ) when |X| = 5.
Γ∅ : no relations at all
Γ12 : only 1 − 2 (and 2 − 1 of course)
Γ123 : only 1 − 2 and 2 − 3
Γ12−34 : only 1 − 2 and 3 − 4
Γ1234 : only 1 − 2, 2 − 3 and 3 − 4
Γ∗ : only 1 − 2, 1 − 3 and 1 − 4
Show that
Aut(Γ∅ ) = Sym(4)
Aut(Γ12 ) = Aut(Γ12−34 ) = {1, (1, 2), (3, 4), (1, 2)(3, 4)}
Aut(Γ123 ) = {1, (1, 3)}
Aut(Γ12−34 ) = {1, (12), (34), (12)(34), (13)(24), (23)(14), (1324), (1223)}
Aut(Γ1234 ) = {1, (14)(23)}
Aut(Γ∗ ) = {1, (12), (13), (23), (123), (132)}
x. Let n ≥ 3 and let Γ be the cyclic graph on {1, 2, . . . , n}, i.e. the only
relations are 1 − 2 − 3 − . . . − (n − 1) − n − 1. Show that ρ := (1, 2, . . . , n) ∈
Aut(Γ). Show that τ = (2, n)(3, n−1) . . . ∈ Aut(Γ). (For example if n = 6
then τ = (2, 6)(3, 5), if n = 7 then τ = (2, 7)(3, 6)(4, 5)). Show that
i. Show that an element of G respect the parallelism, i.e. sends two parallel
lines onto two parallel lines.
ii. For c ∈ R>0 , let hc : R2 −→ R2 be defined by hc (x, y) = (cx, y). Show
that hc ∈ G and that the set H := {hc : c ∈ R>0 } is a group under composition.
iii. For d ∈ R define ud : R2 −→ R2 by ud (x, y) = (x + dy, y). Show that
ud ∈ G and that the set U := {td : d ∈ R} is a group under composition.
iv. For a bijection phi : R −→ R satisfying the properties φ(x + y) =
φ(x) + φ(y), φ(xy) = φ(x)φ(y) and φ(1) = 1, define the map αφ : R2 −→ R2
by αφ (x, y) = (φ(x), φ(y)). Show that αφ ∈ G and that the set A := {αφ :
φ as above} is a group under composition.
v. Show that for any g ∈ G there is a unique (a, b) ∈ R2 such that such that
(τa,b ◦ g)(0, 0) = (0, 0).
vi. Show that for any g ∈ G such that g(0, 0) = (0, 0) there is there is a
unique θ ∈ [0, 2π) such that (ρθ ◦ g)(0, 0) = (0, 0) and (ρθ ◦ g)(1, 0) is on the
positive side of the x-axis.
vii. Show that for any g ∈ G such that g(0, 0) = (0, 0) and g(1, 0) is on the
positive side of the x-axis, there is a unique c ∈ R>0 such that (hc ◦ g)(0, 0) =
(0, 0) and (hc ◦ g)(1, 0) = (1, 0).
viii. Show that for any g ∈ G such that g(0, 0) = (0, 0) and g(1, 0) = (1, 0)
there is a unique d ∈ R such that (ud ◦ g)(0, 0) = (0, 0), (ud ◦ g)(1, 0) = (1, 0)
and (ud ◦ g)(0, 1) = (0, 1).
ix. Show that if g ∈ G satisfies g(0, 0) = (0, 0), g(1, 0) = (1, 0) and
g(0, 1) = (0, 1), then g ∈ A. (Hint: Express the addition and multiplication
of real numbers geometrically and use part (i)).
x. Show that for any g ∈ G there are unique (a, b) ∈ R2 , θ ∈ [0, 2π),
c ∈ R>0 , d ∈ R and bijection phi : R −→ R satisfying the properties φ(x + y) =
φ(x)+φ(y), φ(xy) = φ(x)φ(y) and φ(1) = 1, such that g = τ(a,b) ◦ρθ ◦hc ◦ud ◦αφ .
The group G is called the affine transformations of R2 .
Problem 7.3.4 On R2 define the metric d((x, y), (z, t)) := |z − x| + |t − y|. Let
G be the group of isometries of this metric. Find the elements of G.
Problem 7.3.5 On R2 define the metric d((x, y), (z, t)) := max(|z − x|, |t − y|).
Let G be the group of isometries of this metric. Find the elements of G.
Formulae
∧, ¬, ∃, (, ), =, ∈, v0 , v1 , v2 , v3 , . . .
These symbols – although do have an intended meaning – do not have a
meaning. They are only symbols and nothing more.
The formulae will be certain “words” in this alphabet, i.e. a finite string of
symbols written only using these symbols.
69
70 CHAPTER 8. FORMULAE
Chapter 9
Miscellaneous Exercises
71
72 CHAPTER 9. MISCELLANEOUS EXERCISES
Part II
73
Chapter 10
Basics
Y := {x ∈ X : x 6∈ x}.
∀x (x ∈ Y ⇐⇒ x 6∈ x).
Since Y is a set, the formula above – that holds for all sets x – should also
hold for Y . Replacing x by Y we get:
Y ∈ Y ⇐⇒ Y 6∈ Y.
In English this translates as follows: Y is an element of itself if and only if it
is not an element of itself. This is certainly a contradiction, and a contradiction
in set theory, the basis of all mathematics, therefore of all sciences... This is
very serious, and one cannot just ignore it.
Russell’s Paradox changed the way mathematicians looked at mathematics;
from naive mathematicians – that believed naively that any collection could be
a set – they turned into more careful creatures.
A careful analysis of the above paradox (like the one a careful creature
would carry out) reveals that the acceptance of the collection of all sets as a set
is the source of the problem. The collection of all sets is certainly something, a
75
76 CHAPTER 10. BASICS
“collection” for example, but is not allowed to be a set itself. Something that
contains all sets cannot – or should not be – a set, because otherwise we arrive
at a contradiction...
What to do?
The solution is the following: be much more careful before naming something
a set. Set the rules for something to be a set and insure that each naive set is
really a set, i.e. that it passes the test of being a set.
The experience shows that collections which are too large cause problems.
Therefore our test should exclude too large collections from being sets. The
easiest way to avoid big collections from being sets is to start from the smallest
of all sets, the emptyset, and to construct the other sets step by step from the
emptyset, by taking the unions, the intersections, the products, the “set” of
subsets of the previously constructed sets to construct new sets. By doing so,
one should never have enough time to arrive at large collections for them to
be sets. For example, if the steps never end, if after each step we can take
the next step to invent new sets, during this procedure, we will never meet the
collection of all sets. This is the idea behind Russell’s theory of types as well as
the Zermelo-Fraenkel set theory that we will expose in this book.
∃x∀y y 6∈ x.
Now the following question arises: How many sets without elements are
there? We would like to say that there is only one set without elements. This
would be saying that the set of humans with five heads on their shoulders is equal
to the set of apple trees of 3000 meters long, since both sets are - presumably -
empty.
To prove that there is only one set with no elements, we assume that x and
y are two sets with no elements and we proceed to show that x = y. But since
we do not know the meaning of the equality of two sets, we cannot proceed!
The second axiom will tell us exactly when two sets are equal.
10.2. EASY AXIOMS 77
A2. Equality. Two sets which have the same elements are equal.
Formally this axiom is written as
Proof: By A1 we know that there is at least one set without elements. Let
x and y be “two” sets without elements. Assume that x 6= y. Then by A2,
there is an element in one of them which is not in the other. But this is absurd
because none of the sets can have elements. Thus it is not true that x 6= y.
Hence x = y. ¤
The statement of the theorem can be written as follows:
The unique set without elements is called emptyset and is denoted by the
symbol ∅.
We will use the symbol ∅ in our formal formulas as an abbreviation.
We prove
√ a statement which is not supposed to make any sense at this point
(because 2 is not defined yet):
√
Theorem 10.2.2 For any x ∈ ∅, x = 2.
√
Proof: Assume not. Then ∅ contains an element which is not equal to 2.
But this is absurd because ∅ does not contain any elements at all! ¤
What saves us from a contradiction in the statement above is that emptyset√
has no elements. But if it had one, this element would have to be equal to 2,
and as you must have guessed to π as well. √Fortunately ∅ has no elements and
we do not get a contradiction of the form “ 2 = π”.
A set x is called a subset of another set y if any element of x is an element
of y. We then write x ⊆ y.
Formally we write this as
x ⊆ y ⇐⇒ ∀z(z ∈ x → z ∈ y).
We use the symbol ⇐⇒ as an abbreviation for the English phrase “if and
only if”, while the symbol ↔ is used as a mathematical symbol.
To prove that x is a subset of y we need to prove that x and y are sets and
that every element of x is an element of y.
Clearly every set is a subset of itself. Formally ∀x x ⊆ x.
A3. Definable Subsets. Let x be a set and φ(y) a “property”. Then there
is a set whose elements are exactly the elements of x that satisfy the property φ.
We will be unprecise about the meaning of the word “property”. The reader
should only be aware that “properties” are given by finite formulas that involve
only the mathematical symbols
∀, ∃, ∧, ∨, →, ⇐⇒ , (, ), =, ¬,
the abbreviations like ∅ and ⊆, variables like x, y and z and constants (param-
eters, the existing sets).
By A2, given x and φ, the set as in A3 is unique. We denote this set as
{y ∈ x : φ(y)}.
Using this axiom we can prove that the intersection of two sets is a set.
Theorem 10.2.5 If x and y are sets then there is a set whose elements are
exactly the common elements of x and y.
Proof: Let φ(z) be z ∈ y. Use A3 to see that {z ∈ x : φ(z)} is a set. This set
is exactly the set of common elements of x and y. ¤
By A2, given x and y, the set given in Theorem 10.2.5 is unique. We call
this set the intersection of x and y and we denote it by x ∩ y.
Thus z ∈ x ∩ y ⇐⇒ (z ∈ x) ∧ (z ∈ y).
Axiom A3 allows us to prove that the difference of two sets is a set:
Theorem 10.2.6 If x and y are sets then there is a set whose elements are
exactly the elements of x which are not in y.
Proof: Let φ(z) be z 6∈ y. Use A3 to see that {z ∈ x : φ(z)} is a set. This set
is exactly the set of elements of x which are not in y. ¤
By A2, given x and y, the set given in Theorem 10.2.6 is unique. We denote
this set by x \ y. It can be called “x minus y”.
Now we prove that a certain collection cannot be a set:
10.2. EASY AXIOMS 79
Theorem 10.2.7 (Bertrand Russell) There is no set that contains all sets
as elements.
Proof: Assume not. Let x be a set that contains all sets as elements. Let φ(y)
be “y 6∈ y” Consider the set
z := {y ∈ x : φ(y)} = {y ∈ x : y 6∈ y}.
y ∈ z ⇐⇒ y 6∈ y.
Since the above statement holds for any set y and since z is a set, we may replace
y of the formula above by z:
z ∈ z ⇐⇒ z 6∈ z.
This is a clear contradiction. Thus x is not a set, or the set of all sets does not
exist. ¤
At this point we cannot prove that the union of two sets is a set. We need
the following axiom for this.
A4. Union of Two Sets. If x and y are two sets, then there is a set whose
elements are exactly the elements that are in either x or y. By A2 such a set is
unique. It is called the union of x and y and is denoted by x ∪ y.
(x \ y) \ z = x \ (y ∪ z)
y ∪ (x \ y) = x ∪ y
With the first four axioms in hand, we can only be sure of the existence of
∅, indeed:
1) The first axiom tells us that emptyset exists.
2) The second axiom cannot be used to create new sets.
3) The new sets obtained by A3 are subsets of the old sets. Thus, starting
from ∅, we cannot obtain new sets using A3.
4) If x and y are emptysets, the new set obtained using A4 is also emptyset,
hence not new.
Another way of seeing this is by noticing that the universe that contains
only emptyset as a set satisfies all four axioms.
Now we will adopt a new axiom that will allow us to define new sets.
80 CHAPTER 10. BASICS
A5. Sets with One Elements. If x is a set, then there is a set which has
only x as an element.
We write this set as {x}.
Now, starting from ∅, we can obtain new sets:
∅
{∅}
{{∅}}
{{{∅}}}
...
These sets have only one element. Such sets are called singleton sets. A set
whose elements are x and y is denoted by {x, y}. If we can name all the elements
of a set one by one and enumerate them as a1 , . . . , an , then we will denote this
set by {a1 , . . . , an }.
Using A4, we can obtain sets with more than one element:
{∅} ∪ {{∅}} = {∅, {∅}}
{∅, {∅}} ∪ {{{∅}}} = {∅, {∅}, {{∅}}}
0 := ∅.
S(x) = x ∪ {x}.
By using our axioms and results we can form sets that contain any finite number
of these sets. For example, {0, 3} is a set because
{0, 3} = 1 ∪ (4 \ 3).
To prove that {0, 3} is a set we can also use A3 with x = 4 and φ(y) as “y =
0 ∨ y = 3”.
Although we now have sets with as many elements as we wish, we are still
not sure that there are sets with infinitely many elements. For example, we do
not know that yet that there is a set that contains 0, 1, 2, 3, 4,... In fact, we
cannot prove yet that there is such a set. We need a new axiom for this. Before
creating sets with infinitely many elements, we will state a few more axioms and
we will define some basic notions of set theory.
10.3. SLIGHTLY MORE COMPLICATED AXIOMS 81
A50 . Sets with Two Elements. If x and y are sets then there is a set whose
elements are only x and y.
We denote this set as {x, y} of course. By taking x = y in A50 , we see
that A5 is a consequence of A50 , therefore we can erase A5 from the list of our
axioms. Also, as we have noticed A4 is a consequence of A40 and A50 , and we
can also erase A4 from our list.
Lemma 10.3.1 ∪∅ = ∅.
Proof: By definition, for any set x, z ∈ ∪x if and only if there exists a y ∈ x
such that z ∈ y. Apply this to x = ∅: z ∈ ∪∅ if and only if there exists a y ∈ ∅
such that z ∈ y. Thus ∪∅ cannot have an element. ¤
We can also form the intersection of all sets which are the elements of a
given set:
Theorem 10.3.2 Let x be a set. Then there is a set whose elements are exactly
the elements of ∪x which are elements of all the elements of x.
Proof: Let φ(z) be “∀y(y ∈ x → z ∈ y)”. Now use A3: {z ∈ ∪x : φ(z)} is the
set we are looking for. ¤
This set is denoted by ∩x or ∩y∈x y. Thus
z ∈ ∩x ⇔ ∀y (y ∈ x → z ∈ x).
A6. Power Set. If x is a set then there is a set whose elements are exactly
the subsets of x.
We denote this set with the symbol ℘(x) and call it the power set of x.
Thus
y ∈ ℘(x) ⇐⇒ y ⊆ x.
For example if x = 2 = {0, 1}, then
Proof: See Exercise xxi, page 15. The second part follows also from Exercise
vi, page 83. ¤
Lemma 10.4.2 Let X and Y be two sets. Then there is a set X × Y whose
elements are exactly the ordered pairs (x, y) for x ∈ X and y ∈ Y .
form (x, y) by a formula φ(z), i.e. by a property. In other words, we will find a
formula φ(z) such that for all z, the following will hold:
X × Y = {z ∈ ℘(℘(X ∪ Y )) : φ(z)},
In this ”formula”, the strings t = {x} and u = {x, y} are still nonacceptable.
We replace t = {x} by x ∈ t ∧ ∀s (s ∈ t → s = x). And we replace u = {x, y} by
x ∈ u ∧ y ∈ u ∧ ∀s (s ∈ u → (s = x ∨ s = y)). After doing all these replacements,
we get φ(z), a legitimate formula. ¤
Exercises.
i. Find X × ∅.
iv. Find ∪ ∪ 4.
vi. Show that ∩∩(x, y) = x. Show that y = (∪∪(x, y)\∩∩(x, y))∪(∩∪(x, y)).
ix. Find a formula φ(Z, T ) such that φ(X × Y, T ) holds if and only if T = X.
Find a formula ψ(Z, T ) such that φ(X × Y, T ) holds if and only if T = Y .
84 CHAPTER 10. BASICS
10.5 Functions
In naive set theory, a function f from a set X into a set Y is a rule that assigns
to each element x of X a unique element f (x) of Y . The graph of a function is
the set of pairs (x, y) such that x ∈ X, y ∈ Y and y = f (x).
Since everything should be a set in set theory, we may attempt to define a
function as its graph, hence as a subset F of X × Y with the property that for
every x ∈ X there is a unique y ∈ Y such that (x, y) ∈ F . This attempt is not
too far from the accepted definition of a function. We also need the sets X and
Y in the definition.
Given a function f : X −→ Y , we can extend the set Y to a larger set Y1
to get another function f1 : X −→ Y1 : For each x ∈ X, just let f1 (x) = f (x).
Although the two functions f and f1 take the same values with the same input,
we would like to differentiate them, they should be two different functions. But
this is impossible if we define a function only as its graph. So, rather than
defining a function as its graph, we will define a function as a triple (F, X, Y )
where F ⊆ X ×Y will be the graph of the function. Here is the formal definition:
Let X and Y be two sets. A function or a map is a triple (F, X, Y ) with
the following properties:
i. F is a subset of X × Y .
ii. For each x ∈ X there is a unique y ∈ Y such that (x, y) ∈ F .
The set X is called the domain and the set Y is called the set of arrival
of the function. The set F is called the graph of the function.
In fact we do not need the domain X in the definition of a function, because
given a graph F ⊂ X × Y , the set X can be found back as follows: First of
all note that ∪ ∪ F = X ∪ Y . Now X = {x ∈ ∪ ∪ F : (x, y) ∈ G for some y}.
Given a a set F , we define π1 (F ) as the set {x ∈ ∪ ∪ F : (x, y) ∈ F for some y}.
Clearly π1 (G) is a set. With this notation in hand, a reformed definition of a
graph may be read as follows:
A function or a map is a pair (F, Y ) such that
i. F ⊆ pr1 (F ) × Y ,
ii. For each x ∈ pr1 (F ) there is a unique y ∈ Y such that (x, y) ∈ F .
If f = (F, Y ) is a function, given x ∈ pr1 (F ) the unique element y of Y for
which (x, y) ∈ F is denoted by f (x)
It may happen that we are not so much interested in Y , in which case we
drop Y from the notation and we only say that f is a function (from X into Y ).
If (f, Y ) is a function and (x, y) ∈ f , we write y = f (x).
If (f, Y ) is a function from X into Y , we very often denote this fact as
f : X −→ Y . The “rule” f may be made explicit by the notation x 7→ f (x).
When we say that f : X −→ Y is a function, we assume implicitly that X
and Y are sets and that X 6= ∅.
Very often the condition (ii) is easily checked. Condition (i) may be more
tedious to check. One should not forget to prove (at this beginning stage of our
mathematical education) that f is a set. The fact that f is a subset of X × Y
will then be clear most of the time.
10.5. FUNCTIONS 85
Proof: We need to check condition (i) of the definition. For this we just need
to show that the diagonal
δ(X) := {(x, x) : x ∈ X}
The first two conditions imply y = y1 , and now, the last two conditions imply
z = z1 . ¤
The function g ◦ f : X −→ Z is called the composition of f and g.
Exercises.
i. Let X and Y be two sets. Show that there is a set whose elements are
exactly the functions from X into Y . We denote this set by X Y .
X
ii. Find ∅.
iii. Show that if we allowed X to be emptyset in the definition of a function
from X into Y , then ∅ Y would be the set of all sets.
iv. Let X be a set. Let π1 (X) := {x : fo some y, (x, y) ∈ X}. Show that
π1 (X) is a set.
v. Let X and Y be sets. Show that pr1 : X × Y −→ X given by pr1 (x, y) = x
and pr2 : X × Y −→ Y given by pr1 (x, y) = y are functions. These are
called first and second projections.
vi. Let f : X −→ Y be a function.
For A ⊆ X, show that f (A) := {f (a) : a ∈ A} is a set. It is called the
image of A under f . The set f (X) is called the image of f .
For two subsets A and B of X show that f (A∪B) = f (A)∪f (B) and that
f (A ∩ B) ⊆ f (A) ∩ f (B). Show that the equality in the second formula
does not always hold.
vii. Let X and Y be two sets.
a) Show that there is a set whose elements are bijections from X into Y .
b) Show that there is a set whose elements are injections from X into Y .
c) Show that there is a set whose elements are surjections from X into Y .
Natural Numbers
87
88 CHAPTER 11. NATURAL NUMBERS
11.2 Well-ordering on ω
A well-ordered set is a linear order with the property that every nonempty
subset has a least element. In this subsection, we will show that ω is a well-
ordered set with respect to the relation ∈.
Exercises.
Theorem 11.4.3 2 + 2 = 4.
Proof: This is clear if z = 0. Assume the result for z. Assume also that
x + S(z) = y + S(z). Then S(x + z) = S(y + z). Since S is one to one, this
implies that x + z = y + z. By induction x = y. ¤
Proof: If x = 0, then this is just Lemma 11.4.5. Assume the result for x. Then
by Lemma 11.4.7 and induction, S(x) + y = x + S(y) = S(x + y) = S(y + x) =
y + S(x). ¤
92 CHAPTER 11. NATURAL NUMBERS
Exercises.
Theorem 11.5.2 2 × 2 = 4.
Proof: We directly compute using definitions and the previous results about
addition: 2 × 2 = 2 × S(1) = 2 × 1 + 2 = 2 × S(0) + 2 = (2 × 0 + 2) + 2 =
(0 + 2) + 2 = 2 + 2 = 4. ¤
Proof: This follows from the definition of the multiplication and Lemma 11.4.5:
x1 = xS(0) = x0 + x = 0 + x = x. ¤
Exercises.
Exercises.
i. Let x ∈ N. Show that there is no y ∈ N such that x < y < S(x).
ii. Show that x + x = 2 × x for all x ∈ N.
iii. Show that 2N ∩ (2N + 1) = ∅.
iv. Show that if the structure (N1 , S1 , 01 ) satisfies the Peano Axioms, then
(N1 , S1 , 01 ) ' (N, S, 0) and the isomorphism is unique.
v. Show that given x, y ∈ N, y ∈ N, if x < y then S(x) ≤ y.
Proof: Since x < y, there is an a ∈ N \ {0} such that x + a = y. By
hypothesis a 6= 0. Thus a = S(b) for some b. Thus y = x + a = x + S(b) =
S(x) + b by Lemma 11.4.7 and so S(x) ≤ y. ¤
96 CHAPTER 11. NATURAL NUMBERS
vii. Show that the ordering < defined in this section is the same as the relation
∈. I.e. show that for x, y ∈ N, x > y if and only if x ∈ y.
Given a finite set A, the natural number n as in the definition is unique as the
next lemma shows:
It is easy to check that g is a bijection. Now the map g ◦ f|n is a bijection from
n onto k. By induction n = k, and so n + 1 = S(n) = S(k) = m. ¤
Thus if A is a finite set, then there is a unique natural number n such that
A and n are in bijection. We set |A| = n and call n the cardinality of A.
Exercises.
i. Show that if A and B are finite sets with |A| = n and |B| = m, then
|A ∪ B| ≤ n + m.
11.9 Powers
Corollary 11.9.1 There is a unique map f : N×N\{(0, 0)} such that f (n, 0) =
1 for all n 6= 0, f (0, 1) = 0 and f (n, m + 1) = f (n, m)n for all n, m ∈ N.
We let f (n, m) = nm .
Lemma 11.9.2 For all a, b, c ∈ N for which the operations below are defined,
ab+c = ab ac , (ab )c = abc .
Lemma 11.9.3 Let X be the set of finite subsets of N × N. Then there is a
unique function f : X −→ N such that
f (∅) = 1
and
f ({(n1 , m1 ), . . . , (nk , mk )}) = f ({(n1 , m1 ), . . . , (nk−1 , mk−1 )})nm
k .
k
We let
f ({(n1 , m1 ), . . . , (nk , mk )}) = nm mk
k . . . nk .
k
Exercises.
i. Let X be the set of finite subsets of N. Show that there is a unique function
f : X −→ N such that
f (∅) = 0
and
f ({n1 , . . . , nk }) = f ({n1 , . . . , nk−1 }) + nk .
11.10 Divisibility
Theorem 11.10.1 (Division) Let a, b ∈ N. Assume b 6= 0. Then there are
unique q, r ∈ N such that a = bq + r and r < b.
Proof: We proceed by induction on a to show the existence. If a < b, we can
let q = 0 and r = a. Assume a ≥ b. Let c be such that a = b + c. Since c < a,
by induction there are q1 and r such that c = bq1 + r and r < b. Now, we have,
a = b + c = b + bq1 + r = b(1 + q1 ) + r. We let q = 1 + q1 . This proves the
existence.
Now we prove the uniqueness. Assume bq + r = bq1 + r1 and r < b, r1 < b.
If q = q1 , then, by simplifying we get r = r1 . Assume q 6= q1 . We may assume
without loss of generality that q < q1 . Let p > 0 be such that q + p = q1 . Then
bq + r = bq1 + r1 = b(q + p) + r1 = bq + bp + r1 , so r = bp + r1 ≥ bp ≥ b, a
contradiction. ¤
We say that a natural number a divides another natural number b if ac = b
for some c ∈ N. We then write a|b. Note that all natural numbers divide 0, but
that only 1 divides 1. Note also that 1 divides all natural numbers.
98 CHAPTER 11. NATURAL NUMBERS
Theorem 11.10.6 (Euclid) The set of prime numbers is infinite (i.e. there
are infinitely many prime numbers).
Proof: Suppose that there are only n prime numbers. Call them p1 , . . . , pn .
Consider the number k = p1 . . . pn + 1. By Proposition 11.10.3, some prime
number pi for i = 1, . . . , k divides k. Since pi divides the product p1 . . . pn + 1,
by Lemma 11.10.4, pi divides 1, a contradiction. ¤
Lemma 11.10.8 Let p1 < . . . < pr and q1 < . . . < qs be two finite sets of
prime numbers. Let n1 , . . . , nr and m1 , . . . , ms be natural numbers. Assume that
pn1 1 . . . pnr r = q1m1 . . . qsms . Then r = s, pi = qi and ni = mi for all i = 1, . . . , r.
Exercises.
iv. Analyzing carefully the inductive nature of Theorem 11.10.1, write a com-
puter program that knows how to divide a natural number into another
(nonzero) natural number. Hint: See Exercise i, 92 and Exercise i, 94.
100 CHAPTER 11. NATURAL NUMBERS
11.11 Uniqueness of N
In this subsection, we show that if (N1 , S1 , O1 ) is a structure satisfying the
Peano’s Axioms (defined below), then there is a (unique) bijection f : N −→ N1
such that f (S(x)) = S(f (x)) and f (0) = 01 for all x ∈ N. This will show that a
structure satisfying Peano’s Axioms is unique “up to isomorphism”. We make
this more precise:
Let N0 be a set, S 0 : N0 −→ N0 a function and 00 ∈ N0 an element. Suppose
that the triple (N0 , S 0 , 00 ) satisfies the following:
PA1. S 0 is a one to one function from N0 into N0 .
PA2. If X is a subset of N0 with the property that
a) 00 ∈ X,
b) For all x ∈ X, S 0 (x) ∈ X,
then X = N0 .
Then we say that the triple (N0 , S 0 , 00 ) satisfies the Peano axioms. Of course,
for a triple that satisfies the Peano axioms, all the results of the previous sections
xxx hold.
Theorem 11.11.1 Any two triples (N0 , S 0 , 00 ) and (N00 , S 00 , 000 ) satisfying the
Peano Axioms are “isomorphic”, i.e. there is a bijection f : N00 −→ N0 such
that f (000 ) = 00 and f (S 00 (x)) = S 0 (f (x)) for all x ∈ N00 .
Proof: Since the composition and the inverse of isomorphisms is clearly an
isomorphism, we may suppose that (N00 , S 00 , 000 ) = (N, S, 0). Define f : N −→ N0
by the rule,
f (0) = 00
and
f (S(x)) = S 0 (f (x)).
By Theorem 11.8.1 f is a function. We just need to prove that it is one to one
and that it is unique.
We first show that f is one to one. Assume f (x) = f (y). We will show that
x = y. We proceed by induction on x.
Assume x = 0. Then f (y) = 00 . If y 6= 0, then y = S(x1 ) and so 00 = f (y) =
f (S(x1 )) = S 0 (f (x1 )), contradicting the fact that 00 is not in the range of S 0 .
Thus y = 0 = x.
Assume now x 6= 0. Then x = S(x1 ). So S 0 (f (x1 )) = f (S(x1 )) = f (x) =
f (y). In particular f (x) and f (y) are nonzero. Therefore y 6= 0 as well. Let
y = S(y1 ). Then S 0 (f (x1 )) = f (y) = f (S(y1 )) = S 0 (f (y1 )). Since S 0 is one to
one, it follows that f (x1 ) = f (y1 ). By the inductive hypothesis x1 = y1 . Hence
x = S(x1 ) = S(y1 ) = y. This proves that f is one to one.
We now show that if f 0 is another such function then f = f 0 . By assump-
tion f (0) = 00 = f 0 (0). Assume f (x) = f 0 (x). Then f (S(x)) = S 0 (f (x)) =
S 0 (f 0 (x)) = f 0 (S(x)). This proves that f = f 0 . ¤
Chapter 12
Integers
(x, y) ≡ (z, t) ⇐⇒ x + t = z + y.
(x, y) ≡ (z, t) ⇐⇒ x + t = z + y
is an equivalence relation.
101
102 CHAPTER 12. INTEGERS
Proof: It is clear that (x, y) ≡ (x, y). It is also clear that if (x, y) ≡ (z, t) then
(z, t) ≡ (x, y). It remains to prove the transitivity. Assume (x, y) ≡ (z, t) and
(z, t) ≡ (u, v). Thus x + t = z + y and z + v = u + t. Adding these two equalities
term by term, we get,
(x + t) + (z + v) = (z + y) + (u + t).
Using the associativity and the commutativity of the addition, we get,
x + v + t + z = u + y + z + t.
Simplifying, we find x + v = u + y, i.e. (x, y) ≡ (u, v). ¤
Now we are ready to define the set Z of integers:
Z := N × N/ ≡ .
Note that
(0, 0) ≡ (1, 1) ≡ (2, 2) . . .
(1, 0) ≡ (2, 1) ≡ (3, 2) . . .
(0, 3) ≡ (1, 4) ≡ (2, 5) . . .
The class of (0, 0) will stand for 0, the class of (1, 0) will stand for 1 and the
class of (0, 3) will stand for −3, but not now, in due time.
and
(z, t) = (z1 , t1 ),
but that
(x + z, y + t) 6= (x1 + z1 , y1 + t1 ),
in which case we are not allowed to define the addition of (x, y) and (z, t) as
(x + z, y + t), because this definition depends not on the equivalence classes
(x, y) and (z, t), but on the choice of the elements (x, y) and (z, t). Fortunately,
this problem does not occur, all that should work does work:
Proof: Assume (x, y) = (x1 , y1 ) and (z, t) = (z1 , t1 ). Thus (x, y) ≡ (x1 , y1 )
and (z, t) ≡ (z1 , t1 ), i.e.
x + y1 = x1 + y and z + t1 = z1 + t.
x + z + y1 + t1 = x1 + z1 + y + t,
which means exactly that (x+z, y+t) ≡ (x1 +z1 , y1 +t1 ) i.e. that (x + z, y + t) =
(x1 + z1 , y1 + t1 ).
ii. Take the first equality as it is and reverse the second one:
(∗) x + y1 = x1 + y and z1 + t = z + t1 .
xz + yt + x1 t1 + y1 z1 = x1 z1 + y1 t1 + xt + yz.
We will eliminate y1 and t1 from the above equality and arrive at a known
equality. Then, going backwards, the equality will be proven.
The quantities y1 and t1 occur four times, twice on the left, twice on the
right. It is easy to deal with the ones on the left where they appear linearly. It
is slightly harder to get rid of the ones at the right hand side where they appear
as a product. We first deal with the right hand side. We add xz + xt1 + zy1
to both sides: (xz + yt + x1 t1 + y1 z1 ) + (xz + xt1 + zy1 ) = (x1 z1 + y1 t1 +
xt + yz) + (xz + xt1 + zy1 ) = (x1 z1 + xt + yz) + (xz + xt1 + zy1 + y1 t1 ) =
104 CHAPTER 12. INTEGERS
Now there is no more y1 nd t1 left on the right hand side. Now we deal with
the left hand side. We add x1 z, xz1 and 2zx to both sides, factor out x1 and
z1 from the left hand side and use the known equalities (*): (2x1 z1 + xt + yz +
x1 t + yz1 ) + x1 z + xz1 + 2zx = (2xz + x1 t1 + y1 z1 + xt1 + zy1 ) + x1 z + xz1 + 2zx =
2xz + x1 (t1 + z) + (y1 + x)z1 + x(t1 + z) + z(x + y1 ) = 2xz + x1 (t + z1 ) + (y +
x1 )z1 + x(t + z1 ) + z(x1 + y) = 2xz + x1 t + x1 z1 + yz1 + x1 z1 + xt + xz1 + zx1 + zy,
i.e. 2x1 z1 + xt + yz + x1 t + yz1 + x1 z + xz1 + 2zx = 2xz + x1 t + x1 z1 + yz1 +
x1 z1 + xt + xz1 + zx1 + zy. Simplifying, we see that this last equality holds.
Now, we can go backwards. ¤
At this point, we can define the three operations +, − and × on Z as above,
i.e.
Exercises.
α−β = α + (−β)
−(α − β) = −α + β
−(−α + β) = α−β
−(−α − β) = α + β.
12.3 Ordering on Z
We would like to define the ordering on Z as follows: For (x, y), (z, t) ∈ Z,
But for this definition to make sense, we need to prove the following result:
Lemma 12.3.1 Assume (x, y) ≡ (x1 , y1 ) and (z, t) ≡ (z1 , t1 ). Assume that
x + t < z + y. Then x1 + t1 < z1 + y1 .
(1) x + y1 = x1 + y
(2) z + t1 = z1 + t
(3) x+t<z+y
We have to prove that x1 + t1 < z1 + y1 . We compute using (1), (2) and (3):
x1 + y + t1 + z = x + y1 + z1 + t = z + y + y1 + z1 ,
Exercises.
ii. Show that 1 × α = α for all α ∈ Z. (Here 1 stands for the element
i(1) = (1, 0) of Z).
iii. Show that −1 × α = −α for all α ∈ Z. (Here −1 stands for the element
−i(1) = (0, 1) of Z).
iv. Show that 2 × α = α + α for all α ∈ Z. (Here 2 stands for the element
i(2) = (2, 0) of Z).
(α + β) + γ = ((x + x1 ) + x2 , (y + y1 ) + y2 )
and
α + (β + γ) = (x + (x1 + x2 ), y + (y1 + y2 )).
The equality is now clear.
ii, iii, iv. Easy. ¤
We now define the following terms:
−x + y := (−x) + y
−x − y := (−x) + (−y) = (−x) − y
−(x − y) = −x + y
−(−x + y) = x−y
−(−x − y) = x+y
Absolute Value. For α ∈ Z, we define |α| = max{α, −α}. We call |α|, the
absolute value of α.
12.8. DIVISIBILITY AND SUBGROUPS 109
Lemma 12.8.3 For any a, b ∈ Z, gcd(a, b) exists and there are x, y ∈ Z such
that ax + by = gcd(a, b).
Proof: Replacing a and b by |a| and |b|, we may assume that a ≥ 0 and b ≥ 0.
Existence. Since 1 divides both a and b and since any number that divides
both a and b can be at most max(a, b) > 0, the set of natural numbers that
divide both a and b is a finite nonempty set bounded by max(a, b). Therefore
there is a largest such number. This proves the existence of gcd(a, b). We let
d = gcd(a, b).
Second Part. We proceed by induction on max(a, b). If a = 1, then take
x = 1, y = 0. If b = 1, then take x = 0, y = 1. This takes care of the initial
step max(a, b). Assume max(a, b) > 1. If a = b, then d = a and we may take
x = 1, y = 0. Assume a 6= b. Without loss of generality, we may assume that
a > b. Note that the divisors of a and b are the same as the divisors of a − b
and b. Hence gcd(a − b, b) = gcd(a, b) = d. Since max(a − b, b) < a = max(a, b),
by induction there are two integers x and y 0 such that x(a − b) + y 0 b = d, i.e.
xa + (y 0 − x)b = d. Take y = y 0 − x. ¤
12.8. DIVISIBILITY AND SUBGROUPS 111
Let a and b be two nonzero integers. We say that m is the least common
multiple of a and b if m is the least natural number that is divisible by both a
and b.
Lemma 12.8.4 For any a, b ∈ Z\{0}, lcm(a, b) exists and ab = ± gcd(a, b) lcm(a, b).
Proof: Replacing a and b by |a| and |b| again, we may assume that a > 0 and
b > 0. Since a and b both divide ab, lcm(a, b) exists.
Let d = gcd(a, b) and m = lcm(a, b). Let a0 and b be such that a = da0 and
b = db0 . Then ab = d2 a0 b0 . We need to prove that m = da0 b0 .
Since da0 b0 = ab0 = a0 b, a and b both divide da0 b0 .
Let x be divisible by both a and b. Then x = au = bv for some u, v. We
have a0 du = au = x = bv = b0 dv and so a0 u = b0 v. Since a0 and b0 cannot have
a common divisor (otherwise d would be larger), b0 must divide u. (This last
fact needs a serious proof, that we have not undertaken yet. I should
put this somewhere else). Write u = cb0 . Now x = au = acb0 = a0 dcb0 and
so a0 b0 d divides x, in particular a0 b0 d ≤ x. This shows that a0 b0 d is the least
multiple of a and b, i.e. a0 b0 d = m.
There is another way to define gcd and lcm, which is more modern and better
in several ways. If (Hi )i is any family of subgroups of Z, then it is clear that
∩i Hi is also a subgroup of Z. In particular, for any n, m ∈ Z, nZ ∩ mZ = kZ
for some unique k ∈ N. Since nZ ∩ mZ is the largest subgroup contained in nZ
and in mZ, it is clear that k is the smallest natural numbers that is a multiple
of both n and m. We call k the least common multiple of n and m and we
let lcm(n, m) = k.
If (Hi )i is any family of subgroups of Z, then it is clear that
X
Hi = {hi1 + . . . + hik : k ∈ N and hij ∈ Hij for all j = 1, . . . , k}
i
and Y
gcd(n, m) = pmin{ordp (n),ordp (m)} .
p
In particular,
Q min{ordp (n),ordp (m)}+min{ordp (n),ordp (m)}
lcm(n, m) gcd(n, m) = p
Qp ordp (n)+ordp (m) Q ordp (n) Q ordp (m)
= pp = pp pp = |nm|.
112 CHAPTER 12. INTEGERS
Thus we have:
Two integers are said to be prime to each other if they are both divisible
only by 1 and −1. In other words n and m are prime to each other if and only
if gcd(n, m) = 1.
Theorem 12.8.6 Two integers a and b are prime to each other if and only if
there are integers x and y such that ax + by = 1.
Exercises.
12.10 Quotients
The reader must have seen how to work “modulo n”. Here we set the founda-
tions.
For x ∈ Z and A ⊆ Z, we let
n + A = {n + a : a ∈ A}
12.11. CHINESE REMAINDER THEOREM 113
and
nA = {na : a ∈ A}.
Let H be a subgroup of Z. Thus H = nZ for some n ∈ N. Define the
following relation on Z:
x ≡n y ⇐⇒ x − y ∈ nZ ⇐⇒ n divides x − y.
x = {y ∈ Z : n divides x − y} = {y ∈ Z : x − y ∈ nZ}
= {y ∈ Z : y − x ∈ nZ} = {y ∈ Z : y ∈ x + nZ} = x + nZ.
Rational Numbers
115
116 CHAPTER 13. RATIONAL NUMBERS
iii. Transitivity. Let (x, y), (z, t), (u, v) ∈ X be such that (x, y) ≡ (z, t)
and (z, t) ≡ (u, v). Hence xt = yz and zv = tu. Multiplying these equalities
side by side, we get xtzv = yztu. Since t 6= 0, by simplifying we get xzv = yzu.
If z 6= 0, then we can simplify further to get xv = yu, hence (x, y) ≡ (u, v).
Assume z = 0. Then xt = yz = 0 and tu = zv = 0. Since t 6= 0, we get
x = u = 0, so that xv = 0 = yu and (x, y) ≡ (u, v) again. ¤
We let Q = Z × (Z \ {0})/ ≡. Now we show that the attempt to define the
four operations as above is successful:
Lemma 13.1.2 Let (x, y), (z, t), (x0 , y 0 ), (z 0 , y 0 ) ∈ Z×(Z\{0}). Assume (x, y) ≡
(x0 , y 0 ) and (z, t) ≡ (z 0 , t0 ). Then
i. (xt + yz, yt) ≡ (x0 t0 + y 0 z 0 , y 0 t0 ).
ii. (xt − yz, yt) ≡ (x0 t0 − y 0 z 0 , y 0 t0 ).
iii. (xz, yt) ≡ (x0 z 0 , y 0 t0 ).
iv. If z 6= 0, then z 0 6= 0 and (xt, yz) ≡ (x0 t0 , y 0 z 0 ).
Lemma 13.1.3 Let (x, y), (z, t), (x1 , y1 ), (z1 , y1 ) ∈ Z × (N \ {0}). Assume
(x, y) ≡ (x1 , y1 ), (z, t) ≡ (z1 , t1 ) and xt < yz. Then x1 t1 < y1 z1 .
α+β
Lemma 13.1.5 (Density.) For all α, β ∈ Q, if a < b then α < 2 < β.
Finally we embed Z in Q.
Proposition 13.1.6 Let i : Z −→ Q be the map defined by i(x) = (x, 1). Then
i is a one to one map and for all x, y ∈ Z,
i. i(x + y) = i(x) + i(y).
ii. i(xy) = i(x)i(y).
iii. x < y if and only if i(x) < i(y).
Furthermore, with our earlier convention, we have i(0) = 0 and i(1) = 1.
Also, for any α ∈ Q, there are x ∈ Z, y ∈ N \ {0} such that α = i(x)/i(y).
If we make the assumption that (x, y) = 1, then x and y are unique.
Proof: Easy. ¤
Now we identify Z with the subset i(Z) of Q. With this identification
Exercises.
Real Numbers
119
120 CHAPTER 14. REAL NUMBERS
Chapter 15
Well-Ordered Sets
Examples.
iii. Union – Addition. Let (X, <1 ) and (Y, <2 ) be two well-ordered sets.
Replacing X by X × {0} and Y by Y × {1}, and translating the orders
of X and Y onto these sets via the obvious maps, we may assume that
X ∩ Y = ∅. Now consider the set Z = X ∪ Y . Define the relation < on Z
as follows:
z, z 0 ∈ X and z <1 z 0
0
z < z ⇐⇒ z, z 0 ∈ Y and z <2 z 0
z ∈ X and z 0 ∈ Y
This relation well-orders Z. We will say that the ordered set is the disjoint
union of the ordered sets (X, <1 ) and (Y, <2 ) (in this order!) We will also
say for a while that Z is the sum of X and Y and we will write Z = X +Y .
121
122 CHAPTER 15. WELL-ORDERED SETS
iv. Lexicographic Ordering. Let (X, <1 ) and (Y, <2 ) be two well-ordered
sets. Consider the following relation on the set X × Y
½
0 0 y <2 y 0
(x, y) < (x , y ) ⇐⇒
y = y 0 and x <1 x0
This defines a well-ordering called lexicographic ordering on the Carte-
sian product X × Y .
Note that the lexicographic ordering on X × 2 is exactly the order defined
in the previous item when X = Y , i.e. X × 2 = X + X.
A nonempty well-ordered set X has a minimal element, say x0 . If X 6= {x0 },
then X \ {x0 } has also a minimal element, say x1 . Thus x1 is the element ”right
after” x0 . In other words x0 < x1 and if x0 < x then x1 ≤ x.
Let X be a well-ordered set, and let x ∈ X. Suppose x is the last element of
X, i.e. suppose that {y ∈ X : x < y} is not empty. Then this set has a (unique)
least element. We will call this element the successor of x and we will denote
it S(x).
An initial segment of a well-ordered set X is a subset I such that for all
a ∈ I and x ∈ X, if x < a then x ∈ I.
15.3 Morphisms
A morphism from a well-ordered structure (X, <1 ) into a well-ordered struc-
ture (Y, <2 ) is a map f : X −→ Y such that for all x, x0 ∈ X, x <1 x0 if and
only if f (x) <2 f (x0 ). Note that any morphism from a well-ordered set into
another must be a one to one map, because if f (x) = f (x0 ) we can neither have
x < x0 nor x0 < x. A morphism which is also onto is called an isomorphism
of well-ordered sets. An isomorphism from a well-ordered set into itself is called
an automorphism, but as we will soon see in this subsection a well-ordered
set has a unique automorphism, only the identity. It follows that there is at
most one isomorphism from a well-ordered set onto another, because if φ and ψ
are two such isomorphisms then ψ −1 ◦ φ is an automorphism, therefore by the
result that we have stated ψ −1 ◦ φ = Id, i.e. φ = ψ.
If two well-ordered sets X and Y are isomorphic, then we write X ' Y .
This is an equivalence relation on the class of all well-ordered sets.
Theorem 15.3.3 Given any two well-ordered sets, there is a unique embedding
of one into an initial segment of the other.
Proof: Uniqueness follows from Lemma 15.3.2. We will show the existence.
Let (X, <) and (Y, <) be two well-ordered sets. Consider the set = of all
initial segments of X that embed into an initial segment of Y . If A ∈ =, let fA
be the unique embedding of A into Y . Note that if A, B ∈ =, then one of A
or B is a subset of the other and if A ⊆ B, then fB is an extension of fA . By
Example vii, page 38, f := ∪A∈= fA is a function from Z := ∪A∈= A into Y . It is
easy to show that Z is an initial segment of X and that f is an embedding of Z
onto an initial segment of Y . Thus Z is a maximal element of =. If Z = X then
there is nothing more to do. If f (Z) = Y then f −1 is an embedding of Y onto
the initial segment Z of X. Assume Z 6= X and f (Z) 6= Y . Let x and y be the
least elements of X \ Z and Y \ f (Z) respectively. We can extend f to Z ∪ {x}
by sending x to y, we then obtain an embedding of the initial segment Z ∪ {x}
onto the initial segment f (Z) ∪ {y}. Thus Z ∪ {x} ∈ =. But this contradicts
the fact that Z is a maximal element of =. ¤
Exercises.
Ordinals
16.1 Definition
An ordinal is a well-ordered set X such that for all x ∈ X, (−∞, x) = x. Thus,
if α is an ordinal and x, y ∈ α, y < x if and only if y ∈ x. Therefore an ordinal
is well-ordered by the membership relation ∈. But this condition is not enough
to make a set an ordinal. (See examples below).
Note that in an ordinal α, if x ∈ α, then x = (−∞, x) ⊆ α, i.e. any element
of an ordinal is a subset of the ordinal.
Examples.
125
126 CHAPTER 16. ORDINALS
Exercises.
iv. An ordinal that has no last element is called a limit ordinal. Find the
set of limit ordinals of ω, ω + ω and ω × ω.
Proof: Uniqueness follows from Corollary 16.1.4. We will show the existence
of an isomorphism. Let X be a well-ordered set. Consider the set = of initial
segments of X which are isomorphic to an ordinal. Thus for each A ∈ =, there
is an ordinal αA and an isomorphism fA : A −→ αA . By Theorem 16.1.4, the
ordinal α is unique. By Theorem 15.3.3, the isomorphism fA is unique.
Let A, B ∈ =. Either A ⊆ B or B ⊆ A. Assume A ⊆ B. Also either
αA ⊆ αB or αB ⊆ αA . Assume αB ⊆ αA . Then fA−1 ◦ fB is an isomorphism
16.4. ADDITION OF ORDINALS 127
Cardinals
A cardinal is an ordinal that is not in bijection with one of its elements. For
example ω and each natural number is a cardinal.
129
130 CHAPTER 17. CARDINALS
IIb) Show that any additive map f from Q into R is given by f (x) = rx for
some r ∈ R.
IIc) Show that the only additive and multiplicative map f from Q into Q is
IdQ .
IId) Show that the only additive and multiplicative map f from R into R
is IdR .
III. Uniqueness of the Real Number System. For i = 1, 2, let (Ri , +i , ×i , 0i , 1i )
be two structures satisfying the axioms of real numbers (ordered complete field).
Show that there is a unique bijection f : R1 −→ R2 such that
i. f (x +1 y) = f (x) +2 f (y)
ii. f (x ×1 y) = f (x) ×2 f (y).
Chapter 18
Axiom of Choice. Any set that does not contain ∅ has a choice function.
131
132 CHAPTER 18. AXIOM OF CHOICE AND ZORN’S LEMMA
form a chain. We will show that the set of comparable elements form a tower.
We already have noticed T1. T3 is easy as well. Let us show T2. Let x
be comparable. If y ⊆ x, since x and g(y) are comparable, g(y) ⊆ x. Let
U := {y ∈ T◦ : either y ⊆ x or g(x) ⊆ y. Then U is a tower. So U = T◦ . It
follows that g(x) is also is comparable. This proves the theorem. ¤
Lemma 18.2.1 (König’s Lemma) Every infinite finitely branching tree with
a unique least element has an infinite branch.
Proof: Let T be such a tree. For n ∈ ω, consider the set T (n) of elements t of
T such that {s ∈ T : s < t} has cardinality n − 1. Since T is finitely branching,
T (n) is finite for all n. An initial subtree of a tree T is subset S of T such
that for s ∈ S, {t ∈ T : t < s} ⊆ S. Consider the set Z of all infinite initial
subtrees of T . Since T ∈ Z, Z 6= ∅. Order Z by reversing the inclusion order,
i.e. for S1 , S2 ∈ Z, define S1 < S2 if S2 ⊂ S1 . We claim that Z is an inductive
set. More precisely, we claim that if (Si )i∈I is a chain from Z, then ∩i∈I Si ∈ Z.
We first show that ∩i∈I Si is an initial subtree. Let s ∈ ∩i∈I Si and let t ∈ T
be such that t < s. Then t ∈ Si for all i ∈ I. Hence t ∈ ∩i∈I Si .
We next show that ∩i∈I Si is infinite. Assume otherwise. Then ∩i∈I Si ⊆
T (n) for some n ∈ ω. For each t ∈ T (n + 1), since t 6∈ ∩i∈I Si there is an i(t) ∈ I
such that t 6∈ Si(t) . Let i = max{i(t) : t ∈ T (n + 1)}. Then T (n + 1) ∩ S(i) = ∅.
But then S(i) ⊆ T (n) and S(i) is finite, a contradiction.
By Zorn’s Lemma Z has a maximal element, say S. Thus S is a minimal
infinite initial tree. We claim that S is a branch. Assume otherwise. Then S
has two incomparable elements t1 and t2 . Deleting one of the ti and elements
above it, we get an infinite proper initial subtree of S, a contradiction. ¤
133
134 CHAPTER 19. AXIOMS OF SET THEORY – ZFC
Chapter 20
V =L
135
136 CHAPTER 20. V = L
Chapter 21
Continuum Hypothesis
137
138 CHAPTER 21. CONTINUUM HYPOTHESIS
Chapter 22
Banach-Tarski Paradox
Proof: Let G be the subgroup formed by the rational multiples of 2π. Let
G = {ρi : i ∈ N}. Let H be a set of representatives of SO2 (R)/G. Let
A = H(1, 0) and Ai = ρi (A). The family (Ai )i is a countable partition of S 1 .
Then (A2i )i and (A2i+1 ) are such that S 1 = ∪i g2i (A2i ) = ∪i g2i+1 (A2i+1 ) where
g2i takes A2i onto Ai and g2i+1 takes A2i+1 onto Ai . ¤
Let G act on a set X. Let A, B ⊆ X. We say that A and B are G-
equidecomposable if there are finite partitions of A = tni=1 Ai and B =
tni=1 Bn and g1 , . . . , gn ∈ G such that gi (Ai ) = Bi . This is an equivalence
relation.
Proof: Easy. ¤
139
140 CHAPTER 22. BANACH-TARSKI PARADOX
But also F = a−1 B(a) = a−1 B(a) u B(a) and F = b−1 B(b) = b−1 B(b) u B(b).
¤
Fact 22.0.9 SO3 (R) contains a free subgroup of rank 2. Thus SO3 (R) is para-
doxical.
Let G ≤ SO3 (R) be free on two generators. Let D be the set of points on
S 2 which are fixed by some g ∈ G \ {g}. Then D is countable. Let G act
on S 2 \ D. Thus S 2 \ D is paradoxical. We will show that S 2 \ D is SO3 (R)-
equidecomposable with S 2 . Choose an axis of rotation not passing through an
element of D. Consider the set of all rotations around this axis for which some
integer power of it sends an element of D to another point of D. This set is
countable. Pick a rotation ρ not in this set. Then ρn (D) ∩ ρm (D) = ∅ for
n 6= m. Let A = ∪∞ n 2 2
n=1 ρ (D) and B = S \ (A ∪ D). We have S \ D = A t B ∼
−1 2
B ∪ ρ (A) = S .
Thus S 2 is SO3 (R)-paradoxical.
Chapter 23
141
142 CHAPTER 23. FIRST ORDER STRUCTURES
Chapter 24
Ultraproducts and
Ultrafilters
143
144 CHAPTER 24. ULTRAPRODUCTS AND ULTRAFILTERS
Chapter 25
Dimension Theory
145
146 CHAPTER 25. DIMENSION THEORY
Chapter 26
Exams
147
148 CHAPTER 26. EXAMS
and this condition holds for all y. Hence ∩1 ∅ is the whole universe and is
not even a set.
Thus we should prefer ∩2 X for the definition of ∩X since the outcome
would then be a set for any set X, even for X = ∅!
S S
b) What is the relationship between i∈I ℘(Ai ) and ℘( i∈I Ai )? (4 pts.)
S S
Answer: We have i∈I ℘(Ai ) ⊆ ℘( i∈I Ai ). Indeed,
S
X∈ i∈I ℘(Ai ) if and only if X ∈ ℘(Ai ) for some i ∈ I
if and only if X ⊆ Ai for some i ∈ I
implies X ⊆ ∪i∈I Ai
if and only if X ∈ ℘(∪i∈I Ai )
The reverse inclusion is false, in fact if oneSof the sets Ai does not contain
all the others, then ∪i∈I Ai ∈ ℘(∪i∈I Ai ) \ i∈I ℘(Ai ).
v. Let α be a set such that x ⊆ α for all x ∈ α. Show that α ∪ {α} has the
same property. Give four examples of such sets. (4 pts.)
Proof: Let x ∈ α ∪ {α}. Then either x ∈ α or x ∈ {α}.
If x ∈ α, then by assumption x ⊆ α. Since α ⊆ α ∪ {α}, in this case we
get x ⊆ α ∪ {α}.
If x ∈ {α}, then x = α, and so x = α ⊆ α ∪ {α}.
26.1. FIRST SEMESTER MIDTERM, NOVEMBER 2002 149
Since ∅ has the property stated, starting from ∅, we can get as many
examples as we wish to, here are the first four:
∅=0
0 ∪ {0} = 1
1 ∪ {1} = 2
2 ∪ {2} = 3
vii. Let φ : R −→ R be a one to one map such that φ(x + y) = φ(x) + φ(y)
and φ(x2 ) = φ(x)2 for all x, y ∈ R. Show that φ(xy) = φ(x)φ(y) for all
x, y ∈ R and φ(q) = q for all q ∈ Q. (10 pts.)
Proof: For any x, y ∈ R, we have φ(x)2 + 2φ(x)φ(y) + φ(y)2 = (φ(x) +
φ(y))2 = φ(x + y)2 = φ((x + y)2 ) = φ(x2 + 2xy + y 2 ) = φ(x2 ) + 2φ(xy) +
φ(y 2 ) = φ(x)2 +2φ(xy)+φ(y)2 and so 2φ(x)φ(y) = 2φ(xy) and simplifying,
we get φ(x)φ(y) = φ(xy). This proves the first part.
Since φ(0) = φ(0 + 0) = φ(0) + φ(0), we must have φ(0) = 0.
Since φ(1) = φ(1 · 1) = φ(1)φ(1), we must have φ(1) = 0 or φ(1) = 1. But
the first case is forbidden because φ is one to one and φ(0) = 0 already.
Hence φ(1) = 1.
Now, it follows easily by induction that φ(n) = n for all n ∈ N because
φ(n+1) = φ(n)+φ(1) = φ(n)+1 = n+1 (the last equality is the inductive
hypothesis).
Also, for n ∈ N, we have 0 = φ(0) = φ(n + (−n)) = φ(n) + φ(−n) and so
φ(−n) = −φ(n) = −n. Thus φ(n) = n for all n ∈ Z.
Now if q ∈ Q, then q = n/m some n, m ∈ Z and m 6= 0. Then we have
n = φ(n) = φ(mn/m) = φ(m)φ(n/m) = mφ(n/m) and so φ(n/m) =
n/m, i.e. φ(q) = q.
ii. Show that there are no sets x and y such that x ∈ y and y ∈ x. (3 pts.)
viii. Show that an ordinal α is a set well-ordered by the relation ∈, i.e. by the
relation < defined as follows: For all β, γ ∈ α, β < γ if and only if β ∈ γ.
Show that the converse of this statement is false. (3 pts.)
iv. Show that for any binary relation R on X the intersection Rt of all the
transitive relations that contain R is the unique smallest transitive relation
on X that contains R. (10 pts.)
Rt is called the transitive closure of R
Solution. By above, the intersection Rt of all the transitive relations that
contain R is the a transitive relation on X that contains R. Since it is
the intersection of all the transitive relations on X that contains R, it can
only be the smallest one.
and
viii. Give an example of a partially ordered set (X, <) and a subset A of X
which
i. has a least upper bound which is not in A.
ii. has exactly two least upper bounds.
iii. does not have a least upper bound.
iv. has a least upper bound which is in A. (4 pts.)
Solution: i. Take X = R with the usual order and let A = (0, 1). Then
lub(A) = 1 6∈ A.
ii. Let X = {a, b, c} and set a < b and a < c. Take also A = X. Then
both b and c are least upper bounds of A.
iii. Let X = R or N with the usual order and take A = N.
iv. Take X = R with the usual order and let A = (0, 1]. Then lub(A) =
1 ∈ A.
156 CHAPTER 26. EXAMS
ix. Let (X, <) be a partially ordered set and A a subset of X. Suppose that
A has a least upper bound which is in A. Show that this is the only upper
bound of A. (2 pts.)
Proof: Let a ∈ A be a least upper bound of A. Let b be another upper
bound of A. Then, since a ∈ A, a ≤ b. Therefore, a being an upper bound
and b a least upper bound, a = b.
x. Let (X, <) be a partially ordered set. Show that any element of X is an
upper bound of ∅. (2 pts.)
Proof: Certainly any element of X is greater than or equal to any element
of ∅. ¤
xi. Let (X, <) be a partially ordered set. What can you say about (X, <) if
∅ has a least upper bound? (2 pts.)
Solution: Then the partially ordered set X must have a unique least
element.
xii. Let U be a set and let X = ℘(U ). Order X by strict inclusion. Show that
this is a partial order on X. (2 pts.) Show that any subset of X has a
unique least upper bound. (5 pts.)
Proof: Let a, b, c ∈ X be such that a ⊂ b ⊂ c. Then a ⊂ c. Since a 6⊂ a,
this shows that X is a partial order. Let A ⊂ X. Then I claim that ∪A,
i.e. ∪a∈A a is the unique least upper bound of A. Since a ⊆ ∪a∈A a for all
a ∈ A, it is clear that ∪a∈A a is an upper bound of A. Assume b is another
upper bound of A. Then a ⊆ b for all a ∈ A; hence ∪a∈A a ⊆ b. This
shows that ∪a∈A a is the least upper bound of A. ¤
xiii. Let (X, <) be a partial order. Suppose that for any a, b ∈ X, the set
{a, b} has a unique least upper bound. Let a ∨ b denote this least upper
bound.
i. Give an infinite example of such a partially ordered set. (2 pts.)
ii. Prove or disprove: (a ∨ b) ∨ c = a ∨ (b ∨ c) for all a, b, c ∈ X. (10 pts.)
Solution: i. N with the natural order is such an example. Here lub(x, y) =
max(x, y).
ii. Proof: Clearly a ≤ a ∨ (b ∨ c). Also b ≤ b ∨ c ≤ a ∨ (b ∨ c), thus
b ≤ a ∨ (b ∨ c) as well. These show that a ∨ b ≤ a ∨ (b ∨ c).
On the other hand c ≤ b ∨ c ≤ a ∨ (b ∨ c). With the result of the previous
paragraph we get (a ∨ b) ∨ c ≤ a ∨ (b ∨ c).
Similarly one can also show that a ∨ (b ∨ c) ≤ (a ∨ b) ∨ c. Therefore
(a ∨ b) ∨ c = a ∨ (b ∨ c).
xiv. Show that in a totally ordered set (X, <) if a subset A of X has a least
upper bound then this least upper bound is the only upper bound of A.
(4 pts.)
Proof: Let A ⊆ X have a least upper bound, say b. Let c be another
least upper bound. Then either b ≤ c or c ≤ b, and any of these imply
b = c.
IV. Well-Ordered Sets. We say that a totally ordered set (X, <) is a
well-ordered set (or that < well-orders X) if every nonempty subset of
X contains a minimal element for that order, i.e. if for every nonempty
subset A of X, there is an m ∈ A such that m ≤ a for all a in A. (Note
that the element m must be in A).
xvi. Let X = N × {0} ∪ N × {1}. On X define the relation < as follows: For
all x, y ∈ N,
xvii. Is the set {1/n : n ∈ N\{0}} together with the natural order a well-ordered
set? (2 pts.)
Answer: No, because the set itself does not have a least element.
xviii. Is the set {1/n : n ∈ N \ {0}} ∪ {0} together with the natural order a
well-ordered set? (2 pts.)
Answer: No. Let A = {1/n : n ∈ N \ {0}}. Then A does not have a least
element: glb(A) = 0 6∈ A.
158 CHAPTER 26. EXAMS
xx. Show that in a well-ordered set the minimal element of any nonempty
subset is unique. (2 pts.)
Proof: Let A be a nonempty subset of a well-ordered set X. Let a and b
be two least elements of A. Either a < b or b < a or a = b, The first case
contradicts the fact that b is a minimal element of A because a ∈ A. The
second case gives a contradiction in a similar way.
xxi. Show that every nonempty well-ordered set has a unique minimal element.
(2 pts.)
Proof: Follows from above taking A to be the well-ordered set itself.
xxii. Let (X, <) be a well-ordered set. Show that all the elements of X except
possibly one of them satisfies the following property: “There exists a y
such that x < y and for all z if x < z then y < z”. (5 pts.) Show that
such a y, when exists, is unique (3 pts.)
Proof: Let x ∈ X. Assume x is not the last element of X. Then
{y ∈ X : x < y} is a nonempty subset of X and as such has a minimal
element, say y, and by one of the questions above this minimal element y
is unique.
T1. ∅ ∈ τ and X ∈ τ.
T2. If U, V ∈ τ, then U ∩ V ∈ τ.
T2. If σ ⊆ τ, then ∪ σ ∈ τ.
iv. Let A and B be two subsets of X. Find a finite topology on X that contains
A and B. (3 pts.)
ix. Show that if σ ⊆ ℘(X) is a set of subsets of X, then the intersection hσi
of all the topologies that contain σ is the smallest topology on X that
contains σ. In other words, if A ∈ σ then A is open in the topology hσi,
and hσi is the smallest topology on X with this property. This topology
is called the topology generated by σ. (10 pts.)
xiii. Let σ ⊆ ℘(X). Consider the set [σ] of subsets A of X with the following
property:
xiv. Let σ be the set of all open intervals of R. Consider the set R with the
topology hσi.
a) Show that a subset A of R is open (in this topology) if and only if for
all a ∈ A there is an ² ∈ R>0 such that (a − ², a + ²) ⊆ A. (7 pts.)
b) Show that no finite and nonempty subset of R is open (in this topology).
(2 pts.)
c) Show that [0, 1) is not open. (3 pts.)
d) Show that a cofinite subset is open. (3 pts.)
d) Is Q open? (3 pts.)
xv. Let σ1 be the set of all intervals of R of the form [a, b) of R for a ≤ b ∈ R.
a. Show that hσi ⊂ hσ1 i. (5 pts.)
b. Can a singleton set be open in this topology? (3 pts.)
c. Show that [0, 1] is not open in this topology. (3 pts.)
xvi. Let σ2 be the set of all closed and bounded intervals of R. Show that
hσ1 i ⊂ hσ2 i where σ1 is as in number xv. (5 pts.)
(x, y) ≡ (z, t) ⇔ xt = yz
ii. Symmetry. Let (x, y), (z, t) ∈ X be such that (x, y) ≡ (z, t). Hence
xt = yz. Therefore zy = tx, implying (z, t) ≡ (x, y).
iii. Transitivity. Let (x, y), (z, t), (u, v) ∈ X be such that (x, y) ≡ (z, t)
and (z, t) ≡ (u, v). Hence xt = yz and zv = tu. Multiplying these
26.5. FIRST SEMESTER FINAL AND ITS CORRECTION, JANUARY 2004161
aa0 , aa00 , a00 a000 , bb0 , bb00 , b00 b000 , cc0 , cc00 , c00 c000 , ab, bc, ca, a0 b00 , b0 c00 , c0 a00 .
It works!
iii. Let a and b be two integers which are not both 0. We say that d is the
greatest common divisor of a and b if d is the largest natural number
that divides both a and b. Show that for any a, b ∈ Z, gcd(a, b) exists and
that there are x, y ∈ Z such that ax + by = gcd(a, b).
Proof: Replacing a and b by |a| and |b|, we may assume that a ≥ 0 and
b ≥ 0.
Existence. Since 1 divides both a and b and since any number that
divides both a and b can be at most max(a, b) > 0, the set of natural
numbers that divide both a and b is a finite nonempty set bounded by
max(a, b). Therefore there is a largest such number. This proves the
existence of gcd(a, b). We let d = gcd(a, b).
Second Part. We proceed by induction on max(a, b). If a = 1, then take
x = 1, y = 0. If b = 1, then take x = 0, y = 1. This takes care of the
162 CHAPTER 26. EXAMS
iv. Let a and b be two nonzero integers. We say that m is the least common
multiple of a and b if m is the least natural number that is divisible by
both a and b. We let m = lcm(a, b). Show that for any a, b ∈ Z \ {0},
lcm(a, b) exists and that ab = ± gcd(a, b) lcm(a, b).
Proof: Replacing a and b by |a| and |b| again, we may assume that a > 0
and b > 0. Since a and b both divide ab, lcm(a, b) exists.
Let d = gcd(a, b) and m = lcm(a, b). Let a0 and b be such that a = da0
and b = db0 . Then ab = d2 a0 b0 . We need to prove that m = da0 b0 .
Since da0 b0 = ab0 = a0 b, a and b both divide da0 b0 .
Let x be divisible by both a and b. Then x = au = bv for some u, v. We
have a0 du = au = x = bv = b0 dv and so a0 u = b0 v. Since a0 and b0 cannot
have a common divisor (otherwise d would be larger), b0 must divide u.
(This last fact needs a serious proof, that we have not undertaken yet. I
shouldn’t have asked this question at this stage). Write u = cb0 . Now
x = au = acb0 = a0 dcb0 and so a0 b0 d divides x, in particular a0 b0 d ≤ x.
This shows that a0 b0 d is the least multiple of a and b, i.e. a0 b0 d = m.
12 + 22 + . . . + n2
and
13 + 23 + . . . + n3 ,
and prove your result.
Proof: We claim that
n(n + 1)(2n + 1)
12 + 22 + . . . + n2 = .
6
We proceed by induction on n. For n = 1, it is easy to check the validity
of the formula. Assume the statement holds for n. To prove it for n + 1,
we compute:
n(n+1)(2n+1)
12 + 22 + . . . + n2 + (n + 1)2 = 6 + (n + 1)2
(n+1)(n(2n+1)+6(n+1))
= 6
(n+1)(2n2 +7n+6))
= 6
(n+1)(n+2)(2n+3)
= 6
n0 (n0 +1)(2n0 +1)
= 6
26.6. SECOND SEMESTER, MIDTERM, MAY 2003 163
iii) ∅ 6∈ = and X ∈ =.
If A ⊆ X is a fixed nonempty subset of X, then the set of subsets =(A) of
X that contain A is a filter on X. Such a filter is called principal filter. If X
is infinite, then the set of cofinite subsets of X is a filter, called Fréchet filter.
A filter is called ultrafilter if it is a maximal filter.
We fix a set X.
ii. Show that the Fréchet filter (on an infinite set) is not contained in a
principal filter.
Proof: Let = be the Fréchet filter. Assume = ⊆ Im(A) for some A ⊆ X.
Let a ∈ A. Then X \ {a}, being a cofinite set, is in =, but is not in =.
It is easy to show that = ⊆ h=i and that h=i is a filter. You should also
note that h=i is the smallest filter that contains =.
vii. (AC) Show that for any filter = on X, there is an ultrafilter on X that
contains =.
Proof: Let Z be the set of filters on X that contains =. Order Z by
inclusion. Since = ∈ Z, Z 6= ∅. It is clear that Z is an inductive set,
because if (=i )i∈I is a chain from Z, then one can show easily that ∪i∈I =i
is a filter that contains =. Hence by Zorn’s Lemma Z has a maximal
element. Clearly this maximal element of Z is an ultrafilter.
viii. (AC) Show that if X is infinite then there are nonprincipal ultrafilters on
X.
Proof: Apply the previous question to the Fréchet Filter to get an ultra-
filter = that contains the Fréchet filter. By ii, = is not principal.
f ≡ g ⇐⇒ {x ∈ X : f (x) = g(x)} ∈ =.
xi. Suppose that each Ax is a set ordered by a relation <. On M define the
relation < by,
{x ∈ X : fx < gx }
and
{x ∈ X : fx > gx }
partition the set {x ∈ X : fx 6= gx } which is in =, one of them should be
in = by Question v again, in which case either [f ] < [g] or [g] < [f ].
xiii. Suppose that each (Ax , <) has a largest element. Is it true that (M, <)
has a largest element?
Proof: Of course!
xiv. Suppose that each (Ax , <) is well-ordered. Is it true that (M, <) is well-
ordered?
Proof:
Index
(X, ?), 35 vn , 69
(n, m) = k, 111 (, 69
(x, y), 29, 82 ), 69
(x, y, z), 30 2+2=4, 91
=, 69 2 × 2 = 4, 93
A−1 , 83
X/ ≡, 50 1, 80
X × Y , 29 2,
√ 80
∅, 13, 77 2, 19
⇔ , 15 3, 80
⇒,
T 15 4, 80
Sx∈X x, 26
i∈I Ai , 28
absolute value, 108
∩X, 26 addition, 58, 90
∩, 25 addition of natural numbers, 90, 91
◦, 32, 41, 85 addition of ordinals, 127
∪, 27, 79, 81 antisymmetric relation, 48
≡, 69 arrival set of a function, 31
∃, 69 associativity, 36, 41
∀, 15 associativity for multiplication, 93
∈, 11, 69 associativity of addition, 91
≤, 54 associativity of functions, 33
¬, 69 Aut(Γ), 63
6∈
Q, 11 automorphism group, 63
Qi∈I X, 44 automorphism of a binary unirela-
Qi∈I Xi , 44 tional structure, 63
i∈I fi , 45 automorphism of well-ordered sets,
\, 25, 78
√ 123
2, 18 automorphisms of (Q, <), 129
⊂, 13 automorphisms of (R, +, ×), 129
⊆, 12, 77 Axiom of Regularity, 152
∧, 69 Axiom of Replacement, 126, 153
℘(x), 82
{x}, 11 back and forth argument, 67
{x1 , . . . , xn }, 11 bijection, 40
f −1 , 40 binary operation, 35
f1 × f2 , 45 binary relation, 47, 153
167
168 INDEX
ultrafilters, 143
ultraproduct, 143
union, 27, 79, 81
union of two functions, 38
upper bound, 155
variables, 69
vertex, 132
X c , 25
Z, 18
Z,√18
Z[ 2], 19
zero, 80