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

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.