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 )

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: