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 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).
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.
February 1, 2007
We showed that 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 formula in the structure coincides with the class of 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.
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.
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 ,
for all .
We began the proof that they are Diophantine by analyzing some of the algebraic identities their terms satisfy.
- Unsolvable problems, by M. Davis. In Handbook of mathematical logic, J. Barwise, ed., North-Holland (1977), 567-594.
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.