## 117b – Turing degrees – Lecture 5

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.