On Sun, Nov 9, 2014 at 6:30 PM, Henry Baker <hbaker1@pipeline.com> wrote:
At 03:02 PM 11/9/2014, Dan Asimov wrote:
Goedel's original undecidable statement, as described in the article by Nagel & Newman about it in the 4-volume set The World of Mathematics, or in the more detailed book by Goedel's Proof by the same authors, is a statement that can be interpreted as saying "There is no proof of me."
So as you may have seen, if it's false then there *is* a proof of it, so it's true. So, if number theory is consistent, then it can't be false since that leads to a contradiction. So it must be true (in a cosmic sense). Therefore there really is no proof of it.
QUESTIONS: ----------
Are there relatively simple propositions in number theory that are known to be undecidable?
Hilbert's Tenth Problem is about as simple as you can get.
What undecidable *proposition* is associated with Hilbert's 10th problem? There is no *algorithm* for deciding whether a given Diophantine equation has a solution, but the proposition "for any Turing machine M, M does not compute, given a (suitably encoded) Diophantine equation as input, whether that equation has a solution" is not undecideable; it's true and provable. A strengthened version of the finite Ramsey theorem is the simplest "natural" statement proven to be undecideable in formal number theory. The result that this is undecideable is called the Paris Harrington theorem. See http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem for details. Andy