5Set theory
II Logic and Set Theory
5.3 Picture of the universe
What does the universe look like? We start with the empty set, and take the
power set, repeatedly, transfinitely.
Definition (von Neumann hierarchy). Define sets
V
α
for
α ∈ On
(where
On
is
the class of ordinals) by ∈-recursion:
(i) V
0
= ∅.
(ii) V
α+1
= P(V
α
).
(iii) V
λ
=
S
{V
γ
: γ < λ} for λ a non-zero limit ordinal.
On
V
0
= ∅
V
1
= {∅}
V
7
.
.
.
.
.
.
V
ω
V
ω+1
.
.
.
.
.
.
V
ω+ω
.
.
.
.
.
.
Note that by definition, we have x ⊆ V
α
⇔ x ∈ V
α+1
.
We would like every
x
to be in some
V
α
, and that is indeed true. We prove
this though a series of lemmas:
Lemma. Each V
α
is transitive.
Proof.
Since we define
V
α
by recursion, it is sensible to prove this by induction:
By induction on α:
(i) Zero: V
0
= ∅ is transitive.
(ii)
Successors: If
x
is transitive, then so is
P
(
x
): given
y ∈ z ∈ P
(
x
), we want
to show that
y ∈ P
(
x
). Since
y
is in a member of
P
(
x
), i.e. a subset of
x
,
we must have y ∈ x. So y ⊆ x since x is transitive. So y ∈ P(x).
(iii) Limits: Any union of transitive sets is transitive.
Lemma. If α ≤ β, then V
α
⊆ V
β
.
Proof. Fix α, and induct on β.
(i) β = α: trivial
(ii)
Successors:
V
β
+
⊆ V
β
since
x ⊆ P
(
x
) for transitive
x
. So
V
α
⊆ V
β
⇒ V
α
⊆
V
β
+
.
(iii) Limits: Trivial by definition
Finally we are ready for:
Theorem. Every x belongs to some V
α
. Intuitively, we want to say
V =
[
α∈On
V
α
,
We’ll need some terminology to start with. If
x ⊆ V
α
for some
α
, then there
is a least α with x ⊆ V
α
. We call this the rank of x.
For example,
rank
(
∅
) = 0,
rank
(
{∅}
) = 1. Also
rank
(
ω
) =
ω
. In fact,
rank(α) = α for all α ∈ On.
Note that we want the least α such that x ⊆ V
α
, not x ∈ V
α
.
Proof. We’ll show that (∀x)(∃α)(x ∈ V
α
) by ∈-induction on x.
So we are allowed to assume that for each
y ∈ x
, we have
y ⊆ V
α
for some
α
.
So y ⊆ V
rank(y)
, or y ∈ V
rank(y)+1
.
Let
α
=
sup{
(
rank
(
y
)
+
:
y ∈ x}
. Then
y ∈ V
α
for every
y ∈ x
. So
x ⊆ V
α
.
Our definition of rank is easy to get wrong — it is easy to be off by of 1. So
the official definition is
Definition (Rank). The rank of a set x is defined recursively by
rank(x) = sup{(rank y)
+
: y ∈ x}.
Then the initial definition we had is now a proposition.
Proposition. rank(x) is the first α such that x ⊆ V
α
.