 Solution

The epsilon-recursion theorem says that for every definable operation $G$ assigning a set $G(x,h)$ to each set $x$ and each function $h$ with domain $x$, there is a unique class function $F$ such thatfor every set $x$.

For uniqueness, suppose $F$ and $F^{\prime }$ both satisfy the recursion. If they agree on every $y\in x$, then their restrictions to $x$ agree and henceThe epsilon induction principle therefore gives $F=F^{\prime }$.

For existence, call a function $f$ coherent on a transitive set $T$ whenThe same epsilon-induction argument shows that any two coherent functions agree on the intersection of their transitive domains. Assuming coherent functions have been constructed below every member of $x$, their compatible union defines all values below $x$; adjoining the value prescribed by $G(x,\cdot )$ extends the construction to $x$. Epsilon induction establishes this construction for every $x$. The compatible local functions therefore unite to the required class function $F$.

A relation $r$ on $x$ is well-founded when every nonempty subset of $x$ has an element with no $r$-predecessor in that subset. It is extensional when

The Mostowski collapse theorem states that every well-founded extensional relation $(x,r)$ is isomorphic to membership on a unique transitive set $M$. Define recursivelyWell-founded recursion makes $\pi$ well defined. Epsilon-style induction along $r$, together with extensionality, shows that $\pi$ is injective. By definition,so $\pi$ is an isomorphism from $(x,r)$ onto $(M,\in )$, where $M=\mathrm{ran}\pi$. If $z\in \pi (a)\in M$, then $z=\pi (b)$ for some $bra$, so $z\in M$; hence $M$ is transitive. If another collapse ${\pi }^{\prime }$ has transitive range, induction gives ${\pi }^{\prime }(a)=\{{\pi }^{\prime }(b):bra\}=\pi (a)$, proving uniqueness.

Finally, suppose $x$ is finite. Its collapse $M$ is a finite transitive set, so every member of $M$ is hereditarily finite. Therefore every well-founded extensional relation on $x$ collapses to a transitive subset of $V_{\omega }$.

Conversely, let $x$ be infinite. Choose the initial infinite ordinal $\kappa$ equinumerous with $x$. The successor ordinal $\kappa +1$ has the same cardinality as $\kappa$. Pulling its membership relation back along a bijection $x\to \kappa +1$ gives a well-founded extensional relation on $x$ whose collapse is $\kappa +1$. But $\kappa \in \kappa +1$ is not hereditarily finite, so $\kappa +1⊈V_{\omega }$. Consequently,