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.