[FOM] Simple historical question
William Tait
williamtait at mac.com
Mon Jul 23 13:56:08 EDT 2007
On Jul 20, 2007, at 1:09 PM, H. Enderton wrote:
> Credit for showing the undecidability of true arithmetic surely goes
> to Alonzo Church, "An unsolvable problem of elementary number theory,"
> Amer. J. of Math., vol. 58 (1936), 345-363. This is the same paper
> that
> presents Church's Thesis for the first time, so it would have been
> hard
> for anyone (Goedel, Post, Turing, ...) to have formulated the result
> before then.
In his 1934 lecture notes "On undecidable propositions of formal
mathematical systems", Gödel defines the notion of general
recursiveness and in section 6 describes the class of systems to
which his first incompleteness theorem applies. (See condition 1 and
note that if truth is re, then it is general recursive.) If truth in
arithmetic were r.e., then it would satisfy those conditions.
Gödel is explicit that he refrains from replacing the term `r.e.' by
`c.e.', or `(general) recursive' by `decidable', because there was
as yet no convincing (to him) argument that all computable functions
must be general recursive. It was only after Turing's analysis (1937)
and the proof of equivalence that he became convinced of the
equivalence. (See his postscriptum of June 1964 in the Collected
Works, volume I.)
I think he was right not to be convinced before Turing's analysis and
that Church in 1936 was premature (but maybe prescient) in stating
his thesis. So I have some trouble accepting the attribution of the
result to Church.
> As for your pedagogical point, I quite agree. Now that we have a
> robust
> theory of computability, I think we can say that the heart of Goedel's
> first incompleteness theorem lies in the fact that true arithmetic is
> not computably enumerable.
The result you state follows from the definability of c.e. relations
in arithmetic and Tarski's theorem on non-definability of arithmetic
truth in arithmetic and ignores the Pi^0_1 nature of the undecidable
sentence.
Regards,
Bill
More information about the FOM
mailing list