On universal pairs in the Ershov hierarchy (Q2221958): Difference between revisions

A classical result of (independently) Muchnik and Smullyan is that if \(A\) and \(B\) are effectively inseparable, then \((C,D)\le_m(A,B)\) for any disjoint c.e.~sets \(C\),~\(D\). The present paper finds analogs of \((A,B)\) for every level of the Ershov hierarchy. The authors then generalize further from pairs to certain finite collections of sets -- again, for each Ershov level.