Past exam of the analytic topology and axiomatic set theory course of the University of Oxford / 2007 / B / 6

The transitive closure $\mathrm{TC}(a)$ is the least transitive set containing $a$ as a subset. Put $a_0=a$, $a_{n+1}=\bigcup a_n$ and defineRecursion and Replacement give the set of iterates, and Union gives its union. It contains $a=a_0$ as a subset. If $u\in v\in \mathrm{TC}(a)$, then $v\in a_n$ for some $n$, so $u\in a_{n+1}\subseteq \mathrm{TC}(a)$; hence it is transitive.

If $T$ is transitive with $a\subseteq T$, induction gives $a_n\subseteq T$ for every $n$, because $\bigcup T\subseteq T$. Therefore $\mathrm{TC}(a)\subseteq T$. This proves minimality and uniqueness. If the alternative convention asks for the least transitive set containing $a$ as an element, that set is $\mathrm{TC}(\{a\})$.

The membership induction principle is the schemaallowing fixed parameters in $\phi$.

Suppose the progressiveness hypothesis holds but $\neg \phi (a)$. The transitive set $T=\mathrm{TC}(\{a\})$ contains $a$. Separation gives the nonempty set $B=\{x\in T:\neg \phi (x)\}$. By Foundation choose $b\in B$ with $b\cap B=\varnothing$. Every $y\in b$ belongs to $T$ because it is a transitive set and cannot belong to $B$, so every such $y$ satisfies $\phi$. Progressiveness now gives $\phi (b)$, a contradiction. Thus the principle holds. The transitive closure is needed to turn a possibly proper class of counterexamples into a set to which Foundation applies.

An $\in$-isomorphism is a bijection $f:X\to Y$ such that $x\in x^{\prime }$ if and only if $f(x)\in f(x^{\prime })$ for all $x,x^{\prime }\in X$. When $Y$ is transitive, surjectivity gives the stronger recursive descriptionIndeed every member of $f(x)$ belongs to $Y$ because it is a transitive set and so has a preimage in $X$; the isomorphism property identifies exactly which preimages occur.

If $f,g$ are two such maps, possibly to different transitive sets, form $B=\{x\in X:f(x)\ne g(x)\}$. If $B$ were nonempty, Foundation would give $x\in B$ with $x\cap B=\varnothing$. All predecessors $u\in x\cap X$ then satisfy $f(u)=g(u)$, and the recursive descriptions force $f(x)=g(x)$, a contradiction. Therefore the map and its transitive range are unique.

The necessary and sufficient condition is that $⟨X,\in ⟩$ be well-founded and extensional as a relation on $X$. Well-foundedness says every nonempty $A\subseteq X$ has a member with no $\in$-predecessor in $A$. The extensional relation condition says distinct elements $x,x^{\prime }\in X$ have distinct predecessor sets $x\cap X$, $x^{\prime }\cap X$. Sufficiency is the Mostowski collapse theorem.

For necessity, an isomorphism transfers well-foundedness from its transitive range, where Foundation applies. For extensionality, if $x\cap X=x^{\prime }\cap X$, the recursive descriptions give $f(x)=f(x^{\prime })$, and injectivity gives $x=x^{\prime }$. Notice that ambient axiom of extensionality alone does not establish this internal predecessor condition; for example $X=\{\{0\},\{2\}\}$ can have distinct elements with no predecessors in $X$.