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

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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2019.04.013
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,489
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

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

Citations of this work BETA

Extremal Numberings and Fixed Point Theorems.Marat Faizrahmanov - forthcoming - Mathematical Logic Quarterly.
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

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.
Accurate Predictions and Fixed Point Theorems.Karl Egil Aubert - 1982 - Social Science Information 21 (3):323-348.
Note on Some Fixed Point Constructions in Provability Logic.Per Lindström - 2006 - Journal of Philosophical Logic 35 (3):225-230.
“Accurate Predictions and Fixed Point Theorems”: Comments.Herbert A. Simon - 1982 - Social Science Information 21 (4-5):605-612.
Fixed Point Theorems on Partial Randomness.Kohtaro Tadaki - 2012 - Annals of Pure and Applied Logic 163 (7):763-774.

Analytics

Added to PP index
2019-04-27

Total views
7 ( #1,072,226 of 2,520,788 )

Recent downloads (6 months)
1 ( #405,623 of 2,520,788 )

How can I increase my downloads?

Downloads

My notes