117b – Turing degrees – Lecture 4

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

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

  • First we reduce the argument to showing that any finite partial order can be embedded in D.
  • Then we argue 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 build such a family using forcing.
Advertisements

One Response to “117b – Turing degrees – Lecture 4”

  1. Abamba Says:

    This is {very|really} interesting, {You are|You’re} a very skilled blogger. {I have|I’ve} joined your {feed|rss feed} and look forward to seeking more of your {great|wonderful|fantastic|magnificent|excellent} post. Also, {I have|I’ve} shared your …

    Hey There. I found your blog using msn. This is a very well written article. I will be sure to bookmark it and come back to read more of your useful info. Thanks for the post. I’ll certainly comeback….

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s


%d bloggers like this: