3
$\begingroup$

I have some questions about the commonly presented proof of Godel's first incompleteness theorem.

First of all, what is the need for the Godel numbers in the proof? Would not the proof be valid without the arithmetization of the language?

How do we construct Godel's statement?

Why do we hold that there are unprovable and undisprovable statements only in arithmetic systems? Is it not possible for the same proof to be reproduced in systems that do not satisfy that property?

I have thought long and hard about all three of these questions and no solution has made itself apparent to me. I would greatly appreciate any help I can get.

$\endgroup$
  • $\begingroup$ "How do we construct Gödel's statement?" Through the arithmetization of the formal language, i.e. using Gödel numbers. $\endgroup$ – Mauro ALLEGRANZA Feb 14 '17 at 10:15
  • $\begingroup$ In general, we do not need "arithmetic systems"; the theorem holds also for other systems, but not for all. $\endgroup$ – Mauro ALLEGRANZA Feb 14 '17 at 10:16
  • $\begingroup$ You can see Raymond Smullyan, Gödel's Incompleteness Theorems (1992). $\endgroup$ – Mauro ALLEGRANZA Feb 14 '17 at 10:17
  • $\begingroup$ Briefly, what is needed for Gödel's proof to work is only that the system is sufficiently strong to express arithmetic. It does not have to be explicitly about arithmetic. More limited axiomatic systems may well be complete. $\endgroup$ – Harald Hanche-Olsen Feb 14 '17 at 10:35
  • $\begingroup$ Also useful : Peter Smith, Gödel Without (Too Many) Tears. $\endgroup$ – Mauro ALLEGRANZA Feb 14 '17 at 15:15
6
+50
$\begingroup$

The key point about Goedel's theorem isn't that there is some sentence which PA (say) can't prove, it's that there's some sentence in the language of PA which PA can't prove.

This is what Goedel number helps us do. The point is that we want to write "This sentence is unprovable," in the language of arithmetic. But arithmetic doesn't let us talk directly about sentences and proofs! So we need to somehow argue that there is a statement about arithmetic - something like $$\mbox{"$\exists x\forall y\exists z\forall w \exists u(3x+4y^2-7z+w^4-u=0)$"}$$ - which somehow "means" "I am unprovable".

This addresses your first question - why arithmetization is necessary. Your second question, how it's done, is harder to answer, and I suggest you look at a book that treats it in detail (say, Goedel without (too many) tears). Ultimately, though, the proof of Goedel's theorem hinges on two non-obvious properties:

  • Arithmetization works - this is ultimately a statement that the theory PA is strong enough.

  • PA is recursively axiomatizable - there is an "explicit" description of what the axioms of PA are. This is ultimately a statement that PA is not too complicated.

Both pieces are needed for Goedel's argument to work:

  • Overly simple theories, like the theory of dense linear orders without endpoints, can be complete in that they prove or disprove every sentence in their language. Such theories must be too simple to "describe arithmetic" in some sense.

  • Overly complicated theories can also be complete. For instance, let $T$ be the true theory of arithmetic - that is, the set of all true statements about the structure $(\mathbb{N}; +, \times, 0, 1, <)$. $T$ is complete - every sentence in its language is either true (in which case $T$ proves it) or false (in which case $T$ disproves it); this doesn't contradict Goedel since $T$ is impossible to "nicely describe".

So one consequence of Goedel's theorem is that PA, and theories like it, occupy a logical "sweet spot" of sorts. This isn't the main takeaway of course, but it's an interesting observation.

It's also worth noting that there are theories in other languages than that of arithmetic, to which Goedel's theorem also applies; for instance, the usual axioms of set theory are both "simple" enough and "strong" enough for the proof to go through. Basically, you don't really need arithmetization on the nose, you just need the notions of sentence, proof, etc. to be representable in your language, and for basic properties of them to be provable in your theory.

$\endgroup$
  • $\begingroup$ Note that of course the example sentence I wrote is nowhere near the actual Goedel sentence - it's just some random junk I cooked up. $\endgroup$ – Noah Schweber Feb 14 '17 at 17:38

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.