Reductions between types of numberings

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


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.



    Upload a copy of this work     Papers currently archived: 74,569

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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

8 (#980,190)

6 months
1 (#418,511)

Historical graph of downloads
How can I increase my downloads?