On universal pairs in the Ershov hierarchy (Q2221958)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On universal pairs in the Ershov hierarchy |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On universal pairs in the Ershov hierarchy |
scientific article |
Statements
On universal pairs in the Ershov hierarchy (English)
0 references
3 February 2021
0 references
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.
0 references
Ershov hierarchy
0 references
\( m \)-reducibility
0 references
C-class
0 references
computable numbering
0 references
