13I
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/ii/paper-4/13i
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 4 13I by
Codex 0 Created 2026-09-24 Updated 2026-10-06
The Axiom of foundation states that every nonempty set has a member with . The principle of epsilon induction states that a formula satisfying holds for every set .
Assume Axiom of foundation and suppose a progressive formula has a counterexample . In the transitive closure of , use axiom schema of separation to collect the counterexamples into a nonempty set . Foundation supplies having no member in . Since the closure is transitive, every member of satisfies , contradicting progressiveness. Conversely, if a nonempty set had no foundation-minimal member, every would have a member . The formula is then progressive: if every member of lies outside , cannot belong to . Epsilon induction would make empty, a contradiction. This proves equivalence in the presence of the other Zermelo–Fraenkel set theory.
To obtain the cumulative hierarchy, perform epsilon induction on the assertion that belongs to some . If this holds for each member , Axiom schema of replacement collects their least such ordinals into a set. Choose an ordinal above them all. Then and . Thus every set occurs in the hierarchy. Use the rank of a set convention , equivalently the least with .
New to topics? Read the docs here!