[FOM] Simple historical question

[William Tait]

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