Strong reducibility of partial numberings (Q1766927)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Strong reducibility of partial numberings
scientific article

    Statements

    Strong reducibility of partial numberings (English)
    0 references
    0 references
    2 March 2005
    0 references
    In the usual definition of reducibility for numberings (\(\nu_0\) reduces to \(\nu_1\) if there exists a computable function \(f\) such that \(\nu_0=\nu_1f\)), it is not assumed that \(\text{dom}\,(\nu_0)=f^{-1}(\text{dom}\,(\nu_1))\). As a result, the behavior of reducibility on partial numberings, i.e., on the numberings whose domains are subsets of \(\omega\), differs very much from that on total numberings. The author studies the strong reducibility, i.e., the usual reducibility with the extra condition mentioned above. In particular, the author extends Ershov's completion construction and proves that the partial order on strong degrees of partial numberings of a given set is a monotone retract of the partial order of the degrees of all total numberings of the extended set and that the upper semilattice of strong degrees is isomorphic to the upper semilattice of the degrees of complete numberings of the extended set.
    0 references
    partial numbering
    0 references
    strong reducibility
    0 references
    Ershov's completion
    0 references

    Identifiers