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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: