Extremal numberings and fixed point theorems

Mathematical Logic Quarterly 68 (4):398-408 (2022)
  Copy   BIBTEX

Abstract

We consider so‐called extremal numberings that form the greatest or minimal degrees under the reducibility of all A‐computable numberings of a given family of subsets of, where A is an arbitrary oracle. Such numberings are very common in the literature and they are called universal and minimal A‐computable numberings, respectively. The main question of this paper is when a universal or a minimal A‐computable numbering satisfies the Recursion Theorem (with parameters). First we prove that the Turing degree of a set A is hyperimmune if and only if every universal A‐computable numbering satisfies the Recursion Theorem. Next we prove that any universal A‐computable numbering satisfies the Recursion Theorem with parameters if A computes a non‐computable c.e. set. We also consider the property of precompleteness of universal numberings, which in turn is closely related to the Recursion Theorem. Ershov proved that a numbering is precomplete if and only if it satisfies the Recursion Theorem with parameters for partial computable functions. In this paper, we show that for a given A‐computable numbering, in the general case, the Recursion Theorem with parameters for total computable functions is not equivalent to the precompleteness of the numbering, even if it is universal. Finally we prove that if A is high, then any infinite A‐computable family has a minimal A‐computable numbering that satisfies the Recursion Theorem.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

Fixed point theorems for precomplete numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.
Reductions between types of numberings.Ian Herbert, Sanjay Jain, Steffen Lempp, Manat Mustafa & Frank Stephan - 2019 - Annals of Pure and Applied Logic 170 (12):102716.
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.
Yet another hierarchy theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
Yet Another Hierarchy Theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
Supervaluation fixed-point logics of truth.Philip Kremer & Alasdair Urquhart - 2008 - Journal of Philosophical Logic 37 (5):407-440.
Definable fixed points in modal and temporal logics — a survey.Sergey Mardaev - 2007 - Journal of Applied Non-Classical Logics 17 (3):317-346.
Note on Some Fixed Point Constructions in Provability Logic.Per Lindström - 2006 - Journal of Philosophical Logic 35 (3):225-230.
Diagonal arguments and fixed points.Saeed Salehi - 2017 - Bulletin of the Iranian Mathematical Society 43 (5):1073-1088.

Analytics

Added to PP
2022-07-22

Downloads
8 (#1,138,312)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

On computable numberings of families of Turing degrees.Marat Faizrahmanov - forthcoming - Archive for Mathematical Logic:1-14.

Add more citations

References found in this work

On notation for ordinal numbers.S. C. Kleene - 1938 - Journal of Symbolic Logic 3 (4):150-155.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7-12):159-166.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7‐12):159-166.
Fixed point theorems for precomplete numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.

View all 6 references / Add more references