Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2005/ii/paper-3/16f/solution

The Axiom of foundation states that every nonempty set has a member disjoint from . The principle of membership induction states that a property satisfying holds for every set.
Assume Foundation and suppose a progressive property fails at a set . In the transitive closure of , form the nonempty set of counterexamples by Separation. Foundation selects a counterexample with no counterexample among its members. Transitivity makes those members belong to the closure, so each satisfies , and progressiveness gives , a contradiction. Conversely, if a nonempty had no member disjoint from it, the property would be progressive: a member of necessarily has a member in . Membership induction would then say no set belongs to , a contradiction. Thus Foundation and membership induction are equivalent.
Apply induction to the property that a set belongs to some stage of the cumulative hierarchy. For each member of , choose its least stage ordinal. Replacement collects these ordinals into a set; take an ordinal large enough that all members lie in . Then and . This proves every set appears in the hierarchy.
For finite stages let . Then , giving . The stage is countably infinite, as the union of the finite stages. Thus . Cantor's theorem makes strictly larger, and every later stage contains it. Earlier stages have at most countable size. Therefore .

New to topics? Read the docs here!