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 S_{1} 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.

### Like this:

Like Loading...

*Related*

This entry was posted on January 16, 2007 at 2:45 pm and is filed under 117b, Turing degrees. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

October 17, 2011 at 4:15 am |

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….