Zermelo’s 1908 system differs from ZFC in three respects. (1) ZFC is a “pure” set theory, without atoms. (2) ZFC includes two additional axioms, Replacement and Foundation. (3) ZFC is a first-order theory. Zermelo’s axioms are not formalized in this way. In this and the next two posts I will go into details.
Everything’s a Set!
In Zermelo’s original conception, we begin with a foundation of so-called atoms (aka urelements), things like the natural numbers. We then build up the universe by forming sets of atoms, sets of sets, etc. Later people realized that with various “coding tricks”, you don’t need any atoms. We’ve already encountered the von Neumann finite ordinals: 0=∅, 1={0}, 2={0,1}, etc. So these can serve for the natural numbers.
Zermelo had no ordered pairs. Kuratowski came up with this trick: define the ordered pair 〈x,y〉 to be the set {{x},{x,y}}. We can extract x and y from p=〈x,y〉={a,b} by noting that x is the only element of a∩b, and then y is the other element of a∪b, if a∪b has two elements. If a∪b has only one element, then of course y is that element. With Kuratowki’s ordered pairs on hand, we can deal with relations and functions without Zermelo’s awkward workarounds.
von Neumann defined ordinals by two properties. First:
A set X is transitive if b∈a∈X implies b∈X. Equivalently, if a∈X implies a⊆X.
Then:
An ordinal is a transitive set that is well-ordered under ∈.
We need transitivity, otherwise (for example) {5} would compete with {0} for the title of “1”.
I won’t go through the development of the ordinals in detail, but here are the first few steps. The precedessors of an ordinal are its elements: β<α iff β∈α. The successor of an ordinal α (denoted α+ in this post) is α∪{α}. If α is neither 0 nor a successor, it is a limit ordinal. By standard convention, λ always denotes a limit ordinal.
A finite ordinal (aka natural number) is defined as a non-limit ordinal (i.e., either a successor or 0), all of whose elements are also non-limit ordinals. If an ordinal is finite, so is its successor. The Axiom of Infinity says there is a set, say w, closed under α↦α+ and containing 0. Separation now says there is set, denoted ω, of all the finite ordinals in w. One proves that ω is the set of all finite ordinals.
Ω denotes the class of all ordinals. (Some authors use “On”.) Classes are not a formal part of ZFC, but we permit them as a “manner of speaking”. If φ(x) is a property of sets, we might talk about the class φ of all sets x satisfying φ(x), and write x∈φ to mean φ(x). For example, α∈Ω is just another way to say that α satisfies von Neumann’s two properties. We write V for the class of all sets, corresponding to the property x=x. Any set x is a class, corresponding to the property y∈x. A non-set class is called a proper class. After a fashion, proper classes are the descendents of Cantor’s “absolutely infinite multitudes”.
It is almost trivial to prove transfinite induction on Ω. Say φ(α) is a property of ordinals, and say we have this implication: If φ holds for all β<α, then it holds for α. Then φ holds for all ordinals. (Proof: If it doesn’t hold for α, then it doesn’t hold for some β<α. Since α is well-ordered, there is a least β<α for which it doesn’t hold. But then it holds for all γ<β, and hence for β.)
While Ω isn’t a well-ordered set, it shares enough properties to call it (informally) a well-ordered class. Namely, the ordinals are simply ordered: we will prove this in a later post. Any property φ of ordinals has a least ordinal satisfying it.
Definitions by transfinite recursion take a bit more fussing. I’ll leave the details to the textbooks, but basically: we have a “rule” determining a value sα whenever we are given all the values sβ with β<α. How are we given all these values? By a function fα with domain α, so fα(β)=sβ for all β<α. The “rule” is a predicate with two free variables, say ρ(x,y); we want ρ(fα,sα) to hold. The rule ρ should be “function-like”, i.e., for every x there is a unique y such that ρ(x,y) holds. You drop the function fα into the input hopper of ρ, and out pops a value sα. (If you’re wondering how s0 gets assigned, for α=0 the function is the empty function f0=∅.)
Using transfinite induction, one can show that for every α∈Ω there is a unique function gα with domain α+=α∪{α} that “obeys the recursion”. That is, for every β≤α, if fβ is the restriction of gα to β, then ρ(fβ,gα(β)). We say that we’ve defined gα by transfinite recursion up to and including the ordinal α.
Thus we have a function gα, with domain α+, for every ordinal α. For any β<α, gβ is the restriction of gα to β′. We can’t formally define a function with domain Ω, but we do have a “function-like” predicate γ(x,y) with “domain” Ω: γ(α,sα) holds if and only if gα(α)=sα.
Now that we have pairs, functions, and ordinals, we can populate our universe with all the usual flora and fauna. ℕ is the same as ω. The standard rigamarole then constructs integers, rationals, reals, Hilbert spaces,…
What about cardinalities? Frege and Russell both proposed “The cardinality of M is the set of all sets equivalent to M.” But a more elaborate version of Russell’s paradox kills this approach. Informally, we can talk about the class of all sets equivalent to M. We need to pick a representative from each such class.
von Neumann proposed: the first ordinal in the class. ℵ0 is just ω. ℵ1 is the first uncountable ordinal. 2ℵ0 is whichever ordinal is the first one with cardinality c. The cardinality of M is thus the unique smallest ordinal μ such that M is equivalent to μ.
All this assumes that for any M, there is an ordinal equivalent to it. That follows from the well-ordering theorem, which uses the Axiom of Choice. If AC isn’t around, then you need a different idea. We’ll see one later.
Diagonal Argument 