In the standard proof for Godel incompleteness theorem he code our language with Godel's numbering and of course there are is a lot of freedom in our coding. The proof then provide us with an undecidable statement about the natural numbers. I wonder if it's known whether or not all undecidable statements (maybe up to some isomorphism) can be achieved in this way using a suitable coding for each such statement.

  • 1
    $\begingroup$ Are you asking "does every undecidable statement have a Goedel number"? Or are you asking "is there a (nice) way to assign numbers to the set of undecidable statements"? If so, can you be more specific about what sort of numbering you're interested in? It follows from this that the set of statements that PA does not decide is not even recursively enumerable, so does that answer your question..? $\endgroup$ Mar 3 at 21:19
  • 1
    $\begingroup$ As in the comment above, I am not entirely sure what you are asking. But, when considering whether all undecidable statements can be captured by "a suitable coding," a good first question is whether the outcome of your question is a system with enumerable undecidable statements. If so, this will not work: You could apply the same sort of undecidability approach to "PA + (enumeration of undecidable statements)" to exhibit the existence of an unprovable (unlisted) truth. $\endgroup$ Mar 3 at 21:30
  • 2
    $\begingroup$ The answer to that is "yes, because every statement has a Goedel number". Is that really what you wanted to ask? $\endgroup$ Mar 4 at 0:19
  • 1
    $\begingroup$ @IzaakvanDongen I don't understand. When I say that every statement has a Godel number I mean a Godel number which the standard proof shows it is undecidable. My question is probably on the edge of metamathematics, but I believe it is a precise question $\endgroup$
    – ziv
    Mar 4 at 12:55
  • 1
    $\begingroup$ Aha, OK, I think I'm more or less with you now! Would you be happy with an answer to "is there a statement independent of PA, which PA does not prove is equivalent to any Goedel sentence"? I think that this paper from Lawrence Wong's comment here shows the answer to that is "yes, there is such a statement" (because any sentence that says "I am not provable in PA" implies Con(PA)). The answer there also gives some nice examples of PA-undecidable statements that don't "look" like a Goedel sentence. $\endgroup$ Mar 4 at 14:33


Browse other questions tagged .