GENERALIZED RECUBION THEORY II © North-Holland Publishing Company (1978) MONOTONE QUANTIFIERS AND ADMISSIBLE SETS Ion Barwise University of Wisconsin ...

Provability, Computability and Reflection.

We prove that the boundedness theorem of generalized recursion theory can be derived from the ω-completeness theorem for number theory. This yields a proof of the boundedness theorem which does not refer to the analytical hierarchy theorem.

iterations of REA operators, as well as extensions, generalizations and other applications are given in [6] while those for the ...

In [6], Metakides and Nerode introduced the study of the lattice of recursively enumerable substructures of a recursively presented model as a means to understand the recursive content of certain algebraic constructions. For example, the lattice of recursively enumerable subspaces,, of a recursively presented vector spaceV∞has been studied by Kalantari, Metakides and Nerode, Retzlaff, Remmel and Shore. Similar studies have been done by Remmel [12], [13] for Boolean algebras and by Metakides and Nerode [9] for algebraically closed fields. In all (...) of these models, the algebraic closure of a set is nontrivial., is given in §1, however in vector spaces, cl is just the subspace generated byS, in Boolean algebras, cl is just the subalgebra generated byS, and in algebraically closed fields, cl is just the algebraically closed subfield generated byS.)In this paper, we give a general model theoretic setting in which we are able to give constructions which generalize many of the constructions of classical recursion theory. One of the main features of the modelswhich we study is that the algebraic closure of setis just itself, i.e., cl = S. Examples of such models include the natural numbers under equality 〈N, = 〉, the rational numbers under the usual ordering 〈Q, ≤〉, and a large class ofn-dimensional partial orderings. (shrink)

Bailey, C. and R. Downey, Tabular degrees in \Ga-recursion theory, Annals of Pure and Applied Logic 55 205–236. We introduce several generalizations of the truth-table and weak-truth-table reducibilities to \Ga-recursion theory. A number of examples are given of theorems that lift from \Gw-recursion theory, and of theorems that do not. In particular it is shown that the regular sets theorem fails and that not all natural generalizations of wtt are the same.

The Uniformly Reflexive Structure was introduced by E. G. Wagner who showed that the theory of such structures generalized much of recursive function theory. In this paper Uniformly Reflexive Structures are constructed as factor algebras of Free nonassociative algebras. Wagner's question about the existence of a model with no computable splinter ("successor set") is answered in the affirmative by the construction of a model whose only computable sets are the finite sets and their complements. Finally, for each countable (...) Boolean algebra R of subsets of a countable set which contains the finite subsets, a model is constructed with R as its family of computable sets. (shrink)

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We (...) emphasize the algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory. (shrink)

Dominical categories are categories in which the notions of partial morphisms and their domains become explicit, with the latter being endomorphisms rather than subobjects of their sources. These categories form the basis for a novel abstract formulation of recursion theory, to which the present paper is devoted. The abstractness has of course its usual concomitant advantage of generality: it is interesting to see that many of the fundamental results of recursion theory remain valid in contexts far (...) removed from their classic manifestations. A principal reason for introducing this new formulation is to achieve an algebraization of the generalized incompleteness theorem, by providing a category-theoretic development of the concepts and tools of elementary recursion theory that are inherent in demonstrating the theorem.Dominical recursion theory avoids the commitment to sets and partial functions which is characteristic of other formulations, and thus allows for an intrinsic recursion theory within such structures as polyadic algebras. It is worthy of notice that much of elementary recursion theory can be developedwithout referencetoelements.By Gödel's generalized incompleteness theorem for consistent arithmetical systemTwe mean any statement of the following sort: if every recursive set is definable inT, thenTis essentially undecidable [41]; or if all recursive functions are definable inT, thenTis essentially undecidable [41]; or if every recursive set is definable inT, thenT0andR0 are recursively inseparable [39]; or if all re sets are representable inT, thenT0is creative [28], [39]; or ifTis a Rosser theory, thenT0andR0are effectively inseparable [39]. (shrink)

Machine generated contents note: 1. The Computability Concept;2. General Recursive Functions;3. Programs and Machines;4. Recursive Enumerability;5. Connections to Logic;6. Degrees of Unsolvability;7. Polynomial-Time Computability;Appendix: Mathspeak;Appendix: Countability;Appendix: Decadic Notation;.

