The noneffectivity of Arslanov’s completeness criterion and related theorems

Archive for Mathematical Logic 59 (5-6):703-713 (2020)
  Copy   BIBTEX

Abstract

We discuss the effectivity of Arslanov’s completeness criterion. In particular, we show that a parameterized version, similar to the recursion theorem with parameters, fails. We also discuss the effectivity of another extension of the recursion theorem, namely Visser’s ADN theorem, as well as that of a joint generalization of the ADN theorem and Arslanov’s completeness criterion.

Categories

Add categories

Keywords

Reprint years

DOI

10.1007/s00153-020-00712-z

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion.C. G. Jockusch, M. Lerman, R. I. Soare & R. M. Solovay - 1989 - Journal of Symbolic Logic 54 (4):1288-1323.
Completeness and cut-elimination theorems for trilattice logics.Norihiro Kamide & Heinrich Wansing - 2011 - Annals of Pure and Applied Logic 162 (10):816-835.
Three theorems of Godel.Andrew Boucher - manuscript
Reverse Mathematics and Completeness Theorems for Intuitionistic Logic.Takeshi Yamazaki - 2001 - Notre Dame Journal of Formal Logic 42 (3):143-148.
Semantical Completeness of First-Order Predicate Logic and the Weak Fan Theorem.Victor N. Krivtsov - 2015 - Studia Logica 103 (3):623-638.
On completeness and cocompleteness in and around small categories.Duško Pavlović - 1995 - Annals of Pure and Applied Logic 74 (2):121-152.
Appearance vs. Reality as a Scientific Problem.Bas C. van Fraassen - 2005 - Philosophic Exchange 35 (1):34-67.
Deductive completeness.Kosta Došen - 1996 - Bulletin of Symbolic Logic 2 (3):243-283.
An analytic completeness theorem for logics with probability quantifiers.Douglas N. Hoover - 1987 - Journal of Symbolic Logic 52 (3):802-816.
Comments on some completeness theorems of Urquhart and méndez & Salto.Kenneth Harris & Branden Fitelson - 2001 - Journal of Philosophical Logic 30 (1):51-55.
Arithmetical Completeness Theorem for Modal Logic $$mathsf{}$$.Taishi Kurahashi - 2018 - Studia Logica 106 (2):219-235.
Recursion theorems and effective domains.Akira Kanda - 1988 - Annals of Pure and Applied Logic 38 (3):289-300.
On the proof of Solovay's theorem.Dick de Jongh, Marc Jumelet & Franco Montagna - 1991 - Studia Logica 50 (1):51-69.
Applications of cut-free infinitary derivations to generalized recursion theory.Arnold Beckmann & Wolfram Pohlers - 1998 - Annals of Pure and Applied Logic 94 (1-3):7-19.
Arithmetical interpretations and Kripke frames of predicate modal logic of provability.Taishi Kurahashi - 2013 - Review of Symbolic Logic 6 (1):1-18.

Analytics

Added to PP
2020-01-22

Downloads
7 (#1,356,784)

6 months
5 (#629,136)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

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.
Kleene's amazing second recursion theorem.Yiannis N. Moschovakis - 2010 - Bulletin of Symbolic Logic 16 (2):189 - 239.
Generalizations of the recursion theorem.Sebastiaan A. Terwijn - 2018 - Journal of Symbolic Logic 83 (4):1683-1690.

Add more references