117b – Turing degrees – Lecture 4

We defined languages and structures in the model theoretic sense, and the notion of an embedding between structures of the same language.

We proved that the theory of the degrees is decidable by means of forcing:

• First we reduced the argument to showing that any finite partial order can be embedded in .
• Then we argued that for this it is enough to show that there is an infinite independent family of degrees, where independence means that no element of the family is reducible to the join of finitely many of the other members of the family.
• Finally, we built such a family using forcing.

Advertisement