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

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.

Statement (ii) is always true even when $y$ is not transitive. Given a nonempty subset $z\subseteq y$, the Axiom of foundation supplies $a\in z$ with $a\cap z=\varnothing$. Thus no member of $z$ is a member of $a$, so $a$ is minimal for membership restricted to $y$. An isomorphic relation $r$ is therefore well-founded.

Statement (iii) can fail because a nontransitive ambient set can omit the elements that distinguish two of its members. TakeNeither element of $y$ has an element that also lies in $y$: the second contains $\{\varnothing \}$, which is omitted. Their predecessor sets for membership restricted to $y$ are therefore both empty, although the two elements are distinct. Hence this restricted membership relation, and any isomorphic relation, is not extensional.