Exercise sessions for the Set theory course, spring
semester 2021
Giulio Lo Monaco
Week 1
Definition Given some symbols p, q, . . . and a (non-quantified) formula containing the
given symbols and →, ¬, =, giving a truth table means to specify the truth
values of the whole formula for each possible assignment of truth values
on the symbols p, q, . . ..
We say that two formulas are equivalent if they have the same truth tables.
Example The formula p → q has the following truth table:
p q p → q
T T T
T F F
F T T
F F T
Recall that we can shorten ¬p → q into p ∨ q and ¬(p → ¬q) into p ∧ q.
Let us compute their truth tables and see that they correspond with the
expected ones, that is, p ∨ q is false if and only if both p and q are false,
and p ∧ q is true if and only if both p and q are true.
p q ¬p ¬p → q
T T F T
T F F T
F T T T
F F T F
p q ¬q p → ¬q ¬(p → ¬q)
T T F F T
T F T T F
F T F T F
F F T T F
Exercise Find the truth table of the formula
¬(p ∨ q) ∨ (¬p ∧ q).
Solution We can build it one step at a time in the following table
p q p ∨ q ¬(p ∨ q) ¬p ¬p ∧ q ¬(p ∨ q) ∨ (¬p ∧ q)
T T T F F F F
T F T F F F F
F T T F T T T
F F F T T F T
1
Exercise Verify if the two following formulas are equivalent:
¬(p ∧ q) ∧ (¬q ∧ ¬r)
¬p ∧ ¬q ∧ ¬r.
Solution We need to calculate the truth tables of both formulas:
p q r ¬q p ∧ ¬q ¬(p ∧ ¬q) ¬r ¬q ∧ ¬r ¬(p ∧ ¬q) ∧ (¬q ∧ ¬r)
T T T F F T F F F
T T F F F T T F F
T F T T T F F F F
T F F T T F T T F
F T T F F T F F F
F T F F F T T F F
F F T T F T F F F
F F F T F T T T T
p q r ¬p ¬q ¬r ¬p ∧ ¬q ∧ ¬r
T T T F F F F
T T F F F T F
T F T F T F F
T F F F T T F
F T T T F F F
F T F T F T F
F F T T T F F
F F F T T T T
so they are equivalent, because their truth values always coincide.
Exercise Suppose we are given a language with a binary relation symbol R. Express
in formulas the following properties:
1. R is a function;
2. R is a bijection;
3. R is an equivalence relation;
4. R is a linear order on a set with three elements.
Solution We will have to be specifically careful to all instances of the phrase “it
exists a unique x such that φ(x)”. The usual way to express this is
∃!xφ(x)
but using the symbols of predicate logic this has to be written
∃xφ(x) ∧ ∀y(φ(y) → y = x).
Now let us proceed with the solution
2
1. ∀x(∃yRxy ∧ ∀z(Rxz → z = y));
2. ∀x(∃yRxy ∧ ∀z(Rxz → z = y)) ∧ ∀y(∃xRxy ∧ ∀w(Rwy → w = x));
3. ∀x∀y∀z(Rxx) ∧ (Rxy → Ryx) ∧ ((Rxy ∧ Ryz) → Rxz);
4. ∃x∃y∃z(∀w(w = x) ∨ (w = y) ∨ (w = z))∧
(¬x = y ∧ ¬y = z ∧ ¬x = z)∧
(Rxx ∧ Rxy ∧ Ryy ∧ Ryz ∧ Rzz ∧ Rxz)
∀u∀v(Ruv → (u = v ∨ (u = x ∧ v = y) ∨ (u = x ∧ v = z) ∨ (u =
y ∧ v = z))).
Exercise Let us consider a language with one binary operation symbol +. Express
the following properties of a realization M in formulas:
1. M is associative;
2. M contains a unit element;
3. M is a group;
4. M is an abelian group.
Solution As is usual practice, the symbol + goes between variables instead of preceding
them. If we want to stick to our definition of terms and formulas,
let us for example use the symbol f for the sum operation, and write it in
prefix notation.
1. ∀a∀b∀cffabc = fafbc;
2. ∃e∀a(fae = a) ∧ (fea = a);
3. This includes the two previous formulas plus invertibility of all ele-
ments:
∀a∃b(fab = e) ∧ (fba = e);
4. This includes all of the previous plus
∀a∀bfab = fba.
Note that, if we are describing an abelian group, the existence of a
unit and invertibility of elements can be simplified to the following
forms:
∃e∀afae = a;
∀a∃bfab = e.
Week 2
Definition Fixing a language, a sequent is a string of the form Θ ⇒ φ, where Θ is a
finite set of formulas in the given language, φ is a single formula and ⇒
is a new symbol, not comprised in the language.
Remark The way to think of sequents is: if all the premises in the antecedent Θ
are true, then we conclude that φ is also true.
We can also take Θ to be an empty set, in which case we often abbreviate
the sequent to the single formula φ.
3
Definition A theory is a pair (L, A), where L is a formal language and A is a set of
sequents, called the axioms of set theory.
Informal definition A model for a theory is a realization that makes all its axioms true.
Example Given the theory whose language contains one binary operation symbol
f, and having the two axioms
∀a∀b∀cffabc = fafbc;
∃e∀a(fae = a) ∧ (fea = a)
a model for this theory is precisely a monoid.
Example Given the theory whose language contains one binary operation symbol f
and one constant symbol e, and having the three axioms
∀a∀b∀cffabc = fafbc;
∀a(fae = a) ∧ (fea = a);
∀a∃b(fab = e) ∧ (fba = e)
then a model for this theory precisely a group.
Example Axiomatic set theory can be formalized as a theory in the sense above.
Unfortunately, we will leave its description incomplete for now, concentrating
on its parts a little at a time.
The language of set theory only comprises one binary relation symbol ∈.
So far, we have seen only some of its axioms, namely:
Extensionality ∀x∀y(x = y ↔ (∀z(z ∈ x ↔ z ∈ y)));
Union ∀x∃y∀z(z ∈ y ↔ (∃t(t ∈ x ∧ z ∈ t)));
Power ∀x∃y∀z(z ∈ y ↔ z ⊆ x);
Pairing ∀x∀y∃z(x ∈ z ∧ y ∈ z);
Infinity ∃x(∅ ∈ x ∧ ∀y(y ∈ x → y ∪ {y} ∈ x));
note that when we write ∅, we can either define it through separation (see
below) or add it to the language as a constant symbol, but in that case
we need an additional axiom giving it the desired property.
The separation schema, rather than an axiom, is a family of axioms (in
fact, an infinite family) indexed by all possible formulas in the given language.
In order to define it precisely, we need a preliminary definition.
Definition Let x be a variable symbol and φ a formula in which x appears. Then x
is said to be free in φ if its first occurrence is not quantified, i.e. it is not
preceded by ∀ or ∃.
Given a formula φ(x1, . . . , xn) where the variables xi’s are free, and given
other variable symbols a1, . . . , an, then φ(a1, . . . , an) will denote the formula
φ where all the occurrences of the variable symbols xi’s have been
replaced by the corresponding symbols ai’s.
Continuation We can now define the axioms of separation. Given any formula φ(x) in
the language of set theory, where x is free, then there is an axiom
4
∀z∃y(a ∈ y ↔ (a ∈ z ∧ φ(a)).
Exercise Given a set A, how do we define the intersection of all its elements using
the axioms of set theory?
Solution We choose one of the sets a ∈ A, and then we observe that the expression
∀b ∈ A(x ∈ b) is a formula in which x is free. The intersection is now
defined using separation, as
∩b∈Ab := {x ∈ a|∀b ∈ A(x ∈ b)}.
Remark We might want to define union similarly. The string ∃b ∈ A(x ∈ b) is a
formula in which x is free, and it certainly expresses the desired property
of the union of all sets b ∈ A. However, there is a priori no set containing
all the b’s, which is precisely why we need the axiom of union.
• We know Cantor-Bernstein theorem, which states that if A and B are two
sets and there are two injective functions f : A → B and g : B → A, then
there is a bijection A ∼= B. The proof is non-trivial, but it is presented in
the course notes, except for Tarski’s fixed point thorem, which is used to
find a subset C ⊆ A such that C = A − g(B − f(C)).
Definition A complete lattice is a partially ordered set such that every set of points
in it admits a join.
Tarski’s theorem Let X be a complete lattice and f : X → X an order-preserving function.
Then there is a fixed point for f, i.e. ∃xf(x) = x.
Proof By the axiom of separation, we can define Y = {y ∈ X|y ≤ f(y)}. Now
take x := sup Y , which exists because X is complete. We have then
that ∀y ∈ Y, y ≤ f(y) ≤ f(x) because f is order-preserving, therefore by
definition of supremum we obtain x ≤ f(x).
Moreover, this relation implies, again since f is order-preserving, that
f(x) ≤ f2
(x), which means that f(x) ∈ Y . Consequently, f(x) ≤ x. Now
we have that x ≤ f(x) and f(x) ≤ x which immediately gives x = f(x).
Remark Tarski’s theorem can be applied in the proof of Cantor-Bernstein theorem,
because for every set A, the power set P(A) is a complete lattice, ordered
by inclusion.
Week 3
Definition Recall that the product of two cardinals α = |A| and β = |B| is defined
as α · β = |A × B|, and their exponential is αβ
= |AB
|, where the latter is
the set of all functions B → A.
Exercise Put the following cardinals in increasing order: ℵ0, 2·ℵ0, ℵ0·2, 2ℵ0
, ℵℵ0
0 , cℵ0
, ℵc
0, ℵ0·
ℵ0.
Solution We know that ℵ0 ≤ 2 · ℵ0 ≤ ℵ0 · ℵ0 = ℵ0, and moreover multiplication of
cardinals is commutative, because for any two sets A and B the products
A × B and B × A are naturally in bijection. Therefore we have
5
ℵ0 = 2 · ℵ0 = ℵ0 · 2 = ℵ0 · ℵ0.
We also know, by Cantor theorem, that 2ℵ0
> ℵ0, and certainly ℵℵ0
0 ≥ 2ℵ0
so
ℵℵ0
0 > ℵ0.
Next, we can show that ℵℵ0
0 = 2ℵ0
= c. To see this, compute
2ℵ0
≤ ℵℵ0
0 ≤ (2ℵ0
)ℵ0
= 2ℵ0·ℵ0
= 2ℵ0
.
Similarly we compute
2ℵ0
≤ cℵ0
= (2ℵ0
)ℵ0
= 2ℵ0·ℵ0
= 2ℵ0
so that cℵ0
= c.
Finally, we compute
ℵc
0 ≤ 2ℵ0·c
= 2c
≤ ℵc
0
so ℵc
0 = 2c
> c. In conclusion, we can order
ℵ0 = 2 · ℵ0 = ℵ0 · 2 = ℵ0 · ℵ0 < 2ℵ0
= ℵℵ0
0 = cℵ0
< ℵc
0.
Exercise Show that, for two infinite cardinals α, β, we have α + β = α · β =
max{α, β}.
Solution Let us first consider the sum, assuming without loss of generality that
α ≤ β, so that max{α, β} = β. We compute
β ≤ α + β ≤ β + β = 2 · β = β.
The computation for the product is entirely analogous:
β ≤ α · β ≤ β · β = β2
= β.
Exercise Show that, for two infinite cardinals α ≤ β, we have αβ
= 2β
.
Solution We have to show that 2β
≤ αβ
and αβ
≤ 2β
. We can proceed as in the
previous exercise.
2β
≤ αβ
≤ (2α
)β
= 2α·β
= 2β
Exercise Given infinite cardinals α, β, γ such that α < β, determine if it is true that
αγ
< βγ
and that γα
< γβ
.
Solution Neither of the two inequalities is true in general. For example, it is true
that ℵ < c but
6
ℵℵ0
0 = cℵ0
= c
as we have seen above, and
(2c
)ℵ0
= (2c
)c
because they both equal (2c
), as it is easily proven with an argument just
like the ones seen above.
In general, we can only say that αγ
≤ βγ
and γα
≤ γβ
.
Exercise Show that |Q| = |N|.
Solution We know that |Z| = |N|, so it suffices to show that Q+
is in bijection with
N. By the tabular argument we build a bijection between N and N × N,
that is, we enumerate N as in the following diagram
(0, 0) (0, 1) (0, 2) . . .
(1, 0) (1, 1) (1, 2) . . .
(2, 0) (2, 1) (2, 2) . . .
...
...
...
...
Now, we have a surjection N × N → Q+
given by (p, q) → p
q . Choosing
p and q to be coprime gives us a left inverse function, which is clearly an
injection Q+
→ N × N ∼= N.
Moreover, there is an injection N → Q+
given simply by n → n
1 .
We conclude using Cantor-Bernstein’s theorem, which provides a bijection
N ∼= Q+
.
Exercise Show that |R| > |N|.
Solution There is an inclusion N → R, so |N| ≤ |R|. We need to prove that there
is no bijection R → N.
By a geometrical projection, we know that the open interval (0, 1) is in
bijection with the whole R, so we are reduced to prove that (0, 1) is not in
bijection with N. Assume by contradiction that there is such a bijection.
Then, if we express real numbers through their decimal representation, we
have an enumeration
0.h1
1h1
2h1
3 . . .
0.h2
1h2
2h2
3 . . .
0.h3
1h3
2h3
3 . . .
...
Now define a new real number 0.k1k2k3 . . . where kn = 1 whenever hn
n is
even and kn = 2 whenever hn
n is odd. This number can’t be part of this
enumeration by construction, so the claimed bijection is not surjective,
which is a contradiction.
7
Week 4
Exercise Characterize all well-ordered sets A such that Aop
is also well-ordered.
Solution These sets are precisely the finite ones. Indeed, if A is finite then each of
its subsets has a maximum element, which becomes a minimum in Aop
.
On the other hand, if A is infinite, then we know that |ω| ≤ |A|, so that ω is
an initial segment of A. Now take a non-empty subset of ω, and therefore
of A, which has no maximum. Its corresponding subset in ωop
⊆ Aop
has
no minimum.
Exercise Give an example of a well-ordering on the set ω × ω.
Solution A possible solution is the lexicographic ordering: for (a, b), (a , b ) ∈ ω×ω,
set
(a, b) < (a , b ) if either a < a or a = a and b < b .
It is immediate to check that it is a total order. Moreover, suppose S ⊆
ω × ω is non-empty. Then take
a0 := min{a ∈ ω|∃b such that (a, b) ∈ S}
which exists because ω is well-ordered, and
b0 := min{b ∈ ω|(a0, b) ∈ S}
which exists for the same reason. Then (a0, b0) is the minimum of S.
Another possible well order is:
(a, b) < (a , b ) if either a + b < a + b or a + b = a + b and a < a .
(0, 0) (0, 1) (0, 2) (0, 3) . . .
(1, 0) (1, 1) (1, 2) (1, 3) . . .
(2, 0) (2, 1) (2, 2) (2, 3) . . .
(3, 0) (3, 1) (3, 2) (3, 3) . . .
...
...
...
...
...
This is a total order because ω is, and a + b, a + b ∈ ω.
Moreover, given a non-empty subset S ⊆ ω × ω, define
8
n0 := min{n ∈ ω|∃a∃b such that (a, b) ∈ S and a + b = n}
which exists because ω is well-ordered. Then define
a0 := min{a ∈ ω|∃b such that (a0, b) ∈ S and a + b = n0}
which again exists for the same reason. Then (a0, n0 −a0) is the minimum
of S.
We can give yet another solution: calling c = max{a, b} and c = {a , b },
(a, b) < (a , b ) if c < c or c = c and a < a or c = c , a = a and b < b .
In other words, it restricts to the lexicographic order whenever the maxima
coincide.
(0, 0) (0, 1) (0, 2) (0, 3) . . .
(1, 0) (1, 1) (1, 2) (1, 3) . . .
(2, 0) (2, 1) (2, 2) (2, 3) . . .
(3, 0) (3, 1) (3, 2) (3, 3) . . .
...
...
...
...
...
This is a linear order because ω is linearly ordered and c, c ∈ ω.
To see that it is a well-ordering, let us consider a non-empty subset S ⊆
ω × ω, and define
c0 := min{c ∈ ω|∃(a, b) ∈ S such that max{a, b} = c}
a0 := min{a ∈ ω|∃b such that (a, b) ∈ S and max{a, b} = c0}
b0 := min{b ∈ ω|(a0, b) ∈ S}.
Then the pair (a0, b0) is the minimum of S.
Exercise Prove that the set of algebraic numbers is countable.
Solution Remember that a real number r is called algebraic if there is a polynomial
a0 + a1x + a2x2
+ . . . + anxn
with integers coefficients such that a0 +
a1r . . . + anrn
= 0.
The set of polynomials of degree n is in bijection with Zn
, because every
polynomial is determined by its coefficients. Now, we know from algebra
that a polynomial of degree n has at most n roots, so the set of real
numbers that are roots of polynomials of degree n is contained in n ×
9
Zn
. As a consequence, the set Q of all algebraic numbers is contained in
n∈N n × Zn
.
Now observe that Z is countable, as we already know, and a finite product
of countable sets is easily shown to be countable, so Zn
is countable as
well. A fortiori, we know that n × Zn
is countable, because it is a finite
product of sets that are at most countable. Finally, a countable union of
countable sets is countable, because n∈N N × {n} = N × N. It follows
that n∈N n × Zn
is countable, so that there is an injective function
Q → n∈N n × Zn ∼= N
and |Q| ≤ |N|.
For the other direction, observe that every natural number n is algebraic,
just taking the polynomial −n + x, so the inclusion N ⊆ Q implies that
|N| ≤ |Q|.
Axiom of choice The axiom of choice states that for every family of sets (Xi)i∈I there is a
function c : I → i∈I Xi such that ∀i ∈ I we have that c(i) ∈ Xi.
Well-ordering principle The well-ordering principle states that for every set X there can be defined
a well-ordering on X.
Exercise Show that the well-ordering principle implies the axiom of choice.
Solution Assume the well-ordering principle. Then make every Xi into a wellordered
set, and define the function
c : i → min Xi.
Remark In fact, the converse implication is also true, that is, assuming the axiom
of choice we can define a well-ordering on every set, but the proof of this
is much more involved.
Week 5
Exercise Show that ω · 2 ω
Solution If there was an isomorphism of ordered sets, each subset of ω · 2 would
correspond uniquely to a subset of ω with the same order-theoretic properties.
But ω · 2 has an infinite subset with a maximum, namely ω + 1,
which ω doesn’t have. Therefore they can’t be isomorphic.
Definition We denote ω0 := ω. Then inductively for every ordinal α we denote as
ωα+1 the smallest ordinal number whose cardinality is bigger than |ωα|.
For example, the symbol ω1 will denote the smallest uncountable ordinal.
Exercise Find, in the class of ordinal numbers:
1. The third smallest infinite ordinal number;
2. some ordinal α such that ω2
< α < ω3
;
3. the largest countable ordinal number;
10
4. the ω-th uncountable ordinal number.
Solution We separate the four requests:
1. The smallest infinite ordinal number is ω, so we only have to take
its successor twice, in the class of ordinals. We obtain that ω + 2 is
what we are looking for.
2. Any ordinal of the form ω2
· n with n finite, or ω2
+ β, with β < ω3
,
satisfies the requirement.
3. No such ordinal exists. Indeed, for each countable ordinal α we have
α < α + 1, and α + 1 is clearly also countable.
4. By ω-th, we mean that the linearly ordered set of all uncountable
ordinals smaller than the one we wish to find is isomorphic to ω.
Now, since the smallest uncontable ordinal is ω1, the second smallest
uncountable ordinal will be ω1 + 1, so by induction we obtain that
the (n + 1)-th smallest uncountable ordinal is ω1 + n. This implies
that the ω-th smallest will be ω1 + ω.
Exercise Write the following ordinals in the simplest possible way: 1ω
, 2ω
, . . . , nω
, . . . , ωω
.
Determine which ones, if any, are countable.
Solution By definition, 1ω
is the supremum of the set {1m
|m < ω}, which is constant
on 1. Therefore, 1ω
= 1.
For each 1 < n < ω, the set nω
is the supremum of the set {nm
|m < ω}.
All the elements of this set are finite ordinals, and moreover they are unbounded,
because for every m < ω we have m < nm
. Therefore, nω
is
equal to ω itself.
ωω
is the supremum of the set {ωn
|n < ω}. Since all these ordinals are
distinct, there is no simpler way of writing ωω
. Moreover, it is a countable
union of countable sets, therefore it is itself countable.
Observation The examples above are instances of one important fact: the arithmetic
of cardinals does not correspond with the arithmetic of ordinals. For
example, addition and multiplication are commutative in the former, but
not in the latter. Moreover, an operation like αβ
can have very different
results depending on whether we regard α and β as cardinals or as ordinals.
However, it is still true that αβ+γ
= αβ
· αγ
and (αβ
)γ
= αβ·γ
, although
a little more complicated to prove (it will be done later on in the course).
Exercise Show that the equality α · ω1 = ω1 holds for each ordinal 1 ≤ α < ω1.
Solution α · ω1 is the supremum of the set {α · β|β is countable }. Each element
α · β is countable because it is a product of countable sets, so we have
α · β < ω1, which implies α · ω1 ≤ ω1.
On the other hand, for each countable ordinal β we have that β ≤ α · β <
α · ω1, so that α · ω1 is bigger than all countable ordinals, and therefore
ω1 ≤ α · ω1.
We have proven both the desired inequalities, so ω1 = α · ω1.
11
Week 6
Exercise We saw in an earlier exercise that the cardinals ℵ0, 2·ℵ0, ℵ0·2, 2ℵ0
, ℵℵ0
0 , cℵ0
, ℵc
0, ℵ0·
ℵ0 are ordered as
ℵ0 = 2 · ℵ0 = ℵ0 · 2 = ℵ0 · ℵ0 < 2ℵ0
= ℵℵ0
0 = cℵ0
< ℵc
0.
We want to do an analogous exercise, but regarding the given numbers
as ordinals instead. In other words, find the increasing ordinal order of
ω, 2 · ω, ω · 2, 2ω
, ωω
, ωω
1 , ωω1
, ω · ω.
Solution First, recall from the lecture that 2·ω = ω. Moreover, we have seen above
that ω·2 ω, so we obviously conclude that ω < ω·2. In another exercise,
we have seen that 2ω
= ω, while ωω
is bigger than all ωn
’s and therefore
all ω ·n’s, but it is still countable, and it behaves very differently in regard
to the respective order relations.
Next we compute
ωω1
= (2ω
)ω1
= 2ω·ω1
= 2ω1
= ω1.
As for ωω
1 , this is the supremum of the set {ωn
1 |n < ω}, all of whose
elements are strictly bigger than ω1, so ωω
1 > ω1.
Finally, we know that ω · ω is countable, and it is obviously bigger than
ω · 2 but smaller than ωω
.
In conclusion, the order of the given ordinals is
ω = 2 · ω = 2ω
< ω · 2 < ω · ω < ωω
< ωω1
< ωω
1 .
Exercise Find the smallest ordinal number α such that the power αω
is
1. a finite ordinal number;
2. a countable ordinal number;
3. an uncountable ordinal number.
Solution The solution to (1) is immediate, because 0ω
= 0, and 0 is the smallest
ordinal number.
For (2), observe that 1ω
= 1 and 2ω
= ω. Since 2 = 1+
, our solution is
exactly 2.
For (3), observe that for every countable ordinal number β we have βω
=
sup{βn
|n ∈ N}. Now, βn
is the product of a finite number of countable
sets, therefore it is countable itself. It follows that βω
, being a countable
union of countable sets, is itself countable. So the ordinal we are looking
for must be uncountable, therefore at least ω1. Since ωω
1 is uncountable,
our solution is precisely ω1.
Exercise Define ωω as the smallest ordinal whose cardinality is strictly bigger than
the cardinality of all ωn’s. In other words,
ωω := min{α, ∀n ∈ N|ωn| < |α|}.
12
Show that ωω = supn ωn.
Solution We will show both inequalities. First, observe that |ωn| < |ωω| implies
ωn < ωω for each n ∈ N, so that, by definition of supremum, we obtain
supn ωn ≤ ωω.
Conversely, since for each n the inequality ωn < supn ωn holds, it must
be true that |ωn| ≤ | supn ωn| (with the weak inequality sign, for the
moment). Thus we obtain
|ωn| < |ωn+1| ≤ | supn ωn|
now with a strict inequality sign. By definition of ωω, this means that
ωω ≤ supn ωn.
Definition Remember that for every ordinal number α > 0 there are non-null natural
numbers k, m0, . . . , mk and ordinal numbers γ0 > . . . > γk such that
α = ωγ0
· m0 + . . . + ωγk
· mk.
This expression is known as the Cantor normal form of α.
Exercise Find the Cantor normal form of ωn, or each n, and ωω.
Solution Following the first steps of the proof of the existence theorem for Cantor
normal forms, we start by looking at the set
X := {γ|ωγ
≤ ωn}
and then we study the ordinal ωsup X
.
Now, if n = 0, then X = {0, 1}, so that the above ordinal becomes ω1
=
ω = ω0, and we are done.
If 0 < n < ω, then X is the set of all ordinals of cardinality strictly smaller
than ωn, so that sup X = ωn. Thus we obtain that ωωn
≤ ωn. We only
need to show the other inequality. For that, observe that by previous
exercises we know that 2ωn
= ωn, so compute
ωn = 2ωn
≤ ωωn
.
Finally, turning to ωω, our X will be the set of all ordinals of cardinality
strictly smaller than ωω, therefore the same argument shows that the
Cantor normal form turns out to be ωωω
.
Remark The same line of reasoning proves in fact a more general result: if α is an
ordinal which is the smallest with its cardinality, then its Cantor normal
form is ωα
.
13
Proposition The Cantor normal form is unique.
Proof Consider an ordinal α, and take two Cantor normal forms for it
ωγ0
· m0 + . . . + ωγk
· mk
and
ωδ0
· n0 + . . . + ωδl
· nl
assuming without loss of generality that k ≤ l.
Since γ0 > . . . > γk and δ0 > . . . > δl, if γ0 < δ0 we would have that the
first normal form is smaller than the second, which is absurd. Therefore,
γ0 = δ0. For the same reason, we must have m0 = n0. Inductively, we
obtain that for 0 ≤ i ≤ k we have γi = δi and mi = ni.
It only remains to prove that k = l. Suppose by contradiction that k < l.
Then the remaining terms of the second normal form sum up to an ordinal
β = 0. Therefore, we obtain that first normal form gives α, while the
second gives α + β > α, which is absurd. This concludes the proof.
Week 7
Exercise Order the following ordinals increasingly: ω + 1 + ω, ω · (ω + 1), (1 + ω) ·
ω, (1 + ω) · (ω + 1), ω + 1 + ω2
+ ω.
Solution Remember that sum of ordinal numbers is associative, so the first is equal
to
ω + (1 + ω) = ω + ω.
Also remember that multiplication distributes with respect to addition, so
we have
ω · (ω + 1) = ω · ω + ω = ω2
+ ω.
Next, we have again (1 + ω) · ω = ω · ω = ω2
.
Use the same principles to compute
(1 + ω) · (ω + 1) = ω · (ω + 1) = ω2
+ ω.
Finally, we have
ω + (1 + ω2
+ ω) = ω + (ω2
+ ω) = (ω + ω2
) + ω = ω · (1 + ω) + ω =
ω · ω + ω = ω2
+ ω.
These ordinals are then ordered as
ω + 1 + ω < (1 + ω) · ω < ω · (ω + 1) = (1 + ω) · (ω + 1) = ω + 1 + ω2
+ ω.
14
Exercise Decide whether ωω
= ω or ω(ωω
)
= ωω
.
Solution Both are false. The proof of the first is analogous to the proof of ω ·2 = ω,
which extends to all ω · n’s and all ωn
’s.
As for the second, consider in both sets the subset of all elements γ such
that the set {δ|δ < γ} has no maximum. For the left-hand side, this is isomorphic
(as an ordered set) to ωω
, for the right-hand side it is isomorphic
to ω, so the result follows from the first part.
Exercise Define 0 to be the smallest ordinal α such that ωα
= α. Prove that
0 = ωωω···
.
Solution The ordinal ωω···
is defined to be the supremum of the sequence of ordinals
defined by α0 = ω and for each n ∈ ω, αn+1 = ωαn
. First, observe that,
this limit obviously has the required property. Therefore, by minimality
of 0, we have
0 ≤ ωω···
.
To prove the opposite inequality, let us start by observing that 0 cannot
be finite, so α0 = ω ≤ 0. Recursively, exponentiating ω with the n-th
obtained inequality, we get αn+1 = ωαn
≤ ω 0
= 0, so αn ≤ 0, for
each αn of the sequence defined above. Therefore, by the property of the
supremum, we obtain
ωω···
≤ 0.
Exercise Show that the axiom of choice is equivalent to the statement: every surjective
function f : X → Y has a right inverse.
Solution Assuming the axiom of choice, then we can choose a point xy ∈ Xy for
every fiber of f, and define a function by y → xy. This is clearly a right
inverse to f.
Conversely, consider a family of sets (Xi)i∈I, and the projection function
i∈I Xi → I. This is surjective, then by assumption it has a right inverse
c : I → i∈I Xi. Therefore, for every i ∈ I we have c(i) ∈ pi = Xi, so
this is a choice function.
Curiosities The axiom of choice has been proven to be independent of ZF set theory.
Therefore, both ZF +AC and ZF +¬AC are consistent theories (provided
ZF is). Both AC and its negation ¬AC have weird and counterintuitive
consequences, the most famous of which, assuming AC is Banach-Tarski
paradox: given a 3-dimensional full ball, there is a way of cutting it into
a finite number of pieces, and then reassemble these to form two spheres
identical in size to the original one.
Another statement which is equivalent to AC is:
– Every vector space has a basis.
On the contrary, assuming ¬AC, we have these fun facts:
15
– There is an infinite set X with no injection N → X;
– there is a set X and a partition of X such that there are more elements
in the partition than elements in the set;
– there are families of non-empty sets whose Cartesian product is empty;
– there are vector spaces with no basis;
– it is possible to express real numbers as a countable union of countable
sets;
– it is furthermore possible to express real numbers as a union of two
subsets of strictly smaller cardinality.
Week 8
Definition The cofinality of a cardinal κ is the minimum size of a set of cardinals
smaller than κ whose sum is κ, i.e.
cf(κ) = min{|I|, κ = i∈I λi with ∀i ∈ I, λi < κ}.
Definition Also remember, a cardinal κ is called regular if for every family of cardinals
(λi)i∈I such that λi < κ and |I| < κ, then
i∈I λi < κ.
Remark Obviously, for every cardinal we have cf(κ) ≤ κ, because κ 1 = κ. The
statement that κ is a regular cardinal is then equivalent to the statement
cf(κ) = κ.
Definition The sequence of ℵ numbers is recursively defined on ordinals:
– ℵ0 = ω;
– for an ordinal α, ℵα+1 = ℵ+
α ;
– for a limit ordinal γ, ℵγ = β<γ ℵβ.
Definition The sequence of numbers is recursively defined on ordinals:
– 0 = ω;
– for an ordinal α, α+1 = 2 α
;
– for a limit ordinal γ, γ = β<γ β.
Remark Cantor’s theorem states that we always have κ < 2κ
. Therefore, we also
always have ℵα ≤ α.
Remark With this notation, the continuum hypothesis states that ℵ1 = 1. In
particular, it is consistent with ZFC that 1 = ℵ+
0 . It is also consistent
that 1 = ℵ++
0 . In fact, for any finite number n, the statement
1 = ℵ+n
0 = ℵn
16
is consistent with ZFC.
Therefore, the statement that for every ordinal α and every natural number
n the equality
α = ℵα+n
holds is consistent with ZFC.
Remark Even more, given any cardinal κ, the following statement is consistent
with ZFC: there is a possibly infinite ordinal λ such that 2κ
= κ+λ
.
We can choose such an ordinal λ for each κ with some degree of liberty.
However, it has been proven that if we want to choose a single λ such that
the equality 2κ
= κ+λ
is true simultaneously for every cardinal κ, then λ
needs to be finite.
Remark The generalized continuum hypothesis can be reformulated as
∀α, ℵα = α.
Definition A cardinal κ is called a strong limit if whenever λ < κ then 2λ
< κ.
It is called a weak limit if whenever λ < κ then λ+
< κ.
Furthermore, κ is strongly inaccessible if it is regular and a strong limit,
it is weakly inaccessible if it is regular and a weak limit.
Remark Every, strong limit is clearly also a weak limit, and every strong inaccessible
is a weak inaccessible. Under GCH, the definitions of strong limit and
weak limit are equivalent, and the definitions of strongly inaccessible and
weakly inaccessible are likewise equivalent.
Exercise Show that, for each finite n, the cardinal ℵn is regular but, if n ≥ 1, it is
not a strong or weak limit. Further show that ℵω is a weak limit but not
regular. Decide if ℵω is a strong limit.
Solution We know that a finite sum of finite numbers is finite, which means that ℵ0
is regular. For any n, assume that we have a family of cardinals (λi)i∈I
with |I| ≤ ℵn and λi ≤ ℵn, therefore we can compute
i∈I λi ≤ i∈I ℵn = |I| × ℵn ≤ ℵn · ℵn = ℵn
which proves that ℵn+1 is regular.
For each n we have that ℵn < ℵn+1 but 2ℵn
≥ ℵ+
n = ℵn+1 so ℵn+1 is not
a weak or a strong limit.
ℵω is not regular because by its very definition n∈ω ℵn = ℵω.
Moreover, it is a weak limit because every cardinal smaller than ℵω is
either finite or of the form ℵn. It is obvious that both n + 1 < ℵω and
that ℵ+
n = ℵn+1 < ℵω.
In ZFC, it is not possible to prove that ℵω either is a strong limit or is
not such. Under GCH, for instance, it is obviously a strong limit because
strong limits coincide with weak limits. On the other hand, it is consistent
with ZFC that there is an n and and infinite λ such that 2ℵn
= ℵ+λ
n . In
this case, ℵn < ℵω, but 2ℵn
≥ ℵω.
17
Remark By transfinite induction, we can prove that it is always the case that
κ ≤ ℵκ, for an arbitrary cardinal κ.
Remark Whenever α is an initial ordinal (least with its cardinality) then we have
cf(ℵα) = α.
Exercise Show that an uncountable cardinal κ is weakly inaccessible if and only if
κ = ℵκ.
Solution Assume that κ = ℵκ. Then we have cf(κ) = cf(ℵκ) = κ so that κ is
regular. Take now a cardinal µ < κ, therefore µ < ℵκ, so that there is an
ordinal α < κ such that µ < ℵα. Therefore µ+
< ℵα+1 < ℵκ = κ.
Conversely, if κ is weakly inaccessible. Since κ ≤ ℵκ, we need to prove
the opposite inequality. We have ℵ0 < κ by hypothesis. Since κ is a weak
limit, for each ordinal α we also have that
ℵα < κ ⇒ ℵα+1 < κ.
Finally, for a limit ordinal λ < κ, by the previous step and regularity of κ
we deduce that
ℵλ < κ.
By definition of ℵ number associated to a limit ordinal, this implies that
ℵκ ≤ κ.
Remark The same reasoning yields that an uncountable cardinal κ is strongly inaccessible
if and only if κ = κ.
Remark There is a function, called the ℵ function, from the class of cardinals to
itself, defined by κ → ℵκ. A weakly inaccessible cardinal can be defined
as a fixed point of the ℵ function.
Similarly we can define strongly inaccessible cardinals as fixed points of
an analogously defined function.
Remark The existence of one inaccessible cardinal is independent of ZFC. Moreover,
the existence of λ+1 inaccessible cardinals is independent of ZFC +
“there are λ inaccessible cardinals”. Finally, the existence of a proper class
of inaccessible cardinals is independent of ZFC + “there are λ inaccessible
cardinals” for every λ.
Week 9
Exercise Show that, for a set x, we have rk(x) = sup{rk(z) + 1|z ∈ x}.
Solution Let α = sup{rk(z) + 1|z ∈ x}. This means in particular that for every
z ∈ x we have z ⊆ Vβ for some β such that β+1 ≤ α, which implies z ∈ Vα.
As a consequence, x ⊆ Vα, which means that rk(x) ≤ α. We want to show
that this is an equality. Suppose by contradition that rk(x) = γ < α. In
other words, x ⊆ Vγ. Then for each element z ∈ x we have z ∈ Vγ, which
contradicts the minimality of α. This proves that rk(x) = α, as desired.
18
Remark Another way to express this is: if ∃ max{rk(z)|z ∈ x} then rk(x) =
max{rk(z)|z ∈ x} + 1.
If that maximum doesn’t exist, then rk(x) = sup{rk(z)|z ∈ x}.
Exercise Prove by induction that |Vω+α| = α.
Solution For α = 0, notice that Vω is a countable union of finite sets, which is
bigger than any finite set, therefore |Vω| = ω = 0.
Now consider the isolated step, and assume by induction that |Vω+α| = α.
Then |Vω+α+1| = |P(Vω+α)| = 2|Vω+α|
= 2 α
= α+1.
Finally, if α is a limit ordinal, then
|Vω+α| = | β<α Vω+β| = β<α |Vω+β| = β<α β = α.
Exercise Conclude that if κ is an inaccessible cardinal, then |Vκ| = κ.
Solution We can regard a cardinal as an initial ordinal. Since κ is uncountable, we
have ω + κ = κ, thus the exercise above says
|Vκ| = |Vω+κ| = κ
but we know from last week that κ = κ, so we are done.
Exercise Show that, if x and y have rank ≤ α then {x, y}, x ∪ y, x, P(x), (x, y)
and xy
have rank < α + ω.
Solution {x, y} has rank ≤ α + 1 by the exercise above.
Next, for each element z ∈ x or z ∈ y we have z ∈ Vβ for some β ≤ α,
therefore, again by the same exercise above, we conclude rk(x∪y) ≤ α+1.
By x we mean the union of all sets y such that y ∈ x. Since rk(x) ≤ α,
we also have a fortiori rk(y) ≤ α and, for each element z ∈ y, rk(z) ≤ α.
Therefore rk( x) ≤ α. In fact, we even have rk( x) < rk(x).
If rk(x) = β ≤ α, then for each z ∈ x we have rk(z) ≤ β, so for each
subset y ⊆ x, by the exercise above we deduce rk(y) ≤ β + 1. Thus,
rk(P(x)) ≤ β + 2 ≤ α + 2.
We use the definition (x, y) = {x, {x, y}}. By the above reasoning, rk({x, y}) ≤
α + 1, so by the exercise above we have rk((x, y)) ≤ max{α + 1, α + 2} =
α + 2.
A function y → x is defined as a specific subset of y × x. Now, if y and x
have rank ≤ α, every element of them also has rank ≤ α, therefore by the
previous part a pair (y0, x0) where y0 ∈ y and x0 ∈ y has rank ≤ α + 2.
The above exercise implies that a function y → x, when regarded as a set,
has rank ≤ α+3. The set xy
of all functions y → x now has rank ≤ α+4.
19
Week 10
Definition The axiom schema of replacement says that for each formula φ containing
the variables x, t1, . . . , tn, y there is an axiom as follows
∀x∀y∀z (φ (x, t1, . . . , tn, y) ∧ φ (x, t1, . . . , tn, z) → y = z) →
∀X∃Y ∀y (y ∈ Y ↔ ∃x (x ∈ X ∧ φ (x, t1, . . . , tn, y)))
Intuition We should think of φ as a relation which depends on parameters t1, . . . , tn,
so for the sake of intuition we now abbreviate φ(x, t1, . . . , tn, y) by xRy.
Now what the first part of the above axiom is saying is that R is a binary
relation such that to each x there is at most one y which is in relation
with it. The second half of it says that if X is a set, then the elements y
that are associated to some element x ∈ X form themselves a set Y
One more layer of simplification is the following: if R is a function (wherever
it is defined) then the images of elements that range over a set X
form themselves a set Y .
The non-triviality of this axiom lies in the fact that, if R is a function,
its codomain is a priori the class of all sets, which is not a set. What the
axiom says is, in these terms, that the image of a set along a class function
is a set.
Definition A Grothendieck universe is a set U satisfying the following axioms:
1. X ∈ U and Y ∈ X implies Y ∈ U;
2. If X ∈ U, then also P(X) ∈ U;
3. If I ∈ U and (Xi)i∈I is an I-indexed family of sets in U, then
i∈I Xi ∈ U;
4. N ∈ U.
Remark If U is a Grothendieck universe and X ∈ U, then |X| < |U|. To see this,
simply use axiom 2 to see that P(X) ∈ U, then observe that by axiom 1
P(X) ⊆ U, therefore |X| < |P(X)| ≤ |U|.
Exercise Show that if X ∈ U and Y ⊆ X then Y ∈ U.
Solution We have Y ∈ P(X) ∈ U by axiom 2. Then we conclude by axiom 2.
Exercise Show that if µ < |U|, then there is a set X ∈ U such that |X| = µ.
Solution By the previous exercise and the fact that µ ≤ µ, it suffices to show that
there is a set Y ∈ U such that |Y | = µ. Let us proceed by induction on
µ.
If µ = 0, then the result follows by axiom 4.
Assume by induction that we have proven the result up to α, then there
is a set Yα ∈ U with cardinality α. By axiom 2, its power set belongs to
U and, moreover, it has cardinality α+1 by definition.
Now assume that λ is a limit ordinal, and that for each α < λ there is a set
20
Yα ∈ U with cardinality α. Assume that λ < λ (the proof when λ = λ
is much more complicated), so there is some α < λ such that λ < α.
By inductive hypothesis, there is a set Yα ∈ U with cardinality α, so by
the previous exercise there must be also a set I ∈ U with cardinality λ,
so that we can index a family (Yi)i∈I including all the sets of the form Yα
with α < λ. Now the union i∈I Yi belongs to U by axiom 3, and it is
equal to α<λ Yα, which has cardinality λ. This concludes the proof.
Exercise Show that, if U is a Grothendieck universe, then its cardinality is uncountable
and strongly inaccessible.
Solution By axiom 4, we have that N ∈ U, so the above remark implies that |N| <
|U|, which means that U is uncountable.
Let |I| < |U| and (Xi)i∈I a family of sets such that |Xi| < |U|. By
the previous exercise, we know that I, Xi ∈ U, therefore i∈I Xi ∈ U.
Again, we conclude by the same remark that the cardinality of this union
is strictly smaller than that of U. Thus, |U| is a regular cardinal.
Finally, if µ < |U|, choosing a set X such that |X| = µ, we have again
by the previous exercise that X ∈ U, so axiom 2 implies that P(X) ∈ U.
Once more, we use the same remark to compute 2µ
= |P(X)| < |U|.
Remark In particular, this implies that the existence of a Grothendieck universe is
not provable in ZFC.
Theorem [ZFC] If U is a Grothendieck universe, then it is a model of ZFC.
Proof This is essentially the same proof seen in the lecture to see that Vκ is
a model of ZFC when κ is inaccessible. In fact, we have the following
stronger result.
Proposition κ is an inaccessible cardinal if and only if Vκ is a Grothendieck universe.
Proof Observe that axioms 1
Tarski axiom Letting Univ(y) be an abbreviation for all five axioms that say that y is a
Grothendieck universe, then Tarski axiom can be formulate as follows
∀x∃y(x ∈ y ∧ Univ(y))
Definition Naturally, Tarski axiom is not provable in ZFC. We call TG the theory
having all axioms of ZFC + Tarski axiom.
Theorem [TG] ZFC is consistent.
Proof By Tarski axiom, there is a Grothendieck universe U. Then this is a model
of ZFC.
Week 11
Definition Recall that a set X is called transitive if ∀x we have x ∈ X ⇒ x ⊂ X.
Remark Observe that the ⊂ sign in the definition above can never become an =
sign, because that would contradict the axiom of regularity.
21
Definition Also recall that the transitive closure of a set X is the smallest set TC(X) ⊇
X which is transitive. It can be explicitly defined as follows: fix X0 = X
and then inductively
Xn+1 = Xn.
Then we have TC(X) = n∈N Xn.
• We recall one last definition:
Definition A set x is called symmetric is there is a finite set of atoms N(x) =
{a1, . . . , an} such that whenever we have a permutation f : A → A such
that ∀i = 1, . . . n, f(ai) = ai then the extension ˆf : WA
→ WA
satisfies
ˆf(x) = x.
We say that a set x is hereditarily symmetric if it is symmetric and every
element of TC(x) is symmetric.
Remark Observe that the definition of carrier of a set is ambiguous, because it
does not fix a single set N(x), rather it is based on the fact that such a
set exists. So we will slightly modify this definition for the moment.
Definition For a set x ∈ WA
, define Carr(x) ⊆ Pfin(A) to be the collection of all
carriers of x. They naturally form a poset via the inclusion relation. We
will say that a set is symmetric if it satisfies Carr(x) = ∅.
Exercise Prove the following:
1. Every set x ∈ V is hereditarily symmetric with carrier N(x) = ∅;
2. Every atom a ∈ A is hereditarily symmetric with carrier N(a) = {a};
Solution 1. Observe that if x ∈ V then we also have TC(x) ∈ V . Therefore, this
amounts to prove that for every set x ∈ V and every permutation
f : A → A we have ˆf(x) = x. Proceed inductively on bounded
stages of the universe of discourse V . For V0 = there is nothing
to prove, so we start at height 1. The restriction of f1 to V1 is
defined as follows: for x ∈ V1, we necessarily have x = ∅, therefore
f1(x) = {f0(y)|y ∈ x} = ∅ = x.
Now assume that the for all ordinals up to α we have fα(x) = x
whenever x ∈ V . Take x ∈ Vα+1 = P(Vα). For all y ∈ x, we have
y ∈ Vα, so by inductive hypothesis fα(y) = y. Therefore, we have,
by definition,
fα+1(x) = {fα(y)|y ∈ x} = {y|y ∈ x} = x.
Finally, if α is a limit ordinal and x ∈ Vα, then x ∈ Vβ for some β < α,
so the result is true by directly applying the inductive hypothesis.
2. Since atoms have no elements by definition, we have TC(a) = a.
Therefore, we only need to show that a is symmetric with carrier
N(a) = {a}. But this is obvious, since whenever f(a) = a, then
ˆf(a) = a by definition.
22
Exercise Give an example of a set that has two carriers C1 and C2 such that C1 ∩C2
is not a carrier.
Solution For example, consider the set of atoms A = {a, b, c, d}, and take x = {a, b}.
Now, if C1 = {a, b}, then it is obviously a carrier of x. On the other
hand, taking C2 = {c, d} also gives a carrier of x, because the only two
permutation that fix C2 are the identity and the transposition (a, b), and
in both cases ˆf({a, b}) = {a, b}.
Finally, we have C1 ∩ C2 = ∅ and this is not a carrier of x, because for
example if f is the cycle (a, b, c, d) then ˆf(x) = {b, c} = x.
Exercise Give an example of a set that is symmetric but not hereditarily symmetric.
Solution Let A be an infinite set containing a subset C such that both C and A\C
are infinite. Consider now P(A) ∈ WA
2 . This is clearly symmetric with
carrier ∅, because if f : A → A is a permutation, then the images along ˆf
of all subsets of A exhaust all subsets of A.
On the other hand C is an element of TC(P(A)), but this is not symmetric,
because both itself and its complement are infinite.
Exercise Give an example of a set that is not symmetric but all its elements are
symmetric.
Solution It suffices to take the set C from the exercise above.
Exercise Give an example of a set x such that TC(x) contains all the atoms, every
element of x is symmetric but x is not.
Solution Consider an infinite set A, and take as set of atoms the union of two
distinct copies A A. So we denote every element either as a1 or as a2.
Now, consider the set x = {{a1, a2}}a∈A. Every element of x is a finite set
of atoms, so it is symmetric having itself as a carrier. Moreover, we have
TC(x) = x ∪ (A A), which contains all the atoms. We need to show
that x is not symmetric.
Let C ⊆ A A be any finite subset, and select two elements a1, b1 /∈ C.
Define the permutation f : A A → A A as follows: on the first copy
of A, it is the identity; on the second copy of it, it is the transposition
(a, b). Now we have ˆf({b1, b2}) = {b1, a2}. This set is an element of ˆf(x),
but not an element of x, therefore ˆf(x) = x.
Week 12
Exercise Given a filter F ⊆ P(X), prove that F is an ultrafilter if and only if for
every finite union A =
n
i=1 Ai ⊆ X such that A ∈ F then we have Ai ∈ F
for at least one of the indices i.
Solution Assume that F is an ultrafilter, and by contradiction assume that there is
a finite union A ∈ F such that for every index i we have Ai /∈ F. By the
ultrafilter property, we have X \ Ai ∈ F. Therefore, since elements of a
filter are closed under finite intersection, we have X \A =
n
i=0(X \Ai) ∈
F. Thus, we also have ∅ = A ∩ (X \ A) ∈ F which is impossible because
every ultrafilter is proper.
23
Conversely, assume that F is a filter but not an ultrafilter. Then there
is a set A ⊆ X such that A /∈ F and X \ A /∈ F, but obviously we have
A ∪ (X \ A) = X ∈ F.
Definition The cofinite filter is that defined as {A ⊆ X|X \ A is finite }.
Exercise Show that any non-principal ultrafilter contains the cofinite filter.
Solution Let F be a non-principal ultrafilter, and let A ⊆ X be such that X \ A
is finite. Since F is an ultrafilter, it will suffice to show that X \ A /∈ F.
In other words, we need to show that F does not contain any finite set.
Since elements of F are closed under finite intersection, we are reduced to
show that for every x ∈ X, we have {x} /∈ F. Suppose by contradiction
that there is x ∈ X such that {x} ∈ F. Then every set containing {x}
is in F, and every set not containing it is not in F, because otherwise we
would have ∅ ∈ F. In other words, F is the principal ideal generated by
x, which contradicts our hypothesis.
Definition A two-valued measure µ on a set X is called λ-additive if for every set I
such that |I| < λ and every family (Ai)i∈I of pairwise disjoint subsets of
X, we have µ( i∈I Ai) = i∈I µ(Ai).
Example For a point x ∈ X, we can always define a two-valued λ-additive measure
on X given by µ(A) = 1 if and only if x ∈ A.
Definition An uncountable cardinal λ is called measurable if for every set of cardinality
λ it is possible to define a non-trivial two-valued λ-additive measure
on it.
• The next definitions and propositions give an idea of how large these
cardinals are.
Definition Let us give a definition which is recursive on ordinals. We call a cardinal
0-inaccessible if it is inaccessible. For an ordinal α > 0, we say that a
cardinal κ is α-inaccessible if it is inaccessible and for every ordinal β < α
the set of β-inaccessible cardinals < κ is unbounded.
We will say that a cardinal is hyperinaccessible if it is α-inaccessible for
every ordinal α.
Proposition Every measurable cardinal is hyperinaccessible.
Proposition Vopˇenka’s principle implies the existence of arbitrarily large measurable
cardinals.
Remark Vopˇenka’s principle is provably independent of ZFC + existence of measurable
cardinals. In fact, it implies the existence of supercompact cardinals,
which are a stronger version of strongly compact cardinals, but still much
weaker than Vopˇenka’s principle.
• Our final point will be to establish conditions under which Vopˇenka’s
principle can be satisfied.
Definition A model of a theory is transitive if it is transitive as a set, i.e. x ∈ y ∈ M
implies x ∈ M.
24
Definition Given two models of ZFC M1 and M2, a map h : M1 → M2 is called an
elementary embedding if for each formula φ(x1, . . . , xn) and any assignment
xi → ai with ai ∈ M1, we have that φ(a1, . . . , an) is true in M1 if
and only if φ(ha1, . . . , han) is true in M2.
Definition A cardinal λ is called huge if there exists a transitive model M of ZFC
and an elementary embedding h : V → M such that:
1. λ is the smallest ordinal such that h(λ) = λ;
2. M contains every function h(λ) → M.
• This definition is quite technical. We won’t be interested in all the details
that come with it, rather we only want to focus on the following point:
Proposition Suppose λ is a huge cardinal, then Wλ is a model of ZFC in which
Vopˇenka’s principle is true.
Remark This does not mean that the truthfulness of Vopˇenka’s principle follows
from the existence of huge cardinals. It only means that if there is a huge
cardinal, then we can find at least one model of ZFC in which the principle
holds true, i.e. it is consistent with ZFC.
25