Kleene’s Normal Form Theorem entails Gödel’s First Incompleteness Theorem

Talking about this result at a maths seminar, I realized my previous effort at this in the book is less pretty than it should be. In effect, I stupidly embedded (i) a proof that  not every partial recursive function is potentially recursive in Church’s sense into (ii) the proof of incompleteness. They should of course be neatly separated. So here (in under two pages) is how.

And comments or notes of typos/thinkos will be welcome!

This entry was posted in This and that. Bookmark the permalink.

2 Responses to Kleene’s Normal Form Theorem entails Gödel’s First Incompleteness Theorem

  1. Gillman Payette says:

    Hi, I think there is a typo in the proof of theorem two. What is written there is f(n)\approx U(\mu z(C(n,n,z)=0)+1). I think the `+1′ should be outside of the brackets.

Leave a Reply

Your email address will not be published. Required fields are marked *