Zermelo-Fraenkel set theory can be motivated by the idea of the cumulative hierarchy 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 be the collection of
all sets we have at this moment in time. is of course empty.
But then we can make new sets by looking at it and its subsets.
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 .
At the next stage we have the set and its subsets, so
that gives us the following collection of sets
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 . At further stages we see that ,
the power set of the previous level, so
so the size of grows pretty quickly with . We
can also check that for
But the construction need not stop there. We think of as the next counting number after and set , collecting together all sets constructed at finite stages, and then we can continue as before with , , and so on. Then after these stages we can collect together all previous stages with , 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
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
In other words it is a central tenet of Zermelo–Fraenkel that all sets
occur in some for some ordinal , and this
is something we will be able to prove from the axioms later.
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 with , and also for a few other specific transfinite ordinals such as . Some exercises require a peek forward to other axioms or definitions that come later.
We will also look here at with the relation as a first-order structure 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.
Prove that is finite for all . (Use induction.)
Prove that is infinite but doesn't contain any finite set.
Read ahead to find out what the axiom of infinity is. Show that does not satisfy the axiom of infinity.
Prove that implies for all .
Prove that, for all , implies and hence .
The rank of a set is the least such that .
Prove that for each and each non-empty theree is such that , i.e. that the axiom of foundation holds for the cumulative hierarchy as far as this.
Extend the last result by showing that satisfies the axiom scheme of -induction discussed in one of the other web pages in this set.
Let be the set of all first-order m sentences true in . Show that there is some satisfying with for such that for all . In other words, there is an infinite descending -chain in . (Add constants to the language and use compactness.) Deduce that the principle of there being no infinite descending -chain is not first order.
A transitive set is one, , such that .
Find all transitive sets that is a member of .
An ordinal is a transitive set such that the relation defined on all by is a linear order.
Find all the ordinals that are subsets of: for finite ; ; for finite ; and . State the rank of each such ordinal.