Does Gödel's diagonal lemma follow from Kleene's recursion theorem? I believe the converse is true, by an argument like the following.

Let e ↦ θ_{e} be a bijection between ω and the set of Σ^{0}_{1} formulas in the language of arithmetic having just the variable v_{0} free.

Let e ↦ W_{e} be a numbering of the r.e. subsets of ω such that for all e, W_{e} = {n ∈ ω : θ_{e}(n) is true}. This is possible because every r.e. set is defined in the standard model of arithmetic by a Σ^{0}_{1} formula.

Let f be any recursive operation on ω. To prove the recursion theorem, we seek a number d such that W_{d} = W_{f(d)}.

Toward that, let φ(v_{0}, v_{1}) be a Σ^{0}_{1} formula satisfied by a pair (n, e) iff θ_{f(e)}(n) is true. For instance, φ might be

Σ

^{0}_{1}-Tr[ Sub(numeral(v_{0}), 0, f(v_{1})) ]

so that φ(n, e) says that a true Σ^{0}_{1} sentence results from substituting the numeral for n into the formula with code f(e).

By the diagonal lemma, there is a Σ^{0}_{1} formula θ_{d}(v_{0}) such that

∀v

_{0}[ θ_{d}(v_{0}) ↔ φ(v_{0}, d) ]

is provable in Robinson's arithmetic. Hence

W

_{d}= {n ∈ ω : θ_{d}(n) is true} = {n ∈ ω : φ(n,d) is true} = {n ∈ ω : θ_{f(d)}(n) is true} = W_{f(d)}

as desired. The second equality follows by choice of θ_{d}.

My question is whether we can prove the diagonal lemma from the recursion theorem. For specificity, here is the lemma I have in mind:

For any formula φ(v

_{0}, v_{1}, … v_{n}) in the language of arithmetic, one can find a formula ψ(v_{1}, … v_{n}) in that language, so that Robinson's arithmetic proves ∀φv_{1}…∀φv_{n}[ ψ(v_{1}, … v_{n}) ↔ φ(⌜ψ⌝, v_{1}, … v_{n}) ].

Note that it is not sufficient to prove that for each φ there is a ψ for which the stated equivalence holds; the equivalence must be provable in Robinson's arithmetic.

Kleene's amazing Second Recursion Theorem, by Yiannis N. Moschovakis,Bulletin of Symbolic Logic, June 2010, pages 189 — 239, an online copy of which is available at math.ucla.edu/~asl/bsl/1602-toc.htm – Ali Enayat Jul 15 '11 at 21:56