The relation between least and diagonal fixed points is a well known and completely studied question for a large class of partially ordered models of the lambda calculus and combinatory logic. Here we consider this question in the context of algebraic recursion theory, whose close connection with combinatory logic recently become apparent. We find a comparatively simple and rather weak general condition which suffices to prove the equality of least fixed points with canonical (corresponding to those produced (...) by the Curry combinator in lambda calculus) diagonal fixed points in a class of partially ordered algebras which covers both combinatory spaces of Skordev and operative spaces of Ivanov. Especially, this yields an essential improvement of the axiomatization of recursion theory via combinatory spaces. (shrink)

The foundation scheme in set theory asserts that every nonempty class has an ∈\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\in $$\end{document}-minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set theory and α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}-recursion theory. We take KP set theory without foundation as the base theory. We show that KP-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} (...) \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$^-$$\end{document} + Π1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi _1$$\end{document}-Foundation + V=L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V=L$$\end{document} is enough to carry out finite injury arguments in α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}-recursion theory, proving both the Friedberg-Muchnik theorem and the Sacks splitting theorem in this theory. In addition, we compare the strengths of some fragments of KP. (shrink)

The first example of a simultaneous inductive-recursive definition in intuitionistic type theory is Martin-Löf's universe á la Tarski. A set U 0 of codes for small sets is generated inductively at the same time as a function T 0 , which maps a code to the corresponding small set, is defined by recursion on the way the elements of U 0 are generated. In this paper we argue that there is an underlying general notion of simultaneous inductive-recursive (...) definition which is implicit in Martin-Löf's intuitionistic type theory. We extend previously given schematic formulations of inductive definitions in type theory to encompass a general notion of simultaneous induction-recursion. This enables us to give a unified treatment of several interesting constructions including various universe constructions by Palmgren, Griffor, Rathjen, and Setzer and a constructive version of Aczel's Frege structures. Consistency of a restricted version of the extension is shown by constructing a realisability model in the style of Allen. (shrink)

General Process Theory (GPT) is a new (non-Whiteheadian) process ontology. According to GPT the domains of scientific inquiry and everyday practice consist of configurations of ‘goings-on’ or ‘dynamics’ that can be technically defined as concrete, dynamic, non-particular individuals called general processes. The paper offers a brief introduction to GPT in order to provide ontological foundations for research programs such as interactivism that centrally rely on the notions of ‘process,’ ‘interaction,’ and ‘emergence.’ I begin with an analysis of (...) our common sense concept of activities, which plays a crucial heuristic role in the development of the notion of a general process. General processes are not individuated in terms of their location but in terms of ‘what they do,’ i.e., in terms of their dynamic relationships in the basic sense of one process being part of another. The formal framework of GPT is thus an extensional mereology, albeit a non-classical theory with a non-transitive part-relation. After a brief sketch of basic notions and strategies of the GPT-framework I show how the latter may be applied to distinguish between causal, mechanistic, functional, self-maintaining, and recursively self-maintaining interactions, all of which involve ‘emergent phenomena’ in various senses of the term. (shrink)

When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of $\alpha$-finiteness. As examples we discuss bothcodings of models of arithmetic (...) into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal $\alpha$ is effectively close to $\omega$ (where this closeness can be measured by size or by cofinality) then such constructions maybe performed in the $\alpha$-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natu. (shrink)

The article introduces recursive ontology, a general ontology which aims to describe how being is organized and what are the processes that drive it. In order to answer those questions, I use a multidisciplinary approach that combines the theory of levels, philosophy and systems theory. The main claim of recursive ontology is that being is the product of a single recursive process of generation that builds up all of reality in a hierarchical fashion from fundamental physical particles (...) to human societies. To support this assumption, I provide the general laws and the basic principles of recursive ontology as well as a semi-formalised model of the theory based on a recursive generative grammar. Recursive ontology not only actively promotes a multidisciplinary investigation of reality, but also can be used as a general framework to develop future domain-specific theories. (shrink)

We prove a model theoretic generalization of an extension of the Keisler-Morley theorem for countable recursively saturated models of theories having a K-like model, where K is an inaccessible cardinal.

