117b – Turing degrees – Lecture 5

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

In particular, we stated the Slaman-Woodin theorems on coding countable relations inside  and on the structure of .

The coding theorem and the arithmetic definability of give a new proof of Simpson's theorem on the complexity of : Not only it is undecidable, but it is recursively isomorphic to the theory of second-order arithmetic. That is definable in first-order arithmetic will be shown as part of the second topic.

The results on  imply that there are only countably many automorphisms of , that they are all arithmetically definable, and coincide with the identity above . This was then used by Slaman and Shore to prove that the relation  iff is definable in .

We then stated Martin’s theorem on Turing Borel determinacy that any degree invariant property which is Borel as a subset of  and -cofinal holds on a cone.

Advertisement