Epsilon-induction and epsilon-recursion

1. Epsilon-induction

Earlier, we stated the principle of epsilon-induction.

Axiom Scheme of $∈$-Induction: For all first order formulas $ϕ ( x , a _ )$ of the language $L ∈$, $∀ a _ ( ∀ x ( ∀ y ∈ x ϕ ( y ) → ϕ ( x ) ) → ∀ x ϕ ( x , 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: $∀ x ( ∃ y y ∈ x → ∃ y ( y ∈ x ∧ ¬ ∃ z ( z ∈ x ∧ z ∈ 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 $∈$-Induction follows from the axiom of foundation and other axioms of set theory.

Proof.

Suppose $∀ x ( ∀ y ∈ x ϕ ( y ) → ϕ ( 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 ∈ b ¬ ϕ ( x )$. If $c$ were nonempty then by foundation let $x ∈ c$ with $x ∩ c = ∅$. So for every $y ∈ x$ we have $y ∈ b$ since $x ∈ c ⊆ b$ and $b$ is transitive, and hence $y ∉ c$. It follows from $x ∩ c = ∅$ and $y ∈ b$ that $ϕ ( y )$. Therefore $∀ y ∈ x ϕ ( y )$ and hence $ϕ ( x )$ contradicting $x ∈ c$. Therefore $c$ is empty and $∀ x ∈ b ϕ ( x )$ and in particular $ϕ ( a )$, as required.

2. Epsilon-recursion

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

Theorem.

Suppose $ψ ( x , y , z , a _ )$ is a first order formula and $∀ x ∀ y ∃! z ψ ( x , y , z , a _ )$. Then there is a formula $θ ( x , y , a _ )$ such that $∀ x ∃! y θ ( x , y , a _ )$ and for all $x$ and $f = ⟨ u , v ⟩ u ∈ x ∧ θ ( u , v , a _ )$ with $ψ ( x , f , y , a _ )$ we have $θ ( x , z , 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 ∈ 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 ∈ dom ( f )$ we have $f ( x ) = G ( ⟨ u , f ( u ) ⟩ u ∈ x , x )$. where $G ( r , s )$ is the unique $t$ such that $ψ ( r , s , t , a _ )$.

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