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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 03:34, 2 February 2024

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
    0 references
    0 references
    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

    Identifiers