Set Theory

2018/19
by Peter Koepke

Die Mengenlehre ist das Fundament

der gesamten Mathematik
(Felix Hausdorff,
Grundzüge der Mengenlehre, 1914 )

1 Introduction

1.1 The origin of set theory

Georg Cantor characterized sets as follows:

Unter einer Menge verstehen wir jede Zusammenfassung M von bestimmten,

wohlunterschiedenen Objekten m unsrer Anschauung oder unseres Denkens
(welche die Elemente von M genannt werden) zu einem Ganzen.

Felix Hausdorff in Grundzüge formulated shorter:

Eine Menge ist eine Zusammenfassung von Dingen zu einem Ganzen, d.h. zu
einem neuen Ding.
Sets are ubiquitous in mathematics. According to Hausdorff
Dierential- und Integralrechnung, Analysis und Geometrie arbeiten in Wirklich-
keit, wenn auch vielleicht in verschleiernder Ausdrucksweise, beständig mit unend-
lichen Mengen.

1.2 Set theoretic foundations of mathematics

In current mathematics, many notions are explicitly dened using sets. The following example
indicates that notions which are not set-theoretical prima facie can be construed set-theoretic-
ally:

f is a real funktion  f is a set of ordered pairs (x; y) of real numbers, such

that ... ;
(x; y) is an ordered pair  (x; y) is a set :::fx; yg::: ;
x is a real number  x is a left half of a Dedekind cut in Q  x is a subset of
Q, such that ::: ;
r is a rational number  r is an ordered pair of integers, such that ::: ;
z is an integer  z is an ordered pair of natural numbers (= non-negative
integers);
N = f0; 1; 2; :::g;
0 is the empty set;
1 is the set f0g;
2 is the set f0; 1g; etc. etc.

We shall see that all mathematical notions can be reduced to the notion of set .

1
2 Section 2

Besides this foundational role, set theory is also the mathematical study of the innite. There
are innite sets like N; Q; R which can be subjected to the constructions and analyses of set
theory; there are various degrees of innity which lead to a rich theory of innitary combinat-
orics.
In this course, we shall rst apply set theory to obtain the standard foundation of mathematics
and then turn towards pure set theory.

1.3 The language of set theory

If m is an element of M one writes m 2 M . If all mathematical objects are reducible to sets,
both sides of these relation have to be sets. This means that set theory studies the 2-relation
m 2 M for arbitrary sets m and M . As it turns out, this is sucient for the purposes of set
theory and mathematics. In set theory variables range over the class of all sets, the 2-relation is
the only undened structural component, every other notion will be dened from the 2-relation.
Basically, set theoretical statement will thus be of the form
:::8x:::9y::::::x 2 y:::u  v:::;
belonging to the rst-order predicate language with the only given predicate 2.
To deal with the complexities of set theory and mathematics one develops a comprehensive and
intuitive language of abbreviations and definitions which, eventually, allows to write familiar
statements like
ei = ¡1
and to view them as statements within set theory.
The language of set theory may be seen as a low-level, internal language. The language of math-
ematics possesses high-level macro expressions which abbreviate low-level statements in an e-
cient and intuitive way.

1.4 Russell's paradox

Cantor's naive description of the notion of set suggests that for any mathematical statement
'(x) in one free variable x there is a set y such that
x 2 y $ '(x) ;
i.e., y is the collection of all sets x which satisfy ' .
This axiom is a basic principle in Gottlob Frege's Grundgesetze der Arithmetik, 1893 ,
Grundgesetz V, Grundgesetz der Wertverläufe.
Bertrand Russell noted in 1902 that setting '(x) to be x 2/ x this becomes
x2 y$x2
/ x;
and in particular for x = y :
y2y$y2
/ y:
Contradiction.
This contradiction is usually called Russell's paradox, antinomy, contradiction. It was also dis-
coved slightly earlier by Ernst Zermelo. The paradox shows that the formation of sets as col-
lections of sets by arbitrary formulas is not consistent.

2 The Zermelo-Fraenkel Axioms

The diculties around Russell's paradox and also around the axiom of choice lead Zermelo
to the formulation of axioms for set theory in the spirit of the axiomatics of David Hilbert of
whom Zermelo was an assistant at the time.
Zermelo's main idea was to restrict Frege's Axiom V to formulas which correspond to math-
ematically important formations of collections, but to avoid arbitrary formulas which can lead to
paradoxes like the one exhibited by Russell.
The Zermelo-Fraenkel Axioms 3

The original axiom system of Zermelo was extended and detailed by Abraham Fraenkel
(1922), Dmitry Mirimanoff (1917/20), and Thoralf Skolem.
We shall discuss the axioms one by one and simultaneously introduce the logical language and
useful conventions.

2.1 Set Existence

The set existence axiom
9x8y : y 2 x ;
like all axioms, is expressed in a language with quantiers 9 (there exists) and 8 (for all),
which is familiar from the --statements in analysis. The language of set theory uses variables
x; y; ::: which may satisfy the binary relations 2 or =: x 2 y (x is an element of y) or x = y .
These elementary formulas may be connected by the propositional connectives ^ (and), _
(or), ! (implies), $ (is equivalent), and : (not). The use of this language will be demon-
strated by the subsequent axioms.
The axiom expresses the existence of a set which has no elements, i.e., the existence of the
empty set.

2.2 Extensionality
The axiom of extensionality
8x8x 0(8y(y 2 x $ y 2 x 0) ! x = x 0)
expresses that a set is exactly determined by the collection of its elements. This allows to prove
that there is exactly one empty set.

Lemma 1. 8x8x 0(8y :y 2 x^8y :y 2 x 0 !x = x 0).

Proof. Consider x; x 0 such that 8y :y 2 x^8y :y 2 x 0. Consider y . Then :y 2 x and :y 2 x 0.

This implies 8y(y 2 x $ y 2 x 0). The axiom of extensionality implies x = x 0. 

Note that this proof is a usual mathematical argument, and it is also a formal proof in the sense
of mathematical logic. The sentences of the proof can be derived from earlier ones by purely
formal deduction rules. The rules of natural deduction correspond to common sense gures of
argumentation which treat hypothetical objects as if they would concretely exist.

2.3 Pairing
The pairing axiom
8x8y9z8u(u 2 z $ u = x _ u = y)
postulates that for all sets x; y there is set z which may be denoted as
z = fx; yg:
This formula, including the new notation, is equivalent to the formula
8u(u 2 z $ u = x _ u = y):
In the sequel we shall extend the small language of set theory by hundreds of symbols and con-
ventions, in order to get to the ordinary language of mathematics with notations like
 Z b
p 1 0
N; R; 385 ; ; ; f 0(x)dx = f (b) ¡ f (a); etc:
0 1 a

Such notations are chosen for intuitive, pragmatic, or historical reasons.

Using the notation for unordered pairs, the pairing axiom may be written as
8x8y9z z = fx; yg:
4 Section 2

By the axiom of extensionality, the term-like notation has the expected behaviour. E.g.:

Lemma 2. 8x8y8z8z 0 (z = fx; yg ^ z 0 = fx; yg !z = z 0).

Proof. Exercise. 

Note that we implicitly use several notational conventions: variables have to be chosen in a reas-
onable way, for example the symbols z and z 0 in the lemma have to be taken dierent and dif-
ferent from x and y. We also assume some operator priorities to reduce the number of brackets:
we let ^ bind stronger than _, and _ stronger than ! and $.
We used the term fx; yg to occur within set theoretical formulas. This abbreviation is than to
be expanded in a natural way, so that ocially all mathematical formulas are formulas in the
pure 2-language. We want to see the notation fx; yg as an example of a class term. We dene
uniform notations and convention for such abbreviation terms.

2.4 Class Terms

The extended language of set theory contains class terms and notations for them. There are
axioms for class terms that x how extended formulas can be reduced to formulas in the unex-
tended 2-language of set theory.

Denition 3. A class term is of the form fxj'g where x is a variable and ' 2 L2. The usage
of these class terms is dened recursively by the following axioms: If fxj'g and fyj g are class
terms then
u u
¡ u 2 fxj'g $ ' x , where ' x is obtained from ' by (resonably) substituting the variable x
by the variable u ;
v
¡ u = fxj'g $ 8v (v 2 u $ ' x );
v
¡ fxj'g = u $ 8v (' x $ v 2 u);
v v
¡ fxj'g = fyj g $ 8v (' x $ y
);

¡ fxj'g 2 u $ 9v(v 2 u ^ v = fxj'g;

v
¡ fxj'g 2 fyj g $ 9v( y
^ v = fxj'g).

A term is either a variable or a class term.

Denition 4.
/ xg is the empty set;
a) ; := fxjx =
b) V := fxjx = xg is the universe (of all sets);
c) fx; yg := fuju = x _ u = yg is the unordered pair of x and y .

Lemma 5.
a) ; 2 V.
b) 8x; y fx; y g 2 V.

Proof. a) By the axioms for the reduction of abstraction terms, ; 2 V is equivalent to the fol-
lowing formulas

9v(v = v ^ v = ;)
9v v = ;
9v 8w (w 2 v $ w =/ w)
9v8w w 2 /v
The Zermelo-Fraenkel Axioms 5

which is equivalent to the axiom of set existence. So ; 2 V is another way to write the axiom of
set existence.
b) 8x; y fx; yg 2 V abbreviates the formula
8x; y9z(z = z ^ z = fx; yg):
This can be expanded equivalently to the pairing axiom
8x; y9z8u(u 2 z $ u = x _ u = y): 

So a) and b) are concise equivalent formulations of the axiom Ex and Pair.

We also introduce bounded quantiers to simplify notation.

Denition 6. Let A be a term. Then 8x 2 A '$8x(x 2 A ! ') and 9x 2 A ' $ 9x (x 2 A ^ ').

Denition 7. Let x; y; z; ::: be variables and X ; Y ; Z ; ::: be class terms. Dene

a) X  Y $ 8x 2 X x 2 Y, X is a subclass of Y ;
b) X [ Y := fxjx 2 X _ x 2 Y g is the union of X and Y ;
c) X \ Y := fxjx 2 X ^ x 2 Y g is the intersection of X and Y ;
d ) X n Y := fxjx 2 X ^ x 2
/ Y g is the dierence of X and Y ;
S
e) X := fxj9y 2 X x 2 yg is the union of X ;
T
f) X := fxj8y 2 X x 2 yg is the intersection of X ;
g) P(X): =fxjx  X g is the power class of X;
h) fX g: =fxjx = X g is the singleton set of X;
i ) fX ; Y g: =fxjx = X _ x = Y g is the (unordered) pair of X and Y;
j ) fX0; :::; Xn¡1g: =fxjx = X0 _ ::: _ x = Xn¡1g.

One can prove the well-known boolean properties for these operations. We only give a few
examples.

Proposition 8. X  Y ^ Y  X ! X = Y.
S
Proposition 9. fx; yg = x [ y.

Proof. We show
S the equality by two inclusions:
(). Let u 2 fx; yg. 9v(v 2 fx; yg ^ u 2 v). Let v 2 fx; yg ^ u 2 v. (v = x _ v = y) ^ u 2 v.
Case 1 . v = x. Then u 2 x. u 2 x _ u 2 y. Hence u 2 x [ y.
Case 2 . v = y. Then u 2 y. u 2 x _ u 2 y. Hence u 2 x [ y.
Conversely let u 2 x [ y. u 2 x _ u 2 y. S
Case 1 . u 2 x. Then x 2 fx; yg ^ u 2 x. 9v(v 2 fx; yg ^ u 2 v) and u 2 fx; y g.
S
Case 2 . u 2 y. Then x 2 fx; yg ^ u 2 x. 9v(v 2 fx; yg ^ u 2 v) and u 2 fx; yg. 
S T S T
Exercise 1. Show: a) V = V . b) V = ; . c) ; = ; . d) ;=V .

2.5 Ordered Pairs

Combining objects into ordered pairs (x; y) is taken as an undened fundamental operation of
mathematics. We cannot use the unordered pair fx; yg for this purpose, since it does not
respect the order of entries:
fx; yg = fy; xg:
We have to introduce some asymmetry between x and y to make them distinguishable. Fol-
lowing Kuratowski and Wiener we dene:
6 Section 2

Denition 10. (x; y): =ffxg; fx; ygg is the ordered pair of x and y.

The denition involves substituting class terms within class terms. We shall see in the following
how these class terms are eliminated to yield pure 2-formulas.

Lemma 11. 8x8y9z z = (x; y).

Proof. Consider sets x and y. By the pairing axiom choose u and v such that u = fxg and v =
fx; yg. Again by pairing choose z such that z = fu; v g. We argue that z = (x; y). Note that
(x; y) = ffxg; fx; ygg = fwjw = fxg _ w = fx; ygg.
Then z = (x; y) is equivalent to
8w(w 2 z $ w = fxg _ w = fx; yg),
8w(w = u _ w = v $ (w = fxg _ w = fx; yg),
and this is true by the choice of u and v. 

The Kuratowski-pair satises the fundamental property of ordered pairs:

Lemma 12. (x; y) = (x 0; y 0) !x = x 0 ^ y = y 0.

Proof. Assume (x; y) = (x 0; y 0), i.e.,

(1) ffxg; fx; ygg = ffx 0g; fx 0; y 0gg.
Case 1 . x = y. Then
fxg = fx; yg,
ffxg; fx; ygg = ffxg; fxgg = ffxgg,
ffxgg = ffx 0g; fx 0; y 0gg,
fxg = fx 0g and x = x 0,
fxg = fx 0; y 0g and y 0 = x.
Hence x = x 0 and y = x = y 0 as required.
Case 2 . x =/ y. (1) implies
fx 0g = fxg or fx 0g = fx; yg.
The right-hand side would imply x = x 0 = y, contradicting the case assumption. Hence
fx 0g = fxg and x 0 = x.
Then (1) implies
fx; yg = fx 0; y 0g = fx; y 0g and y = y 0. 

Exercise 2.
a) Show that hx; y i := ffx; ;g; fy; f;ggg also satises the fundamental property of ordered pairs (F.
Hausdorff).
b) Can fx; fy; ;gg be used as an ordered pair?
Exercise 3. Give a set-theoretical formalization of an ordered-triple operation.

2.6 Relations and Functions

Ordered pairs allow to introduce relations and functions in the usual way. One has to distin-
guish between sets which are relations and functions, and class terms which are relations and
functions.

Denition 13. A term R is a relation if all elements of R are ordered pairs, i.e., R  V  V.
Also write Rxy or xRy instead of (x; y) 2 R . If A is a term and R  A  A then R is a rela-
tion on A.

Note that this denition is really an innite schema of denitions, with instances for all terms R
and A . The subsequent extensions of our language are also infinite definition schemas. We
extend the term language by parametrized collections of terms.

Denition 14. Let t(x ~ ) be a term in the variables ~x and let ' be an 2-formula. Then ft(x
~ )j'g
stands for fzj9x
~ (' ^ z = t(x
~ )g.
The Zermelo-Fraenkel Axioms 7

Denition 15. Let R; S ; A be terms.

a) The domain of R is dom(R) := fxj9y x R yg.
b) The range of R is ran(R) := fy j9xx R yg.
c) The eld of R is eld(R) := dom(R) [ ran(R).
d ) The restriction of R to A is R  A := f(x; y)jxRy ^x 2 Ag.
e) The image of A under R is R[A] := R 00A := fyj9x 2 A xRyg.
f ) The preimage of A under R is R ¡1[A] := fxj9y 2 A xRyg.
g) The composition of S and R (S after R) is S  R := f(x; z)j9y (xRy ^ ySz)g.
h) The inverse of R is R ¡1: =f(y; x)jxRyg.

Relations can play dierent roles in mathematics.

Denition 16. Let R be a relation.

a) R is reexive i 8x 2 eld(R) xRx .
b) R is irreexive i 8x 2 eld(R) :xRx .
c) R is symmetric i 8x; y (xRy! yRx).
d ) R is antisymmetric i 8x; y (xRy ^ yRx!x = y).
e) R is transitive i 8x; y; z (xRy ^ yRz!xRz).
f ) R is connex i 8x; y 2 eld(R) (xRy _ yRx _ x = y).
g) R is an equivalence relation i R is reexive, symmetric and transitive.
h) Let R be an equivalence relation. Then [x]R : =fyjy R xg is the equivalence class of x
modulo R .

It is possible that an equivalence class [x]R is not a set: [x]R 2

/ V . Then the formation of the col-
lection of all equivalence classes modulo R may lead to contradictions. Another important
family of relations is given by order relations.

Denition 17. Let R be a relation.

a) R is a partial order i R is reexive, transitive and antisymmetric.
b) R is a linear order i R is a connex partial order.
c) Let A be a term. Then R is a partial order on A i R is a partial order and eld(R) =
A.
d ) R is a strict partial order i R is transitive and irreexive.
e) R is a strict linear order i R is a connex strict partial order.

Partial orders are often denoted by symbols like 6, and strict partial orders by <. A common
notation in the context of (strict) partial orders R is to write
9pRq ' and 8pRq' for 9p(pRq ^ ') and 8p(pRq! ') resp.
One of the most important notions in mathematics is that of a function.

Denition 18. Let F be a term. Then F is a function if it is a relation which satises

8x; y; y 0 (xFy ^xFy 0 ! y = y 0):
If F is a function then
F (x): =fuj8y (xFy!u 2 y)g
is the value of F at x.
8 Section 2

If F is a function and xFy then y = F (x). If there is no y such that xFy then
\ \
F (x) = y= ;=V:
xFy

The value V at x may be read as undefined. A function can also be considered as the
(indexed) sequence of its values, and we also write
(F (x))x2A or (Fx)x2A instead of F : A ! V :

We dene further notions associated with functions.

Denition 19. Let F ; A; B be terms.

a) F is a function from A to B, or F : A ! B, iff F is a function, dom(F ) = A, and
range(F )  B .
b) F is a partial function from A to B, or F : A * B, i F is a function, dom(F )  A, and
range(F )  B .
c) F is a surjective function from A to B i F : A ! B and range(F ) = B.
d ) F is an injective function from A to B i F : A ! B and
8x; x 0 2 A (x =
/ x 0 !F (x) =
/ F (x 0))

e) F is a bijective function from A to B, or F : A $ B, i F : A ! B is surjective and

injective.
f) B: =ff jf : A ! B g is the class of all functions from A to B.
A

One can check that these functional notions are consistent and agree with common usage:
Exercise 4. Dene a relation  on V by
x  y !9f f : x $ y :
One say that x and y are equinumerous or equipollent. Show that  is an equivalence relation on V . What is
the equivalence class of ; ? What is the equivalence class of f;g ?
Exercise 5. Consider functions F : A ! B and F 0: A ! B. Show that
F = F 0 i 8a 2 A F (a) = F 0(a):

2.7 Unions
The union axiom reads
8x9y8z(z 2 y $ 9w(w 2 x ^ z 2 w)):
S
Lemma 20. The union axiom is equivalent to 8x x 2 V.

Proof.
S Observe the following equivalences:
8x x 2 V S
$8x9y (y = y ^ y = S x)
$8x9y 8z(z 2 y $ z 2 x)
$8x9y 8z(z 2 y $ 9w 2 x z 2 w)
which is equivalent to the union axiom. 

Note that the union of x is usually viewed as the union of all elements of x:
[ [
x= w;
w2x
where we dene
[
t(a) = fz j9a 2 A z 2 t(a)g:
a2A
S
Graphically x can be illustrated like this:
The Zermelo-Fraenkel Axioms 9

x
[x

Combining the axioms of pairing and unions we obtain:

Lemma 21. 8x0; :::; xn¡1 fx0; :::; xn¡1g 2 V .

Note that this is a schema of lemmas, one for each ordinary natural number n . We prove the
schema by complete induction on n .

Proof. For n = 0; 1; 2 the lemma states that ; 2 V , 8x fxg 2 V , and 8x; y fx; yg 2 V resp., and
these are true by previous axioms and lemmas. For the induction step assume that the lemma
holds for n , n > 1. Consider sets x0; :::; xn . Then
fx0; :::; xng = fx0; :::; xn¡1g [ fxng:
The right-hand side exists in V by the inductive hypothesis and the union axiom. 

Remark 22. We are developing the axiom systems ZF and ZFC. These will be infinite
schemas, lists, or sets of formulas. These schemas are formulated in the common mathematical
language, which is able to speak about formulas, in particular 2-formulas, and is also able to
speak about innite collections of formulas. If we assume innitely many axioms, it should also
be possible to conclude infinitely many consequences, like the above Lemma: 8x0; :::;
xn¡1 fx0; :::; xn¡1g 2 V . We view the common mathematical language as a meta language which
is able to speak about an object language like the language of set theory. The meta language has
common mathematical tools available. For example induction and recursion on the common nat-
ural numbers, to perform the recursion in the previous schema of lemmas. We shall approach
the problem of meta theory versus object theory in an informal naive way.

2.8 Separation
It is common to form a subset of a given set consisting of all elements which satisfy some condi-
tion. This is codied by the separation schema. For every 2-formula '(z; x1; :::; xn) postulate:
8x1:::8xn8x9y8z (z 2 y$z 2 x ^ '(z; x1; :::; xn)):
Using class terms the schema can be reformulated as: for every term A postulate
8xA \ x 2 V :
10 Section 2

The crucial point is the restriction to the given set x . The unrestricted, Fregean version A 2 V
for every term A leads to the Russell antinomy. We turn the antinomy into a consequence of
the separation schema:

Theorem 23. V 2
/ V.

Proof. Assume that V 2 V . Then 9xx = V . Take x such that x = V . Let R be the Russellian
class:
R: =fxjx 2
/ xg:
By separation, y := R \ x 2 V . Note that R \ x = R \ V = R . Then
y 2 y$ y 2 R$ y 2
/ y;
contradiction. 

This simple but crucial theorem leads to the distinction:

Denition 24. Let A be a term. Then A is a proper class i A 2

/ V.

Set theory deals with sets and proper classes. Sets are the favoured objects of set theory, the
axioms mainly state favorable properties of sets and set existence. Sometimes one says that a
term A exists if A 2 V . The intention of set theory is to construe important mathematical
classes like the collection of natural and real numbers as sets so that they can be treated set-the-
oretically. Zermelo observed that this is possible by requiring some set existences together
with the restricted separation principle.
Exercise 6. Show that the class ffxgjx 2 V g of singletons is a proper class.

2.9 Power Sets

The power set axiom in class term notation is
8xP(x) 2 V :
The power set axiom yields the existence of function spaces.

Denition 25. Let A; B be terms. Then

A  B: =f(a; b)ja 2 A ^ b 2 B g
is the cartesian product of A and B.

Exercise 7.

By the specic implementation of Kuratowski ordered pairs:

Lemma 26. A  B  P(P(A [ B)).

Proof. Let (a; b) 2 A  B. Then

a; b 2 A[B
fag; fa; bg  A[B
fag; fa; bg 2 P(A [ B)
(a; b) = ffag; fa; bgg  P(A [ B)
(a; b) = ffag; fa; bgg 2 P(P(A [ B))


Theorem 27.
a) 8x; y x  y 2 V.
b) 8x; y xy 2 V.
The Zermelo-Fraenkel Axioms 11

Proof. Let x; y be sets. a) Using the axioms of pairing, union, and power sets, P(P(x [ y)) 2 V .
By the previous lemma and the axiom schema of separation,
x  y = (x  y) \ P(P(x [ y)) 2 V :
b) xy  P(x  y) since a function f : x ! y is a subset of x  y . By the separation schema,
x
y =x y \ P(x  y) 2 V : 

Note that to nd the sets in this theorem one has to apply the power set operation repeatedly.
We shall see that the universe of all sets can be obtained by iterating the power set operation.
The power set axiom leads to higher cardinalities. The theory of cardinalities will be developed
later, but we can already prove Cantor's theorem:

Theorem 28. Let x 2 V.

a) There is an injective map f : x ! P(x).
b) There does not exist an injective map g: P(x) ! x .

Proof. a) Dene the map f: x ! P(x) by u 7! fug. This is a set since

f = f(u; fug)ju 2 xg  x  P(x) 2 V :
f is injective: let u; u 0 2 x, u =
/ u 0. By extensionality,
/ fu 0g = f (u 0):
f (u) = fug =
b) Assume there were an injective map g: P(x) ! x . Dene the Cantorean set
/ g ¡1(u)g 2 P (x)
c = fuju 2 x ^ u 2
similar to the class R in Russell's paradox.
Let u0 = g(c). Then g ¡1(u0) = c and
/ g ¡1(u0) = c:
u0 2 c$u0 2
Contradiction. 

2.10 Replacement
If every element of a set is denably replaced by another set, the result is a set again. The
schema of replacement postulates for every term F :
F is a function ! 8xF [x] 2 V :

Lemma 29. The replacement schema implies the separation schema.

Proof. Let A be a term and x 2 V .

Case 1 . A \ x = ; . Then A \ x 2 V by the axiom of set existence.
Case 2 . A \ x =
/ ; . Take u0 2 A \ x . Dene a map F : x ! x by

u , if u 2 A \ x
F (u) =
u0 , else
Then by replacement
A \ x = F [x] 2 V
as required. 

2.11 Innity
All the axioms so far can be realized in a domain of nite sets, see exercise 12. The true power
of set theory is set free by postulating the existence of one innite set and continuing to assume
the axioms. The axiom of innity expresses that the set of natural numbers exists. To this
end, some number-theoretic notions are dened.
12 Section 2

Denition 30.
a) 0: =; is the number zero.
b) For any term t, t + 1: =t [ ftg is the successor of t.

These notions are reasonable in the later formalization of the natural numbers. The axiom of
innity postulates the existence of a set which contains 0 and is closed under successors
9x (0 2 x ^ 8n 2 x n + 1 2 x):
Intuitively this says that there is a set which contains all natural numbers. Let us dene set-the-
oretic analogues of the standard natural numbers:

Denition 31. Dene

a) 1: =0 + 1;
b) 2: =1 + 1;
c) 3: =2 + 1; ...

From the context it will be clear, whether 3, say, is meant to be the standard number three
or the set theoretical object
3 = 2 [ f2g
= (1 + 1) [ f1 + 1g
= (f;g [ ff;gg) [ ff;g [ ff;ggg
= f;; f;g; f;g [ ff;ggg:
The set-theoretic axioms will ensure that this interpretation of three has the important
number-theoretic properties of three.

2.12 Foundation
The axiom schema of foundation provides structural information about the set theoretic uni-
verse V . It can be reformulated by postulating, for any term A :
/ ;!9x 2 A A \ x = ;:
A=
Viewing 2 as some kind of order relation this means that every non-empty class has an 2-min-
imal element x 2 A such that the 2-predecessors of x are not in A. Foundation excludes circles
in the 2-relation:

Lemma 32. Let n be a natural number >1 . Then there are no x0; :::; xn¡1 such that
x0 2 x1 2 ::: 2 xn¡1 2 x0 :

Proof. Assume not and let x0 2 x1 2 ::: 2 xn¡1 2 x0 . Let

A = fx0; :::; xn¡1g:
A=/ ; since n > 1 . By foundation take x 2 A such that A \ x = ; .
Case 1 . x = x0 . Then xn¡1 2 A \ x = ; , contradiction.
Case 2 . x = xi , i > 0 . Then xi¡1 2 A \ x = ; , contradiction. 

Exercise 8. Show that x =

/ x+1.
Exercise 9. Show that the successor function x 7! x + 1 is injective.
Exercise 10. Show that the term fx; fx; ygg may be taken as an ordered pair of x and y .

Theorem 33. The foundation scheme is equivalent to the following, Peano-type, induction
scheme: for every term B postulate
8x (x  B ! x 2 B) !B = V :
The Zermelo-Fraenkel Axioms 13

This says that if a property B is inherited by x if all elements of x have the property B, then
every set has the property B.

Proof. (!) Assume B were a term which did not satisfy the induction principle:
8x (x  B ! x 2 B) and B =
/ V:

Set A = V n B =
/ ; . By foundation take x 2 A such that A \ x = ; . Then
u 2 x!u 2
/ A!u 2 B ;
i.e., x  B . By assumption, B is inherited by x : x 2 B . But then x 2
/ A , contradiction.
( ) Assume A were a term which did not satisfy the foundation scheme:
/ ; and 8x 2 A A \ x =
A= / ;:
Set B = V n A . Consider x  B . Then A \ x = ; . By assumption, x 2 / A and x 2 B . Thus
8x (x  B ! x 2 B). The induction principle implies that B = V . Then A = ;, contradiction. 

This proof shows, that the induction principle is basically an equivalent formulation of the
foundation principle. The 2-relation is taken as some binary relation without reference to spe-
cic properties of this relation. This leads to:
Exercise 11. A relation R on a domain D is called wellfounded, i for all terms A

;=
/ A ^ A  D!9x 2 A A \ fy j yRxg = ;:

Formulate and prove a principle for R-induction on D which coressponds to the assumption that R is well-
founded on D.

2.13 Set Theoretic Axiom Schemas

Note that the axiom system introduced is an innite informal set of axioms. It seems unavoid-
able that we have to go back to some previously given set notions to be able to dene the collec-
tion of set theoretical axioms - another example of the frequent circularity in foundational the-
ories.

Denition 34. The system ZF of the Zermelo-Fraenkel axioms of set theory consists of the
following axioms:
a) The set existence axiom (Ex):
9x8y :y 2 x
- there is a set without elements, the empty set.
b) The axiom of extensionality (Ext):

8x8y(8z(z 2 x $ z 2 y) ! x = y)
- a set is determined by its elements, sets having the same elements are identical.
c) The pairing axiom (Pair):
8x8y9z8w (u 2 z$u = x _ u = y):
- z is the unordered pair of x and y.
d ) The union axiom (Union):
8x9y8z(z 2 y $ 9w(w 2 x ^ z 2 w))
- y is the union of all elements of x.
e) The separation schema (Sep) postulates for every 2-formula '(z; x1; :::; xn):
8x1:::8xn8x9y8z (z 2 y$z 2 x ^ '(z; x1; :::; xn))
14 Section 2

- this is an innite scheme of axioms, the set z consists of all elements of x which satisfy
'.
f ) The powerset axiom (Pow):
8x9y8z(z 2 y $ 8w(w 2 z ! w 2 x))
- y consists of all subsets of x.
g) The replacement schema (Rep) postulates for every 2-formula '(x; y; x1; :::; xn):

8x1:::8xn(8x8y8y 0(('(x; y; x1; :::; xn) ^ '(x; y 0; x1; :::; xn)) ! y = y 0) !

8u9v8y (y 2 v $ 9x(x 2 u ^ '(x; y; x1; :::; xn))))

- v is the image of u under the map dened by '.

h) The axiom of innity (Inf):
9x(9y (y 2 x ^ 8z :z 2 y) ^ 8y(y 2 x ! 9z(z 2 x ^ 8w(w 2 z $ w 2 y _ w = y))))
- by the closure properties of x, x has to be innite.
i ) The foundation schema (Found) postulates for every 2-formula '(x; x1; :::; xn):
8x1:::8xn(9x'(x; x1; :::; xn) ! 9x('(x; x1; :::; xn) ^ 8x 0(x 0 2 x ! :'(x 0; x1; :::; xn))))
- if ' is satisable then there are 2-minimal elements satisfying '.

2.14 ZF in Class Notation

Using class terms, the ZF can be formulated concisely:

Theorem 35. The ZF axioms are equivalent to the following system; we take all free variables
of the axioms to be universally quantied:
a) Ex: ; 2 V.
b) Ext: x  y ^ y  x!x = y .
c) Pair: fx; yg 2 V.
S
d ) Union: x 2 V.
e) Sep: A \ x 2 V.
f ) Pow: P(x) 2 V.
g) Rep: F is a function !F [x] 2 V.
h) Inf: 9x (0 2 x^8n 2 x n + 1 2 x).
i ) Found: A =
/ ;!9x 2 A A \ x = ; .

This axiom system can be used as a foundation for all of mathematics. Axiomatic set theory
considers various axiom systems of set theory.

Denition 36. The axiom system ZF¡ consists of the ZF-axioms except the power set axiom.
The axiom System ST (set theory) onsists of the ZF-axioms except the axiom of innity. The
system EML (elementary set theory) consists of the axioms Ex, Ext, Pair, and Union.

Exercise 12. Consider the axiom system HF consisting of the axioms of EML together with the induction
principle: for every term B postulate
8x; y (x  B ^ y 2 B ! x [ fyg 2 B) !B = V :
Show that every axiom of ZF except Inf is provable in HF, and that HF proves the negation of Inf (HF axio-
matizes the heriditarily finite sets, i.e., those sets such that the set itself and all its iterated elements are
nite).
Ordinal Numbers 15

3 Ordinal Numbers
We had dened some natural numbers in set theory. Recall that
0 = ;
1 = 0 + 1 = 0 [ f0g = f0g
2 = 1 + 1 = 1 [ f1g = f0; 1g
3 = 2 + 1 = 2 [ f2g = f0; 1; 2g





We would then like to have N = f0; 1; 2; 3; :::g. To obtain a set theoretic formalization of num-
bers we note some properties of the informal presentation:
1. Numbers are ordered by the 2-relation:
m < n i m 2 n:
E.g., 1 2 3 but not 3 2 1.
2. On each number, the 2-relation is a strict linear order : 3 = f0; 1; 2g is strictly linearly
ordered by 2.
3. Numbers are complete with respect to smaller numbers
i < j < m ! i 2 m:
This can be written with the 2-relation as
i 2 j 2 m ! i 2 m:

Denition 37.
a) A is transitive, Trans(A), i 8y 2 A8x 2 y x 2 A .
b) x is an ordinal (number), Ord(x), if Trans(x) ^ 8y 2 x Trans(y).
c) Let Ord: =fxjOrd(x)g be the class of all ordinal numbers.

We shall use small greek letter ; ; ::: as variables for ordinals. So 9 ' stands for 9 2 Ord ',
and f j'g for f jOrd( ) ^ 'g.
Exercise 13. Show that arbitrary unions and intersections of transitive sets are again transitive.

We shall see that the ordinals extend the standard natural numbers. Ordinals are particularly
adequate for enumerating innite sets.

Theorem 38.
a) 0 2 Ord.
b) 8 + 1 2 Ord .

Proof. a) Trans(;) since formulas of the form 8y 2 ;::: are tautologously true. Similarly 8y 2
; Trans(y).
b) Assume 2 Ord.
(1) Trans( + 1).
Proof . Let u 2 v 2 + 1 = [ f g.
Case 1 . v 2 . Then u 2  + 1, since is transitive.
Case 2 . v = . Then u 2  + 1. qed (1)
(2) 8y 2 + 1 Trans(y).
Proof . Let y 2 + 1 = [ f g.
Case 1 . y 2 . Then Trans(y) since is an ordinal.
Case 2 . y = . Then Trans(y) since is an ordinal. 

Exercise 14.
T
a) Let A  Ord be a term, A =
/ ; . Then A 2 Ord .
16 Section 3

S
b) Let x  Ord be a set. Then x 2 Ord .

Theorem 39. Trans(Ord).

Proof. This follows immediately from the transitivity denition of Ord. 

Exercise 15. Show that Ord is a proper class. (Hint: if Ord 2 V then Ord 2 Ord.)

Theorem 40. The class Ord is strictly linearly ordered by 2, i.e.,

a) 8 ; ; ( 2 ^ 2 ! 2 ).
b) 8 / .
2
c) 8 ; ( 2 _ = _ 2 ).

Proof. a) Let ; ; 2 Ord and 2 ^ 2 . Then is transitive, and so 2 .

b) follows immediately from the non-circularity of the 2-relation.
c) Assume that there are incomparable ordinals. By the foundation schema choose 0 2 Ord 2-
minimal such that 9 :( 0 2 _ 0 = _ 2 0). Again, choose 0 2 Ord 2-minimal such that :
( 0 2 0 _ 0 = 0 _ 0 2 0). We obtain a contradiction by showing that 0 = 0:
Let 2 0 . By the 2-minimality of 0 , is comparable with 0 : 2 0 _ = 0 _ 0 2 . If
= 0 then 0 2 0 and 0; 0 would be comparable, contradiction. If 0 2 then 0 2 0 by the
transitivity of 0 and again 0; 0 would be comparable, contradiction. Hence 2 0 .
For the converse let 2 0 . By the 2-minimality of 0 , is comparable with 0 : 2 0 _ =
0 _ 02 . If = 0 then 0 2 0 and 0; 0 would be comparable, contradiction. If 0 2
then 0 2 0 by the transitivity of 0 and again 0; 0 would be comparable, contradiction.
Hence 2 0 .
But then 0 = 0 contrary to the choice of 0 . 

Denition 41. Let <: =2\(Ord  Ord) = f( ; )j 2 g be the natural strict linear ordering of
Ord by the 2-relation.

Theorem 42. Let 2 Ord. Then + 1 is the immediate successor of in the 2-relation:
a) < + 1;
b) if < + 1, then = or < .

Denition 43. Let be an ordinal. is a successor ordinal, Succ( ), i 9 = +1. is a

limit ordinal, Lim( ), i =
/ 0 and is not a successor ordinal. Also let
Succ: =f jSucc( )g and Lim := f jLim( )g:

The existence of limit ordinals will be discussed together with the formalization of the natural
numbers.

3.1 Ordinal induction

Ordinals satisfy an induction theorem which generalizes complete induction on the integers:

Theorem 44. Let '(x; v0; :::; vn¡1) be an 2-formula and x0; :::; xn¡1 2 V. Assume that the
property '(x; x0; :::; xn¡1) is inductive, i.e.,
8 (8 2 '( ; x0; :::; xn¡1) ! '( ; x0; :::; xn¡1)):
Then ' holds for all ordinals:
8 '( ; x0; :::; xn¡1):

Proof. It suces to show that

B = fxjx 2 Ord ! '(x; x0; :::; xn¡1)g = V :
Ordinal Numbers 17

Theorem 33 implies
8x (x  B ! x 2 B) !B = V
and it suces to show
8x (x  B ! x 2 B):
Consider x  B. If x 2 / Ord then x 2 B. So assume x 2 Ord. For 2 x we have 2 B, 2 Ord,
and so '( ; x0; :::; xn¡1). By the inductivity of ' we get '(x; x0; :::; xn¡1) and again x 2 B. 

Induction can be formulated in various forms:

Exercise 16. Prove the following transnite induction principle: Let '(x) = '(x; v0; :::; vn¡1) be an 2-for-
mula and x0; :::; xn¡1 2 V . Assume
a) '(0) (the initial case),
b) 8 ('( ) ! '( + 1)) (the successor step),
c) 8 2Lim (8 <  '( ) ! '()) (the limit step).
Then 8 '( ).

3.2 Natural Numbers

We have 0; 1; ::: 2 Ord. We shall now dene and study the set of natural numbers/integers
within set theory. Recall the axiom of innity:
9x (0 2 x ^ 8u 2 x u + 1 2 x):
The set of natural numbers should be the -smallest such x.
T
Denition 45. Let ! = fxj0 2 x ^ 8u 2 x u + 1 2 xg be the set of natural numbers. Sometimes
we write N instead of !.

Theorem 46.
a) ! 2 V.
b) !  Ord.
c) (!; 0; +1) satisfy the second order Peano axiom, i.e.,
8x  ! (0 2 x ^ 8n 2 x n + 1 2 x ! x = !):
d ) ! 2 Ord.
e) ! is a limit ordinal.

Proof. a) By the axiom of innity take a set x0 such that

0 2 x0 ^ 8u 2 x0 u + 1 2 x0 :
Then
\ \
!= fxj0 2 x ^ 8u 2 x u + 1 2 xg = x0 \ fxj0 2 x ^ 8u 2 x u + 1 2 xg 2 V

by the separation schema.

b) By a), ! \ Ord 2 V . Obviously 0 2 ! \ Ord ^ 8u 2 ! \ Ord u + 1 2 ! \ Ord. So ! \ Ord is one
factor of the intersection in the denition of ! and so !  ! \ Ord . Hence !  Ord .
c) Let x  ! and 0 2 x ^ 8u 2 x u + 1 2 x. Then x is one factor of the intersection in the deni-
tion of ! and so !  x . This implies x = !.
d) By b), every element of ! is transitive and it suces to show that ! is transitive. Let
x = fnjn 2 ! ^ 8m 2 n m 2 !g  ! :
We show that the hypothesis of c) holds for x. 0 2 x is trivial. Let u 2 x. Then u + 1 2 !. Let
m 2 u + 1. If m 2 u then m 2 ! by the assumption that u 2 x. If m = u then m 2 x  !. Hence
u + 1 2 x and 8u 2 x u + 1 2 x. By b), x = !. So 8n 2 ! n 2 x , i.e.,
8n 2 ! 8m 2 n m 2 !:
18 Section 3

e) Of course ! =
/ 0 . Assume for a contradiction that ! is a successor ordinal, say ! = +1.
Then 2 ! . Since ! is closed under the +1-operation, ! = + 1 2 ! . Contradiction. 

Thus the axiom of innity implies the existence of the set of natural numbers, which is also the
smallest limit ordinal. The axiom of innity can now be reformulated equivalently as:
h) Inf: ! 2 V .

3.3 Ordinal recursion

Recursion, often called induction, over the natural numbers is a ubiquitous method for dening
mathematical objects. We prove the following recursion theorem for ordinals.

Theorem 47. Let G: V ! V. Then there is a canonical class term F, given by the subsequent
proof, such that
F : Ord ! V and 8 F ( ) = G(F  ):
We then say that F is defined recursively (over the ordinals) by the recursion rule G. F is
unique in the sense that if another term F 0 satises
F 0: Ord ! V and 8 F 0( ) = G(F 0  )
then F = F 0.

Proof. We say that H: dom(H) ! V is G-recursive if

dom(H)  Ord ; dom(H) is transitive, and 8 2dom(H) H( ) = G(H  ):
(1) Let H ; H 0 be G-recursive. Then H ; H 0 are compatible, i.e., 8 2 dom(H) \ dom(H 0) H( ) =
H 0( ).
Proof . We want to show that
8 2 Ord ( 2 dom(H) \ dom(H 0) ! H( ) = H 0( )):
By the induction theorem it suces to show that 2 dom(H) \ dom(H 0) ! H( ) = H 0( ) is
inductive, i.e.,
8 2 Ord (8y 2 (y 2 dom(H) \ dom(H 0) !H(y) = H 0(y)) ! ( 2 dom(H) \ dom(H 0) !H( ) =
H 0( ))):
So let 2 Ord and 8y 2 (y 2 dom(H) \ dom(H 0) !H(y) = H 0(y)). Let 2 dom(H) \ dom(H 0).
Since dom(H) and dom(H 0) are transitive,  dom(H) and  dom(H 0). By assumption
8y 2 H(y) = H 0(y):
Hence H  = H 0  . Then
H( ) = G(H  ) = G(H 0  ) = H 0( ):
qed (1)
Let
[
F : = ff jf is G-recursiveg:

be the union of the class of all approximations to the desired function F .

(2) F is G-recursive.
Proof . By (1), F is a function. Its domain dom(F ) is the union of transitive classes of ordinals
and hence dom(F )  Ord is transitive.
Let 2 dom(F ). Take some G-recursive functionf such that 2 dom(f ). Since dom(f) is trans-
itive, we have
 dom(f)  dom(F ):
Moreover
F ( ) = f ( ) = G(f  ) = G(F  ):
Ordinal Numbers 19

qed (2)
(3) 8 2 dom(F ).
Proof . By induction on the ordinals. We have to show that 2 dom(F ) is inductive in the vari-
able . So let 2 Ord and 8y 2 y 2 dom(F ). Hence  dom(F ). Let
f = F  [f( ; G(F  ))g:
f is a function with dom(f ) = + 1 2 Ord. Let 0< + 1. If 0< then
f ( 0) = F ( 0) = G(F  ) = G(f 
0 0
):
if 0
= then also
f ( 0) = f( ) = G(F  ) = G(f  ) = G(f  0
):
Hence f is G-recursive and 2 dom(f )  dom(F ). qed (3)
The extensional uniqueness of F follows from (1) 

Theorem 48. Let a0 2 V, Gsucc: Ord  V ! V, and Glim: Ord  V ! V. Then there is a canonic-
ally dened class term F : Ord ! V such that
a) F (0) = a0 ;
b) 8 F ( + 1) = Gsucc( ; F ( ));
c) 8 2 Lim F () = Glim(; F  ).
Again F is unique in the sense that if some F 0 also satises a)-c) then F = F 0.
We say that F is recursively dened by the properties a)-c).

