Reductions between types of numberings

Ian Herbert; Sanjay Jain; Steffen Lempp; Manat Mustafa; Frank Stephan

doi:10.1016/j.apal.2019.102716

Reductions between types of numberings

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

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

15 Citations (Scopus)

Abstract

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.

Original language	English
Article number	102716
Pages (from-to)	1-30
Number of pages	30
Journal	Annals of Pure and Applied Logic
Volume	170
Issue number	12
DOIs	https://doi.org/10.1016/j.apal.2019.102716
Publication status	Published - Dec 2019

Keywords

Ordinals in recursion theory
Recursively enumerable sets
Reducibilities between numberings
Theory of numberings in the difference hierarchy
n-r.e. sets

ASJC Scopus subject areas

Logic

Access to Document

10.1016/j.apal.2019.102716Licence: GNU LGPL

Cite this

@article{df18d99319f04f04a517f6f08c9250a7,

title = "Reductions between types of numberings",

abstract = "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 = "Ordinals in recursion theory, Recursively enumerable sets, Reducibilities between numberings, Theory of numberings in the difference hierarchy, n-r.e. sets",

author = "Ian Herbert and Sanjay Jain and Steffen Lempp and Manat Mustafa and Frank Stephan",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2019",

month = dec,

doi = "10.1016/j.apal.2019.102716",

language = "English",

volume = "170",

pages = "1--30",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - Reductions between types of numberings

AU - Herbert, Ian

AU - Jain, Sanjay

AU - Lempp, Steffen

AU - Mustafa, Manat

AU - Stephan, Frank

PY - 2019/12

Y1 - 2019/12

N2 - 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.

AB - 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.

KW - Ordinals in recursion theory

KW - Recursively enumerable sets

KW - Reducibilities between numberings

KW - Theory of numberings in the difference hierarchy

KW - n-r.e. sets

UR - https://www.scopus.com/pages/publications/85068438342

UR - https://www.scopus.com/pages/publications/85068438342#tab=citedBy

U2 - 10.1016/j.apal.2019.102716

DO - 10.1016/j.apal.2019.102716

M3 - Article

SN - 0168-0072

VL - 170

SP - 1

EP - 30

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 12

M1 - 102716

ER -

Reductions between types of numberings

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this