Motivation
Ordinal recursion works because each stage has a well-ordered collection of predecessors. Many constructions have a different dependency pattern: an object can depend on several earlier objects without those objects lying in one linear order. A finite expression tree is an elementary example. The correct requirement is that every nonempty collection of unfinished objects contains one whose dependencies are already outside that collection.
Set membership provides the most important instance. Foundation says that a nonempty set contains a member with no predecessor inside it. This lets us assign every set an ordinal height, its rank. Before doing that, we prove the general recursion principle that makes such assignments legitimate. The same principle turns an abstract well-founded, extensional relation into actual membership on a transitive set. The collapse and rank constructions therefore express two complementary ideas: recover a canonical set from its predecessor structure, and measure how far that structure extends downward.
Definitions
Definition 1.2.1
(Well-founded and extensional relations)
Let be a relation on a set. Write when is an immediate predecessor of , and . The relation is well-founded if every nonempty contains an with . It is extensional if implies .
Definition 1.2.2
(Downward closure)
A set is downward closed if implies . Let contain and all objects reached by following finitely many predecessor steps. Explicitly start with , put , and take . Replacement and union make this a set; it is the least downward-closed subset containing .
Definition 1.2.3
(Transitive sets and the cumulative hierarchy)
A set is transitive if implies . The cumulative hierarchy is defined by , and at nonzero limits. The ordinal chapter proved set-length transfinite recursion and checked that these stages are transitive and increasing.
In the present chapter all relations are on sets. General recursion on proper classes requires additional set-likeness hypotheses and is not being silently included.
Theorem/proposition
Theorem 1.2.4
(Well-founded induction and recursion)
For a well-founded relation on a set , if a formula holds at whenever it holds at every , then it holds throughout . Moreover, suppose a definable rule assigns a unique set whenever and is a function on . There is exactly one function on satisfying
No axiom of choice is needed. The unique-value condition and replacement, rather than arbitrary simultaneous selection, collect the recursive data.
Theorem 1.2.5
(Mostowski collapse for a set relation)
If on is well-founded and extensional, there are a unique transitive set and a unique isomorphism . They are given by
An isomorphism here is a bijection satisfying . Extensionality is essential for injectivity; well-foundedness is essential for the recursive construction.
Concept lensStructural
The collapse as a complete invariant
For well-founded extensional relations, exactly when their collapses have the same range. If is an isomorphism, is an isomorphism of onto the transitive set , so uniqueness gives and equal ranges. Conversely, equal ranges give the isomorphism . Since a transitive set with membership is its own collapse, such structures correspond, up to isomorphism, exactly to transitive sets.
Theorem 1.2.6
(Rank and the cumulative hierarchy)
In ZF every set has a uniquely determined ordinal rank
For every ordinal ,
Consequently every set belongs to some hierarchy stage. This does not make the entire universe or the whole hierarchy a set.
Proof sketch or proof idea
Proof
(Minimal counterexamples and admissible points)
Induction follows by separation: a nonempty set of counterexamples would have an -minimal member, contradicting the hypothesis. The argument does not require a linear order or an immediate predecessor for every nonminimal point.
Here is a set-existence proof of recursion. A good partial function has a downward-closed domain and satisfies the required equation there. Two good functions agree on their common domain. Otherwise the set of their disagreements has an -minimal member, whose predecessor restrictions agree, forcing the next values to agree as well.
Call admissible if a good function exists on . Such a function is unique by the preceding compatibility argument. If there were a nonempty set of nonadmissible points, take an -minimal one, . Each is admissible. Replacement therefore collects the unique good functions on the sets ; no choice of witnesses is required. Their union is a compatible good function on . This domain contains every predecessor of and does not contain , since a finite return path would contradict well-foundedness. Add the uniquely specified value at . The new domain is exactly , contradicting nonadmissibility. All points are therefore admissible. Replacement collects their unique local values into a function on , and compatibility proves its equation and uniqueness.
Proof X-ray
Compatibility does not replace collection
At a minimal bad point in the recursion proof, compatibility guarantees that local graphs agree where they overlap. Replacement separately guarantees that these uniquely determined graphs form a set indexed by the predecessor set. Only then may their union be formed. This is the same two-part check used at ordinal limits, now applied to a nonlinearly ordered dependency structure.
Proof
(Predecessor images and injectivity)
For collapse, apply recursion to . Replacement makes this image a set. The range is transitive because every element of is some with . We still need injectivity: equal sets of predecessor images need not identify their original labels without an argument.
Induct on to prove that implies for every . Assume the assertion for every , and suppose . For , membership in gives with ; the induction hypothesis at gives . Conversely, for , equality of the image sets supplies with , and the same hypothesis gives . Thus , and extensionality yields . Injectivity now makes an isomorphism onto . If another isomorphism has transitive range, every member of its image of is the image of a predecessor, so it satisfies the same recursion. Recursion uniqueness identifies both maps and their ranges.
Proof X-ray
Why the injectivity induction carries a universal quantifier
The induction runs on alone, but the statement carried along is “ implies for every ”. Nothing is known about the partner , so the hypothesis at each must already cover every possible partner . Equality of images matches predecessors in both directions, the hypothesis turns each match into equality of labels, and extensionality, used exactly once, turns equal predecessor sets into . Well-foundedness enters only through the induction itself.
Proof
(Rank by recursion on a transitive bound)
For rank, fix a set . Starting with and repeatedly adjoining unions gives a transitive set containing . Foundation makes membership restricted to well-founded: apply it to any nonempty subset of . Recursion on this set relation assigns . Induction shows that all values are ordinals; the formula is then precisely . Two transitive sets containing give the same value, because their recursive functions agree on their downward-closed intersection. This defines independently of the chosen bound.
Prove the hierarchy formula by transfinite induction on . It is immediate at zero. At a successor,
The last equivalence follows by taking the supremum of the successor ranks, and also holds for an empty . At a nonzero limit, membership in the union means membership at some earlier stage. This is equivalent to rank below the limit, because a successor of any smaller ordinal is still below that limit. The subset formula follows from the successor case. In particular . The union over all ordinal stages is class notation, not a permitted set-indexed union.
Worked examples
Worked example 1.2.7
(A collapse need not be an ordinal)
Take three distinct labels and the relation , , with no other pairs. It is well-founded and extensional. The collapse is , and . Its transitive range is , which is not an ordinal: its members and are incomparable by membership, and the relation is not transitive. A collapse produces a transitive set, not automatically a linearly ordered transitive set.
Counterexample mode
Dropping either collapse hypothesis
Claim: every well-founded relation on a set, or every extensional one, is isomorphic to membership on a transitive set. For two distinct isolated labels, the relation is well-founded but not extensional: both predecessor sets are empty. The recursion sends both to , so it is not injective. For one label with a self-loop, the relation is extensional but not well-founded. A collapse would require , hence , contrary to foundation. The two examples isolate different failures, rather than treating the hypotheses as interchangeable.
Worked example 1.2.8
(Rank is not the number of members)
The empty set has rank zero, and . Every finite ordinal has rank , and transfinite induction gives for every ordinal, since . Thus has rank , while its singleton has rank . A singleton can have arbitrarily large rank despite always containing only one element. Rank measures membership depth, not cardinality.
Worked example 1.2.9
(A set's first containing stage is one step later)
Let , the ordinal two. Its rank is two, so but ; its first containing stage is . For the Kuratowski pair , the singleton and pair formulas give
The two added successor stages come from the two layers of braces, including when . Keeping membership distinct from inclusion prevents an off-by-one error in both calculations.
Worked example 1.2.10
(Infinite height without an infinite descent)
Take with . On natural numbers put exactly when , and put for every natural . The relation is well-founded: a nonempty subset meeting has a least natural member; a subset not meeting it consists only of . Its collapse sends to and to .
Every downward path from first chooses a finite natural number and then decreases among natural numbers, so it cannot continue infinitely. Nevertheless finite downward paths have no uniform length bound. The collapsed set at has rank , not a finite rank. Thus absence of an infinite descending path does not force finite height. Rank uses the supremum of all predecessor heights, and infinitely many individually finite heights can have a limit supremum. This example also explains why evaluating a few finite dependency diagrams is not a proof of the general recursion theorem.
Common mistakes
Common mistake
(Replacing well-foundedness by “no descending sequence”)
“No infinite descending sequence” should not silently replace the subset definition of well-foundedness in a ZF proof. A given infinite descending sequence contradicts well-foundedness by taking its range. Constructing such a sequence from a collection where every point has some predecessor can require a dependent-choice principle. The minimal-counterexample definition avoids that hidden selection step.
Common mistake
(Extensionality concerns predecessor sets)
Extensionality of concerns predecessor sets inside . It is not ordinary equality of labels, and is not a statement that is transitive. Also, rank depends on foundation in this development; it cannot be assigned by the same argument to arbitrary circular membership structures.
Summary
Well-founded recursion resolves set-sized dependency graphs with uniquely specified outputs. Extensionality makes predecessor-image recursion injective, producing the Mostowski collapse. Foundation and transitive closure then assign each set a rank, and the hierarchy formula identifies exactly when it enters the cumulative hierarchy.
Exercises
Quick check
(A four-point collapse)
Collapse a relation on with predecessor sets , , and , respectively. Is its range an ordinal?
Solution · Answer
The images are , , and , in that order. The range is transitive because every member of each displayed set occurs among the images. It is not an ordinal: and remain incomparable. The distinct predecessor sets and the displayed acyclic dependency graph verify the hypotheses.
Quick check
(Rank under membership and inclusion)
Prove implies . Does imply strict inequality?
Solution · Answer
The defining supremum is at least , proving strictness. Inclusion instead gives only , by comparing the two families of successor ranks. It need not be strict even for a proper subset: the even natural numbers form a proper subset of and also have rank , since their finite successor ranks are unbounded in .
Quick check
(The rank of a union)
Prove , including empty sets, and deduce an upper bound in terms of .
Solution
Expand the two suprema:
Empty suprema are zero, so the formula includes and empty members. Since each rank on the right is bounded by , the union rank is at most that rank. It may be smaller: has rank one but its union has rank zero.
Quick check
(Isomorphisms without extensionality)
Explain why a two-label relation with no edges can have many isomorphisms to sets equipped with restricted membership, although the collapse recursion has only one possible output at each label.
Solution · Answer
A suitable target is , where : neither member belongs to the other and neither belongs to itself. In particular, the only member of is , which differs from . Its two labels can be assigned bijectively in either order, giving two isomorphisms of the empty relation. This is not transitive. The collapse theorem requires a transitive range and extensional source relation; the empty two-label relation fails extensionality, and its recursion sends both labels to zero instead of a bijection.