Proof. We incorporate a0 , Gsucc , and Glim into a single recursion rule G: V ! V ,

8
>
> a0 , if f = ;;
>
<
Gsucc( ; f ( )) , if f : + 1 ! V ;
G(f ) =
>
> Glim(; f ) , if f:  ! V and Lim();
>
: ; , else:

Then the term F : Ord ! V dened recursively by the recursion rule G satises the theorem. 

In many cases, the limit rule will just require to form the union of the previous values so that
[
F () = F ( ):
<

Such recursions are called continuous (at limits).

3.4 Ordinal Arithmetic

We extend the recursion rules of standard integer arithmetic continuously to obtain transnite
version of the arithmetic operations. The initial operation of ordinal arithmetic is the +1-opera-
tion dened before. Ordinal arithmetic satises some but not all laws of integer arithmetic.

Denition 49. Dene ordinal addition +: Ord  Ord ! Ord recursively by

+0 = 
 + ( + 1) = ( + ) + 1
[
+ = ( + ) , for limit ordinals 
<

Denition 50. Dene ordinal multiplication
: Ord  Ord ! Ord recursively by


0 = 0

( + 1) = (
) + 
[

 = (
) , for limit ordinals 
<
20 Section 4

Denition 51. Dene ordinal exponentiation __ : Ord  Ord ! Ord recursively by

0 = 1
 +1 = 

[
 =  , for limit ordinals 
<

Exercise 17. Explore which of the standard ring axioms hold for the ordinals with addition and multiplica-
tion. Give proofs and counterexamples.
Exercise 18. Show that for any ordinal , + ! is a limit ordinal. Use this to show that the class Lim of
all limit ordinals is a proper class.

4 Number Systems
We are now able to give set-theoretic formalizations of the standard number systems with their
arithmetic operations.

4.1 Natural Numbers

Denition 52. The structure
N: =(!; +(!  !);
(!  !); <(!  !); 0; 1)

is called the structure of natural numbers, or arithmetic. We sometimes denote this structure
by
N: =(!; +;
; <; 0; 1):

N is an adequate formalization of arithmetic within set theory since N satises all standard
arithmetical axioms.
Exercise 19. Prove:
a) + [!  !] := fm + njm 2 ! ^ n 2 !g  ! .
b)
[!  !] := fm
njm 2 ! ^ n 2 ! g  ! .
c) Addition and multiplication are commutative on ! .
d) Addition and multiplication satisfy the usual monotonicity laws with respect to <.

Denition 53. We dene the structure

Z := (Z; +Z;
Z; <Z; 0Z; 1Z)
of integers as follows:
a) Dene an equivalence relation  on N  N by

(a; b)  (a 0; b 0) i a + b 0 = a 0 + b:

b) Let a ¡ b: =[(a; b)] be the equivalence class of (a; b) in . Note that every a ¡ b is a set.
c) Let Z: =fa ¡ bja 2 N ^ b 2 Ng be the set of integers.
d ) Dene the integer addition +Z: Z  Z ! Z by

(a ¡ b) +Z (a 0 ¡ b 0) := (a + a 0) ¡ (b + b 0):

e) Dene the integer multiplication
Z: Z  Z ! Z by

(a ¡ b)
Z (a 0 ¡ b 0) := (a
a 0 + b
b 0) ¡ (a
b 0 + a 0
b):
Number Systems 21

f ) Dene the strict linear order <Z on Z by

(a ¡ b) <Z (a 0 ¡ b 0) i a + b 0 < a 0 + b:
g) Let 0Z: =0 ¡ 0 and 1Z: =1 ¡ 0.

Exercise 20. Check that the above denitions are sound, i.e., that they do not depend on the choice of rep-
resentatives of equivalence classes.
Exercise 21. Check that Z satises (a sucient number) of the standard axioms for rings.

The structure Z extends the structure N in a natural and familiar way: dene an injective map
e: N ! Z by
n 7! n ¡ 0:
The embedding e is a homomorphism:
a) e(0) = 0 ¡ 0 = 0Z and e(1) = 1 ¡ 0 = 1Z;
b) e(m + n) = (m + n) ¡ 0 = (m + n) ¡ (0 + 0) = (m ¡ 0) +Z (n ¡ 0) = e(m) +Z e(n);
c) e(m
n) = (m
n) ¡ 0 = (m
n + 0
0) ¡ (m
0 + n
0) = (m ¡ 0)
Z (n ¡ 0) = e(m)
Z e(n);
d) m < n$m + 0 < n + 0$ (m ¡ 0) <Z (n ¡ 0) $e(m) <Z e(n).
By this injective homomorphism, one may consider N as a substructure of Z : N  Z .

4.2 Rational Numbers

Denition 54. We dene the structure
Q+ + Q Q Q Q Q
0 := (Q0 ; + ;
; < ; 0 ; 1 )

of non-negative rational numbers as follows:

a) Dene an equivalence relation w on N  (N n f0g) by
(a; b) w (a 0; b 0) i a
b 0 = a 0
b:
a a
b) Let b
: =[(a; b)]' be the equivalence class of (a; b) in '. Note that b is a set.
a
c) Let Q+ 0 : =f b ja 2 N ^ b 2 (N n f0g)g be the set of non-negative rationals.

d) Dene the rational addition +Q: Q+ +

0  Q0 ! Q0 by
+

a Q a0 a
b 0 + a0
b
+ 0 := :
b b b
b0
e) Dene the rational multiplication
Q: Q+ + +
0  Q0 ! Q0 by

a Q a0 a
a0

0 := :
b b b
b0
f ) Dene the strict linear order <Q on Q+
0 by

a Q a0
< 0 i a
b 0 < a 0
b:
b b
0 1
g) Let 0Q: = 1 and 1Q: = 1 .

Again one can check the soundness of the denitions and the well-known laws of standard non-
negative rational numbers. Also one may assume N to be embedded into Q+ 0 as a substructure.
The transfer from non-negative to all rationals, including negative rationals can be performed in
analogy to the transfer from N to Z .

Denition 55. We dene the structure

Q := (Q; +Q;
Q; <Q; 0Q; 1Q)
22 Section 4

of rational numbers as follows:

a) Dene an equivalence relation  on Q+ +
0  Q0 by

(p; q)  (p 0; q 0) i p + q 0 = p 0 + q :

b) Let p ¡ q: =[(p; q)] be the equivalence class of (p; q) in .

c) Let Q: =fp ¡ qjp 2 Q+ +
0 ^ p 2 Q0 g be the set of rationals.

Exercise 22. Continue the denition of the structure Q and prove the relevant properties.

4.3 Real Numbers

Denition 56. r  Q+
0 is a positive real number if

a) 8p 2 r 8q 2 Q+ +
0 (q < p! q 2 r), i.e., r is an initial segment of (Q0 ; < );
Q Q

b) 8p 2 r 9q 2 r p <Q q , i.e., r is right-open in (Q+ Q

0 ; < );

/ Q+
c) 0 2 r = +
0 , i.e., r is nonempty and bounded in (Q0 ; < ).
Q

Denition 57. We dene the structure

R+ := (R+; +R;
R; <R; 1R)
of positive real numbers as follows:
a) Let R+ be the set of positive reals.
b) Dene the real addition +R: R+  R+ ! R+ by

r +R r 0 = fp +Q p 0jp 2 r ^ p 0 2 r 0g:

c) Dene the real multiplication
R: R+  R+ ! R+ by

r
R r 0 = fp
Q p 0jp 2 r ^ p 0 2 r 0g:

d ) Dene the strict linear order <R on R+ by

r <R r 0 i r  r 0 ^ r =
/ r 0:
e) Let 1R: =fp 2 Q+ Q
0 jq < 1g.

We justify some details of the denition.

Lemma 58.
a) R+ 2 V.
b) If r; r 0 2 R+ then r +R r 0 , r
R r 0 2 R+.
c) <R is a strict linear order on R+.

Proof. a) If r 2 R+ then r  Q+ + +
0 and r 2 P(Q0 ). Thus R  P(Q0 ), and R is a set by the
+ +

power set axiom and separation.

b) Let r; r 0 2 R+. We show that
r
R r 0 = fp
Q p 0jp 2 r ^ p 0 2 r 0g 2 R+:
Obviously r
R r 0  Q+ +
0 is a non-empty bounded initial segment of (Q0 ; < ).
Q
a a0 a a0 c
Consider p 2 r
R r 0, q 2 Q+0 , q < p . Let p = b

Q Q
b0
where b 2 r and b 0 2 r 0. Let q = d
. Then
c c
b0 Q a0
d
= d
a 0
b 0 , where
c
b0 b0 b0 a a0 b0 a
0
= q
Q 0 <Q p
Q 0 =
Q 0
Q 0 = 2 r :
d
a a a b b a b
Number Systems 23

c
b0
Hence d
a0
2 r and
c c
b 0 Q a0
=
0 2 r
R r 0:
d d
a0 b
Similarly one can show that r
R r 0 is open on the right-hand side.
c) The transitivity of <R follows from the transitivity of the relation $. To show that <R is
/ r 0. Then r and r 0 are dierent subsets of Q+
connex, consider r; r 0 2 R+, r = 0 . Without loss of
generality we may assume that there is some p 2 r 0 n r . We show that then r <R r 0, i.e., r $ r 0.
/ r we have p Q q and q 6Q p . Since r 0 is an initial segment of Q+
Consider q 2 r . Since p 2 0, q2
r.
0


Exercise 23. Show that (R+;
R ; 1R ) is a multiplicative group.

We can now construct the complete real line R from R+ just like we constructed Z from N .
Details are left to the reader. We can also proceed to dene the structure C of complex numbers
from R .
Exercise 24. Formalize the structure C of complex numbers such that R  C .

4.4 Discussion
The constructions carried out in the previous subsections contained many arbitrary choices. One
could, e.g., dene rational numbers as reduced fractions instead of equivalence classes of frac-
tions, ensure that the canonical embeddings of number systems are inclusions, etc. If such
choices have been made in reasonable ways we obtain the following theorem, which contains
everything one wants to know about the number systems. So the statements of the following
theorem can be seen as rst- and second-order axioms for these systems.

Theorem 59. There are structures N; Z; Q; R; and C with the following properties:
a) the domains of these structures which are also denoted by N; Z; Q; R; and C, resp., sat-
isfy
! = N  Z  Q  R  C;
b) there are functions +: C  C ! C and
: C  C ! C on C which are usually written as
binary inx operations;
c) (C; +;
; 0; 1) is a eld; for a; b 2 C write a ¡ b for the unique element z such that a = b +
a
z ; for a; b 2 C with b =
/ 0 write b for the unique element z such that a = b
z ;
d ) there is a constant i, the imaginary unit, such that i
i + 1 = 0 and
C = fx + i
y jx; y 2 Rg;

e) there is a strict linear order < on R such that (R; <; +R2;
 R2; 0; 1) is an ordered
eld.
f ) (R; <) is complete, i.e., bounded subsets of R possess suprema:
/ ;^9b 2 R8x 2 Xx < b ¡! 9b 2 R (8x 2 Xx < b^:9b 0 < b8x 2 Xx < b 0))
8X  R (X =

g) Q is dense in (R; <):

8r; s 2 R (r < s¡!9a; b; c 2 Q a < r < b < s < c);
h) (Q; +Q2;
 Q2; 0; 1) is a eld; moreover
n o
a
Q= ja 2 Z; b 2 Z n f0g ;
b
i ) (Z; +Z2;
 Z2; 0; 1) is a ring with a unit; moreover
Z = fa ¡ b ja; b 2 Ng;

j ) +N2 agrees with ordinal addition on ! ;
 N2 agrees with ordinal multiplication on ! ;

24 Section 5

k ) (N; +1; 0) satises the second-order Peano axioms, i.e., the successor function n 7! n + 1
is injective, 0 is not in the image of the successor function, and
8X  N (0 2 X ^ 8n 2 Xn + 1 2 X ¡! X = N):

This theorem is all we require from the number systems. The details of the previous construc-
tion will not be used again. So we have the standard complex plane, possibly with the identica-
tion of N and !.

i
N
Z
x 0 1 ::: ::: QR

z = x + iy

Remark 60. In set theory the set R of reals is often identied with the sets !! or !2 , basically
because all these sets have the same cardinality. We shall come back to this in the context of
cardinality theory.

5 Sequences
The notion of a sequence is crucial in many contexts.

Denition 61.
a) A set w is an -sequence i w: ! V; then is called the length of the -sequence w and
is denoted by j j. w is a sequence i it is an -sequence for some . A sequence w is
called nite i jwj < ! .
b) A nite sequence w: n ! V may be denoted by its enumeration w0; :::; wn¡1 where we write
wi instead of w(i). One also writes w0:::wn¡1 instead of w0; :::; wn¡1 , in particular if w
is considered to be a word formed out of the symbols w0; :::; wn¡1 .
c) An !-sequence w: ! ! V may be denoted by w0; w1; ::: where w0; w1; ::: suggests a denition
of w .
d ) Let w: ! V and w 0: 0
! V be sequences. Then the concatenation w^w 0: + 0
! V is
dened by
(w^w 0)  = w  and 8i < 0
w^w 0( + i) = w 0(i):
e) Let w: ! V and x 2 V. Then the adjunction wx of w by x is dened as
wx = w^f(0; x)g:
Sequences 25

Sequences and the concatenation operation satisfy the algebraic laws of a monoid with cancella-
tion rules.

Proposition 62. Let w; w 0; w 00 be sequences. Then

a) (w^w 0)^w 00 = w^(w 0 ^w 00).
b) ;^w = w^; = w .
c) w^w 0 = w^w 00 !w 0 = w 00.

There are many other operations on sequences. One can permute sequences, substitute elements
of a sequence, etc.

5.1 (!-)Sequences of Reals

!-sequences are particularly prominent in analysis. One may now dene properties like
lim wi = z i 8" 2 R+9m < !8i < ! (i > m! (z ¡ " < wi ^ wi < z + "))
i!1
or
8x: ! ! R ( lim xi = a ! lim f (xi) = f(a)):
i!1 i!1
If x0; x1; ::: is given then the partial sums
n
X
xi
i=0
are dened recursively as
0
X n+1
X n
X
xi = 0 and xi = ( xi) + xn :
i=0 i=0 i=0

The map ': !2 ! R dened by

1
X n
X
xi xi
'((xi)i<!) = = lim :
2i+1 n!1 2i+1
i=0 i=0

maps the function space 2 surjectively onto the real interval

!

[0; 1] = fr 2 Rj0 6 r 6 1g:

Such maps are the reason that one often identies !2 with R in set theory.

5.2 Symbols and Words

Languages are mathematical objects of growing importance. Mathematical logic takes terms and
formulas as mathematical material. Terms and formulas are nite sequences of symbols from
some alphabet. We represent the standard symbols =, 2, etc. by some set-theoretical terms = _,
2_ , etc. Note that details of such a formalization are highly arbitrary. One really only has to x
certain sets to denote certain symbols.

Denition 63. Formalize the basic set-theoretical symbols by

a) =
_ =0, 2_ =1, ^_ =2, __ =3, ! _ =5, :_ =6, (_ =7, )_ = 8, 9_ =9, 8_ =10.
_ =4, $
b) Variables v_n = (1; n) for n < !.
c) Let L2 = f= _ ; 2_ ; ^_ ; __ ; ! _ ; :_ ; (_;)_; 9_ ; 8_ g [ f(1; n)jn < !g be the alphabet of set theory.
_ ;$
d ) A word over L2 is a nite sequence with values in L2 .
e) Let L2 = fw j9n < ! w: n ! L2g be the set of all words over L2 .
f ) If ' is a standard set-theoretical formula, we let '_ 2 L2 denote the formalization of '.
_ = 9_ v_08_ v_1:_ v_1 2_ v_0 is the formalization of the set existence axiom. If the intention
E.g., Ex
is clear, one often omits the formalization dots and simply writes Ex _ = 9v08v1:v1 2 v0 .
26 Section 6

This formalization can be developed much further, so that the notions and theorems of rst-
order logic are available in the theory ZF. By carrying out the denition of the axiom system
ZF within set theory, one obtains a term ZF _ which represents ZF within ZF. This (quasi) self-
referentiality is the basis for limiting results like the Gödel incompleteness theorems.

6 The von Neumann Hierarchy

We use ordinal recursion to obtain more information on the universe of all sets.

Denition 64. Dene the von Neumann Hierarchy (V ) 2Ord by recursion:

a) V0 = ; ;
b) V +1 = P(V );
S
c) V = < V for limit ordinals  .

We show that the von Neumann hierarchy is indeed a (fast-growing) hierarchy

Lemma 65. Let < 2 Ord. Then

a) V 2 V
b) V  V
c) V is transitive

Proof. We conduct the proof by a simultaneous induction on .

= 0: ; is transitive, thus a)-c) hold at 0.
For the successor case assume that a)-c) hold at . Let < + 1. By the inductive assumption,
V  V and V 2 P(V ) = V +1 . Thus a) holds at + 1. Consider x 2 V . By the inductive
assumption, x  V and x 2 V +1 . Thus V  V +1 . Then b) at + 1 follows by the inductive
assumption. Now consider x 2 V +1 = P(V ). Then x  V  V +1 and V +1 is transitive.
For the limit case S assume that is a limit ordinal and that a)-c) hold at all < . Let < .
Then V 2 V +1  < V = V hence a) holds at . b) is trivial for limit . V is transitive as
a union of transitive sets. 

The V are nicely related to the ordinal .

Lemma 66. For every , V \ Ord = .

Proof. Induction on . V0 \ Ord = ; \ Ord = ; = 0 .

For the successor case assume that V \ Ord = . V +1 \ Ord is transitive, and every element of
V +1 \ Ord is transitive. Hence V +1 \ Ord is an ordinal, say  = V +1 \ Ord . = V \ Ord
implies that 2 V +1 \ Ord =  and + 1 6  . Assume for a contradiction that + 1 <  . Then
+ 1 2 V +1 and + 1  V \ Ord = , contradiction. Thus + 1 =  = V +1 \ Ord .
For the limit case assume that is a limit ordinal and that V \ Ord = holds for all < .
Then
[ [ [
V \ Ord = ( V ) \ Ord = (V \ Ord) = = :
< < <


The foundation schema implies that the V -hierarchy exhausts the universe V .

Theorem 67.
S
a) 8x  2Ord V 9 x  V .
S
b) V = 2Ord V .
The von Neumann Hierarchy 27

S
Proof. a) Let x  2Ord . Dene a function f: x ! Ord by
f(u) = min f ju 2 V g:
S
By the axioms of replacement and union, = ff(u) + 1ju 2 xg 2 V and 2 Ord. Let u 2 x .
Then f (u) < f(u) + 1 6 and u 2 Vf (u)  V . Thus x  V .
S
b) Let B = 2Ord V . By the schema of 2-induction it suces to show that

8x (x  B !x 2 B):
S S
So let x  B = 2Ord V . By a) take such that x  V . Then x 2 V +1  2Ord V =B. 

The V -hierarchy ranks the elements of V into levels.

Denition 68. Dene the rank (function) rk: V ! Ord by

x 2 Vrk(x)+1 n Vrk(x) :

The rank function satises a recursive law.

S
Lemma 69. 8x rk(x) = y 2x rk(y) + 1 .

Proof. Let us prove the statement

[
8x2V rk(x) = rk(y) + 1
y2x
S
by induction on . The case = 0 is trivial. The limit case is obvious since V = < V for
limit  .
For the successor case assume that the statement holds for . Consider x 2 V +1 . If x 2 V the
statement holds by the inductive assumption. So assume that x 2 V +1 n V . Then S rk(x) = .
Let y 2 x  V . Then y 2 V +1 n V for some = rk(y) < . rk(y) + 1  . Thus y 2x rk(y) +
S
1  . Assume that = y 2x rk(y) + 1 < . Let y 2 x . Then rk(y) + 1 6 and y 2 Vrk(y)+1 
V . Thus x  V , x 2 V +1  V , contradicting the assumption that x 2 V +1 n V . 

Lemma 70. Let A be a term. Then A 2 V i 9 A  V .

The previous analysis of the V -hierarchy suggest the following picture of the universe V .

Ord V

+1
V +1

0
28 Section 7

7 The Axiom of Choice

Natural numbers n 2 N are used to enumerate nite sets a as
a = fa0; a1; :::; an¡1g:
Assuming the axiom of choice, one can use ordinals to enumerate any set a as
a = fai j i < g:

Denition 71. The Axiom of Choice, AC is the statement

8x(; 2
/ x ^ 8u; v 2 x(u =
/ v ! u \ v = ;) ! 9z8u 2 x9wu \ z = fwg):
The axiom expresses that for every set x consisting of nonempty pairwise disjoint elements there
exists a choice set z , i.e., for every element u 2 x the intersection u \ z consists exactly of one
element. Thus z chooses one element out of every element of x .

x
z

u :::

It seems intuitively clear that such choices are possible. On the other hand we shall see that the
axiom of choice has unintuitive, paradoxical consequences.

Theorem 72. The following statements are equivalent:

a) AC ;
b) 8x9g (g is a function with domain x ^ 8u 2 x (u =
/ ; ! g(u) 2 u)); such a function g is
called a choice function for x ;
c) 8x9 9ff : $ x .

Proof. a) ! b) Assume AC. Let x be a set. We may assume that every element of x is
nonempty. The class
x 0 = ffug  uju 2 xg
is the image of x under the set valued map u 7! fug  u, and thus a set by replacement. The ele-
ments fug  u of x 0 are nonempty and pairwise disjoint. By AC, take a choice set z for x 0.
Dene a choice function g: x ! V by letting g(u) be the unique element of u such that
(fug  u) \ z = f(u; g(u))g:
The Axiom of Choice 29

