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
Due Thursday, February 1 at 1:00 pm.
The second pdf contains some hints for problem 3.
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 begin 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.
January 18, 2007
Due Thursday, January 25 at 1:00 pm.
January 16, 2007
We defined languages and structures in the model theoretic sense, and the notion of an embedding between structures of the same language.
We proved that the theory of the degrees is decidable by means of forcing:
- First we reduced the argument to showing that any finite partial order can be embedded in .
- Then we argued that for this it is enough to show that there is an infinite independent family of degrees, where independence means that no element of the family is reducible to the join of finitely many of the other members of the family.
- Finally, we built such a family using forcing.