Goedel’s Theorem is True

I’m sorry if my last post misled anyone. Goedel’s theorem is true. Lots of people have checked the proof. I’ve checked the proof. There are multiple proofs (the usual proof is Rosser’s, not Goedel’s original proof), as well as vast generalizations.

Here’s a two line proof of the theorem (some details are left out):

  • If Goedel’s theorem is false, then the Halting Problem for Turing machines is solvable.
  • The Halting Problem is unsolvable, therefore Goedel’s theorem is true.

At the time, Goedel’s result was very surprising, but by modern standards it’s almost obvious. The set of provable theorems of arithmetic is recursively enumerable. It’s not that surprising that first-order arithmetic would be at least as expressive as Turing machines, which implies that the set of provable theorems is not recursive. Goedel’s theorem follows.

I intended the post to be tongue-in-cheek. My real point was that a certain number of papers on Arxiv are apparently written by cranks.

7 thoughts on “Goedel’s Theorem is True

  1. Someone was apparently a little tightly wound. The problem of course is that the import of your last sentence “There you have it.” was missed, because they left off the implied sardonic inflection. I have a hard time believing though that someone actually read that entry title and took it at face value.

    This site is about mathematical commentary as well as reporting. Ridicule can be commentary.

  2. > I have a hard time believing though that someone actually read that
    > entry title and took it at face value.

    This is a great story that shows how many people are prepared to read something like that at face value. :-)

  3. Holy Crap. The jibberish made my head throb. That letter must have been from that “other” mathematician Anthony Wiles or Andrew Wiles is a far greater crank-baiter than I could EVER imagine.

    Reading a reference to a statement that an axiom is “false” makes my eyeballs hurt.

  4. The model theorist, Wilfrid Hodges, once wrote a nice paper about the many submissions he’d received as editor of the “Bulletin of Symbolic Logic”, purporting to show that Cantor’s theorem about the non-countability of the reals was false. He concluded that there are many people out there, often philosophers rather than mathematicians, who find this counter-intuitive result so shocking, that they set to to find the error. The fact that for a century mathematicians have looked at Cantor’s proofs and found no errors, and indeed, have developed their own independent proofs of the result, does not deter them. Rather it motivates them, as this is their chance to leave their name on history — to overturn a century of error and waywardness.

    The article details are:

    @ARTICLE{hodges:bsl98,
    author = “Wilfrid Hodges”,
    title = “An editor recalls some hopeless papers”,
    journal = “Bulletin of Symbolic Logic”,
    year = “1998″,
    volume = “4″,
    number = “1″,
    pages = “1–16″}

  5. I’d tend to assume that there’s more crank at Arxiv than reliable science and mathematics. Although I’ve never really looked too closely either.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>