117b – Homework 3

January 18, 2007

Due Thursday, January 25 at 1:00 pm.

Homework 3

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.