Fixed point theorems for precomplete numberings

Annals of Pure and Applied Logic 170 (10):1151-1161 (2019)
  Copy   BIBTEX

Abstract

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.

Links

PhilArchive



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

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

Remarks on Uniformly Finitely Precomplete Positive Equivalences.V. Shavrukov - 1996 - Mathematical Logic Quarterly 42 (1):67-82.
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.
Fixed Point Theorems on Partial Randomness.Kohtaro Tadaki - 2012 - Annals of Pure and Applied Logic 163 (7):763-774.

Analytics

Added to PP
2019-04-27

Downloads
8 (#980,062)

6 months
1 (#417,896)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Extremal Numberings and Fixed Point Theorems.Marat Faizrahmanov - 2022 - Mathematical Logic Quarterly 68 (4):398-408.
Ordinal Analysis of Partial Combinatory Algebras.Paul Shafer & Sebastiaan A. Terwijn - 2021 - Journal of Symbolic Logic 86 (3):1154-1188.
Computability in Partial Combinatory Algebras.Sebastiaan A. Terwijn - 2020 - Bulletin of Symbolic Logic 26 (3-4):224-240.

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.
Classifying Positive Equivalence Relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.
The |Lambda-Calculus.H. P. Barendregt - 1988 - Philosophical Review 97 (1):132-137.
Theorie der Numerierungen I.Ju L. Eršov - 1973 - Mathematical Logic Quarterly 19 (19‐25):289-388.

View all 13 references / Add more references