We briefly discussed the problem of generalizing the proof of unsolvability of Hilbert’s tenth problem to other (recursive) rings.
We proved a version of the first incompleteness theorem as a consequence of the unsolvability of the tenth problem: If is any recursive set of axioms strong enough to prove a very weak fragment of arithmetic (the addition and multiplication tables for suffice) then either is not true of , or else is incomplete. The reason is that if is true of , then the set of consequences of is an undecidable r.e. set (by the unsolvability of the tenth problem), but the set of consequences of a complete theory is decidable.
- 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).