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′*.

## 117b – Unsolvable problems – Lecture 3

Advertisements

## Leave a Reply