117b – Undecidability and incompleteness – Lecture 7

February 13, 2007

Define essentially undecidable theories as those theories (of arithmetic) that are recursively axiomatizable but such that any recursive extension T is undecidable and therefore incomplete. We showed that if S is essentially undecidable then there are continuum many complete extensions of S, none of which are c.e. The argument gives an example of a complete binary tree recursive in {\bf 0}' with no c.e. branches.

We showed that if \varphi is \Sigma^0_0 then its characteristic function is primitive recursive and that if R is a c.e. relation, then it is the range of a primitive recursive function. We used this to prove Craig’s trick showing that a theory admits a c.e. axiomatization iff it admits a primitive recursive axiomatization.

We defined (numeralwise) representability and binumerability of a relation by a formula in a given theory. Next lecture we will show that there is an essentially undecidable finitely axiomatizable theory that represents all c.e. relations and binumerates all recursive relations. This will be the key to the proof of the incompleteness theorems.


117b – Undecidability and incompleteness – Lecture 6

February 8, 2007

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.

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

117b – Undecidability and incompleteness – Lecture 5

February 8, 2007

We completed the proof of the undecidability of Hilbert’s tenth problem, and discussed some of its consequences, tying up with the general theory of the degrees and leading directly into the second part of this topic: The incompleteness theorems.


117b – Undecidability and Incompleteness – Lecture 4

February 1, 2007

We showed that a=n! is Diophantine. This implies that the prime numbers are Diophantine. Therefore, there is a polynomial in several variables with integer coefficients whose range, when intersected with the natural numbers, coincides with the set of primes. Amusingly, no nonconstant polynomial with integer coefficients can only take prime values.

We proved the bounded quantifier lemma, the last technical component of the proof of the undecidability of Hilbert’s tenth problem. It implies that the class of relations definable by a \Sigma^0_1 formula in the structure ({\mathbb N},+,\times,<,0,1) coincides with the class of \Sigma_1 relations (i.e., the Diophantine ones).

To complete the proof of the undecidability of the tenth problem, we will show that any c.e. relation is Diophantine. For this, recall that a set is c.e. iff it is the domain of a Turing machine. We proceeded to code the behavior of Turing machines by means of a Diophantic representation. This involves coding configurations of Turing machines and it remains to show how to code the way one configuration changes into another one.


117b – Undecidability and incompleteness – Lecture 3

January 30, 2007

We concluded the proof that Matiyasevich sequences are Diophantine. This involved a delicate analysis of congruences satisfied by terms of these sequences.

It follows that exponentiation is Diophantine. Using exponentiation, we can now proceed to code finite sequences, the key idea behind both the proof of undecidability of the tenth problem and of the incompleteness theorems.


117b – Undecidability and Incompleteness – Lecture 2

January 25, 2007

The core of the proof of the undecidability of the tenth problem is the proof that exponentiation is Diophantine. We reduced this to proving that certain sequences given by second-order recurrence equations are Diophantine. These are the Matiyasevich sequences: For b\ge 4,

\alpha_b(0)=0,
\alpha_b(1)=1, and
\alpha_b(n+2)=b\alpha_b(n+1)-\alpha_b(n) for all n.

We began the proof that they are Diophantine by analyzing some of the algebraic identities their terms satisfy.

Additional reference:

  • Unsolvable problems, by M. Davis. In Handbook of mathematical logic, J. Barwise, ed., North-Holland (1977), 567-594.

117b – Undecidability and Incompleteness – Lecture 1

January 23, 2007

We reviewed the statements of the first, second and tenth problems of the list presented by Hilbert during the International Congress in 1900. The tenth problem (undecidability of Diophantine equations) will be our immediate focus. The goal is to show that any r.e. set is Diophantine. The undecidability of the halting problem will give the result. Then we will use this characterization as part of the proof of the incompleteness theorems.

Diophantine sets are closed under conjunction and disjunction. `Easy’ number theoretic relations and functions (e.g., being divisible by, the least common multiple) are Diophantine.