Friedberg–Muchnik theorem

Remarks

The sets are built in stages by the priority method. The requirements are $R_{2e}$: $A \ne \Phi_e^B$ and $R_{2e+1}$: $B \ne \Phi_e^A$, where $\Phi_e$ is the $e$-th oracle machine. To meet $R_{2e}$, one picks a witness $x$ and puts $x$ into $A$ once $\Phi_e^B(x) = 0$ appears, then tries to keep $B$ unchanged below the use of that computation. Actions for requirements of lower priority may be undone, but each requirement is injured only finitely often, so all of them are met.

As a consequence, the degrees $\deg(A)$ and $\deg(B)$ are incomparable, so neither is $\mathbf{0}$ or $\mathbf{0}'$. So both lie strictly between $\mathbf{0}$ and $\mathbf{0}'$, which solves Post's problem.

Going deeper

For a student

This is the result that solved Post's problem, and its proof introduced the finite-injury priority method. The same method, refined, shows that the computably enumerable Turing degrees are dense (Sacks) and that every countable partial order embeds in them. The construction is also a model for many other constructions in computability theory, where infinitely many conflicting requirements must be met at once.