## 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 – Homework 4

January 25, 2007

Due Thursday, February 1 at 1:00 pm.

The second pdf contains some hints for problem 3.

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

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

## 117b – Homework 3

January 18, 2007

Due Thursday, January 25 at 1:00 pm.

## 117b – Turing degrees – Lecture 5

January 18, 2007

We finished the first topic of the course with a survey of results about the theory of ${\mathcal D}$.

In particular, we stated the Slaman-Woodin theorems on coding countable relations inside ${\mathcal D}$ and on the structure of ${\rm Aut}({\mathcal D})$.

The coding theorem and the arithmetic definability of $<_T$ give a new proof of Simpson’s theorem on the complexity of ${\rm Th}({\mathcal D})$: Not only it is undecidable, but it is recursively isomorphic to the theory of second-order arithmetic. That $<_T$ is definable in first order arithmetic will be shown as part of the second topic.

The results on ${\rm Aut}({\mathcal D})$ imply that there are only countably many automorphisms of ${\mathcal D}$, that they are all arithmetically definable, and coincide with the identity above ${\bf 0}''$. This was then used by Slaman and Shore to prove that the relation $R(x,y)$ iff $y=x'$is definable in ${\mathcal D}$.

We then stated Martin’s theorem on Turing Borel determinacy that any degree invariant property which is Borel as a subset of $2^{\mathbb N}$ and $<_T$-cofinal holds on a cone.

## 117b – Turing degrees – Lecture 4

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 $\Sigma_1$ 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 ${\mathcal D}$.
• 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.

## 117b – Homework 2

January 11, 2007

Due Thursday, January 18 at 1:00 pm.

## 117b – Turing degrees – Lecture 3

January 11, 2007

We presented a general framework for forcing arguments, and gave the proof of the existence of incomparable degrees in the language of forcing.

We defined the hierarchy of $\Sigma_n$ formulas and defined theories, the theory of a structure, and what it means for a theory to be decidable.

We want to show that the $\Sigma_1$ theory of ${\mathcal D}$ is decidable. For this, we will use the technique of forcing to show that there is an infinite set of independent degrees.

We defined the structure ${\mathcal D}$ of the Turing degrees as the quotient of the set of functions $f:{\mathbb N}\to{\mathbb N}$ by the equivalence relation $\equiv_T$ of recursive bi-reducibility, seen as a partial order with the order $<_T$ induced by Turing reducibility. This structure has a least degree and any degree has only countably many predecessors. It is an upper semilattice, and any countably many degrees have a common upper bound.
Generalizing the halting problem, we can define the Turing jump ${\bf a}'$ of any degree ${\bf a}$. It is strictly above ${\bf a}$ and any $A$ r.e. in ${\bf a}$ is T-reducible to ${\bf a}'$.