6
$\begingroup$

Background: I'm working on a talk that presents Godel's first Incompleteness Theorem from a computability-theoretic perspective. The idea is to show that the first incompleteness theorem follows from the unsolvability of the halting problem. See Scott Aaronson's post for a high-level description: http://www.scottaaronson.com/blog/?p=710

I've almost got the proof down without using the concept of a Godel numbering except for one last step: I need to show that the set of functions definable in Peano Arithmetic is closed under primitive recursion. That will show that all p.r. functions are definable in PA, which lets me complete the proof.

Question: is there a way to prove that PA-definable functions are closed under primitive recursion without using the full machinery of a godel numbering?

$\endgroup$
  • $\begingroup$ Hi, i want to know more about the concept of "... is representable in ..." which keyword I should search to know more about it (maybe on wikipedia)? $\endgroup$ – MphLee Jul 5 '13 at 16:21
  • 1
    $\begingroup$ A function f is representable in a language $L$ if there is a well-formed-formula $\phi$ of $L$ such that $\phi(\mathbf{x},\mathbf{y})$ is true iff $f(x) = y$. I couldn't find it on Wikipedia, but this seems to be a good overview: cs.cornell.edu/courses/cs4860/2009sp/lec-22.pdf $\endgroup$ – Satvik Beri Jul 5 '13 at 16:25
  • 2
    $\begingroup$ Do you know about Godel's $\beta$-function? $\endgroup$ – Elchanan Solomon Jul 5 '13 at 16:47
  • 1
    $\begingroup$ @IsaacSolomon I looked it up after reading your comment...for some reason I had been under the impression that the $\beta$-function relied on a Godel numbering, but that's not the case. This completes the proof, thank you! I would upvote your comment, but I don't have upvoting privileges yet. $\endgroup$ – Satvik Beri Jul 5 '13 at 17:05
  • 2
    $\begingroup$ The notion of "representable" in Satvik Beri's comment is what is usually called "definable". The word "representable" is usually used for a stronger property, namely that there is a formula $\phi$ such that, whenever $f(a)=b$, then the theory in question (here PA) proves $\forall z\,(\phi(\bar a,z)\iff z=\bar b)$. (Here $\bar a$ and $\bar b$ are standard closed terms denoting the numbers $a$ and $b$.) $\endgroup$ – Andreas Blass Jul 5 '13 at 17:05
2
$\begingroup$

The answer presented in the comments was to use Gödel's β function, which does not require Gödel numbering.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.