Talk:Tennenbaum's theorem

Who's Tennenbaum?[edit]

Added name and date for Stanley Tennebaum re: the theorem with his name.

Added a link to an online paper by R. W. Kaye about the theorem; I couldn't find any non-online source so I elected for 'External Links' rather than 'References'. Kaye has written about models of Peano Arithmetic so I feel this is a legitimate link to include, but I defer to other editors if there is a preferred way to do so. Thanks! Zero sharp 06:30, 27 September 2007 (UTC)[reply]

Kaye's list of publications on his website doesn't claim this paper was published anywhere. Since it's unpublished, I think it's more appropriate to put it in the external links section than the references section. It certainly is a relevant link to include. — Carl (CBM · talk) 12:59, 27 September 2007 (UTC)[reply]

The URL lacked the essential extension '.pdf' which I have added. At the same time I removed the link to Richard Kaye's Wikipedia page: they are not the same person. — Preceding unsigned comment added by 213.122.19.111 (talk) 11:49, 28 September 2011 (UTC)[reply]

Clarification[edit]

"If the elements of M were to be coded onto the (standard) natural numbers in such a way that the addition and multiplication operations of the model were recursive functions on the codes, then every subset of the model defined by a first-order formula with finitely many parameters and bounded quantifiers is a recursive set of natural numbers." How do we know this is true? — Preceding unsigned comment added by TheKing44 (talk • contribs) 03:48, 5 June 2018 (UTC)[reply]

What they are saying is not written very clearly. I think that goes for the entire proof. I am going to work on the article some. — Carl (CBM · talk) 12:33, 5 June 2018 (UTC)[reply]

@CBM: I directly added the algorithm for computing C (based on http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennrosser). What do you think? TheKing44 (talk) 12:47, 5 June 2018 (UTC)[reply]

I see your edit now and I think it did a good job clarifying. I had been editing the article at the same time to abridge the proof; I thought that the previous version, in trying to be chatty, just ended up being unclear. I have Kaye's book in front of me, so that makes it easier for me to see the details written out clearly. I am worried that trying to include "some" of the details, like the previous editor did, can just cause confusion.

Do you think it is better for us to include a more detailed definition of the standard system, so that we can then include the more detailed kind of argument you wrote? Or better to leave it more as a sketch? — Carl (CBM · talk) 12:55, 5 June 2018 (UTC)[reply]

I think a nice concise proof outline would be nice, since its hard to find one online. Most proof outlines online are kinda wordy and difficult to understand. TheKing44 (talk) 13:09, 5 June 2018 (UTC)[reply]

Let's keep working on the article. I'm done for the moment - please edit it to clarify things or post any issues here. Best, — Carl (CBM · talk) 13:43, 5 June 2018 (UTC)[reply]

Notational car crash[edit]

In section 'Recursive structures for PA' in the inline text, we're defining what it means for a structure 'M' to be recursive, then suddenly we're talking about operations + and x on 'N' (not 'M') -- and then moments later in the formula, we're talking about circle-+ and circle-x. What's the relation between + and circle-+ and x and circle-x? Is there one? It's totally unclear. We also talk about a recursive binary relation '<' (also on 'N') but then a moment later it's subscripted with 'M' (not 'N'). While it's entirely possible this is meaningful and consistent it is _not at all clear_.