Previously, both Soare and Simpson considered sets without subsets of higher -degree. Cintioli and Silvestri, for a reducibility , define the concept of a -introimmune set. For the most common reducibilities , a set does not contain subsets of higher -degree if and only if it is -introimmune. In this paper we consider -introimmune and -introimmune sets and examine how structurally easy such sets can be. In other words we ask, What is the smallest class of the Kleene's (...) class='Hi'>Hierarchy containing -introimmune sets for ? We answer the question by proving the existence of -introimmune sets in the class , bi--introimmune sets in , and bi--introimmune sets in. (shrink)

Computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930s. This theory includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, and subrecursive hierarchy classifications. Recent work in computability theory has focused on Turing definability and promises to have far-reaching mathematical, scientific, and philosophical consequences. Written by a leading researcher, Computability Theory provides a concise, comprehensive, and authoritative introduction to (...) contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The book includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable and lively way. (shrink)

Subrecursive hierarchy classifications are used to compare the complexities of recursive functions according to their derivations in a version of Kleene's equation calculus, and their computations by term-rewriting. In each case ordinal bounds are assigned, and it turns out that the respective complexity measures are given by a version of the Fast Growing Hierarchy, and the Slow Growing Hierarchy. Known comparisons between the two hierarchies then provide ordinal trade-offs between derivation and computation. Characteristics of some well-known (...) subrecursive classes are also read off. (shrink)

Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On (...) the other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element. (shrink)

The use of Extended Logics to replace ordinary second order definability in Kleene’s Ramified Analytical Hierarchy is investigated. This mirrors a similar investigation of Kennedy, Magidor and Väänänen [11] where Gödel’s universe L of constructible sets is subjected to similar variance. Enhancing second order definability allows models to be defined which may or may not coincide with the original Kleene hierarchy in domain. Extending the logic with game quantifiers, and assuming strong axioms of infinity, we obtain minimal correct (...) models of analysis. A wide spectrum of models can be so generated from abstract definability notions: one may take an abstract Spector Class and extract an extended logic for it. The resultant structure is then a minimal model of the given kind of definability. (shrink)

§1. The origins of recursion theory. In dedicating a book to Steve Kleene, I referred to him as the person who made recursion theory into a theory. Recursion theory was begun by Kleene's teacher at Princeton, Alonzo Church, who first defined the class of recursive functions; first maintained that this class was the class of computable functions ; and first used this fact to solve negatively some classical problems on the existence of algorithms. However, it was Kleene who, in (...) his thesis and in his subsequent attempts to convince himself of Church's Thesis, developed a general theory of the behavior of the recursive functions. He continued to develop this theory and extend it to new situations throughout his mathematical career. Indeed, all of the research which he did had a close relationship to recursive functions.Church's Thesis arose in an accidental way. In his investigations of a system of logic which he had invented, Church became interested in a class of functions which he called the λ-definable functions. Initially, Church knew that the successor function and the addition function were λ-definable, but not much else. During 1932, Kleene gradually showed1 that this class of functions was quite extensive; and these results became an important part of his thesis 1935a. (shrink)

Barrio et al. (_Journal of Philosophical Logic_, _49_(1), 93–120, 2020 ) and Pailos (_Review of Symbolic Logic_, _2020_(2), 249–268, 2020 ) develop an approach to define various metainferential hierarchies on strong Kleene models by transferring the idea of distinct standards for premises and conclusions from inferences to metainferences. In particular, they focus on a hierarchy named the \(\mathbb {S}\mathbb {T}\) -hierarchy where the inferential logic at the bottom of the hierarchy is the non-transitive logic ST but where (...) each subsequent metainferential logic ‘says’ about the former logic that it is transitive. While Barrio et al. ( 2020 ) suggests that this hierarchy is such that each subsequent level ‘in some intuitive sense, more classical than’ the previous level, Pailos ( 2020 ) proposes an extension of the hierarchy through which a ‘fully classical’ metainferential logic can be defined. Both Barrio et al. ( 2020 ) and Pailos ( 2020 ) explore the hierarchy in terms of semantic definitions and every proof proceeds by a rather cumbersome reasoning about those semantic definitions. The aim of this paper is to present and illustrate the virtues of a proof-theoretic tool for reasoning about the \(\mathbb {S}\mathbb {T}\) -hierarchy and the other metainferential hierarchies definable on strong Kleene models. Using the tool, this paper argues that each level in the \(\mathbb {S}\mathbb {T}\) -hierarchy is non-classical to an equal extent and that the ‘fully classical’ metainferential logic is actually just the original non-transitive logic ST ‘in disguise’. The paper concludes with some remarks about how the various results about the \(\mathbb {S}\mathbb {T}\) -hierarchy could be seen as a guide to help us imagine what a non-transitive metalogic for ST would tell us about ST. In particular, it teaches us that ST is from the perspective of ST as metatheory not only non-transitive but also transitive. (shrink)

This paper introduces an extension A of Kleene's axiomatization of Brouwer's intuitionistic analysis, in which the classical arithmetical and analytical hierarchies are faithfully represented as hierarchies of the domains of continuity. A domain of continuity is a relation R(α) on Baire space with the property that every constructive partial functional defined on {α : R(α)} is continuous there. The domains of continuity for A coincide with the stable relations (those equivalent in A to their double negations), while every relation (...) R(α) is equivalent in A to ∃αA(α, β) for some stable A(α, β) (which belongs to the classical analytical hierarchy). The logic of A is intuitionistic. The axioms of A include countable comprehension, bar induction, Troelstra's generalized continuous choice, primitive recursive Markov's Principle and a classical axiom of dependent choices proposed by Krauss. Constructive dependent choices, and constructive and classical countable choice, are theorems, A is maximal with respect to classical Kleene function realizability, which establishes its consistency. The usual disjunction and (recursive) existence properties ensure that A preserves the constructive sense of "or" and "there exists.". (shrink)