Strong reducibility of partial numberings

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.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Strong reducibility of partial numberings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1766927)