117b – Unsolvable problems – Lecture 3

At the beginning of the course we built (recursively in 0′) two incomparable sets A,B. It follows that A and B have degrees intermediate between 0 and 0′. The construction required that we fixed finite initial segments of A and B during an inductive construction and so it is not clear whether they are c.e. or not. (A c.e. construction would add elements to a set and we would not have complete control on what is kept out of the set). Post asked whether there is an intermediate c.e. degree and this was solved by Friedberg and Muchnik using what is now called a finite injury priority construction. We show this construction; again, 2 incomparable sets A and B are built and the construction explicitly shows they are c.e. This implies they are not recursive and have degree strictly below 0′.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: