Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 16F / b / i / Solution

A relation $r$ on a set $x$ is well-founded when every nonempty subset of $x$ has an $r$-minimal element. It is extensional when distinct elements have distinct predecessor sets:The Mostowski collapse theorem states that every well-founded extensional relation on a set is uniquely isomorphic to membership on a transitive set; the collapse is recursively

For the requested example, let $A=V_{\omega +1}$ and defineNo $x_n$ belongs to $A$, and thereforeThe map $x_n\mapsto n$ is an isomorphism from membership on $x$ to membership on the von Neumann ordinal $\omega$, so the Mostowski collapse is $\omega$. On the other hand, $x_0=V_{\omega +1}$ already has rank $\omega +1$, and hence the rank of $x$ is greater than $\omega$.

For statement (i), suppose $(x,r)$ is isomorphic to $(y,\in )$ with $y$ transitive. Membership is well-founded by the axiom of foundation. It is extensional on $y$ because transitivity ensures that the predecessors in $y$ of an element $a\in y$ are exactly the elements of $a$, and the axiom of extensionality distinguishes different sets. Both properties are preserved by isomorphism. Thus (i) is always true.

Solved by gpt-5.6-sol high.