[FOM] Freeman Dyson on Inexhaustibility

H. Enderton hbe at math.ucla.edu
Thu Apr 29 13:02:47 EDT 2004


Thanks to Allen Hazen for reminding me of the New Yorker piece.
He further wrote:

>the First Incompleteness Theorem -- the existence of unprovable truths
> -- follows easily from the Unsolvability of the Halting Problem.
> Because of the intuitive nature of Turing  Machines (and because this
> argument avoids the puzzling "self-referential"  sentence), I have
> found this the easiest proof of First Incompleteness to present to
> students 

I would argue that "avoids" here might better be "disguises."
I claim that the proof you describe, if you push hard on it to
see what prevents having a recursive axiomatization of true number
theory, actually is constructive enough to squeeze out an unprovable
sentence (from a partial axiomatization).  And -- surprise? --
that sentence can be interpreted as saying "I am unprovable from
those axioms."

The argument in support of this claim I put into the second edition
of my logic textbook (A Math. Intro. to Logic, pages 257-258).  And
it's just that -- an argument, not a rigorous proof.

>   The Second Incompleteness Theorem, on the other hand....

Yes, indeed!

--Herb Enderton





More information about the FOM mailing list