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

### Like this:

Like Loading...

*Related*

This entry was posted on March 12, 2007 at 1:05 pm and is filed under 117b, Unsolvable problems. 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.

## Leave a Reply