From: ikastan@my-deja.com
Subject: Re: Nonstandard analysis, forcing, and P = NP
Date: Fri, 25 Jun 1999 00:03:47 GMT
Newsgroups: sci.math,sci.logic
Keywords: Tennenbaum's theorem (arithmetic is nonrecursive)
In article ,
Bill Dubuque wrote:
> Tim Chow wrote:
> |
> | 1. This is probably a FAQ, but anyway...in _Goedel,_Escher,_Bach_,
> | Hofstadter says that one can index nonstandard integers by 3-tuples
> | of standard integers, but there is no such way of doing so that
> | makes both addition and multiplication recursively computable.
> | What precisely is the theorem here, and how is it proved? [...]
>
> This is known as Tennenbaum's theorem/phenomenon. For pointers into
> the related literature follow the review URLs of papers cited below.
> There have been comments on related topics in sci.math and sci.logic
> in the past, esp. by Ilias Kastanas; you may find these articles by
> searching for "tennenbaum" in the DejaNews archive; e.g. see URL [d].
Please do; I'd rather not post that material afresh for the
moment, as I'm on vacation and connecting is quite slow. In fact
I'll be in Marathon tomorrow; getting through to the net would be
a real battle.
Anyway, I've just realized that that passage in "G.E.B." is the
reason Tennenbaum's theorem is often considered to be "in a non-stand-
ard model of PA, + and * cannot both be recursive". Much more is
true; _neither_ one can be recursive... and if the model is actually a
model of true arithmetic ( Th(N) ), neither can be even arithmetical.
Ilias
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.