The cumulative hierarchy of pure sets

1. The cumulative hierarchy

Zermelo-Fraenkel set theory can be motivated by the idea of the cumulative hierarchy $V_{α}$ of pure sets. The intention here is to give some intuitive ideas of the hierarchy, to motivate later definitions. Later on we shall see how the hierarchy can actually be formally constructed inside axiomatic set theory.

A set is a pure set if all its elements are sets, and elements of those, and so on. The first problem to to decide where such sets come from. We imagine constructing sets, barehandedly. Initially we have no sets, which is not so good. We let $V_{0} = \{\}$ be the collection of all sets we have at this moment in time. $V_{0}$ is of course empty. But then we can make new sets by looking at it and its subsets. $V_{0} = \{\}$ is one such and the only subset of the empty set is the empty set, so this is the only such set. Therefore at this stage, the collection of all sets we have is $V_{1} = \{\{\}\}$ . At the next stage we have the set $V_{1}$ and its subsets, so that gives us the following collection of sets $V_{2} = \{\{\}, \{\{\}\}\}$ . This continues, and the next stage is more interesting. Our collection of sets is now the set of subsets of a two-element set, and is $V_{3} = \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}$ . At further stages we see that $V_{n + 1} = P (V_{n})$ , the power set of the previous level, so $V_{n + 1}$ has $2^{|V_{n}|}$ elements, so the size of $V_{n}$ grows pretty quickly with $n$ . We can also check that $V_{n} \subseteq V_{m}$ for $n ⩽ m$ .

But the construction need not stop there. We think of $ω$ as the next counting number after $0, 1, 2, 3, \dots$ and set $V_{ω} = ⋃_{i < ω} V_{i}$ , collecting together all sets constructed at finite stages, and then we can continue as before with $V_{ω + 1} = P (V_{ω})$ , $V_{ω + 2} = P (V_{ω + 1})$ , and so on. Then after these stages we can collect together all previous stages with $V_{ω + ω} = ⋃_{i < ω + ω} V_{i}$ , and continue.

The indices here are called ordinals. They are a kind of counting number that can be infinite (the word usually used is transfinite), and were invented by Cantor. We generally use lower case Greek letters $α, β, γ, \dots$ to denote ordinals. General addition, multiplication and exponentiation can be defined on ordinals and we will look at this theory later.

Thus, in this picture, ordinals control the way all sets are constructed. In other words it is a central tenet of Zermelo–Fraenkel that all sets occur in some $V_{α}$ for some ordinal $α$ , and this is something we will be able to prove from the axioms later.

2. Exercises

In these exercises you should argue informally, i.e. not from any particular set of axioms for set theory, but rather from the so-called naïve viewpoint of ordinal mathematics. Since implicitly the hierarchy is defined by induction on ordinals, you may not be able to prove all results here by induction until you have read about transfinite induction, i.e. the principle of induction on ordinals, in which case you should prove the results for all $V_{n}$ with $n < ω$ , and also for a few other specific transfinite ordinals such as $ω, ω + 1, \dots, ω + ω$ . Some exercises require a peek forward to other axioms or definitions that come later.

We will also look here at $V_{α}$ with the $\in$ relation as a first-order structure $(V_{α}, \in)$ for the language of set theory. Because this cumulative hierarchy is the basis of the conception of set it is important to investigate the axioms of set theory against this picture.

Exercise.

Prove that $V_{α}$ is finite for all $α < ω$ . (Use induction.)

Exercise.

Prove that $V_{ω}$ is infinite but doesn't contain any finite set.

Exercise.

Read ahead to find out what the axiom of infinity is. Show that $(V_{ω}, \in)$ does not satisfy the axiom of infinity.

Exercise.

Prove that $x \in y \in V_{α + 1}$ implies $x \in V_{α}$ for all $α ⩽ ω + ω$ .

Exercise.

Prove that, for all $α < ω + ω$ , $x \in V_{α}$ implies $x \subseteq V_{α}$ and hence $x \in V_{α + 1}$ .

Definition.

The rank of a set $x$ is the least $α$ such that $x \subseteq V_{α}$ .

Exercise.

Prove that for each $α < ω + ω$ and each non-empty $x \in V_{α}$ theree is $y \in x$ such that $y \cap x = \emptyset$ , i.e. that the axiom of foundation holds for the cumulative hierarchy as far as this.

Exercise.

Extend the last result by showing that $(V_{ω + ω}, \in)$ satisfies the axiom scheme of $\in$ -induction discussed in one of the other web pages in this set.

Exercise.

Let $T$ be the set of all first-order m $L_{\in}$ sentences true in $(V_{ω + ω}, \in)$ . Show that there is some $(W, ε)$ satisfying $T$ with $w_{i} \in W$ for $\in ℕ$ such that $w_{i +1} ε w_{i}$ for all $i$ . In other words, there is an infinite descending $ε$ -chain in $(W, ε)$ . (Add constants to the language and use compactness.) Deduce that the principle of there being no infinite descending $\in$ -chain is not first order.

Definition.

A transitive set is one, $x$ , such that $\forall u \forall v u \in v \land v \in x \to u \in x$ .

Exercise.

Find all transitive sets $x$ that is a member of $V_{4}$ .

Definition.

An ordinal is a transitive set $x$ such that the relation $u < v$ defined on all $u, v \in x$ by $u \in v$ is a linear order.

Exercise.

Find all the ordinals that are subsets of: $V_{n}$ for finite $n$ ; $V_{ω}$ ; $V_{ω + n}$ for finite $n$ ; and $V_{ω + ω}$ . State the rank of each such ordinal.