Replacement and Foundation
Thirteen years after Zermelo published his axioms, Fraenkel pointed out that they weren’t quite strong enough. For example, you couldn’t prove the existence of the set ⋃n∈ω𝒫n(0).
Fraenkel suggest the Axiom of Replacement (aka Substitution): If we have a way of “associating” with every element m of a set M a set Xm, then {Xm:m∈M} is a set. In other words, if you go through a set, replacing each element with another set, you get a set. The intuition: {Xm:m∈M} is “no bigger” than M, and so ought to be a set also.
Combined with Axiom of Unions, this is the gateway to big sets. Replacement gives us {𝒫n(0):n∈ω}, and then Union gives us Fraenkel’s set.
Zermelo agreed with Fraenkel for this addition to the axioms. Skolem also pointed out the need.
Using transfinite recursion, we now define the Cumulative Hierarchy:
| V0 | = ∅ |
| Vα+1 | = Vα∪𝒫(Vα) |
| Vλ | = ⋃α<λ Vα |
Fraenkel’s set is Vω.
(Two variations: it turns out that “Vα∪’’ isn’t neeeded in the second line, you get the same sets with “Vα+1=𝒫(Vα)’’. Some authors modify the definition so that their Vλ is the same as our Vλ+1.)
Power Set plus Replacement plus Union shows that all the Vα are sets. The rank of a set is where it first appears in the cumulative hierarchy, or more precisely: rk(X) is the least α with X∈Vα+1. The “+1’’ is so that α has rank α.
How do we know that every set appears somewhere in the cumulative hierarchy? That brings us to our second additional axiom: Foundation.
Skolem noticed the need to exclude “pathological” sets, such as A={A} or infinite descending chains A1∋A2∋…. Such sets will never appear in any of the Vα’s. The Foundation Axiom does the trick.
von Neumann gave the most elegant version of Foundation: Every nonempty set contains an element disjoint from it. That is, for any set A, there is an a∈A with a∩A=∅. This a is minimal in the ∈ ordering of the elements of M. That’s another way to phrase it: Every nonempty set A has a minimal element in its ∈-ordering.
Foundation is equivalent to every set having a rank. Writing this the classy way, V=⋃α∈ΩVα. The proof of this takes a few steps; I’ll save it for the end of this post.
For so-called “ordinary mathematics”, you usually don’t need to go any higher than rank ω2. Example: the complex Hilbert space L2(ℝ3), beloved by analysts and physicists alike. We build up to this by contructing all the natural numbers, then the integers, rational numbers, and reals, ordered pairs and ordered triples of reals, then functions from the ordered triples to ordered pairs, and finally equivalence classes of these functions. (Recall that two L2 functions are identified if they agree except for a set of measure zero; hence, the actual elements of L2(ℝ3) are equivalence classes.) We have all the natural numbers by the time we get to Vω. If x,y∈Vα, then the ordered pair 〈x,y〉∈Vα+2. So if A∈Vα, then any subset of A×A is in Vα+3. Integers are often defined as sets of ordered pairs of natural numbers, rational numbers as sets of ordered pairs of integers, and real numbers as sets of rational numbers (Dedekind cuts). If I counted right, that puts all the elements of ℝ in Vω+7 and any subset of ℝ in Vω+8. The Hilbert space in question should belong to Vω+15, again if I haven’t miscounted.
Although sets of high rank aren’t “needed” by most mathematicians, it would be quite strange to impose a “rank ceiling” limitation on the power set axiom. Just maybe if Vω+1 were adequate—but it isn’t.
Without Choice, we cannot use von Neumann’s definition of card(M) as the least ordinal equivalent to M. An alternative is Scott’s trick: card(M) is the set of all sets of least rank equivalent to M. In other words, S∈card(M) iff S≡M and for all T≡M, rk(T)≥rk(S). This lacks the simplicity of von Neumann’s definition, but it’s the best we’ve got. Scott’s trick can be used for other purposes, e.g., to define the order type of a simply-ordered set.
Okay, let’s look at the equivalence of Foundation with V=⋃α∈ΩVα. We’ll need some machinery: transitive closures, ∈-induction, and the suprenum of a set of ordinals.
Recall that a set A is transitive if b∈a∈A implies b∈A, i.e., a∈A implies a⊆A. Every set A is contained in a transitive set called its transitive closure, tc(A). First we set f(A)=⋃a∈Aa. Then set tc(A)=⋃n∈ωfn(A), where f0(A)=A. The transitive closure is the smallest transitive set containing A: A⊆tc(A), and if A⊆B with B transitive, then tc(A)⊆B.
Suppose φ is a property where the following implication holds: If every element of A satisfies φ, then so does A. Then ∈-induction says that φ holds for all sets. Foundation justifies this. Suppose on the contrary that A is a non-φ set. Then some element of A is non-φ. Consider the subset S of tc(A) consisting of all non-φ elements. This is nonempty by hypothesis, so let s∈S be ∈-minimal in S. All the elements of s belong to tc(A) because tc(A) is transitive, so therefore all of s’s elements must satisfy φ (otherwise s wouldn’t be ∈-minimal). But then s must also satisfy φ, contradiction.
Lemma: If S is a set of ordinals, then ⋃α∈Sα is an ordinal. This is a set by the Union Axiom. That S is simply-ordered under ∈ is easy as pie. Foundation makes the proof of the well-ordering property trivial, though it’s not hard to prove without it. For ordinals, α⊆β is equivalent to α≤β (we’ll prove this in a later post), so S is an upper bound to all its elements. As usual, we call the least uppper bound to S its suprenum, denoted sup S.
Now suppose X is a set, and we associate an ordinal αx with each x∈X. Replacement says that {αx:x∈X} is a set; we denote its suprenum by supx∈Xαx.
Time to prove that every set has a rank. We use ∈-induction. Suppose all the elements of A have ranks. Set α=supa∈A(rk(a)+1). As a∈A belongs to Vrk(a)+1 and Vβ⊆Vα whenever β≤α, all the elements of A belong to Vα. Therefore A belongs to Vα+1.
The reverse implication is straightforward, given this fact about rank: a∈b implies rk(a)<rk(b). (Proof: transfinite induction.) It follows that an element of A of lowest rank is ∈-minimal in A.
Diagonal Argument 