b) ! c) Assume b). Let x be a set and let g: P(x) n f;g ! V be a choice function for P(x) n f;g.
Dene a function F : Ord ! x [ fxg by ordinal recursion such that

g(x n F [ ]), if x n F [ ] =
/ ;;
F( )=
x, if x n F [ ] = ;:

At time , the function F chooses an element F ( ) 2 x which has not been chosen before. If
all elements of x have been chosen, this is signaled by F by the value x which is not an element
of x.
(1) Let < and F ( ) = / x . Then F ( ); F ( ) 2 x and F ( ) =/ F ( ).
Proof . F ( ) = / x implies that x n F [ ] =
/ ; and hence F ( ) = g(x n F [ ]) 2 x n F [ ]. Since 2 ,
x nF[ ]= / ; and F ( ) = g(x n F [ ]) 2 x n F [ ]. F ( ) =
/ F ( ) follows from F ( ) 2 x n F [ ]. qed (1)
(2) There is 2 Ord such that F ( ) = x .
Proof . Assume not. Then by (1), F : Ord ! x is injective. Hence F ¡1 is a function and Ord =
F ¡1[x]. By replacement, Ord is a set, but this is a contradiction. qed (2)
By (2) let be minimal such that F ( ) = x . Let f = F  : ! x . By the denition of F , x n
F [ ] = ; , i.e., F [ ] = x and f is surjective. By (1), f is also injective, i.e., f: $ x . S
c) ! a) Assume c). Let the set x consist of S nonempty pairwise disjoint elements. Apply c) to
x . Take an ordinal and a function f: ! x . Dene a choice set z for x by setting
z = ff ()j9u 2 x (f () 2 u ^ 8 < f () 2
/ u)g:
So z chooses for every u 2 x that f() 2 u with  minimal. 

We shall later use the enumeration property c) to dene the cardinality of a set. Zorn's Lemma
is an important existence principle which is also equivalent to AC.

Denition 73. Let (P ; 6) be a partial order.

a) X  P is a chain in (P ; 6) if (X ; 6) is a linear order where (X ; 6) is a short notation
for the structure (X ; 6\X 2).
b) An element p 2 P is an upper bound for X  P i 8x 2 Xx 6 p .
c) (P ; 6) is inductive i every chain in (P ; 6) possesses an upper bound.
d ) An element p 2 P is a maximal element of (P ; 6) i 8q 2 P (q > p! q = p).

Theorem 74. The axiom of choice is equivalent to the following principle, called Zorn's
Lemma: every inductive partial order (P ; 6) 2 V possesses a maximal element.

Proof. Assume AC and let (P ; 6) 2 V be an inductive partial order. Let g: P(P ) n f;g ! V be
a choice function for P(P ) n f;g. Dene a function F : Ord ! P [ fP g by ordinal recursion; if
there is an upper bound for F [ ] which is not an element of F [ ] let
F ( ) = g(fp 2 P n F [ ] j p is an upper bound for F [ ]g);
otherwise set
F( )=P:
At time , the function F chooses a strict upper bound of F [ ] if possible. If this is not pos-
sible, this is signaled by F by the value P .
The denition of F implies immediately:
(1) Let < and F ( ) = / P . Then F ( ) < F ( ).
(2) There is 2 Ord such that F ( ) = P .
Proof . Assume not. Then by (1), F : Ord ! P 2 V is injective, and we get the same contradic-
tion as in the proof of Theorem 72. qed (2)
By (2) let be minimal such that F ( ) = P . By (1), F [ ] is a chain in (P ; 6). Since the partial
order is inductive, take an upper bound p of F [ ]. We claim that p is a maximal element of (P ;
6). Assume not and let q 2 P , q > p. Then q is a strict upper bound of F [ ] and q 2/ F [ ]. But
then the denition of F yields F ( ) = / P , contradiction.
30 Section 8

For the converse assume Zorn's Lemma and consider a set x consisting of nonempty pairwise
disjoint elements. Dene the set of partial choice sets which have empty or singleton intersec-
tion with every element of x :
 [
P= z x j 8u 2 x(u \ z = ;_9wu \ z = fwg) :
S
P is partially ordered by  . If X is a chain in (X ; ) then X is an upper bound for X.
Hence (X ; ) is inductive.
By Zorn's Lemma let z be a maximal element of (X ; ). We claim that z is a total choice set
for x :
(3) 8u 2 x9wu \ z = fwg.
Proof . If not, take u 2 x such that u \ z = ;. Take w 2 u and let z 0 = z [ fwg. Then z 0 2 P , con-
trary to the the -maximality of z. 

Theorem 75. The axiom of choice is equivalent to the following principle, called Hausdor's
Maximality Principle: every partial order (P ; 6) 2 V possesses an -maximal chain X  P, i.e.,
X is a chain, and whenever X 0  P is a chain with X 0  X then X 0 = X .

Proof. It is straightforward to show the equivalence with Zorn's Lemma. See also: Hausdor,
Grundzüge der Mengenlehre, p. 141: Wir haben damit für eine teilweise geordnete Menge A die
Existenz gröÿter geordneter Teilmengen B bewiesen; natürlich kann es deren verschiedene
geben. 

Denition 76. The axiom system ZFC consists of the ZF-axioms together with the axiom of
choice AC.

The system ZFC is usually taken as the foundation of mathematics. The ZF axioms have a good
intuitive motivations. The axiom of choice is more controversial; AC has desirable consequences
like Zorn's Lemma and its applications, but on the other hand AC has some paradoxical and
problematic consequences. The status of AC within set theory can be compared to the parallel
axiom in geometry. Similar to the situation in (non-)euclidean geometry one can show that if
there is a model of the ZF axioms then there is a model of ZFC.

8 Cardinalities
Apart from its foundational role, set theory is mainly concerned with the study of arbitrary
innite sets and in particular with the question of their size. Cantor's approach to innite sizes
follows naive intuitions familiar from nite sets of objects.

Denition 77.
a) x and y are equipollent, or equipotent, or have the same cardinality, written x  y, if
9ff : x $ y .
b) x has cardinality at most that of y, written x 4 y, if 9ff: x ! y is injective.
c) We write x  y for x 4 y and x  y .

These relations are easily shown to satisfy

Lemma 78. Assume ZF. Then

a)  is an equivalence relation on V.
b) x  y!x 4 y ^ y 4 x .
c) x 4 x .
d ) x 4 y ^ y 4 z!x 4 z .
e) x  y!x 4 y .
Cardinalities 31

The converse of b) is also true and proved in an exercise.

Theorem 79. (Cantor - Bernstein) x 4 y ^ y 4 x!x  y .

Assuming the axiom of choice, every set is equipollent with an ordinal (Theorem 72 c). One can
take the minimal such ordinal as the canonical representative of the equivalence class with
respect to .

Denition 80.
a) card(x) = min f j 9ff : $ xg is the cardinality of the set x. One also writes x = card(x).
b) An ordinal  is a cardinal i it  = card(x) for some set x.
c) Let Cd = f 2 Ord j  is a cardinal g be the class of all cardinals, and let Card = f > ! j 
is a cardinal g be the class of innite cardinals.

Let us assume AC until further notice. Then Cantor's two approaches to cardinality agree.

Theorem 81.
a) x 4 y$ card(x) 6 card(y).
b) x  y$ card(x) = card(y).

Proof. a) Let x 4 y and let f : x ! y be injective. Further let fx: card(x) $ x and fy: card(y) $
y . Then fy¡1  f  fx: card(x) ! card(y) is injective. Let z = fy¡1  f  fx[card(x)]  card(y). Then
card(x) = card(z) 6 otp(z) 6 card(y).
Conversely, let card(x) 6 card(y) with fx: card(x) $ x and fy: card(y) $ y as above. Then fy 
fx¡1: x ! y is injective and x 4 y .
b) is trivial. 

As an immediate corollary we get the CantorSchröderBernstein theorem with AC.

Theorem 82. (ZFC) Let a 4 b and b 4 a . Then a  b.

We shall now explore small cardinals. Below !, the notions of natural number, ordinal number
and cardinal number agree.

Theorem 83. For all natural numbers n < ! holds

a) card(n) = n;
b) n 2 Cd .

Proof. a) By complete induction on n.

For n = 0, ;: 0 $ 0 and hence card(0) = 0 .
Assume that card(n) = n. We claim that card(n + 1) = n + 1. Obviously card(n + 1) 6 n + 1 .
Assume for a contradiction that m = card(n + 1) < n + 1 . Take f : m $ n + 1 . Let f (i0) = n.
Case 1 : i0 = m ¡ 1. Then f  (m ¡ 1): (m ¡ 1) $n and card(n) 6 m ¡ 1 < n , contradiction.
Case 2 : i0 < m ¡ 1 . Then dene g: (m ¡ 1) $ n by

f (i) , if i =
/ i0;
g(i) =
f (m ¡ 1) , if i = i0 :
Hence card(n) 6 m ¡ 1 < n , contradiction.
b) follows immediately from a). 

Theorem 84.
a) card(!) = ! ;
b) ! 2 Card .
32 Section 9

Proof. Assume for a contradiction that n = card(!) < ! . Let f : n $ ! . Dene g: (n ¡ 1) !! by


f(i), if f(i) < f(n ¡ 1);
g(i) =
f(i) ¡ 1; if f (i) > f (n ¡ 1):
(1) g is injective.
Proof. Let i < j < n ¡ 1.
Case 1. f (i); f (j) < f (n ¡ 1). Then g(i) = f (i) =
/ f (j) = g(j).
Case 2. f (i) < f (n ¡ 1) < f(j). Then g(i) = f (i) < f (n ¡ 1) 6 f (j) ¡ 1 = g(j).
Case 3. f (j) < f (n ¡ 1) < f (i). Then g(j) = f (j) < f(n ¡ 1) 6 f (i) ¡ 1 = g(i).
Case 4. f (n ¡ 1) < f(i); f (j). Then g(i) = f (i) ¡ 1 = / f (j) ¡ 1 = g(j). qed (1)
(2) g is surjective.
Proof . Let k 2 !.
Case 1. k < f (n ¡ 1). By the bijectivity of f take i < n ¡ 1 such that f (i) = k . Then g(i) =
f (i) = k .
Case 2. k > f (n ¡ 1). By the bijectivity of f take i < n ¡ 1 such that f (i) = k + 1 . Then g(i) =
f (i) ¡ 1 = k . qed (2)
But this is a contradiction to the supposed minimality of n = card(!). 

Lemma 85.
a) card(! + 1) = ! .
b) card(! + !) = ! .
c) card(!
!) = ! .

Proof. a) Dene fa: ! $ ! + 1 by 

! , if n = 0
f (n) =
n ¡ 1 , else
b) Dene fb: ! $ ! + ! by 
m , if n = 2
m
f (n) =
! + m , if n = 2
m + 1
c) Dene fc: ! $ !
! by
f(n) = !
k + l, if n = 2k
(2
l + 1) ¡ 1


9 Finite, countable, uncountable sets

Denition 86.
a) x is nite if card(x) < ! .
b) x is innite if x is not nite.
c) x is countable if card(x) 6 ! .
d ) x is countably innite if card(x) = ! .
e) x is uncountable if x is not countable.

9.1 Finite sets

We have the following closure properties for nite sets:

Theorem 87. Let a; b nite, let x 2 V.

a) Every subset of a nite set is nite.
b) a [ fxg, a [ b, a \ b, a  b, a n b, and P(a) are nite. We have card(P(a)) = 2card(a).
S
c) If ai is nite for i 2 b then i<b ai is nite.
Finite, countable, uncountable sets 33

Proof. Easy. 

Finite sets can be distinguished by dependencies between injective and surjective maps.

Theorem 88. Let a be nite. Then

 inj: surj:

a) 8f f : a !!
!
!
!
!!
!
!! a implies f : a !
!
!!
!!
!
!!
!
!!a
 surj: inj:

b) 8f f : a !
!
!
!!
!
!!
!! a implies f : a !!
!
! !
!!
!
!!
!!a

Using the axiom of choice one can also show the converse.

Theorem 89. Let a be innite. Then

inj:
a) 9ff : ! !!
!
!
!
!! a.
!
!
!
 inj: surj:

b) 9f f : a !!
!
!!
!!
!
!! a and :f : a !
!
!!
!!
!
!!
!!
!a
 surj: inj:

c) 9f f : a !
!
!!
!!
!!
!! a and :f : a !!
!
! !
!!
!
!!
!!a

This yields:

Theorem 90. For a 2 V the following statements are equivalent:

a) a is nite;
 inj: surj:

b) 8f f : a !!
!
!!
!!! a implies f : a !
!
! !
!!
!!
!
!!
!
!!a ;
 surj: inj:

c) 8f f : a !
!!
!
!!!
!
!! a implies f : a !!
!
! !
!!
!
!!
!!a .

If one does not assume the axiom of choice, one can use b) or c) to dene the notion of nite-
ness.

9.2 Countable sets

We have the following closure properties for countable sets:

Theorem 91. Let a; b countable, let x 2 V.

a) Every subset of a countable set is countable
b) a [ fxg, a [ b, a \ b, a  b, a n b are countable
S
c) If an is countable for n < ! then n<! an is countable

Proof. Countability will be shown by exhibiting injections into countable sets. Then a) is
trivial.
b) Let fa: a ! ! and fb: b ! ! be injective. Then dene injective maps:

fa(u) + 1, if u 2 a
f0: a [ fxg ! !; f0(u) =
0, else

2
fa(u) + 1, if u 2 a
f1: a [ b ! !; f1(u) =
2
fb(u), else

f2: a  b ! !; f2(u; v) = 2fa(u)
(2
fb(v) + 1)

c) By the axiom of choice choose a sequence (hn jn < !) of injections hn: an ! ! . Dene
[
f3: an ! ! ; f3(u) = 2n
(2
hn(u) + 1), where n is minimal such that u 2 an :
n<!
34 Section 10

9.3 Uncountable sets

Theorem 92. (Cantor) x  P(x)

Proof. card(x) 6 card(P(x)) is clear. Assume that card(x) = card(P(x)) and let f : x $ P(x) be
bijective. Dene
a = fu 2 xju 2
/ f (u)g  x:
Let a = f (u0). Then
u0 2 f (u0) $ u0 2 a $ u0 2 f (u0):
Contradiction. Hence card(x) < card(P(x)). 

Theorem 93. @ := card(P(!)) is an uncountable cardinal.

Note that by previous exercises or lemmas we have

card(P(!)) = card(R) = card(2!) = card(!!)
Cantor spent a lot of eort on determining the size of @ and postulated that @ is the smallest
uncountable cardinal.

10 The Alefs
Theorem 94. 8 9 2 Card  > . Hence Card is a proper class of ordinals.

Proof. Let > !. Then  = card(P( )) > card( ). And  > since otherwise card(P( )) 6
and card(card(P( ))) 6 card( ). 

Denition 95. For any ordinal  let  + be the smallest cardinal > .
S
Theorem 96. Let X  Cd be a set. Then X 2 Cd.
S
Proof. Set  = X.  is an ordinal. Assume that card() < . Take  2 X such that card() <
. Then  6  and card() 6 card() < . But card() =  because  is a cardinal. 

This allows the following

Denition 97. Dene the alef sequence

(@ j 2 Ord)
recursively by
@0 = !
@ +1 = @+
[
@ = @ for limit ordinals 
<

Obviously
Card = f@ j 2 Ordg
is the class of all cardinals.

Denition 98. An innite cardinal of the form @ +1 is a successor cardinal. An innite car-
dinal of the form @ with  a limit ordinal is a limit cardinal.

Exercise 25. There are cardinals  such that  = @k .

Cardinal Arithmetic 35

11 Cardinal Arithmetic
For disjoint nite sets a and b natural addition and multiplication satises
card(a [ b) = card(a) + card(b) and card(a  b) = card(a)
card(b):
This motivates the following extension of natural arithmetic to all cardinals.

Denition 99. Let ;  nite or innite cardinals. Then let

a)  +  = card(a [ b), where a; b are disjoint sets with  = card(a) and  = card(b);  +  is
the (cardinal) sum of  and  .
b) 
 = card(  ); 
 is the (cardinal) product of  and  .
c)  = card();  is the (cardinal) power of  and  .

Note that we are using the same notations as for ordinal arithmetic. It will usually be clear
from the context whether ordinal or cardinal operations are intended.
The arithmetic properties of certain set operations yield usual arithmetic laws for cardinal
arithmetic.

Lemma 100.
a) Cardinal addition is associative and commutative with neutral element 0.
b) Cardinal multiplication is associative and commutative with neutral element 1.
c) 
( + ) = 
 + 
 .
d ) 0 = 1 , 0 = 0 for  =
/ 0, 1 = , 1 = 1, +  = 
  , 
 = () .

Proof. c) Let a; b be disjoint sets with  = card(a) and  = card(b). Then


