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.