Reductions between types of numberings

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

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.

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 102,323

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

Strong reducibility of partial numberings.Dieter Spreen - 2005 - Archive for Mathematical Logic 44 (2):209-217.
A note on partial numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
Some applications of computable one-one numberings.Martin Kummer - 1990 - Archive for Mathematical Logic 30 (4):219-230.
On computable numberings of families of Turing degrees.Marat Faizrahmanov - 2024 - Archive for Mathematical Logic 63 (5):609-622.
Extremal numberings and fixed point theorems.Marat Faizrahmanov - 2022 - Mathematical Logic Quarterly 68 (4):398-408.
Fixed point theorems for precomplete numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.
On btt‐Degrees of Sets of Minimal Numbers in Gödel Numberings.Jefim Kinber - 1976 - Mathematical Logic Quarterly 23 (13‐15):201-212.

Analytics

Added to PP
2019-07-06

Downloads
25 (#902,780)

6 months
4 (#1,179,027)

Historical graph of downloads
How can I increase my downloads?