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.

We proved 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 {\mathbb N} suffice) then either S is not true of {\mathbb N}, or else S is incomplete. The reason is that if S is true of {\mathbb 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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: