117b – Homework 2

January 11, 2007

Due Thursday, January 18 at 1:00 pm.

Homework 2


117b – Turing degrees – Lecture 3

January 11, 2007

We presented a general framework for forcing arguments, and gave the proof of the existence of incomparable degrees in the language of forcing.

We defined the hierarchy of \Sigma_n formulas and defined theories, the theory of a structure, and what it means for a theory to be decidable.

We want to show that the \Sigma_1 theory of {\mathcal D} is decidable. For this, we will use the technique of forcing to show that there is an infinite set of independent degrees.

Additional reference:

  • Degree structures: local and global investigations, by R. Shore. Bulletin of Symbolic Logic 12 (3) (2006), 369-389.