We briefly discuss the problem of generalizing the proof of unsolvability of Hilbert’s tenth problem to other (recursive) rings.

We prove a version of the first incompleteness theorem as a consequence of the unsolvability of the tenth problem: If *S* is any recursive set of axioms strong enough to prove a very weak fragment of arithmetic (the addition and multiplication tables for **N **suffice) then either *S* is not true of **N**, or else *S* is incomplete. The reason is that if *S* is true of **N**, then the set of consequences of *S* is an undecidable r.e. set (by the unsolvability of the tenth problem), but the set of consequences of a complete theory is decidable.

Additional references:

*The incompleteness theorems*, by C. Smorynski. In **Handbook of mathematical logic**, J. Barwise, ed., North-Holland (1977), 821-865.
**Models of Peano Arithmetic**, by R. Kaye. Claredon Press (1991).
**Aspects of incompleteness**, by P. Lindström. Springer (1997).
*On formally undecidable sentences of ***Principia Mathematica** and related systems (German: *Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I.*), by K. Gödel. Monatshefte für Mathematik und Physik **38** (1931), 173-198. Reprinted in several places. See for example **Collected Works, vol. I, **K. Gödel. Oxford University Press (2001).

### Like this:

Like Loading...

*Related*

This entry was posted on February 8, 2007 at 2:54 pm and is filed under 117b, Undecidability and incompleteness. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply