## 117b – Unsolvable problems – Lecture 3

At the beginning of the course we built (recursively in ${bf 0}$) two incomparable sets $A,B$. It follows that $A$ and $B$ have degrees intermediate between ${bf 0}$ and ${bf 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, so we would not be able to “fix” an initial segment of the set being constructed, as this requires that we keep some elements out of it).

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 showed 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 ${bf 0}'$.

Advertisements