Earlier, we stated the principle of epsilon-induction.

**Axiom Scheme of $\in $-Induction:** For all first order formulas
$\varphi (x,\stackrel{\_}{a})$ of the language ${L}_{\in}$,
$\forall \stackrel{\_}{a}\u200a(\forall x\u200a(\forall y\in x\u200a\varphi \left(y\right)\to \varphi (x\left)\right)\to \forall x\u200a\varphi (x,\stackrel{\_}{a}))$.

Instead of adopting this as an axiom scheme, we followed most authors in adopting only a special case of it, the Axiom of Foundation.

**Axiom of Foundation:**
$\forall x\u200a(\exists y\u200ay\in x\to \exists y\u200a(y\in x\wedge \neg \exists z\u200a(z\in x\wedge z\in y)))$.

It is time to show that with the axiom of foundation (and the other axioms, nortably replacement and the axiom of infinity) we can derive the principle of epsilon-induction.

Proposition.

The axiom scheme of $\in $-Induction follows from the axiom of foundation and other axioms of set theory.

**Proof.**

Suppose $\forall x\u200a\left(\forall y\in x\u200a\varphi \right(y)\to \varphi (x\left)\right)$ and $a$ is a set. We want to show $\varphi \left(a\right)$. Let $b$ be a transitive set containing $a$. (The existence of such transitive sets was proved from Infinitity and Replacement.) Let $c=\{x\in b:\neg \varphi \left(x\right)\}$. If $c$ were nonempty then by foundation let $x\in c$ with $x\cap c=\varnothing $. So for every $y\in x$ we have $y\in b$ since $x\in c\subseteq b$ and $b$ is transitive, and hence $y\notin c$. It follows from $x\cap c=\varnothing $ and $y\in b$ that $\varphi \left(y\right)$. Therefore $\forall y\in x\u200a\varphi \left(y\right)$ and hence $\varphi \left(x\right)$ contradicting $x\in c$. Therefore $c$ is empty and $\forall x\in b\u200a\varphi \left(x\right)$ and in particular $\varphi \left(a\right)$, as required.

Just as for the integers, $\in $-induction wouldn't be so useful if it didn't go hand-in-hand with a principle of recursion.

Theorem.

Suppose $\psi (x,y,z,\stackrel{\_}{a})$ is a first order formula and $\forall x\u200a\forall y\u200a\exists !z\u200a\psi (x,y,z,\stackrel{\_}{a})$. Then there is a formula $\theta (x,y,\stackrel{\_}{a})$ such that $\forall x\u200a\exists !y\u200a\theta (x,y,\stackrel{\_}{a})$ and for all $x$ and $f=\{\u27e8u,v\u27e9:u\in x\wedge \theta (u,v,\stackrel{\_}{a})\}$ with $\psi (x,f,y,\stackrel{\_}{a})$ we have $\theta (x,z,\stackrel{\_}{a})$.

In other words, given a class function $G$ we can define a new class function $F$ by $F\left(x\right)=G(\{\u27e8u,F\left(u\right)\u27e9:u\in x\},x)$. The proof is similar to the previous recursion theorem.

**Proof.**

Define an *attempt* to be a set function $f$
with transitive domain $dom\left(f\right)$ such that for all
$x\in dom\left(f\right)$ we have
$f\left(x\right)=G(\{\u27e8u,f\left(u\right)\u27e9:u\in x\},x)$.
where $G(r,s)$ is the unique $t$ such that
$\psi (r,s,t,\stackrel{\_}{a})$.

We just need to prove now by $\in $-induction that: (A) if $f,g$ are attempts and $x\in dom\left(f\right)\cap dom\left(g\right)$ then $f\left(x\right)=g\left(x\right)$; and (B) for all $x$ there is an attempt $f$ with $x\in dom\left(f\right)$. This is straightforward.