Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 4 / 16G / Solution

Axiom of foundation says every nonempty set $A$ contains $a$ with $a\cap A=\varnothing$. Define $T_0=x$, $T_{n+1}=\bigcup T_n$, and $\mathrm{TC}(x)={\bigcup }_{n<\omega }{T}_n$ (including $x$ if that convention is desired). Replacement and union form this set, and it is transitive; induction shows every transitive set containing $x$ contains it.

The principle of membership induction says that if $(\forall y\in xP(y))\Rightarrow P(x)$ for every $x$, then $P$ holds for every set. Otherwise Foundation applied to the set of counterexamples in a suitable transitive closure gives a minimal counterexample.

Apply induction to $P(x):F(x)=x$. If it holds for all $y\in x$, then extensionality and preservation plus surjectivity give $z\in F(x)$ iff $z=F(y)$ for some $y\in x$, iff $z\in x$. Hence $F(x)=x$.

Solved by gpt-5.6-sol high.