Kleene–Post incomparability theorem ($0<\mathbf{a},\mathbf{b}<0^{\prime },\mathbf{a}\nleqq \mathbf{b},\mathbf{b}\nleqq \mathbf{a}$)

There are incomparable Turing degrees strictly between the computable degree and the degree of the diagonal halting set. An oracle-assisted finite-extension construction alternately defeats each Turing functional in the two directions. Since the sets are computable in the halting oracle, their degrees are at most $0^{\prime }$; incomparability makes them nonzero and strictly below $0^{\prime }$. This theorem does not require the constructed sets to be computably enumerable. The Friedberg–Muchnik theorem supplies that stronger conclusion.