Epsilon-induction and epsilon-recursion

1. Epsilon-induction

Earlier, we stated the principle of epsilon-induction.

Axiom Scheme of $\in$ -Induction: For all first order formulas $ϕ (x, \overline{a})$ of the language $L_{\in}$ , $\forall \overline{a} (\forall x (\forall y \in x ϕ (y) \to ϕ (x)) \to \forall x ϕ (x, \overline{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 (\exists y y \in x \to \exists y (y \in x \land \neg \exists z (z \in x \land 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 (\forall y \in x ϕ (y) \to ϕ (x))$ and $a$ is a set. We want to show $ϕ (a)$ . 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 ϕ (x)\}$ . If $c$ were nonempty then by foundation let $x \in c$ with $x \cap c = \emptyset$ . 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 = \emptyset$ and $y \in b$ that $ϕ (y)$ . Therefore $\forall y \in x ϕ (y)$ and hence $ϕ (x)$ contradicting $x \in c$ . Therefore $c$ is empty and $\forall x \in b ϕ (x)$ and in particular $ϕ (a)$ , as required.

2. Epsilon-recursion

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 $ψ (x, y, z, \overline{a})$ is a first order formula and $\forall x \forall y \exists! z ψ (x, y, z, \overline{a})$ . Then there is a formula $θ (x, y, \overline{a})$ such that $\forall x \exists! y θ (x, y, \overline{a})$ and for all $x$ and $f = \{⟨ u, v ⟩: u \in x \land θ (u, v, \overline{a})\}$ with $ψ (x, f, y, \overline{a})$ we have $θ (x, z, \overline{a})$ .

In other words, given a class function $G$ we can define a new class function $F$ by $F (x) = G (\{⟨ u, F (u) ⟩: 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 (f)$ such that for all $x \in dom (f)$ we have $f (x) = G (\{⟨ u, f (u) ⟩: u \in x\}, x)$ . where $G (r, s)$ is the unique $t$ such that $ψ (r, s, t, \overline{a})$ .

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