= Kleene–Post incomparability theorem
{c}
{title2=$0<\mathbf a,\mathbf b<0',\quad\mathbf a\not\leq\mathbf b,\ \mathbf b\not\leq\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'$; incomparability makes them nonzero and strictly below $0'$. This theorem does not require the constructed sets to be <computably enumerable>. The <Friedberg–Muchnik theorem> supplies that stronger conclusion.
Back to article page