( + ) = card(  (a [ b))
= card((  a) [ (  b))
= card((  a)) + card((  b))
= 
+ 
;
using that   (a [ b) = (  a) [ (  b) and that   a and   b are disjoint.
d)
0 = card(0) = card(f;g) = card(1) = 1:
In case  =
/ 0 we have that 0 = ff jf :  ! ;g = ; and thus
0 = card(0) = card(;) = 0:
For 1 =  consider the map  $ 1 given by 7! f(0; )g.
For 1 = 1 observe that 1 = ff( ; 0)j < gg is a singleton set.
Let a; b be disjoint sets with  = card(a) and  = card(b). Then
+  = card(a[b)
= card((a)  (b))
= card(a)
card(b)
= 
  ;
using that a[b
  (a)  (b) via the map f 7! (f  a; f  b).
Finally,

 = card()
= card( ())
= card() 
= ()  ;
36 Section 12

using that 

  () via the map
f 7! (f j < )
where f:  !  with f() = f ( ; ), 

12 Wellfounded Relations
The axiom schema of foundation yields an induction theorem for the 2-relation, and in the pre-
vious section we have seen a recursive law for the rank-function. We generalize these techniques
to wellfounded relations. The results of this section do not require the axiom of choice.

Denition 101. Let R be a relation on a domain D.

a) R is wellfounded, i for all terms A
;=
/ A ^ A  D!9x 2 A A \ fy j yRxg = ;:

b) R is strongly wellfounded i it is wellfounded and

8x 2 D fy 2 D j yRxg 2 V :

c) R is a wellorder i R is a wellfounded strict linear order.

d ) R is a strong wellorder i R is a strongly wellfounded wellorder.

By the scheme of foundation, the 2-relation is strongly wellfounded. The ordinals are strongly
wellordered by <. There are wellfounded relations which are not strongly wellfounded: e.g., let
R  Ord  Ord,
xRy i (x =
/ 0^ y=
/ 0 ^ x < y) _ (y = 0 ^ x =
/ 0);
be a rearrangement of (Ord; <) with 0 put on top of all the other ordinals.
For strongly wellfounded relations, every element is contained in a set-sized initial segment of
the relation.

Lemma 102. Let R be a strongly wellfounded relation on D. Then

8x  D9z (z  D ^ x  z ^ 8u 2 z8vRu v 2 z):
Moreover for all x  D, the R-transitive closure
\
TCR(x) = fz jz  D ^ x  z ^ 8u 2 z8vRu v 2 z g

of x is a set. In case R is the 2-relation, we write TC(x) instead of TC2(x).

Proof. We prove by R-induction that

8x 2 D TCR(fxg) 2 V :
So let x 2 D and 8yRx TCR(fyg) 2 V . Then
[
z = fxg [ TCR(fyg) 2 V
yRx

by replacement. z is a subset of D and includes fxg. z is R-closed, i.e., closed with respect to
R-predecessors: each TCR(fyg) is R-closed, and if y R x then y 2 fyg  TCR(fyg)  z . So
TCR(fxg) is the intersection of a non-empty class, hence a set.
Finally observe that we may set
[
TCR(x) = TCR(fyg):
y2x


Exercise 26. Show that for an ordinal , TC( ) = and TC(f g) = +1.
Wellfounded Relations 37

For strongly wellfounded relations, the following recursion theorem holds:

Theorem 103. Let R be a strongly wellfounded relation on D . Let G: V ! V. Then there is a

canonical class term F, given by the subsequent proof, such that
F : D ! V and 8x 2 D F (x) = G(F  fy j yRxg):
We then say that F is dened by R-recursion with the recursion rule G. F is unique in the sense
that if another term F 0 satises
F 0: D ! V and 8 2 D F 0(x) = G(F 0  fy j yRxg)
then F = F 0.

Proof. We proceed as in the ordinal recursion theorem. Let

F~: =ff j9z  D (8x 2 z fy j yRxg  z ; f : z ! V and 8x 2 z f (x) = G(f  fy j yRxg))g
be the class of all approximations to the desired function F .
(1) Let f ; g 2 F~. Then f ; g are compatible, i.e., 8x 2 dom(f ) \ dom(g) f (x) = g(x).
Proof . By induction on R . Let x 2 dom(f ) \ dom(g) and assume that 8yRx f (y) = g(y). Then
f  fy j yRxg = g  fy j yRxg

f (x) = G(f  fy j yRxg) = G(g  fy j yRxg) = g(x):

qed (1)
By the compatibility of the approximation functions the union
[
F= F~

is a function dened on dom(F )  D . dom(F ) is R-closed since the domain of every approxima-
tion is R-closed.
(2) 8x 2 dom(F ) (fy j yRxg  dom(F ) ^ F (x) = G(F  fy j yRxg)).
Proof . Let x 2 dom(F ). Take some approximationf 2 F~ such that x 2 dom(f ). Then
fy j yRxg  dom(f )  dom(F ) and

F (x) = f (x) = G(f  fy j yRxg) = G(F  fy j yRxg):

qed (2)
(3) D = dom(F ).
Proof . We show by R-induction that 8x 2 D x 2 dom(F ). Let x 2 D and assume that 8yRx y 2
dom(F ). TCR(fy j yRxg)  dom(F ) since dom(F ) is R-closed. Then

f = (F  TCR(fy j yRxg)) [ f(x; G(F  fy j yRxg))g

is an approximation with x 2 dom(f), and so x 2 dom(F ). 

Exercise 27. Dene set theoretic operations

x + y = x [ fx + z jz 2 y g
and
[
x
y= (x
z + x)
z2y

and study their arithmetic/algebraic properties. Show that they extend ordinal arithmetic.

Theorem 104. Let R be a strongly wellfounded relation on D and suppose that R is exten-
 and an iso-
sional, i.e., 8x; y 2 D (8u (uRx$uRy) !x = y). Then there is a transitive class D
 
morphism : (D; R) $ (D ; 2). D and  are uniquely determined by R and D, they are called the
Mostowski-collapse of R and D.

Proof. Dene : D ! V by R-recursion with

(x) = f(y)jyRxg:
38 Section 12

Let D = rng().

(1) D is transitive.
Proof . Let (x) 2 D  and u 2 (x) = f(y)jyRxg. Let u = (y), yR x . Then u 2 rng() = D .
qed (1)
(2)  is injective.
Proof . We prove by 2-induction that every z 2 D  has exactly one preimage under  . So let z 2

D and let this property be true for all elements of z . Assume that x; y 2 D and (x) = (y) = z .
Let u Rx . Then (u) 2 (x) = (y) = f(v)jv R yg. Take v R y such that (u) = (v). By the
inductive assumption, u = v, and uRy . Thus 8u (uRx!uRy). By symmetry, 8u (uRx$uRy).
Since R is extensional, x = y . So z has exactly one preimage under  . qed (2)
(3)  is an isomorphism, i.e.,  is bijective and 8x; y 2 D (xRy$(x) 2 (y)).
Proof . Let x; y 2 D. If x R y then (x) 2 f(u)ju R y g = (y). Conversely, if (x) 2
f(u)ju R yg = (y) then let (x) = (u) for some u Ry . Since  is injective, x = u and x R y .
qed (3)
Uniqueness of the collapse D and  is given by the next theorem. 

Theorem 105. Let X and Y be transitive and let : X $ Y be an 2-2-isomorphism between X

and Y, i.e., 8x; y 2 X (x 2 y $ (x) 2 (y)). Then  = id  X and X = Y.

Proof. We show that (x) = x by 2-induction over X. Let x 2 X and assume that 8y 2
x (y) = y .
Let y 2 x. By induction assumption, y = (y) 2 (x). Thus x  (x).
Conversely, let v 2 (x). Since Y = rng() is transitive take u 2 X such that v = (u). Since  is
an isomorphism, u 2 x. By induction assumption, v = (u) = u 2 x. Thus (x)  x. 

If R is a well-order on D then R is obviously extensional. We study the Mostowski collapse of

strongly well-ordered relations.

Theorem 106. Let R be a strongly well-ordered relation on D. Let : (D; R) $ (D  ; 2) be the


Mostowski-collapse of R and D. If D is a proper class then D = Ord. If D is a set then D  is

an ordinal which is called the ordertype of (D; R). We then write D = otp(D; R).

Proof. D  is transitive since it is a Mostowski collapse.

(1) Every element of D  is transitive.
Proof . Let x 2 y 2 z 2 D . Since D  is transitive, x; y; z 2 D
 and there are a; b; c 2 D such that x =
(a), y = (b), and z = (c). Since  is an order-isomorphism, aRbRc . Since R is a transitive
relation, aRc . This implies x 2 z . qed (1)
(2) Every element of D  is an ordinal.

Proof . Let z 2 D . z is transitive, and it remains to show that every element of z is transitive.
Let y 2 z . Then y 2 D  and so y is transitive by (1). qed (2)
Consider the case that D is a proper class. Then D  is a proper class of ordinals. D  must be
unbounded in the ordinals, since it would be a set otherwise. By transitivity, every ordinal
which is smaller than some element of D  is an element of D  . Hence D
 = Ord.
If D is a set, then D is a transitive set, and by (1), D  2 Ord. 

By Lemma 105, any order-isomorphism : ( ; <) $ ( ; <) between ordinals must be the iden-
tity. So the ordertype of a set-sized well-order (D; R) is the unique ordinal, to which it is order-
isomorphic.

Lemma 107. Let x  2 Ord. Then (x; <) is a well-order. Let : (x; <) $ (opt(x; <); <) be
the Mostowski collapse of (x; <). Then 8 2 x  > () and otp(x; <) 6 .

Proof. By induction on  2 x . Let  2 () = f()j 2 x ^  <  g. Let  = () with  2 x ^  <
 . By induction  = () 6  <  . Thus ()   and () 6  .
Similarly consider  2 otp(x; <) = f()j 2 xg. Let  = () with  2 x . Then  = () 6  < .
Thus otp(x; <)  . 
Further Cardinal Arithmetic 39

13 Further Cardinal Arithmetic

We determine the values of cardinal addition and multiplication for innite cardinals.

Denition 108. Dene the Gödel ordering <2 of Ord  Ord by

( ; ) <2 ( 0 ; 0
) i max ( ; ) < max ( 0; 0);
or max ( ; ) = max ( 0; 0) ^ < 0
;
or max ( ; ) = max ( 0; 0) ^ = 0
^ < 0
:

Lemma 109. <2 is a wellordering of Ord  Ord . Let G: (Ord  Ord; <2) $ (Ord; <) be the
Mostowski collapse of (Ord  Ord; <2). G is the Gödel pairing function. Dene inverse func-
tions G1: Ord ! Ord and G2: Ord ! Ord such that
8 G(G1( ); G2( )) = :

Lemma 110. G: @  @ $ @ .

Proof. By induction on .
Case 1 . = 0 . By the denition of <2, @0  @0 is an initial segment of <2. Let
G[@0  @0] =  2 Ord :
We show that  = @0 . Since @0  @0 is innite,  > @0 . Assume that  > @0 . Take m; n 2 ! such
that G(m; n) = !. Then (m; n) has innitely many predecessors in <2. But on the other hand
f(k; l)j(k; l) <2 (m; n)g  (max (m; n) + 1)  (max (m; n) + 1)
is nite. Hence G[@0  @0] = @0 .
Case 2 . > 0 and the Lemma holds for < . Let
G[@  @ ] =  2 Ord :
We show that  = @ . Since card(@  @ ) > @ we have  > @ . Assume that  > @ . Take (;
) 2 @  @ such that G(; ) = @ . Then G witnesses that
f( 0;  0)j( 0;  0) <2 (; )g  @ :
On the other hand set @ = card(max ( ; ) + 1) < @ . Then, using the inductive hypothesis,
card(f( 0;  0)j( 0;  0) <2 ( ; )g) 6 card((max (; ) + 1)  (max (; ) + 1))
= card(@  @ )
= @ <@ ;
contradiction. Hence G[@  @ ] = @ . 

Theorem 111.
a) If  2 Card then 
 =  .
b) If  2 Card and  2 Cd,  =
/ 0 then 
 = max (; ) .
c) If  2 Card and  2 Cd then  +  = max (; ) .

Proof. a) 
 = card(  ) =  , by the properties of the Gödel pairing function.

b) The map i 7! (i; 0) injects  into    , and the map j 7! (0; j) injects  into    . Hence ;
 6 
 . Thus
(a)
max (; ) 6 
 6 max (; )
max (; ) =
=
=
==
=
== max(; ):
=
=
=
c) Obviously   f0g   and   f1g   . The inclusion
(f0g  ) [ (f1g  )  max (; )  max (; )
implies
(a)
max (; ) 6  +  6 max (; )
max (; ) =
=
=
==
=
== max(; ):
=
=
= 
40 Section 14

For innite cardinal exponentiation the situation is very dierent. Only a few values can be
determined explicitely.

Lemma 112. For  2 Card and 1 6 n < ! we have n =  .

Proof. By complete induction. 1 =  was proved before. And

n+1 = (n)
1 = 
 = : 

The next exponential value 2@0 is however very undetermined. It is possible, in a sense to be
made precise later, that 2@0 is any successor cardinal, like e.g. @13 .
Cantor's continuum hypothesis is equivalent to the cardinal arithmetic statement

2@0 = @1 :

Lemma 113. For  2 Card and 2 6  6 2 we have  = 2.

Proof.
2 6  6 (2) = 2
 = 2: 

14 Conality
To get some more information on cardinal exponentiation, we need to measure how fast a car-
dinal can be approximated using smaller cardinals.

Denition 114.
a) A set x   is conal in the limit ordinal  if 8 < 9 2 x <  .
b) The conality of a limit ordinal  is
cof() = min fotp(x)jx   is conal in g:

c) A limit ordinal  is regular if cof() =  ; otherwise  is singular.

These notions are due to Felix Hausdor, who called them konnal and Konnalität. Please
observe the konnal in German.

Lemma 115.
a) cof() = min fcard(x)jx   is conal in g
b) cof(@0) = @0 , i.e., @0 is regular
c) cof() 6 card() 6 
d ) cof() 2 Card
e) cof() is regular, i.e., cof(cof()) = cof()
f ) If is a limit ordinal then cof(@ ) = cof( )
g) cof(@!) = @0 , i.e., @! is a singular cardinal

Proof. a) > holds since otp(x) > card(x). Conversely let x have minimal cardinality such that x
is conal in  and let f: card(x) $ x . Dene a weakly increasing map g: card(x) !  by
[
g(i) = f (j) :
j <i

g is welldened by the minimality of x . y = g[card(x)] is conal in  . y is order-isomorphic to

fi < card(x)j8j < ig(j) < g(i)g  card(x):
Cofinality 41

Hence
otp(y) = otp(fi < card(x)j8j < ig(j) < g(i)g) 6 card(x):
Thus
cof() 6 otp(y) = card(x) = min fcard(x)jx   is conal in g:
b) ¡ d) follow from a).
e) Let x   be conal in in  with otp(x) = cof() and order-isomorphism f : cof() $ x . Let
y  cof() be conal with otp(y) = cof(cof()) and order-isomorphism g: cof(cof()) $ y . Then
z = f  g[cof(cof())] is conal in  with otp(z) = cof(cof()). Hence
cof() 6 otp(z) = cof(cof()):
The converse inequality follows from c).
f ) (6) Let x be conal in with otp(x) = cof( ). Then f@i ji 2 xg is conal in @ with
otp(f@i ji 2 xg) = otp(x) = cof( ):
Hence cof(@ ) 6 cof( ).
(>) Now let y be conal in @ with otp(y) = cof(@ ). Dene x = fi < j9 2 y @i 6  < @i+1g.
Then x is conal in with card(x) 6 card(y) = cof(@ ). Hence cof( ) 6 cof(@ ). 

Theorem 116. Every successor cardinal @ +1 is regular.

Proof. Assume that @ +1 is singular. Let x have minimal cardinality such that x is conal in
@ +1 . Then card(x) 6 @ . Let f: @ ! x be surjective. Using the axiom of choice take a
sequence (gi j0 < i < @ +1) of surjective functions gi: @ ! i . Dene function h: @  @ ! @ +1
by
h(; ) = gf ()():
(1) h: @  @ ! @ +1 is surjective.
Proof . Let  2 @ +1 . Take  < @ such that f () >  . gf (): @ ! f () is surjective. Take  < @
such that gf ()() = . Thus  = h(; ) 2 ran(h). qed (1)
This implies
@ +1 = card(@ +1) 6 card(@ @ )=@
@ =@ :
Contradiction. 

So @0; @1; @2; :::; @n; ::: are all regular.

Question 117. (Hausdor) Are there regular limit cardinals >@0 ?

Denition 118. For (i ji < ) a sequence of nite or innite cardinals dene the sum
!
X [
i = card i  fig
i< i<
and the product
Y ¡
i = card i<i

i<
where
i<Ai = ff jf:  ! V ^ 8i < f (i) 2 Aig:
Theorem 119. (König) If (i ji < ) and (i ji < ) are sequences of cardinals such that 8i <
i < i then
X Y
i < i
i< i<

P Q S
Proof. Assume for a contradiction that i< i > i< i and that G: i< i  fig $ i<i
were a surjection. For i < 
card(fG( ; i)(i)j < ig) 6 i < i ;
42 Section 14

and one can choose i 2 i n fG( ; i)(i)j < ig. Dene f 2 i<i by
f (i) = i :
Since G is surjective, take (0; i0) 2 dom(G) such that G(0; i0) = f . Then
G(0; i0)(i0) = f(i0) = i0 =
/ G( ; i0)(i0)
for all  < i0 . Contradiction. 

Theorem 120. If ;  are cardinals such that  > 2 and  > @0 then
cof() > 
Hence
cof(2@0) > @1
and in particular
2@0 =
/ @! :

Proof. Assume that cof() 6  . Then there is a function f :  !  such that ran(f) is conal
S
in . Then i< f (i) =  and so
! ! !
[ [ [ X
 = card

f (i) 6 card f (i)  fig = card card(f(i))  fig = card(f (i)):
i< i< i< i<

But by König's Theorem,

Y X
 = 
 = () =  > card(f (i)): 
i< i<

Theorem 121. (The Hausdor recursion formula)

@ @
@ +1 = @
@ +1 :

Proof. Distinguish two cases:

Case 1 : @ +1 6 2@ . Then
@ @ @ @
@ +1 = 2 =@ =@
@ +1 :

Case 2 : 2@ < @ +1 : Then @ < @ +1 . Using the regularity of @ +1

@
@
@ +1
@ @
6 @ +1
@ +1 =
@
=@ +1 = card(ff jf : @ ! @ +1g)
!
[
= card ff jf: @ !  g
 <@ +1
X
6 card(ff jf : @ !  g)
 <@ +1
X
= card(ff jf : @ ! card()g)
 <@ +1
X
= card()@
 <@ +1
X @
6 @
 <@ +1

@
= @
@ +1


Cardinal exponentiation and the Generalized Continuum Hypothesis 43

15 Cardinal exponentiation and the Generalized Continuum

Hypothesis
The function  7! 2 is called the continuum function, due to the relations between 2@0 and the
usual continuum of real numbers. The beth numbers are dened in analogy with the aleph func-
tion, using the 2-operation instead of the cardinal successor function.

Denition 122. Dene the sequence

(i j 2 Ord)
of beth numbers recursively by
i0 = @0
i +1 = 2i
[
i = i for limit ordinals 
<

Like every continuous ordinal function, there are xed points i = of this sequence.

Denition 123.
a) An inaccessible cardinal  is a regular xed point of the @ -function:
 = @ and cof() = :

b) A strongly inaccessible cardinal  is a regular xed point of the i -sequence:

 = i and cof() = :

The existence of inaccessible and strongly inaccessible cardinals can not be shown in ZFC,
provided the theory ZFC is consistent.

Denition 124. Dene the gimel function j: Card ! Card by j() = cof().

By König's theorem, j() >  . Note that @ (Alef), i (Beth) and j (Gimel) are the rst three let-
ters of the Hebrew alphabet. The gimel function determines all values of the continuum func-
tion.

Denition 125. For  2 Cd and  2 Card let

[
< = card():
 <
Theorem 126.
a) If  is regular then 2 = j().
b) If  is a singular cardinal and the continuum function is eventually constant below  ,
i.e.,
9 < 8 ( 6  < !2 = 2);
then 2 = 2<.
c) If  is a singular cardinal and the continuum function is not eventually constant below 
then 2 = j(2<).

Proof. a) If  is regular then

2 =  = cof() = j():
Now let  be singular and let the sequence (i ji < cof()) be strictly increasing and conal in  .
For i < cof() choose (AC) an injection fi: P(i) ! 2< . Dene

G: P() ! cof()(2<)
44 Section 15

by
x7! (fi(x \ i)ji < cof()):
We argue that G is injective: let x; y 2 P(), x = / y. Then take i < cof() such that x \ i =
/ y\
i . Since fi is injective: fi(x \ i) =
/ fi(y \ i). Then G(x) =
/ G(y) because
G(x)(i) = fi(x \ i) =
/ fi(y \ i) = G(y)(i):
By the injectivity of G
2 6 (2<)cof():
b) Let 2< = 2 be the eventually constant value of the continuum function below  . Then

2< 6 2 6 (2<)cof() = (2)cof() = 2
cof() = 2max(;cof()) = 2 = 2<:

c) In this case we show that cof() = cof(2<). The function

i7!2i
is not eventually constant and thus maps cof() conally into 2<. Hence cof(2<) 6 cof().
Assume that cof(2<) < cof(). Let z  2< be conal such that card(z) < cof(). Then
z = fij9 2 z 2i 6  < 2i+1g  cof()
is conal in cof() and card(z) 6 card(z) < cof(), contradiction.
So we obtain
j(2<) = (2<)cof(2 = (2<)cof() 6 (2)cof() 6 2 6 (2<)cof() = (2<)cof(2
< <
) )
= j(2<):


The following theorem shows that  is uniquely determined by the gimel function.

Theorem 127. Let  2 Card. Then  is determined by the previous theorem and by recursion
on :
a) 0 = 0, 1 = 1.
b) For 2 6  6  we have  = 2.
c) If  >  and  <  such that   >  then  =  .
d ) If  > , 8 <    <  , and cof() >  then  =  .
e) If  > , 8 <    <  , and cof() 6  then  = j() .

Proof. a) and b) follow immediately from earlier results.

c)   6  6 ( ) =  .
d) cof() >  implies that every function from  into  is bounded by some ordinal  <  . Hence
 6  = cardff jf :  ! g
!
[
= card ff jf :  !  g
 <
X
6 card(ff jf :  !  g)
 <
X
= card(ff jf :  ! card()g)
 <
X
= card()
 <
X
6 
 <
= :
Cardinal exponentiation and the Generalized Continuum Hypothesis 45

e) Let (i ji < cof()) be a strictly increasing sequence which is conal in  . Dene a function

G:  ! i<cof() i
by
f 7! (fi ji < cof())
where 
f ( ), if f ( ) < i
fi( ) =
0, else

Then G is injective: Let f ; g 2 , f = / g . Take such that f( ) = / g( ) and take i such that
f ( ); g( ) < i . Then fi( ) = f ( ) = / gi , and hence G(f ) =
/ g( ) = gi( ), fi = / G(g).
Using G we get
Y
j() = cof() 6  6 card(i)
i<cof()
Y
6 
i<cof()

= cof() = j()


Denition 128. (Hausdor) The generalized continuum hypothesis (GCH) is the statement
8 2 Card 2 = +:

This is the minimal hypothesis in view of Cantor's 2 > +. The GCH generalizes Cantor's
continuum hypothesis CH and also the hypothesis 2@1 = @2 also expressed by Cantor. Since CH
is independent of the axioms of set theory, GCH is independent as well. Indeed the continuum
function is hardly determined by the axioms of ZFC and one can for example have
2@0 = @73; 2@1 = @2015 ; :::
Obviously

Lemma 129. GCH implies that 8 2 Card j() = +.

Thus GCH also determines all values of the  function. Axiomatic set theory proves that one
can assume GCH without the danger of adding inconsistencies to the system ZFC: a model of
the ZFC axioms can be modied into a model of ZFC + GCH. The consequences of GCH for
cardinal exponentiation can be readily described.

Theorem 130. Assume GCH. Then for ;  2 Card  is determined as follows:

a) For  < cof():  =  .
b) For cof() 6  6  :  = +.
c) For  >  :  = +.

Proof. a)
 6 
= cardff jf:  ! g
[
= card ff jf :  !  g
 <
X
6 card()
 <
X
6 
 <
= :
46 Section 16

b) By GCH and König's theorem, cof() = +. Thus

+ = cof() 6  6  = 2 = +:
c)
+ = 2 6  6  = 2 = +: 
Q
Question 131. Is every (innite) cardinal product i< i also determined by GCH?

16 Closed unbounded and stationary sets

The continuum function  7! 2 satises the laws
a)  6 !2 6 2
b) cof(2) > 
Axiomatic set theory shows that for regular cardinals  these are the only laws deducible from
ZFC: for (adequate) functions F : Card ! Card satisfying a) and b) for regular cardinals there is
a model of set theory in which
 regular !2 = F ():
So there remains the consideration of 2 for singular cardinals . Indeed singular cardinal expo-
nentiation satises some interesting further laws and is an area of present research. To prove a
few of these laws we have to extend the apparatus of uncountable combinatorics.

Denition 132. Let  2 Card and C   . C is unbounded in  if

8 < 9 2 C < :
C is closed in  if
8 <  ( is a limit ordinal ^C \  is unbounded in ! 2 C):
Thus C contains its limit points < .
C is closed unbounded, or cub in , if C is unbounded in  and closed in  .

Exercise 28. Dene a topology on  such that the closed sets of the topology are exactly the closed sets in
the sense of the previous denition.

Lemma 133. Let  2 Card, cof() > !1 and C ; D be closed unbounded in  . Then C \ D is cub
in  .

Proof. C \ D is closed in  : Let  <  be a limit ordinal and a limit point of C \ D. Then  is
a limit point of C and  2 C. Similarly  2 D and together  2 C \ D .
C \ D is unbounded in  : Let < . Dene a sequence ( n jn < !) by recursion:

the least element of C which is larger than ; 0; :::; n¡1 in case n is even
n =
the least element of D which is larger than 0; :::; n¡1 in case n is odd
S
Let = n<! n . is a limit ordinal > . <  since cof() > !1 . By construction, is a
limit point of C and of D. Hence 2 C \ D. 

Exercise 29. Let  2 Card, cof() > !1 . Let (Ci ji < ) be a sequence of sets Ci which are closed unbounded
T
in  and let < cof() . Then i< Ci is cub in  .

Denition 134. Let  2 Card, cof() > !1 . The closed unbounded lter on  is
C = fX  jthere is a set C  X which is closed unbounded in g:
Closed unbounded and stationary sets 47

Lemma 135. C is a cof()-complete lter on  , i.e.

a) ; =
/ C  P()
b) ; 2
/ C
c) X 2 C ^X  Y  !Y 2 C
d ) X 2 C ^Y 2 C !X \ Y 2 C
T
e) < cof() ^ fXi ji < g  C ! i< Xi 2 C

Proof. c) and d) follow from Lemma 133 and Exercise 29. 

A lter captures a notion of large set. Even intersections of large sets are large, so that certain
contructions can be continued on large sets. Largeness also yields notions of small and of not
small, called non-stationary and stationary.

Denition 136. Let  2 Card, cof() > !1 .

a) X   is non-stationary in  if  n X 2 C . We call
NS = fX j  n X 2 C g
the non-stationary ideal on  .
b) X   is stationary in  if X 2
/ NS .

Lemma 137. X   is stationary in  i X \ C =

/ ; for every cub C   .

