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 \Sigma_1 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 {\mathcal D}.
  • 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: