117b – Undecidability and incompleteness – Lecture 6

We briefly discussed the problem of generalizing the proof of unsolvability of Hilbert’s tenth problem to other (recursive) rings. (For a technical and thorough discussion of this topic, see

• MR2297245 (2009e:11235). Shlapentokh, Alexandra. Hilbert’s tenth problem. Diophantine classes and extensions to global fields. New Mathematical Monographs, 7. Cambridge University Press, Cambridge, 2007. xiv+320 pp. ISBN: 978-0-521-83360-8; 0-521-83360-4.

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.

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).

Advertisement