Proof. X is stationary i X 2/ NS i  n X 2/ C i there is no C   cub such that C   n X

i for every cub C   C *  n X i for every cub C   X \ C = / ;. 

Lemma 138. Every set in C is stationary.

Lemma 139. NS is a cof()-complete ideal on  , i.e.

/ NS  P()
a) ; =
/ NS
b)  2
c) X 2 NS ^Y  X  !Y 2 NS
d ) X 2 NS ^Y 2 NS !X \ Y 2 NS
S
e) < cof() ^ fXi ji < g  NS ! i< Xi 2 NS

Proof.
T e) Let < cof() ^ fXi ji < g  NS . Then f n Xi ji < g  C . By Lemma 133,
i< ( n Xi) 2 C . Hence
[ \
Xi =  n ( n Xi) 2 NS :
i< i<


For regular uncountable  these lters and ideals have even better completeness properties.

Denition 140. Let  be a regular uncountable cardinal. For a sequence (Xi)i< of subsets of
 dene
a) the diagonal intersection
i
Xi = f <  j 8i < 2 Xig;
i<
b) the diagonal union
h
Xi = f <  j 9i < 2 Xig:
i<
48 Section 16

Lemma 141. Let  be a regular uncountable cardinal. Then

a) C is closed under diagonal intersections, i.e.,
i
fXi ji < g  C ! Xi 2 C ;
i<

b) NS is closed under diagonal unions, i.e.,

h
fXi ji < g  NS ! Xi 2 NS :
i<

Proof. a) Let fXi ji < g  C . For i <  choose Ci 2 C such that Ci  Xi . Then
i i
Ci  Xi
i< i<
a
and it suces to show that i< Ci is cub in  .
a a
i< Ci is closed in  : Let  <  be a limit ordinal and a limit point of i< Ci . Consider j <
 . By the denition of the diagonal intersection
!
i
Ci n (j + 1)  Cj :
i<

Hence
a  is a limit point of Cj and  2 Cj by the closure of Cj . Thus 8j <   2 Cj and thus  2
C .
a i< i
i< Ci is unbounded in  : Let < . Dene a sequence ( n jn < !) by recursion: set 0 =
and !
\
n+1 = the least element of Ci n ( n + 1) :
i< n

S a
Let = n<! n . is a limit ordinal > . <  since cof() > !1 . We show that 2 i< Ci .
Consider j < . Take n < ! such that j < n . Then
f k j n < k < !g  Cj
and is a limit point of Cj . 2 Cj by the closure of Cj . Hence 8j < 2 Cj . 

Sets in an ideal behave similar to sets of (Lebesgue-)measure 0. Then sets not in the ideal have
positive measure. So stationary sets are positive with respect to the non-stationary ideal.
Closure under diagonal intersections corresponds to a surprising canonization property of certain
functions.

Denition 142. A function f : Z ! Ord where Z  Ord is regressive if

2 Z n f0g ! f ( ) < :

Exercise 30. If > ! then there is no regressive injective function f : ! .

Theorem 143. (Fodor's Lemma) Let  be a regular uncountable cardinal and let f: S !  be
regressive, where S is stationary in  . Then there is a stationary T  S such that f  T is con-
stant.

Proof. Assume that for every i <  f ¡1[fig] is not stationary. So for every i <  choose a Ci
cub such that 8j 2 T \ Ci f (j) =
/ i . The set
i
C= Ci
i<

is cub in , and so there is 2 C \ T , > 0. But then for all i < 2 T \ Ci and f( ) =
/ i. But
then f ( ) > , contradicting the regressivity of f . 
Closed unbounded and stationary sets 49

We now give examples of closed unbounded and stationary sets.

Lemma 144. Let  be an uncountable regular cardinal and let C be cub in  . The derivation
C 0 of C is dened as
C0 =f 2 C j is a limit point of C g:
Then C is cub in  .
0

On can form iterated derivations C (i) for i <  by

C (0) = C
(i+1)
C = (C (i)) 0
\
C () = C (i) for limit ordinals  < 
i<

Every C (i)
is cub in  .

The lemma implies immediately:

Lemma 145. Let Lim be the class of limit ordinals. Let  be an uncountable regular cardinal.
Then Lim \  is cub in  .

Topologically these derivation correspond to the process of omitting isolated points. Such iter-
ated derivations were rst studied by Cantor.

Example 146. For  an uncountable regular cardinal let ()<! be the set of all nite sequences
from  , i.e., ()<! = fu j 9n < ! u: n ! g. For h: ()<! !  let
Ch = f <  j h[( )<!]  g
be the set of ordinals < which areSclosed under h . Then Ch is cub in  . Given <  , a closed
ordinal > can be found as = n<! n where 0 = and
¡[

n+1 = h[( n)<!] + 1 < :

Conversely, if C is cub in  one can dene g:  !  by

g( ) = the smallest element of C which is > :
If we dene Cg as above then
Cg = f0g [ C 0:

Lemma 147. Let  <  be uncountable regular cardinals. Then

E = f <  j cof( ) = g
is stationary in  .

Proof. Let C be cub in  . Dene a strictly increasing  + 1-sequence ( i)i6  of elements of C

by
i = the smallest element of C such that 8j < i j < :
Then < and cof( ) =  . Hence C / ;.
\ E = 

So E!@2 and E!@12 are disjoint stationary subsets of @2 . Actually one can nd a lot of disjoint sta-
tionary sets, using Fodor's lemma.

Theorem 148. Let  be a successor cardinal and let S   be stationary. Then there is a family
(Si j i < ) of pairwise disjoint stationary subsets of S .

Proof. Let  2 Card such that  = +. For each  <  ,  =

/ 0 choose a surjective function f :
! .
50 Section 17

f

i; i


(1) For every <  there is some i <  such that f 2 S j f (i) > g is stationary in  .
Proof . Assume for a contradiction that there is <  such that for any i <  the set f 2
S j f (i) > g is non-stationary in  . Choose cub sets Ci such that
f 2 S j f (i) > g \ Ci = ;:
T T
The set i< Ci is cub in  . Let  2 S \ i< Ci and  > . Then f (i) < for all i <  , which
contradicts the surjectivity of f :  !  . qed (1)
(2) There is some i <  such that for every <  the set f 2 S j f (i) > g is stationary in  .
Proof . By (1), we can nd for every <  some i <  such that f 2 S j f (i ) > g is sta-
tionary in  . By the pidgeon principle there is an unbounded subset Z   and an i <  such
that 8 2 Z i = i . So for every 2 Z the set f 2 S j f (i) > g is stationary in  , which
proves the claim. qed (2)
For <  set S = f 2 S j f (i) = g.
(3) The set of <  , where S is stationary in  , is unbounded in  .
Proof . Assume not and let <  such that S is stationary implies < . By (2), T = f 2
S j f (i) > g is stationary in  . The function  7! f (i) <  is regressive on T . By Fodor's
Theorem the function is constant on a stationary subset of T . Let , 6 <  be the constant
value. Then S = f 2 S j f (i) = g is stationary in  , contradiction. qed (3)
So there are -many <  such that S is stationary. Note that these S are pairwise disjoint
subsets of S. 

Abstractly this means that every NS-positive set can be split into -many NS-positive sets.
Consider the property: there are -many NS-positive sets (Si j i < ) which are almost disjoint
with respect to NS : i =
/ j !Si \ Sj 2 NS . If this property is false, we say that the ideal NS is
-saturated . The property that NS@1 is @2-saturated is not decided by ZFC. That property has
many consequences and is central in modern set theoretic research.

17 Silver's Theorem
The value of 2 for regular cardinals  is hardly determined by the value of 2 at other car-
dinals. The situation at singular cardinals is dierent, the rst result in this area was proved by
Jack Silver. We shall use the notion of almost disjoint functions.
Silver's Theorem 51

Denition 149. Let  be a limit ordinal. Two functions f ; g:  ! V are almost disjoint if there
is <  such that 8 ( < < ! f ( ) = / g( )). A set F  V of functions is almost disjoint if
f and g are almost disjoint for any f ; g 2 F, f =
/ g.

Lemma 150. a) There is no almost disjoint family F  !2 of size 3.

b) There is an almost disjoint family F  !! of size 2@0.

Proof. a) is obvious. b) Take h: (!)<! $ ! . For a: ! ! 2 dene fa: ! ! ! by

fa(n) = h(a  n):
Consider functions a; b: ! ! 2 , a = / b . We show that fa and fb are almost disjoint. Take n < !
such that a  n =
/ b  n . Then for n 6 m < ! we have
fa(m) = h(a  m) =
/ h(b  m) = fb(m):

Thus ffa j a 2 !2g is an almost disjoint family of size 2@0. 

Theorem 151. (Silver) Let ! <  = cof() <  2 Card. Let 2  = + for all !   2  \ Card.
Then 2 = +.

So let us assume that ! <  = cof() <  2 Card and 2  = + for all !   2  \ Card. Fix a
strictly increasing sequenceS( j < ) which is conal in  and continuous, i.e., for any limit
ordinal  <  we have  = <  .
Q
Lemma 152. Assume that  <  for all  <  . Let F  < A be almost disjoint, where
S0 = f <  j card(A )   g is stationary in  . Then card(F )  .

Proof. Assume w.l.o.g. that A   for 2 S . For f 2 F dene hf : S0 !  by

hf ( ): = the least such that f( ) 2  .
Then h  (S0 \ Lim) is regressive. So, by Fodor's lemma, one can choose a stationary Sf  S0 \
Lim such that h is constant on Sf . Hence f is, on Sf , bounded in . If f  Sf = g  Sg, then f =
g, since F is almost disjoint. So f 7! f  Sf is one-to-one. For a xed T   , the set of functions
on T that are bounded in  has cardinality supfj  < g =  by the cardinality assumption.
Also there are < such T , since card(}()) = 2 < . Hence card(F)  
 =  . 

Lemma
Q 153. Let ! <  = cof() <  2 Card, and assume that  <  for all  <  . Let F 
+
< A be almost disjoint, card(A )   . Then card(F )   .
+

Proof. Assume w.l.o.g. that A  +. Let S   be stationary and f 2 F. Let

Ff ;S = fg 2 Fj (8 2 S)(g( )  f ( ))g:
Q
The map g 7! g  S injects Ff ;S into 2S (f ( ) + 1) where card(f ( ) + 1)   . By the pre-
vious lemma, card(Ff ;S )   .
Dene
[
Ff = fFf ;S j S   is stationaryg:

Since there are < stationary subsets of  ,

(1) card(Ff )  . S
We construct a sequence (fj  < ) of functions in F by induction such that F = fFfj  <  g.
Take an arbitrary f0 2 F . S
If (f j  < ) is already dened, choose f 2 fFf  j v <  g if possible. If there is no such f, set
 =  and stop.
(2)   +.
Proof . Assume that f+ is dened. If  < + then f+ 2 / Ff . So f j f+( )  fv( )g is non-sta-
tionary and f j f ( )  f+( )g 2 C. Thus fv 2 F+ for all v <  , and card(Ff+) > +. This
contradicts (1). qed (2)
52 Section 18

Altogether
[ X X
card(F) = card( fFfj  < g) 6 card(Ff) 6  6 
+ = + :
< <

Q
Proof. (Silver's Theorem) Dene a map from P() into < }( ) by

X 7! fX = (X \  j < ):
If X =
/ Y then fX and FY are almost disjoint. So
Y
F = ffX j X 2 P()g  }( )
<

is an almost disjoint family of functions. The GCH below  implies that card(}( )) = 2 =
+ . Moreover  6 max (; )max(;) = max (; )+ <  for all  <  . By Lemma 153,
card(F) 6 +. Hence
+ 6 2 = card(P()) 6 card(F ) 6 +


Exercise 31. Use the methods of the proof of Silver's Theorem to show
Q ++
a) Let F  < A be almost disjoint, card(A )   . Then card(F)  ++.

b) Let ! <  = cof() <  2 Card. Let 2 = ++ for all !   2  \ Card. Then 2 6 ++.

18 Ranks of functions
The previous exercise indicates the possibility that one may generalize Silver's theorem by a
kind of induction on the height of the continuum function below  . This idea will lead to the
Galvin-Hajnal theorem. Let  = @ be a singular strong limit cardinal (i.e.,  < @ ! 2 < @ )
with ! <  = cof(@ ) < @ . Let ( j  < ) be a strictly increasing continuous sequence conal in
@ . The continuum function below @ determines a function '0:  ! by
+'0()
2   =  ;
+' ()
where  0 = @+ '0()if  = @ .
Let us now study functions ':  ! along appropriate wellfounded relations. Fix a regular
uncountable cardinal  and some limit ordinal .

Denition 154. For a stationary set S   dene a relation <S on functions '; :  ! by
' <S i there is a cub C   such that 8 2 S \ C '() < ():

Equivalently one can say that the set of  where ' and behaves dierently is very small:
' <S i f 2 S j '() > ()g 2 NS :

Lemma 155. <S is a strongly wellfounded relation on 

.

Proof. Assume not. Then, using AC, there is a strictly descending !-sequence

0 >S 1 >S 2 >S ::::

T
Choose cub sets C0; C1T
; :::   such that 8 2 S \ Cn n() > n+1() . Since n<! Cn is cub in
 one can take  2 S \ n<! Cn . Then
0() > 1() > 2() > ::::

is a descending !-sequence of ordinals. Contradiction. 

Ranks of functions 53

Denition 156. Dene the <S-rank k kS 2 Ord of 2  by recursion on <S :

[
k kS = fk'kS + 1 j ' <S g:

We also write k k instead of k k .

We prove some properties of this rank.

Lemma 157.
a) If S  T are stationary in  then ' <T implies ' <S .
b) If S  T are stationary in  then k kT 6 k kS .
c) If S ; T are stationary in  then
k kS [T = min (k kS ; k kT ):

d ) If S is stationary and N is nonstationary then ' <S [N i ' <S .

e) If S is stationary and N is nonstationary then
k kS [N = k kS :

Proof. a) Let ' <T . Take C   cub such that 8 2 T \ C '() < (). Then 8 2 S \ C
'() < () and so ' <S .
b) By induction on <T .
[
k kT = fk'kT + 1 j ' <T g
[
6 fk'kS + 1 j ' <T g by the inductive assumption
[
6 fk'kS + 1 j ' <S g by a)
= k kS :

c) By b) k kS [T 6 k kS ; k kT and so
k kS [T 6 min (k kS ; k kT ):
Assume that the equality is false and consider <S [T -minimal such that
k kS [T < min (k kS ; k kT ):
S
Since k kS [T 2 k kS = fk'kS + 1 j ' <S g take S <S such that k kS [T < k S kS + 1 , i.e.,
k kS [T 6 k S kS ; take CS   cub such that 8 2 S [ CS S () < (). Similarly take T <T
such that k kS [T 6 k T kT and some CT   cub such that 8 2 T [ CT T () < (). Dene ':
! ,
8
> S () if  2 S n T
>
>
<
T () if  2 T n S
'() =
>
> max ( S (); T ()) if  2 S \ T
>
: 0 else

For  2 (S [ T ) \ (CS \ CT ) holds '() < (), thus ' <S[T . Since 8 2 S S () 6 '() we have
k S kS 6 k'kS . Similarly k T kT 6 k'kT . By the <S [T -minimality of we have

k'kS [T = min (k'kS ; k'kT ) > min (k S kS ; k T kT ) > k kS [T

contradicting ' <S [T .
d) ' <S [N i f 2 S [ N j '() > ()g 2 NS i f 2 S j '() > ()g 2 NS i ' <S .
e) follows directly from d). 

Note that k k = k k 6 k kS . This motivates to exclude stationary sets S which do not com-
pute the correct rank of .
54 Section 18

Denition 158. Let

I = NS [ fS j S is stationary and k k < k kS g:

Lemma 159. I is an ideal on  .

Proof. I is a non-empty family of subsets of  and  2 /I .

I is closed under subsets: let A 2 I and B  A . If B is nonstationary then B 2 I . If B is sta-
tionary then k kB > k kA > k k and B 2 I .
I is closed under unions: let A 2 I and B 2 I . If A and B are nonstationary then A [ B 2
NS  I . If A is stationary and B is nonstationary then by e) of Lemma 160 k kA[B = k kA >
k k and A [ B 2 I . If A is stationary and B is stationary then by c) of Lemma 160
k kA[B = min (k kA; k kB ) > k k
and A [ B 2 I . 

Lemma 160.
a) If k k = 0 then f <  j () = 0g is stationary in  .
b) If k k is a successor ordinal then
f <  j () is a successor ordinal g 2
/I :

c) If k k is a limit ordinal then

f <  j () is a limit ordinal g 2
/I :

Proof. a) Let k k = 0. If f <  j () = 0g is nonstationary there is a cub C   such that 8 2

C () > 0 . But then > const0 and k k > 1 . Contradiction.
b) Let k k be a successor ordinal but assume that
f <  j () is a successor ordinalg 2 I :
Then
S = f <  j () is a limit ordinalg 2
/I :
By the denition of I we get that k kS = k k is also a successor ordinal. By the denition of
k kS take ' <S such that k kS = k'kS + 1: Take a cub set C   such that 8 2 S \ C '() <
(). Dene '+:  ! by '+() = '() + 1 . Since () is a limit ordinal for  2 S :
8 2 S \ C '() < '+() < ():
Then ' <S '+ <S and k'kS < k'+kS < k kS , contradicting k kS = k'kS + 1 .
c) Let k k be a limit ordinal but assume that
f <  j () is a limit ordinalg 2 I :
Then
S = f <  j () is a successor ordinalg 2
/I :
By the denition of I we get that k kS = k k is also a limit ordinal. Dene ¡
:! by

¡ () ¡ 1 , if  2 S
() =
0 , else
Consider a function ' <S . Take a cub set C   such that 8 2 S \ C '() < () and thus
8 2 S \ C '() 6 ¡(). Then
k'kS = k'kS\C 6 k ¡
kS \C = k ¡
kS < k kS
This means that
[
k kS = fk'kS + 1 j ' <S g
6 k ¡
kS + 1
The Galvin Hajnal Theorem 55

Since k ¡
kS <k kS this implies
¡
k k = k kS = k kS + 1
is a successor ordinal, contradiction. 

19 The Galvin Hajnal Theorem

Theorem 161. Let  = @ be a singular strong limit cardinal (i.e.,  < @ !2  < @ ) with ! <
 = cof(@ ) < @ . Then
2@ < @
where = (2card( ))+.

Note that if = @ the theorem claims that

2 < @(2 )+
which is obviously true.
Q
Lemma 162. Let :! and let F  < A be an almost disjoint family of functions such
that
+ ()
card(A) 6 
for  <  . Then card(F) 6 @ +k k .

Proof. By induction on k k 2 Ord:

k k = 0 : Then by Lemma 160(a) vanishes on a stationary set S   and Lemma 152 proves
the case.
k k is the successor ordinal + 1: by Lemma 160(b)
S0 = f <  j () is a successor ordinalg 2
/I :
+ ()
We may assume that A   for  <  .
(1) Let f 2 F and S  S0 , S 2
/ I . Then the set
Ff ;S = fg 2 F j 8 2 S g() 6 f()g
has cardinality 6@ + .
Proof. Dene ':  ! by 
() ¡ 1 , if  2 S
'() =
() , else
Since S 2
/I ,
k'k 6 k'kS < k kS = k k = + 1
and k'k 6 . Now
Y
Ff ;S  f ();
<
+ ()
and since f () <  we have
+'()
card(f () + 1) 6  :
By the induction hypothesis, card(Ff ;S ) 6 @ +k'k 6 @ + . qed (1)
(2) Let f 2 F. Then the set
/ I ^8 2 S g() 6 f ())g
Ff = fg 2 F j 9S  S0 (S 2
has cardinality 6@ + .
Proof. Since @ is a strong limit cardinal, there are at most 2 < @ many S  S0 . Hence
[
Ff = Ff ;S
S S0;S 2
/I
56 Section 19

is a union of less than @ many sets of size 6@ + . qed (2)

Like in the proof ofSLemma 153 we construct a sequence (f j  < ) of functions in F by induc-
tion such that F = fFfj  <  g.
Take an arbitrary f0 2 F .
S
If (f j  < ) is already dened, choose f 2 fFf j  <  g if possible. If there is no such f, set
 =  and stop.
(3)  6 @ + +1.
Proof . Assume that f@ + +1 is dened. Set  = @ + +1 . Consider  <  . f 2 / Ff  and so there
is no S  S0 , S 2 / I such that 8 2 S f() 6 f (). This means that

f 2 S j f() 6 f ()g 2 I
and
f 2 S j f () < f()g 2
/I :

This implies that f 2 Ff and thus ff j  < g  Ff . Hence card(Ff) >  = @ + +1 , which
contradicts (2). qed (3)
Now
¡[
X X X
card(F) = card fFfj  <  g 6 card(Ff) 6 @ + 6 @ + =@ + +1 :
<  < <@ + +1

Finally consider the case that k k is a limit cardinal. By Lemma 160(c),

S = f <  j () is a limit ordinalg 2

/I :
+ ()
Again we may assume that A   for  <  .
For functions ':  ! dene

F' = f 2 F j 8 <  f () 2 +'()
 :

Consider f 2 F. Dene ':  ! by taking '() minimal such that

+'()
f () 2  :

Obviously f 2 F' . Moreover ' <S . Since S 2

/ I we have

k'k 6 k'kS < k kS = k k:

By the induction hypothesis
card(F') 6 @ +k'k < @ +k k :

Thus
[
F fF' j 9' (':  ! ^ card(F') < @ +k k)g

and
X
card(F) 6 @ +k k 6 card(

)
@ +k k 6 @
@ +k k = @ +k k :
':!


We are now able to prove

Theorem. Let  = @ be a singular strong limit cardinal (i.e.,  < @ !2  < @ ) with ! <  =
cof(@ ) < @ . Then
2@ < @
where = (2card( ))+.
Q
Proof. Dene an injective map from P() into < }() by

X 7! fX = (X \  j  < ):
Measurable cardinals 57

If X =
/ Y then fX and FY are almost disjoint. So
Y
F = ffX j X 2 P()g  }()
<

is an almost disjoint family of functions. Since  is a strong limit cardinal, there is a function :
 ! such that
+ ()
card(}( )) 6 
for  <  . By the previous lemma
card(P()) 6 card(F) 6 @ +k k :

Since card( ) 6 card( ) = 2card( ), the rank function k:k on 

is bounded by = (2card( ))+.
Hence k k < and
2@ = card(P()) 6 @ +k k < @ + =@ :


If, e.g., @!1 is a strong limit cardinal then by this theorem

2@!1 < @(2@1)+ < @@!1 :

So the continuum function at singular cardinals can be inuenced by the behaviour below that
cardinal. In particular instances the bounds for the continuum function can be improved. With
considerably more eort one can also deal with singular cardinals of countable conality and
prove, e.g.: if @! is a strong limit cardinal then (Shelah)

2@! < @@4 :

20 Measurable cardinals
The results of the previous section used lters and ideals to express that certain sets are large or
small respectively. There are also intermediate notions of size: a set X is of positive measure if
it is not in the ideal under consideration. One may imagine that the measure of X is some pos-
itive real number. This poses the question, which kinds of measures do or can exist. Ideally
every set should be given some non-negative number as a measure.
This approach is also motivated by the classical theory of Lebesgue measure on the real line and
related spaces. Recall that the 1-dimensional Lebesgue measure on R is a function l: ! R [
f1g taking values in the extended real line with the properties:
a)  P(R) contains all intervals and is closed under complements and countable unions;
b) l([0; 1]) = 1;
c) l is countably additive (-additive): if fXi j i < !g  is a pairwise disjoint family then
!
[ X
l Xi = l(Xi);
i<! i<!

d) l is translation invariant: if X 2 and d 2 R then X + d = fx + d j x 2 X g 2 and

l(X + d) = l(X):

Theorem 163. There is a set Z  [0; 1] which is not Lebesgue-measurable, i.e., Z 2

/ .

Proof. Let
A = fQ + d j d 2 Rg:
58 Section 20

(1) A consists of pairwise disjoint nonempty sets which intersect the interval [0; 1).
Proof . Assume that x 2 (Q + d) \ (Q + e). Take rational numbers r; s 2 Q such that
x = r + d = s + e:
Then d = (s ¡ r) + e 2 Q + e and
Q + d = ft + d j t 2 Qg = ft + (s ¡ r) + e j t 2 Qg  Q + e:
Similarly Q + e  Q + d and so Q + e = Q + d .
Consider d 2 R . Take an integer z 2 Z such that z 6 d < z + 1 . Then
¡z + d 2 (Q + d) \ [0; 1)
qed (1)
By the axiom of choice let Z be a choice set for the set
f(Q + d) \ [0; 1) j d 2 Rg:
(2) If q; r 2 Q and q =/ r then (Z + q) \ (Z + r) = ; .
Proof . Assume not, and take z0; z1 2 Z such that z0 + q = z1 + r . Then z0 2 Q + z0 and z1 2 Q +
z0 . Since ZSis a choice set, z0 = z1 . But then q = r . Contradiction. qed (2)
(3) [0; 1]  q 2[¡1;1]\Q Z + q .
Proof . Let d 2 [0; 1]. Let z 2 Z \ (Q + d) \ [0; 1). Take q 2 Q such that z = q + d . Then d = z +
(¡q) where jqj 6 1 . qed (3)
Assume now that Z 2 . Since Z  [0; 1] we have l(Z) 6 1 .
Case 1 : l(Z) = 0. Then
!
[ X X X
1 = l([0; 1]) 6 l Z+q = l(Z + q) = l(Z) = 0 = 0;
q 2[¡1;1]\Q q2[¡1;1]\Q q 2[¡1;1]\Q q2[¡1;1]\Q

contradiction.
Case 2 : l(Z) = " > 0. Then !
[
l Z+q 6 l([0; 2]) = 2
q 2[¡1;1]\Q
but on the other hand
!
[ X X X
l Z+q = l(Z + q) = l(Z) = " = 1:
q2[¡1;1]\Q q 2[¡1;1]\Q q2[¡1;1]\Q q 2[¡1;1]\Q


We shall now consider measures which are dened on all subsets of a given set, but we do not
require a geometric structure on the set and in particular no translation invariance. We also
restrict our consideration to nite measures.

Denition 164. A measure on a set X is a function : P(X) ! [0; 1] such that

a) (;) = 0 and (X) = 1 ;
b) l is countably additive (-additive): if fXi j i < !g  P(X) is a pairwise disjoint family
then !
[ X
 Xi = (Xi):
i<! i<!

 is called non-trivial if (fxg) = 0 for every x 2 X .  is 2-valued if ran() = f0; 1g, otherwise
 is real-valued.

Note that if f :  $ X is a bijection then a measure  on X immediately induces a measure  0

on  by
 0(A) = (f [A]):
So we can focus our attention on measures on cardinals.
Measurable cardinals 59

Lemma 165. Every 2-valued measure  on R is trivial, i.e., there is some x 2 R such that
(A) = 1 i x0 2 A:

Proof. Identify R with !2 . Dene x0: ! ! 2 by

x0(n) = 1 i (fx 2 !2 j x(n) = 1g) = 1:
By the -additivity of  ,
!
[ X X
!
( 2 n fx0g) =  !
/ x0(n)g 6
fx 2 2 j x(n) = (fx 2 !2 j x(n) =
/ x0(n)g) = 0=0:
n<! n<! n<!

So (fx0g) = 1 . 

Assume that  is the smallest cardinal which has a non-trivial measure  . A set A   with
(A) > 0 splits if there is a partition A1; A2  A such that A1 [ A2 = A , A1 \ A2 = ; , 0 < (A1) <
(A) and 0 < (A2) < (A).
Case1 . There is a set A0   with (A0) > 0 which does not split.
Then dene : P(A0) ! 2 by
(A) = 1 i (A) = (A0):
(1)  is a 2-valued non-trivial measure on A0 .
Proof . We have to check -additivity. Let fXi j i < !g  P(A0) be a pairwise disjoint family. By
the -additivity of  !
[ X
 Xi = (Xi):
i<! i<!
Then ! !
[ [
 Xi = 1 i  Xi = (A0) i 9i < ! (Xi) = (A0) i 9i < ! (Xi) = 1:
i<! i<!
Thus !
[ X
 Xi = (Xi):
i<! i<!
qed (1)
By the minimality of  we have card(A0) =  .

Case 2 . Every set A   with (A) > 0 splits. In this case we call the measure  atomless.
We rst show that indeed A splits into relatively large subsets:
1 2
(2) Every set A   with (A) > 0 possesses a subset B  A such that 3 (A) 6 (B) 6 3 (A).
Proof . Assume not. Then
 
1 1
 = sup (B) j B  A^ (B) 6 (A) 6 (A) :
2 3
1
For n 2 ! n f0g choose Bn  A such that  ¡ n < (Bn) 6 .
We show by induction on n that
(B1 [ B2 [ ::: [ Bn) 6  :
Assume that (B1 [ B2 [ ::: [ Bn) 6  .
Assume for a contradiction that (B1 [ B2 [ ::: [ Bn [ Bn+1) >  . Then
2
(B1 [ B2 [ ::: [ Bn [ Bn+1) 6 (B1 [ B2 [ ::: [ Bn) + (Bn+1) 6  +  6 (A):
3
2
By the initial assumption we cannot have (B1 [ B2 [ ::: [ Bn [ Bn+1) = 3 (A). Hence
2
 < (B1 [ B2 [ ::: [ Bn [ Bn+1) < (A)
3
and
1
(A n (B1 [ B2 [ ::: [ Bn [ Bn+1)) > (A) >  :
3
60 Section 20

But then B1 [ B2 [ ::: [ Bn [ Bn+1 or its relative complement A n (B1 [ B2 [ ::: [ Bn [ Bn+1)
would be a counterexample to the denition of  . Thus (B1 [ B2 [ ::: [ Bn [ Bn+1) 6  . The -
additivity of  implies
! !
[ [
 Bn =  (Bn n (B1 [ ::: [ Bn¡1))
16n<! 16n<!
X
= (Bn n (B1 [ ::: [ Bn¡1))
16n<!
m
X
= lim (Bn n (B1 [ ::: [ Bn¡1))
m!1
n=1
m
!
[
= lim  (Bn n (B1 [ ::: [ Bn¡1))
m!1
n=1
= lim (B1 [ ::: [ Bm)
m!1
= :
S
Set B = 16n<! Bn . Then (B) =  . A n B splits, so take a partition A n B = C [_ D such
1
that 0 < (C) 6 (D) < (A n B) = (A) ¡  . By the initial assumption we have (C) < 3 (A)
2 1 2
or (C) > 3 (A), and (D) < 3 (A) or (D) > 3 (A).
1
If (D) < 3 (A) then
1 1 1
(A) = (B [ C [ D) = (B) + (C) + (D) < (A) + (A) + (A) = (A);
3 3 3
1 2
contradiction. Hence (C) < 3 (A) and (D) > 3 (A) . But then
2 1
 < (B [ C) = (A n D) = (A) ¡ (D) < (A) ¡ (A) < (A);
3 2
contradicting the denition of  . qed (2)
Recall the binary tree
<!
2 = fs j 9n < ! s: n ! 2g:
We construct a binary splitting A: <!2 ! P() of the underlying set  by recursion on the length
of the binary sequences. Put A(;) =A0 =  . If A(s) = As   is constructed, use (2) to choose a
1 2
splitting As = As0 [_ As1 of As such that 3 (As) 6 (As0) 6 (As1) 6 3 (As).
We shall pull the measure  back to a measure  on the reals. For X  R dene
[ \
X0 = Axn :
x2X n<!
Dene : P( !2) ! [0; 1] by
(X) = (X 0):
First we show that the assignment X 7! X 0 preserves some set theoretic properties.
(3) ; 0 = ; .
(4) ( !2) 0 =  .
Proof . Let 2  . Dene x: ! ! 2 recursively by
x(n) = 1 i 2 A(xn)1 :
T
Then 2 n<! Axn and
[ \
= Axn :
x2 ! 2 n<!
qed (4)
(5) (X \ Y ) 0 = X 0 \ Y 0. T
Proof . Let 2 (X \ Y ) 0. Take x 2 X \ Y such that 2 n<! Axn . Then
[ \
2 Axn = X 0
x2X n<!
and also 2 Y 0.
Measurable cardinals 61

T
Conversely consider 2 X 0 \ Y 0. Take x 2 X such that 2 n<! Axn and take y 2 Y such that
T
2 n<! Ayn . Assume for a contradiction that x = / y . Take n 2 ! such that x  n = y  n and
/ y(n). Then 2 Ax(n+1) \ Ay(n+1) although Ax(n+1) \ Ay(n+1) = ; by construction.
x(n) =
Thus x = y 2 X \ Y and
[ \
2 Axn = (X \ Y ) 0:
x2X \Y n<!
qed (5)
S S
(6) ( i2I Xi) 0 = i2I Xi0 .
Proof .
!0
[ [ \
Xi = Axn
S
i2I x2 X n<!
i2I i
[ [ \
= Axn
i2I x2Xi n<!
[
= Xi0 :
i2I

qed (6)

(7)  is a non-trivial measure on !2 .

Proof . (;) = (; 0) = (;) = 0 and (!2) = ((!2) 0) = () = 1 .
To check -additivity consider a pairwise disjoint family fXi j i < !g  P(!2). Then fXi0 j i <
!g  P() is pairwise disjoint by (5) and (3). By the -additivity of  and by (6),
! !
[ [ X X
0
 Xi =  Xi = (Xi0) = (Xi):
i<! i<! i<! i<!

To check non-triviality consider x 2 ! 2 . Then

\
fxg 0 = Axn :
n<!
One can show inductively that  n
2
(Axn) 6
3
for all n < ! . Thus  n
2
(fxg 0) 6 (Axn) 6
3
for all n and so (fxg 0) = 0: This implies
(fxg) = (fxg 0) = 0:
qed (7)
Since  was assumed to be minimal carrying a non-trivial measure, we have  6 2@0 in Case 2 .
In both cases we can show a strong additivity property:
(8) The measure  on  is -additive, i.e., for every pairwise disjoint family fXi j i < g  P()
with <  we have !
[ X
 Xi = (Xi) ;
i< i<

where the right hand side is dened as

( )
X X
(Xi) = sup (Xi) j I0 is a nite subset of :
i< i2I0

Proof . Assume that  is not -additive and let <  be least such that there is a family
fXi j i < g  P() with !
[ X
 Xi = / (Xi) :
i< i<
62 Section 20

Then is an uncountable cardinal and

!
[ X
 Xi > (Xi) :
i< i<
Let
J = fi < j (Xi) > 0g  :
We claim that J is at most countable. If J were uncountable, there must be some rational
1 1
number n such that (Xi) > n for uncountably many i 2 J . But then
!
[
 Xi = 1;
i<
contradiction.
The -additivity of  entails
! ! !
[ [ [
 Xi =  Xi ¡  Xi
i2 nJ i< i2J
X X
> (Xi) ¡ (Xi)
i< i2J
X X
= (Xi) ¡ (Xi)
i< i<
= 0:
So we may assume that all elements of the disjoint family fXi j i < gS P() have -measure 0 .
We shall pull the measure  back to a measure  on . Let 0 = ( i2 Xi). Dene : P( ) !
[0; 1] by !
1 [
(Y ) =  Xi
0
i2Y

We show that  is a non-trivial measure

S on .
1 1
(;) =  (;) = 0 and ( ) =  ( i2 Xi) = 1 .
0 0
To check -additivity consider a pairwise disjoint family fYj j j < !g  P( ). Then
( )
[
Xi j j < !  P()
i2Yj

is pairwise disjoint. By the -additivity of 

! !
[ 1 [
 Yj =  Xi
0 S
j <! i2 Y
j <! j
!
1 [ [
=  Xi
0
j <! i2Yj
!
1 X [
=  Xi
0
j <! i2Yj
!
X 1 [
=  Xi
0
j <! i2Yj
X
= (Yj ) :
j <!

Finally,  is non-trivial since for every i <

!
1 [ 1
(fig) =  Xj = (Xi) = 0:
0 0
j 2fig

But the existence of  contradicts the minimality of  . qed (8)

Measurable cardinals 63

We can now draw conclusions from the previous arguments.

Denition 166. A cardinal  is measurable if  is uncountable and possesses a 2-valued -

additive non-trivial measure. A cardinal  is real-valued measurable is  is uncountable and
possesses a non-atomic -additive non-trivial measure.

Recall that  is non-atomic, if every sets A   with (A) > 0 splits, i.e., there is a partition A1;
A2  A such that A1 [ A2 = A , A1 \ A2 = ; , 0 < (A1) < (A) and 0 < (A2) < (A).

Theorem 167. Let  be minimal such that  carries a non-trivial measure. Then either  is a
measurable cardinal, or  6 2@0 and  is a real-valued measurable cardinal.

Proof. If we are in Case 1 above, then  is measurable. In Case 2 ,  6 2@0 . By Lemma 165
there is no 2-valued non-trivial measure on  . Hence  is real-valued measurable. 

Lemma 168. Let  be measurable or real-valued measurable. Then  is regular.

Proof. Let  be a non-trivial -additive measure on  . Assume for a contradiction that

cof() = <  . Let (i j i < )   be conal in  . For i < be have
!
[ X X
(i) =  f g = (f g) = 0=0;
<i <i <i

using non-triviality and -additivity. Similarly

!
[ X X
() =  i 6 (i) = 0=0;
i< i< i<

contradiction. 

Lemma 169. Let  be a measurable cardinal. Then  is strongly inaccessible.

Proof. Let  be a non-trivial -additive 2-valued measure on  . Assume for a contradiction

that  <  but 2 >  . We may assume that  is a measure on 2 . Dene x0:  ! 2 by
x0(i) = 1 i (fy 2 2 j y(i) = 1g) = 1:
The -additivity of  implies
!
[
 
( 2 n fx0g) =  fy 2 2 j y(i) = 1 ¡ x0(i)g
i<
X
6 (fy 2 2 j y(i) = 1 ¡ x0(i)g)
i<
X
= 0
i<
= 0:
But then (fx0g) = 1 which contradicts the non-triviality of  . 

Thus measurable cardinals are large cardinals. Large cardinals are central notions in set theory.
They can be viewed as ideal points in the cardinal hierarchy with respect to certain properties.
A strongly inaccessible cardinal  is an ideal point of cardinal arithmetic.  cannot be reached
by the formation of cardinal powers or even innitary sums and products from smaller para-
meters.
One could cut o the universe of sets at  and restrict consideration to V as a subuniverse.
We shall see in later courses that V is a model of the ZFC-axioms and one could restrict math-
ematics to working inside V . On the other hand the assumption of inaccessible and stronger
large cardinals like measurable cardinals greatly enriches set theoretic combinatorics. There are
also isolated instances, when the assumption of large cardinals influences the behaviour of
smaller sets like the set of real numbers.
64 Section 21

21 Normal measures and ultralters

We shall now combine techniques from lters and ideals with measures on measurable cardinals.

Lemma 170. Let  be an uncountable cardinal. Then  is a measurable cardinal i there is

non-principal, -complete ultralter U on  , i.e., 8i <  fig 2
/ U (non-principality) and for every
family fXi j i < g  U with <  we have
\
Xi 2 U :
i<

Proof. If  is a 2-valued -additive non-trivial measure  on  then

U = fX   j (X) = 1g
is an ultrafilter with the desired properties. Conversely, if U~ is a non-principal, -complete
ultralter on  then ~: P() ! 2 dened by
~(X) = 1 i X 2 U~
is a 2-valued -additive non-trivial measure. 

Let us x a measurable cardinal  and a non-principal, -complete ultralter U on  .

Denition 171. Dene a relation <U on functions f ; g:  !  by

f <U g i fi <  j f (i) < g(i)g 2 U:

Recall that we dened in some previous arguments

' <S i f 2 S j '() > ()g 2 NS :

Lemma 172. <U is a strongly wellfounded on  .

Proof. Assume not and assume that A   , A = / ; does not have a <U -minimal element. Then
dene recursively a sequence fn for n < ! : choose f0 2 A arbitrary; if fn 2 A is dened, it is not
<U -minimal in A, and so we can choose (AC) fn+1 2 A such that fn+1 <U fn .
For n < ! set
Xn = fi <  j fn+1(i) < fn(i)g 2 U :
Since U is -complete,
\
Xn 2 U :
n<!
T
So one can take i0 2 n<! Xn . So for each n < !
fn+1(i0) < fn(i0);
and (fn(i0))n<! is a strictly decreasing !-chain in the ordinals. Contradiction. 

Denition 173. Dene the <U-rank kf kU 2 Ord of f 2  by recursion on <U :

[
kf kU = fkg kU + 1 j g <U f g:

Lemma 174.
a) For <  and for every f 2 
kf kU = i fi <  j f (i) = g 2 U :
Hence kc kU = where c :  !  is the constant function c (i) = .
b) There exists f 2  such that kf kU > 

Normal measures and ultrafilters 65

Proof. a) By induction on <  . Assume a) holds for < . Let f 2  .

Assume that kf kU = but X = fi <  j f(i) = g 2 / U . By inductive hypothesis, also X = fi <
/ U for all < . Since U is -complete, any union of less than  many sets which
 j f (i) = g 2
are not in the ultralter is not in the ultralter. Thus
[
fi <  j f (i) 6 g = X 2/U
6
and
fi <  j f (i) > g 2 U :
This implies that
c <U f :
By inductive hypothesis, kc kU =
/ for all < . Hence kc kU > . But then
kf kU > kc kU > ;
contradiction.
Conversely assume that A = fi <  j f (i) = g 2 U . Then fi <  j f (i) = g 2
/ U for all < and
/ for every < . Hence kf kU > . Assume for a contra-
by the inductive hypothesis kf kU =
diction that kf kU > . Then there exists g 2  such that g <U f and kg kU > . By the
inductive assumption, the set
X = fi <  j g(i) = g 2
/U
for every < . By the -completeness of U
[
fi <  j g(i) < g = X 2
/U
<
and
B = fi <  j g(i) > g 2 U:

Since g <U f , the set C = fi <  j g(i) < f (i)g 2 U . Now take i 2 A \ B \ C . Then

6 g(i) < f(i) = ;

contradiction.
b) Let d:  !  be the diagonal function d(i) = i . For <
\
fi <  j c (i) < d(i)g = fi <  j < ig = ( n f g) 2 U
6

by the non-principality and -completeness of U . Hence c <U d and kdkU > kc kU = . Thus
kdkU >  . 

Consider a function f :  !  with kf kU =  . Then a function g:  !  with g <U f has rank

kg kU = <  , i.e.,
fi <  j g(i) = g 2 U :
This resembles Fodor's theorem by which regressive functions are constant on stationary sets.
Indeed one can modify the lter U to come even closer to Fodor's theorem.
Dene U~  P() by
X 2 U~ i f ¡1(X) = fi <  j f(i) 2 X g 2 U :
(1) U~ is an ultralter on  .
Proof . ; 2/ U~ since f ¡1(;) = ; 2
/ U.
If X 2 U~ and X  Y   , then f ¡1(X) 2 U and f ¡1(X)  f ¡1(Y ), and so f ¡1(Y ) 2 U and Y 2
U~ .
If X ; Y 2 U~ , then f ¡1(X); f ¡1(Y ) 2 U and f ¡1(X \ Y ) = f ¡1(X) \ f ¡1(Y ) 2 U , thus X \ Y 2 U~ .
If X   and X 2 / U~ , then f ¡1(X) 2
/ U and  n f ¡1(X) 2 U . Hence f ¡1( n X) =  n f ¡1(X) 2 U
~
and  n X 2 U . qed (1)
66 Section 21

Note that the argument is based on the preservation of the set theoretic notions ; ,  , \ , n by
the f ¡1(:)-operation.

(2) U~ is -complete. T
Proof . Let fXi j i < g  U~ where  <  . Then ff ¡1(Xi) j i < g  U and i< f ¡1(Xi) 2 U by
the -completeness of U . Since !
\ \
f ¡1 Xi = f ¡1(Xi)
i< i<
T ~
we get i< Xi 2 U . qed (2)

(3) U~ is non-principal.
Proof . Let <  . By Lemma 174(a) fi <  j f (i) = g 2
/ U , so

f ¡1(f g) = fi <  j f(i) = g 2

/U
/ U~ . qed (3)
and f g 2

Denition 175. An ultralter U on  is normal if every function h:  !  which is regressive

on a set in U, i.e., fi <  j h(i) < ig 2 U, is constant on a set in U, i.e., there is a  <  such that
fi <  j h(i) =  g 2 U.

(4) U~ is normal.
Proof . Let h:  !  and fi <  j h(i) < ig 2 U~ . Then

f ¡1(fi <  j h(i) < ig) = fj <  j h(f (j)) < f(j)g 2 U
and h  f <U f . Since kf kU =  , kh  f kU =  for some  <  . By Lemma 174(a) this is equi-
valent to
fj <  j h(f(j)) =  g 2 U :
So
f ¡1(fi <  j h(i) = g) = fj <  j h(f (j)) = g 2 U
and
fi <  j h(i) = g 2 U~ :
qed (4)
Hence we have shown

Theorem 176.  is a measurable cardinal i there is normal non-principal, -complete ultra-

lter of  .

Normal ultralter have better combinatorial properties like

Lemma 177. Let  be measurable carrying a normal non-principal, -complete ultralter U .

Then
a) C  U where C is the closed unbounded lter on  .
b) U is closed unter diagonal intersections, i.e., if fXi j i < g  U then
i
Xi 2 U :
i<

Proof. a) Let C   be closed unbounded in  but assume that C 2

/ U . Dene h:  !  by
h(i) = max (C \ i):
Then h is regressive on  n C 2 U: Since U is normal, take  <  such that
Y = fi <  j h(i) = g 2 U :
Measurable cardinals and the GCH 67

Since Y is unbounded in  , max (C \ ) must be equal to  . But this contradicts the unboun-
dedness of C in  . a
b) Let fXi j i < g  U but assume that i< Xi 2
/ U . Dene h:  !  by

h(j) = min fi < j j j 2

/ Xig if this exists and h(j) = 0 else.
a
Then h is regressive on  n i< Xi 2 U : Since U is normal, take  <  such that
Y = fj <  j h(j) =  g 2 U :
Then !
i
X \ Y \  n Xi  X \ fj <  j j 2
/ X g = ;:
i<

This contradicts the fact that U is an ultralter for which the intersection of three elements has
to also lie in the ultralter. 

22 Measurable cardinals and the GCH

We use the methods of Silver's theorem in the context of measurable cardinals. Let  be a meas-
urable cardinal and x a normal non-principal -complete ultralter U on  .

Lemma 178. kdkU =  where d:  !  is the diagonal function d(i) = i .

Proof. kdkU >  was shown in the proof of 174(b).

For the converse consider f <U d . Then
fi <  j f (i) < ig 2 U
means that f is regressive on a set in U . By the normality of U there is a constant  <  such
that
fi <  j f (i) = g 2 U :
By 174(a), kf kU =  . Thus
[ [
kdkU = fkf kU + 1 j f <U dg 6  = :


Denition 179. Two functions f ; g:  ! V are U-almost disjoint if

fi <  j f(i) =
/ g(i)g 2 U :
A family F  V of functions is U-almost disjoint if f and g are U-almost disjoint for any f ; g 2
/ g.
F, f =

Lemma 180. Let F be a U-almost disjoint family where f <U d for every f 2 F. Then
card(F)  .

Proof. By the previous Lemma, f 7! kf kU maps F into  . Moreover, this assignment is

injective: if kf kU = kg kU then
fi <  j f (i) = kf kU g \ fi <  j g(i) = kg kU g 2 U
and since F is a U -almost disjoint family, f = g . Thus card(F)  . 

Lemma 181. Let d +:  !  be the cardinal successor function d +(i) = i+. Let F be a U-almost
disjoint family where f <U d + for every f 2 F. Then card(F)  +.

Proof. Let f 2 F. Let

Ff = fg 2 Fj g <U f g [ ff g:
68 Section 23

(1) card(Ff )   .
Proof . For i <  with f (i) < i+ choose an injection hi: f (i) ! i . For g 2 Ff dene g 0:  ! V by
(
hi(g(i)), if g(i) < f(i) < i+
g 0(i) =
g(i), else

Then g 7! g 0 is an injective map from Ff into fg 0 j g 2 Ff g. fg 0 j g 2 Ff g is an U -almost disjoint

family where g 0 <U d for every g 2 Ff . By the previous lemma, card(fg 0 j g 2 Ff g) 6  and so
card(Ff )  . qed (1)
S
We construct a sequence (fj  < ) of functions in F by induction such that F = fFfj  <  g.
Take an arbitrary f0 2 F (wlog. F = / ; ).
S
If (f j  < ) is already dened, choose f 2 fFf  j v <  g if possible. If there is no such f, set
 =  and stop.
(2)   +.
Proof . Assume that f+ is dened. If  < + then f+ 2 / Ff . So f+ U f . By the various
assumptions on F: f <U f+ . Thus fv 2 F+ for all v <  , and card(Ff+) > +. This contra-
dicts (1). qed (2)
Altogether
[ X X
card(F) = card( fFfj  <  g) 6 card(Ff) 6  6 
+ = +:
< < 


Theorem 182. Let  be a measurable cardinal and assume that 2 =  for  <  . Then
2 = +:

Proof. Fix a normal non-principal -complete ultralter U on  .

For i <  choose a map hi: P(i) !  which injects P(i) into i+ for innite i . Dene a map from
P() into  by
X 7! fX = (hi(X \ i)ji < ) 2 :
If X =
/ Y then fX and fY are almost disjoint and hence U -almost disjoint. Also fX <U d +. So by
the previous Lemma
card(P()) 6 card(ffX jX 2 P(g) 6 +:


23 Partition properties and partition cardinals

Denition 183. Let X be a term X . For a natural number n < ! let
[X]n = fa  X j card(a) = ng
be the collection of n-element subsets of X . Let

[X]<! = fa  X j card(a) < !g

be the collection of nite subsets of X . Let
[X]! = fa  X j card(a) = !g
be the collection of countable subsets of X .
A function f : [X]n ! V or f: [X]<! ! V or f : [X]n ! V is called a partition of [X]n or [X]<! or
[X]! respectively.

Theorem 184. (Ramsey) Let n < ! and let f : [!]n ! 2 . Then there is an innite X  ! such
that f  [X]n is constant. The set X is called homogeneous for f.
Partition properties and partition cardinals 69

Proof. By induction on n . The claim is trivial for n = 0 , and it is an easy instance of an inn-
itary pidgeon principle in case n = 1. So assume the claim for n and let f : [!]n+1 ! 2 be given.
We shall nd an n + 1-dimensional homogeneous set for f by taking n-dimensional homo-
geneneous sets for sections fx of f . For x 2 ! dene fx: [! n (x + 1)]n ! 2 by
fx(s) = f (fxg [ s):

We dene sequences x0; x1; ::: , c0; c1; ::: and X0; X1; :::: by simultaneous recursion such that
a) x0 < x1 < ::: < !
b) xi < min (Xi), xi+1 2 Xi
c) c0; c1; :::2f0; 1g
d) !  X0  X1  ::: are innite homogeneous sets for fx0 ; fx1 ; ::: respectively such that 8s 2
[Xi]n fxi(s) = ci
Set x0 = 0 . By the inductive assumption take X0 to be an innite homogeneous set for fx0 and
take c0 2 f0; 1g such that 8s 2 [X0]n fx0(s) = c0 .
If xi and Xi are dened, take xi+1 2 Xi . Then use the inductive assumption and take Xi+1 
Xi n (xi+1 + 1) to be an innite homogeneous set for the function fxi+1  [Xi n (xi+1 + 1)]n. Take
ci+1 such that 8s 2 [Xi+1]n fxi+1(s) = ci+1 .
By the pidgeon principle there is an innite set X  fx0; x1; :::g and a c 2 f0; 1g such that 8xi 2
X ci = c .
We show that X is homogeneneous for f with constant value c . Let t 2 [X]n+1. Let xi = min (t)
and s = t n fxig. Then s 2 [Xi]n and
f (t) = fxi(s) = ci = c:

S
Then X is homogeneous for f : n6i<! []
i
! 2 if for every i 2 [n; !) and every x; y 2 [X]i
f (x) = f (y)

Theorem 185. (Rowbottom's Theorem) Let  be a measurable cardinal with normal measure
U . Let F : []<! ! 2 . Then there is X 2 U such that f  [X]n is constant for every n 2 ! . The set
X is called homogeneous for F.

Proof. We show by induction on n 2 ! :

(1) There is X n 2 U such that f  [X n]n is constant.
Proof . The case n = 0 is trivial. The case n = 1 holds because U is a lter.
n ! n + 1 . For i <  dene Fi: [ n (i + 1)]n ! 2 by
Fi(a) = F (fig [ a):
By the inductive hypothesis take Xi 2 U and ci 2 2 such that
Fi[[Xi]n] = fcig:
Take Y 2 U and c 2 2 such that
8i 2 Y ci = c:
Let
i
X n+1 = Y \ Xi 2 U :
i<

Then X n+1 is homogeneous for F  []n+1 with constant value c . Indeed for fig [ a 2 [X n+1]n+1
with i < min a we have a 2 [Xi]n and
F (fig [ a) = Fi(a) = ci = c:
qed (1)
70 Section 23

Now take X 0; X 1; ::: 2 U according to (1) and let

\
X= X n:
n<!

Then X is homogeneous for F  [] for every n 2 ! .

n


Theorem 186. Let  be an innite cardinal. There is F : []! ! 2 such that there is no innite
homogeneous set for F.

Proof. By the axiom of choice take a wellorder  of []!. Dene

F (a) = 0 i 8b 2 [a]!(a =
/ b ! a  b):
So F (a) = 0 expresses that a is -smaller than all its innite subsets. Assume that X   were
an innite homogeneneous subset for F . Let a 2 [X]! be -minimal in [X]!. Then F (a) = 0 .
Take an !-sequence
a0 ( a1 ( a2 ( ::: ( a:
By homogeneity,
F (a0) = F (a1) =


= F (a) = 0:
This implies
a0  a1  a2 


;
which contradicts  being a wellorder. 

Denition 187. For ordinals ; ;  and n 2 ! dene

a) !( )n i every function f : [ ]n !  possesses a homogeneous set X  of ordertype >
:
b) ! ( )<n i every function f: [ ]<n !  possesses a homogeneous set X  of order-
type > :
c) ! ( )! i every function f: [ ]<! !  possesses a homogeneous set X  of ordertype
> :

With these notations we have shown:

¡ ! ! (!)2n ;
¡ if  is a measurable cardinal then  ! ()2<! ;
¡  9 (!)2! .
We dene some associated (large) cardinal notions.

Denition 188. Let  denote an uncountable cardinal.

a)  is weakly compact i  ! ()22 .
b) For 2 Ord let ( ) be the smallest cardinal  such that  ! ( )2<!, if such a  exists.
( ) is called the -th Erdös cardinal.
c)  is a Ramsey cardinal i  ! ()2<! .

Theorem 189. Measurable cardinals are Ramsey cardinals. Ramsey cardinals are weakly com-
pact.

Lemma
S 190. Let > ! and n < ! . Then 9 ( )<! i there is a function g: []n6i<! =
n6i<! [] ! 2 without a homogeneous subset of order type , i.e., there is no X   with
i

otp(X) = such that for all i 2 [n; !) and x; y 2 [X] we have g(x) = g(y).
i

Proof. The implication from right to left is trivial. S

Conversely take f : []<! ! 2 which does not
have a homogeneous subset of order . Deniere g: n6i<! []i ! 2 by

g(x) = f(x n x  n);

Partition properties and partition cardinals 71

where denotes the initial segment of x of order type n . Assume that g has a homogeneous
subset X of order type . Let Y = X n X  n . Since is innite, otp(Y ) = . We show for a
contradiction that Y is homogeneneous for f . Let i < ! and x; y 2 [Y ]i. Then by the homogen-
eity of X
f (x) = g(X  n [ x) = g(X  n [ y) = f(y): 

Lemma 191. Assume  9 ( )<! with innite. Then 2 9 ( + 1)<!. In case  is a limit
ordinal also 2 9 ( )<!.

Proof. Take f : []36n<! ! 2 without a homogeneous subset of order type . We then dene g:
[2]26n<! ! 2 . Let < well-order 2 . Let  denote the lexicographic ordering of 2 . We want to
ensure that on a homogeneous set  agrees with < or with the converse ordering >. For fx;
yg 2 [2]2 with x < y set
g(fx; yg) = 0 i x  y :
The lexicographic order is dened via rst dierences. For x; y 2 2 with x =
/ y let
(x; y) = min fj x() =
/ y()g;

then x  y i 0 = x( (x; y)) < y( (x; y)) = 1 .

Now we dene another auxiliary function which will turn a homogeneous set in 2 into a homo-
geneous set in  . Consider fx; y; zg 2 [2]3 with x  y  z . Since the functions are 2-valued we
cannot have (x; y) = (y; z).
If (x; y) < (y; z) then y and z agree up to and including (x; y). So the rst dierences (x;
y) and (x; z) agree and
(x; y) = (x; z) < (y; z):

If (y; z) < (x; y) then x and y agree up to and including (y; z). So the rst dierences (y;
z) and (x; z) agree and
(y; z) = (x; z) < (x; y)
According to these cases we dene for x  y  z

0 if (x; y) = (x; z) < (y; z)
g(fx; y; z g) =
1 if (y; z) = (x; z) < (x; y)

So for x  y from a g-homogeneous set, the ordinal (x; y) will only depend on the rst argu-
ment in case g  1 or, resp., on the second in case g  0.
So for s 2 [2]46i<! from a g-homogeneous set the set
(s) = f (x; y)j x; y 2 s; x  y g
will have card(s) ¡ 1 many elements.
Dene g: [2]46n<! ! 2 by 
f ( (s)) if card( (s)) > 3
g(s) =
0 else

Set = + 1 if is a successor ordinal, and = if is a limit ordinal. We show that g wit-

nesses 2 9 ( )<!.
So assume for a contradiction that X  2 has order type with respect to < and that X is
homogeneous for g .
Case 1 . g[[X]2] = f0g. This means that < and  agree on X so that X has order type with
respect to . If g[[X]3] = f1g, we have (x; y) > (x; z) for x  y  z from X . Taking an
increasing !-sequence x0  x1 2 ::: from X this yields a contradiction in the form of a des-
cending !-sequence of ordinals:
(x0; x1) > (x0; x2) > (x0; x3)::::
72 Section 23

Therefore g[[X]3] = f0g. Then (x; y) for x; y 2 X ; x  y only depends on x and (X) = f (x;
y)j x; y 2 X ; x  yg  Ord has order type . We obtain a contradiction by showing that (X) is
homogeneous for f : let 3 6 n < ! and consider two ascending n-sequences from (X):

(x0; y0) < ::: < (xn¡1; yn¡1) and (x00 ; y00 ) < ::: < (xn¡1
0 0
; yn¡1):

Then x0  x1  :::  xn¡1  yn¡1 and x00  x10  :::  xn¡1

0 0
 yn¡1 in X and

f (f (x0; y0); :::; (xn¡1; yn¡1)g) = f (f (x0; yn¡1); :::; (xn¡1; yn¡1)g)
= f ( (fx0; x1; :::; xn¡1; yn¡1g))
= g(fx0; x1; :::; xn¡1; yn¡1g)
= g(fx00 ; x10 ; :::; xn¡1
0 0
; yn¡1 g)
0 0 0 0
= f ( (fx0; x1; :::; xn¡1; yn¡1g))
= f (f (x00 ; yn¡10 0
); :::; (xn¡1 0
; yn¡1)g)
0 0 0 0
= f (f (x0; y0); :::; (xn¡1; yn¡1)g):

Case 2 . g[[X]2] = f1g. This means that < and  agree on X so that X has order type with
respect to . If g[[X]3] = f0g, we have (x; z) < (y; z) for x  y  z from X . Taking a
decreasing !-sequence x0  x1 2 ::: from X this yields a contradiction in the form of a des-
cending !-sequence of ordinals:
(x1; x0) > (x2; x0) > (x3; x0)::::

Therefore g[[X]3] = f1g. Then (x; y) for x; y 2 X ; x  y only depends on y and (X) = f (x;
y)j x; y 2 X ; x  yg  Ord has order type . We obtain a contradiction by showing that (X) is
homegeneous for f : let 3 6 n < ! and consider two ascending n-sequences from (X):

(x0; y0) < ::: < (xn¡1; yn¡1) and (x00 ; y00 ) < ::: < (xn¡1
0 0
; yn¡1):

Then x0  y0  :::  yn¡1 and x00  y00  :::  yn¡1

0
in X and

f (f (x0; y0); :::; (xn¡1; yn¡1)g) = f (f (x0; y0); :::; (x0; yn¡1)g)
= f ( (fx0; y0; :::; yn¡1g))
= g(fx0; y0; :::; yn¡1g)
= g(fx00 ; y00 ; :::; yn¡1
0
g)
0 0 0
= f ( (fx0; y0; :::; yn¡1 g))
0 0 0 0
= f (f (x0; y0); :::; (x0; yn¡1 )g)
0 0 0 0
= f (f (x0; y0); :::; (xn¡1; yn¡1)g):

for x  y  z 
0 if (x; y) = (x; z) < (y; z)
g(fx; y; z g) =
1 if (y; z) = (x; z) < (x; y)

Lemma 192. If 2 Lim then ( ) is regular.

Proof. Assume that ( ) is singular. Take x  ( ) conal such that

 := otp(x) = cof(( )) < ( ):

Dene h: ( ) !  by h() = otp( \ x). Then card(h¡1[f g]) < ( ) for <.
Choose functions
f : []<! ! 2 and f : [h¡1[f g]]<! ! 2
for <  that do not possess homogeneous subsets of ordertype . Dene
g: [( )]<! ! 2
Partition properties and partition cardinals 73

by
8
>
> 0 if n = 2 and h(0) = h(1)
>
>
>
< 1 if n = 2 and h(0) < h(1)
g(f0; :::; n¡1g) = f (f2; 3; :::; n¡1g) if n > 2 and h(0) = ::: = h(n¡1) =
>
>
>
> f(fh(2); h(3); :::; h(n¡1)g) if n > 2 and h(1) < ::: < h(n¡1)
>
: 0 else

where 0 < 1 < ::: < n¡1 . Note that the case h(0) > h(1) does not occur since h is a never-
decreasing function.
Let H  ( ) be homogeneous for g with otp(H) = . Let 0 < 1 be the rst and second ele-
ment of H . Let H 0 = H n f0; 1g.
Case 1 . h(0) = h(1). Then h(0) = h() for all  2 H 0. Let = h(0). Then H 0 is homogeneous
for f : Let 2; 3; :::; n¡1 2 H 0 with 2 < ::: < n¡1 and 20 ; 30 ; :::; n¡1
0
2 H 0 with 20 < ::: < n¡1
0
.
Then
f (f2; 3; :::; n¡1g) = g(f0; 1; 2; :::; n¡1g) = g(f0; 1; 20 ; :::; n¡1
0
g) = f (f20 ; 30 ; :::; n¡1
0
g):

But H 0 has ordertype , contradiction to the choice of f .

Case 1 . h(0) < h(1). Then h  H 0 is orderpreserving and h[H 0] has ordertype . We get a con-
tradiction by showing that h[H 0] is homogeneneous for f : Let 2; 3; :::; n¡1 2 H 0 with 2 < ::: <
n¡1 and 20 ; 30 ; :::; n¡1
0
2 H 0 with 20 < ::: < n¡1
0
. Then

f (fh(2); h(3); :::; h(n¡1)g) = g(f0; 1; 2; :::; n¡1g)

= g(f0; 1; 20 ; :::; n¡1
0
g)
0 0 0
= f (fh(2); h(3); :::; h(n¡1 )g):


Theorem 193. If 2 Lim then ( ) is strongly inaccessible.

Theorem 194. If > > ! then ( ) > ( ).

Proof. It suces to dene a map g: [( )]16n<! ! 2 such that every homogeneous subset for g
has ordertype 6 .
For < ( ) choose f : [ ]<! ! 2 which does not have a homogeneous subset of ordertype .
Dene g: [( )]16n<! ! 2 by
g(f0; :::; ng) = fn(f0; :::; n¡1g)
where 0 < ::: < n¡1 < n . Assume that H is homogeneous for g of ordertype > . Let be the
-th element of H . H \ has ordertype . We get a contradiction by showing that H \ is
homogeneous for f : Let Let 0:::; n¡1 2 H 0 with 0 < ::: < n¡1 and 00 ; :::; n¡1
0
2 H 0 with
0 0
0 < ::: < n¡1 . Then

f (f0:::; n¡1g) = g(f0; :::; n¡1; g) = g(f00 ; :::; n¡1

0
; g) = f (f00 :::; n¡1
0
g): 

Theorem 195. If  is a measurable cardinal with normal measure U . Then the set
f < j  is a Ramsey cardinal g 2 U :

Proof. Otherwise X = f < j  is not a Ramsey cardinalg 2 U . We can assume that every  2
X is an innite cardinal. For every  2 X choose a function f: []<! ! 2 which does not have a
homogeneous subset of order type  . Dene f : []<! ! 2 by
(
fmax(x)(x n max (x)) if x =
/;
f (x) =
0 else
Let Y 2 U be homogeneous for f .
(1) f 2 Y j otp(Y \ ) = g 2 U .
74 Section 23

Proof . Otherwise one can dene a regressive function  7! otp(Y \ ) on a measure one set in U
which contradicts that otp(Y ) =  . qed (1)
So let  2 Y with otp(Y \ ) =  . It is easy to see that Y \  is homogeneous for f : if n < !
and x; y 2 [Y \ ]<! then
f(x) = f (x [ fg) = f (y [ fg) = f(x):
Contradiction. 

So we obtain the following picture of the large cardinal hierarchy:

the smallest measurable cardinal 
_
the smallest Ramsey cardinal 
_





_
( )
_ for ! 6 < <
( )
_
(!)
>
the smallest inaccessible cardinal
There are many more questions about this scale of large cardinals, like is (!) > the smallest
inaccessible cardinal? Where are the weakly compact cardinals?