Reductions between types of numberings

DOI10.1016/J.APAL.2019.102716MaRDI QIDQ2326424zbMATH OpenOpenAlexWikidataFDO

Authors Ian Herbert, Sanjay Jain, Steffen Lempp, Frank Stephan, Mustafa Manat

Publication date 7 October 2019

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2019.102716

n-r.e. sets ordinals in recursion theory recursively enumerable sets reducibilities between numberings theory of numberings in the difference hierarchy

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Review text

In this article, the authors obtain a wide collection of results concerning \(k\)-r.e. numberings, \(k\) a positive integer, left-r.e. numberings and \(\alpha\)-r.e. numberings for recursive ordinals \(\alpha\geq \omega\). From the summary: ``This paper considers reductions between types of numberings; these reductions preserve the Rogers semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the \(k\)-r.e. numberings to the \((k+1)\)-r.e. numberings; all further reductions are obtained by concatenating these reductions.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Reductions between types of numberings

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