132 Computability Theory Proposition: 0 is the largest recursively enumerable degree. That is, a 0 for any recursively enumerable degree a. Proof. Take an r.e. set A in a. We saw in Chapter 4 that A m K because K is a complete r.e. set. Therefore A T K. So a 0 . In 1944, Emil Post raised the question whether there were any r.e. degrees other than 0 and 0 . This question, which became known as "Post's problem," was finally answered in 1956 (two years after Post's death), independently by Richard Friedberg (in his Harvard senior thesis) and by Albert A. Muchnik in Russia. They showed that inter- mediate r.e. degrees do indeed exist, and in great profusion. (Nonetheless, there seem to be no "natural" examples of such degrees.) There is no largest degree. We will see shortly how to construct, for each degree a, a strictly larger degree a . Exercises 1. Define A B to be like A m B except not requiring that the function be com- putable. That is, A B if there exists some total function f , computable or not, for which x A f (x) B for all x. Then, is a preordering on PN . So it determines an equivalence rela- tion and a partial ordering on the quotient set. How many equivalence classes are there, and how are they ordered? Let U be the collection of computable subsets of N . Then, m (restricted to U) is a preordering on U. So it determines an equivalence relation m on U and a partial ordering on the quotient set. How many equivalence classes are there, and how are they ordered? Give an example of a set in the degree 0 that is neither recursively enumerable nor the complement of a recursively enumerable set. Assume that A and B are sets for which A m B. Show that we also have A T B. (One says that the equivalence relation m refines the equivalence relation T .) Show that for any partial function f , there is some set B such that f is a partial func- tion computable relative to B. 2. 3. 4. 5. 6.5 Structure of the Degrees Consider any two sets, say A (of degree a) and B (of degree b). Then, there are the four disjoint possibilities: G G a = b. This happens when A T B. We can think of A and B as being, in some sense, "equally complex," or as having the same "information content." a < b. This happens when A T B but A T B. We can think of A as being, in some sense, "simpler" than B is, or of having less information content than B has.