# Post’s Degrees of Unsolvability

Post [42] does it by comparing the complexity of two sets A, *B* c N using several methods of *reducing effectively* the relation of membership in A to that of membership in *B*. The strongest of these is *one-one reducibility**,*

close to the mildly weaker *many-one reducibility* A <_{m} *B* where it is not required that *v _{e}* be an injection. The weakest and most important is

*Turing reducibility*

*,*

We will also use the strict and symmetric versions of these reducibilities,

and similarly for *< _{m}, =_{m}, <_{T}, =_{T}*.

The symmetric relations induce natural notions of *degrees**,* e.g.,

the 1 -1 degree of A = di *(A) ={B : B* = A},

the Turing degree of A = d(*A) = {B : B = _{T}* A};

and the central objects of study are these sets of degrees with their natural partial orders, most significantly the *poset of Turing degrees (**D**,* <_{T}) where

Post focusses on the study of the degrees of *recursively enumerable* sets (App 7). He introduces the “self-referential” version of Turing’s *Halting Problem*

and proves that it is *r.e. complete**,* i.e., it is r.e. and every r.e. set is 1-1 reducible to it. In particular *K* is not recursive, and then the natural question is whether there are r.e. sets intermediate in complexity between the recursive sets and *K*. Post proves this for all of his reducibilities except for Turing’s and asks what became known as *Post’s Problem*: *is there an r.e. set* A *such that 0 < _{T} A <_{T} K*? Friedberg and Muchnik proved that there is, some ten years later, and this initiated a research program in the theory of degrees and r.e. degrees which is still vibrant today.