Annals of Pure and Applied Logic 170 (12):102716 (2019)

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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2019.102716
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,489
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Demuth Randomness and Computational Complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.

View all 8 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

A Note on Partial Numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
Strong Reducibility of Partial Numberings.Dieter Spreen - 2005 - Archive for Mathematical Logic 44 (2):209-217.
Friedberg Numberings in the Ershov Hierarchy.Serikzhan A. Badaev, Mustafa Manat & Andrea Sorbi - 2015 - Archive for Mathematical Logic 54 (1-2):59-73.
Topological Aspects of Numberings.Wolfram Menzel & Frank Stephan - 2003 - Mathematical Logic Quarterly 49 (2):129-149.
Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Some Applications of Computable One-One Numberings.Martin Kummer - 1990 - Archive for Mathematical Logic 30 (4):219-230.
Reductions in the Theory of Types.K. Jaakko Hintikka - 1966 - Journal of Symbolic Logic 31 (4):660-660.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
Combinatory Reductions and Lambda Reductions Compared.Roger Hindley - 1976 - Mathematical Logic Quarterly 23 (7-12):1169-180.
Combinatory Reductions and Lambda Reductions Compared.Roger Hindley - 1977 - Mathematical Logic Quarterly 23 (7‐12):169-180.


Added to PP index

Total views
8 ( #1,010,831 of 2,520,788 )

Recent downloads (6 months)
1 ( #405,623 of 2,520,788 )

How can I increase my downloads?


My notes