117b – Unsolvable problems – Lecture 3

At the beginning of the course we built (recursively in ) two incomparable sets . It follows that  and  have degrees intermediate between  and . The construction required that we fixed finite initial segments of and  during an inductive construction in such a way that the sets are given by the union of the initial segments we fix along the way, 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 go on “fixing” initial segments of the set being constructed, as this requires that we commit to keeping 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 and are built and the construction explicitly shows they are c.e. This implies they are not recursive and have degree strictly below .

Advertisement