Due Thursday, January 25 at 1:00 pm.
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.