117b – Turing degrees – Lecture 5

We finish the first topic of the course with a survey of results about the theory of D.

In particular, we state the Slaman-Woodin theorems on coding countable relations inside D and on the structure of Aut(D).

The coding theorem and the arithmetic definability of <T give a new proof of Simpson’s theorem on the complexity of Th(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 Aut(D) give that there are only countably many automorphisms of D, that they are all arithmetically definable, and coincide with the identity above 0². This was then used by Slaman and Shore to prove that the relation R(x,y) iff y=x¢ is definable in D.

We then state Martin’s theorem on Turing Borel determinacy that any degree invariant property which is Borel as a subset of 2N 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: