Kleene's Amazing Second Recursion Theorem
Yiannis N. Moschovakis · Bulletin of Symbolic Logic · 2010
This little gem is stated unbilled and proved (completely) in the last two lines of §2 of the short note Kleene [1938]. In modern notation, with all the hypotheses stated explicitly and in a strong (uniform) form, it reads as follows: SecondRecursionTheorem(SRT). Fix a set V ⊆ ℕ,and suppose that for each natural number nϵ ℕ = {0, 1, 2, …}, φn: ℕ1+n⇀ Vis a recursive partial function of (1 + n) arguments with values in V so thatthe standard assumptions(a)and(b)hold with . (a)Every n-ary recursive partial function with values in V is for some e. (b)For all m, n, there is a recursive function : Nm+1→ ℕ such that . Then, for every recursive, partial function f of (1+m+n) arguments with values in V, there is a total recursive function of m arguments such that Proof. Fixeϵ ℕ such that and let . We will abuse notation and write ž; rather than ž() whenm= 0, so that (1) takes the simpler form in this case (and the proof sets ž =S(e, e)).