[FOM] Simple historical question
rzach at ucalgary.ca
Wed Jan 28 22:16:11 EST 2009
On Thu, 2007-07-19 at 20:41 -0400, Neil Tennant wrote:
> > To whom should we rightly give first credit for the result/observation
> > that Th(N,0,S,+,*,<) is undecidable?
> Perhaps the answer is to be found in section II.5 (beginning on p.60) of
> A. Tarski, A. Mostowski and R.M. Robinson, Undecidable Theories,
> North-Holland, Amsterdam, 1953.
> The footnotes display the required degree of historical sensitivity.
> Theorem 9 and Corollary 10 cover a wide range of systems. For the special
> case of Th(N) [called sans-serif 'N' in the monograph], the result is
> attributed to Tarski's famous paper on truth (the German version in
> Studia Philosophica), 'in particular footnotes 88 and 95'.
The result attributed to Tarski in fn. 13 is that the set of valid
sentences of N is not definable in N. The undecidability result, TMR
write, is a direct consequence of this *plus* the identification of
recursive sets and functions with those that are definable in PA.
More information about the FOM