Earlier, we stated the principle of epsilon-induction.
Axiom Scheme of -Induction: For all first order formulas of the language , .
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: .
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.
The axiom scheme of -Induction follows from the axiom of foundation and other axioms of set theory.
Suppose and is a set. We want to show . Let be a transitive set containing . (The existence of such transitive sets was proved from Infinitity and Replacement.) Let . If were nonempty then by foundation let with . So for every we have since and is transitive, and hence . It follows from and that . Therefore and hence contradicting . Therefore is empty and and in particular , as required.
Just as for the integers, -induction wouldn't be so useful if it didn't go hand-in-hand with a principle of recursion.
Suppose is a first order formula and . Then there is a formula such that and for all and with we have .
In other words, given a class function we can define a new class function by . The proof is similar to the previous recursion theorem.
Define an attempt to be a set function with transitive domain such that for all we have . where is the unique such that .
We just need to prove now by -induction that: (A) if are attempts and then ; and (B) for all there is an attempt with . This is straightforward.