The number of studies related to natural and artificial mechanisms of learning rapidly increases. However, there is no general theory of learning that could provide a unifying basis for exploring different directions in this growing field. For a long time the development of such a theory has been hindered by nativists' belief that the development of a biological organism during ontogeny should be viewed as parameterization of an innate, encoded in the genome structure by an innate algorithm, (...) and nothing essentially new is created during this process. Noam Chomsky has claimed, therefore, that the creation of a non-trivial general mathematical theory of learning is not feasible, since any algorithm cannot produce a more complex algorithm. This study refutes the above argumentation by developing a counter-example based on the mathematical theory of algorithms and computable functions. It introduces a novel concept of a Universal Learning System (ULS) capable of learning to control in an optimal way any given constructive system from a certain class. The necessary conditions for the existence of a ULS and its main functional properties are investigated. The impossibility of building an algorithmic ULS for a sufficiently complex class of controlled objects is shown, and a proof of the existence of a non-algorithmic ULS based on the axioms of classical mathematics is presented. It is argued that a non-algorithmic ULS is a legitimate object of not only mathematics, but also the world of nature. These results indicate that an algorithmic description of the organization and adaptive development of biological systems in general is not sufficient. At the same time, it is possible to create a rigorous non-algorithmic general theory of learning as a theory of ULS. The utilization of this framework for integrating learning-related studies is discussed. (shrink)

We investigate the algebraic structure of the upper semi-lattice formed by the recursively enumerable Turing degrees. The following strong generalization of Lachlan's Nonsplitting Theorem is proved: Given n ≥ 1, there exists an r.e. degree d such that the interval $\lbrack\mathbf{d, 0'}\rbrack \subset\mathbf{R}$ admits an embedding of the n-atom Boolean algebra B n preserving (least and) greatest element, but also such that there is no (n + 1)-tuple of pairwise incomparable r.e. degrees above d which pairwise join to 0' (and (...) hence, the interval $\lbrack\mathbf{d, 0'}\rbrack \subset\mathbf{R}$ does not admit a greatest-element-preserving embedding of any lattice L which has n + 1 co-atoms, including B n + 1 ). This theorem is the dual of a theorem of Ambos-Spies and Soare, and yields an alternative proof of their result that the theory of R has infinitely many one-types. (shrink)

In this paper we prove conservation theorems for theories of classical first-order arithmetic over their intuitionistic version. We also prove generalized conservation results for intuitionistic theories when certain weak forms of the principle of excluded middle are added to them. Members of two families of subsystems of Heyting arithmetic and Buss-Harnik’s theories of intuitionistic bounded arithmetic are the intuitionistic theories we consider. For the first group, we use a method described by Leivant based on the negative translation combined with a (...) variant of Friedman’s translation. For the second group, we use Avigad’s forcing method. (shrink)

We define a class of functions, the descent recursive functions, relative to an arbitrary elementary recursive system of ordinal notations. By means of these functions, we provide a general technique for measuring the proof-theoretic strength of a variety of systems of first-order arithmetic. We characterize the provable well-orderings and provably recursive functions of these systems, and derive various conservation and equiconsistency results.

Mancosu, P., Generalizing classical and effective model theory in theories of operations and classes, Annas of Pure and Applied Logic 52 249-308 . In this paper I propose a family of theories of operations and classes with the aim of developing abstract versions of model-theoretic results. The systems are closely related to those introduced and already used by Feferman for developing his program of ‘explicit mathematics’. The theories in question are two-sorted, with one kind of variable for individuals and (...) the other for classes. The individual variables range over a domain closed under pairing and containing, among other things, natural numbers and operations.All the theories used assume a common group of axioms that insure that the individuals in the domain satisfy the conditions for a partial combinatory algebra with pairing. We also assume a class of natural numbers and a class induction axiom on . Finally there are various class existence axioms. I work mainly with three theories, FMT0, FMT and FMTΩ, which differ from each other both in their class existence axioms as well as in some further applicative axioms.These theories have various interpretations in which every object is explicitly presented by some means of definition as well as classical, or ‘standard’, set-theoretical interpretation. The systems are formulated in a flexible general language which can be used to prove abstract theorems of mathematics , thereby generalizing recursive, hyperarithmetic and admissible versions of classical mathematics.The aim of my work is to give an abstract development of portions of model theory in the afore-mentioned theories, in a way to look as much as possible like classical mathematics. Thus, FMT0 generalizes portions of countable and recursive model theory; FMT further generalizes portions of countable and hyperarithmetical model theory and finally FMTΩ provides a generalization of the classical L-completeness theorem and of an admissible version of L-completeness due to Bruce and Keisler. This continues the development of the program mentioned above, originating with Feferman. (shrink)

The class of recursive functions over the reals, denoted by , was introduced by Cristopher Moore in his seminal paper written in 1995. Since then many subsequent investigations brought new results: the class was put in relation with the class of functions generated by the General Purpose Analogue Computer of Claude Shannon; classical digital computation was embedded in several ways into the new model of computation; restrictions of were proved to represent different classes of recursive functions, e.g., recursive, primitive (...) recursive and elementary functions, and structures such as the Ritchie and the Grzergorczyk hierarchies.The class of real recursive functions was then stratified in a natural way, and and the analytic hierarchy were recently recognised as two faces of the same mathematical concept.In this new article, we bring a strong foundational support to the Real Recursive Function Theory, rooted in Mathematical Analysis, in a way that the reader can easily recognise both its intrinsic mathematical beauty and its extreme simplicity. The new paradigm is now robust and smooth enough to be taught. To achieve such a result some concepts had to change and some new results were added. (shrink)

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements (...) are disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)

The notion of a function from ℕ to ℕ defined by recursion on ordinal notations is fundamental in proof theory. Here this notion is generalized to functions on the universe of sets, using notations for well orderings longer than the class of ordinals. The generalization is used to bound the rate of growth of any function on the universe of sets that is Σ1-definable in Kripke–Platek admissible set theory with an axiom of infinity. Formalizing the argument provides (...) an ordinal analysis. (shrink)

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. (...) After a careful historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (shrink)

Induction–recursion is a powerful definition method in intuitionistic type theory. It extends inductive definitions and allows us to define all standard sets of Martin-Löf type theory as well as a large collection of commonly occurring inductive data structures. It also includes a variety of universes which are constructive analogues of inaccessibles and other large cardinals below the first Mahlo cardinal. In this article we give a new compact formalization of inductive–recursive definitions by modeling them as initial algebras (...) in slice categories. We give generic formation, introduction, elimination, and equality rules generalizing the usual rules of type theory. Moreover, we prove that the elimination and equality rules are equivalent to the principle of the existence of initial algebras for certain endofunctors. We also show the equivalence of the current formulation with the formulation of induction–recursion as a reflection principle given in Dybjer and Setzer 93). Finally, we discuss two type-theoretic analogues of Mahlo cardinals in set theory: an external Mahlo universe which is defined by induction–recursion and captured by our formalization, and an internal Mahlo universe, which goes beyond induction–recursion. We show that the external Mahlo universe, and therefore also the theory of inductive–recursive definitions, have proof-theoretical strength of at least Rathjen's theory KPM. (shrink)

We define the concept of a logic frame , which extends the concept of an abstract logic by adding the concept of a syntax and an axiom system. In a recursive logic frame the syntax and the set of axioms are recursively coded. A recursive logic frame is called complete , if every finite consistent theory has a model. We show that for logic frames built from the cardinality quantifiers “there exists at least λ ” completeness always implies .0-compactness. (...) On the other hand we show that a recursively compact logic frame need not be ℵ0-compact. (shrink)

Every acceptable numbering of an effective domain is complete. Hence every effective domain admits the 2nd recursion theorem of Eršov[1]. On the other hand for every effective domain, the 1st recursion theorem holds. In this note, we establish that for effective domains, the 2nd recursion theorem is strictly more general than the 1st recursion theorem, a generalization of an important result in recursive function theory.

How do ordinals measure the strength and computational power of formal theories? This paper is concerned with the connection between ordinal representation systems and theories established in ordinal analyses. It focusses on results which explain the nature of this connection in terms of semantical and computational notions from model theory, set theory, and generalized recursion theory.