March 13, 2008
Given any complete, consistent extension of , we showed that there is a minimal model of . This model is unique up to (unique) isomorphism, it is rigid (i.e., it has no automorphisms other than the identity), and has no proper elementary substructures.
Given a model , let , the standard system of , be the set of those coded by elements of , where codes iff Thus is the class of finite sets. We showed that if is nonstandard, contains all recursive sets, and that for any non-recursive there is a nonstandard such that .
March 11, 2008
Due Tuesday March 18 at 1pm.
March 11, 2008
We showed that Exponentiation is Diophantine, completing the proof of the Davis-Matiyasevich-Putnam-Robinson theorem. The result follows from a careful examination of certain second order linear recurrence relations.
March 10, 2008
Hilbert’s tenth problem asks whether there is an algorithm that given a polynomial with integer coefficients (in an arbitrary number of variables) determines whether it has integer roots. A celebrated theorem of Davis, Matiyasevich, Putnam and Robinson shows that this is not the case. Their result shows that the class of Diophantine sets coincides with the a priori larger class of r.e. (or ) sets.
We proved this result under the assumption that exponentiation is Diophantine. This is the key result, and will be dealt with in the following lecture.
March 4, 2008
We proved the Rice, Shapiro, McNaughton theorem characterizing index sets.
We also showed that there incomparable Turing degrees below .