[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