Ars Mathematica

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.