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 2^{N }and <_{T}-cofinal holds on a *cone*.

### Like this:

Like Loading...

*Related*

This entry was posted on January 18, 2007 at 3:58 pm and is filed under 117b, Turing degrees. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply