The main result of this paper is the equivalence of several definition schemas of bar recursion occurring in the literature on functionals of finite type. We present the theory of functionals of finite type, in [T] denoted byqf-WE-HA ω, which is necessary for giving the equivalence proofs. Moreover we prove two results on this theory that cannot be found in the literature, namely the deduction theorem and a derivation of Spector's rule of extensionality from [S]: ifP→T 1=T 2 (...) and Q[X∶≡T1], then P→Q[X∶≡ T2], from the at first sight weaker rule obtained by omitting “P→”. (shrink)

The technical contribution of this paper is threefold.First we show how to encode functionals in a ‘flat’ applicative structure by adding oracles to untyped λ-calculus and mimicking the applicative behaviour of the functionals with an impredicatively defined reduction relation. The main achievement here is a Church-Rosser result for the extended reduction relation.Second, by combining the previous result with the model construction based on partial equivalence relations, we show how to extend a λ-closed simple type structure to a model of (...) the polymorphic λ-calculus.Third, we specialize the previous result to a counter model against a simple minimization. This minimization is realized by a bar recursive functional, which contrasts the results of Spector and Girard which imply that the bar recursive functions are exactly those that are definable in the polymorphic λ-calculus. As a spin-off, we obtain directly the non-conservativity of the extensions of Gödel's T with bar recursion, fan functional, and Luckhardt's minimization functional, respectively. For the latter two extensions these results are new. (shrink)

In this paper we discuss the following contributions to recursion theory made by John Myhill: two sets are recursively isomorphic iff they are one-one equivalent; two sets are recursively isomorphic iff they are recursively equivalent and their complements are also recursively equivalent; every two creative sets are recursively isomorphic; the recursive analogue of the Cantor–Bernstein theorem; the notion of a combinatorial function and its use in the theory of recursive equivalence types.

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)

In transfinite arithmetic 2n is defined as the cardinality of the family of all subsets of some set v with cardinality n. However, in the arithmetic of recursive equivalence types 2N is defined as the RET of the family of all finite subsets of some set v of nonnegative integers with RET N. Suppose v is a nonempty set. S is a class over v, if S consists of finite subsets of v and has v as its (...) union. Such a class is an intersecting class over v, if every two members of S have a nonempty intersection. An IC over v is called a maximal IC , if it is not properly included in any IC over v. It is known and readily proved that every MIC over a finite set v of cardinality n ≥ 1 has cardinality 2n-1. In order to generalize this result we introduce the notion of an ω-MIC over v. This is an effective analogue ot the notion of an MIC over v such that a class over a finite set v is an ω-MIC iff it is an MIC. We then prove that every ω-MIC over an isolated set v of RET N ≥ 1 has RET 2N-1. This is a generalization, for while there only are χ0 finite sets, there are ϰ isolated sets, where c denotes the cardinality of the continuum, namely all the finite sets and the c immune sets. MSC: 03D50. (shrink)

If A and B are subsets of natural numbers we say that A is recursively equivalent to B (denoted A ≃ B) if there is a one-one partial recursive function which maps A onto B, and that A is recursively isomorphic to B (denoted A ≅ B) if there is a one-one total recursive function which maps A onto B and Ā (the complement of A) onto B#x00AF;.

We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe (...) the isomorphism types of some of these partial orders. (shrink)

We solve a longstanding problem by providing a denotational model for nondeterministic programs that identifies two programs iff they have the same range of possible behaviours. We discuss the difficulties with traditional approaches, where divergence is bottom or where a term denotes a function from a set of environments. We see that making forcing explicit, in the manner of game semantics, allows us to avoid these problems.We begin by modelling a first-order language with sequential I/O and unbounded nondeterminism. Then we (...) extend the model to a calculus with higher-order and recursive types, by adapting standard game semantics. Traditional adequacy proofs using logical relations are not applicable, so we use instead a novel hiding and unhiding argument. (shrink)

We present some abstract theorems showing how domination properties equivalent to being $\overline{GL}_{2}$ or array nonrecursive can be used to construct sets generic for different notions of forcing. These theorems are then applied to give simple proofs of some known results. We also give a direct uniform proof of a recent result of Ambos-Spies, Ding, Wang, and Yu [2009] that every degree above any in $\overline{GL}_{2}$ is recursively enumerable in a 1-generic degree strictly below it. Our major new result is (...) that every array nonrecursive degree is r.e. in some degree strictly below it. Our analysis of array nonrecursiveness and construction of generic sequences below ANR degrees also reveal a new level of uniformity in these types of results. (shrink)

The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, (...) such as the polynomial-time reducibility. In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous. (shrink)

The article investigates a system of polymorphically typed combinatory logic which is equivalent to Gödel’s T. A notion of (strong) reduction is defined over terms of this system and it is proved that the class of well-formed terms is closed under both bracket abstraction and reduction. The main new result is that the number of contractions needed to reduce a term to normal form is computed by an ε 0-recursive function. The ordinal assignments used to obtain this result are (...) also used to prove that the system under consideration is indeed equivalent to Gödel’s T. It is hoped that the methods used here can be extended so as to obtain similar results for stronger systems of polymorphically typed combinatory terms. An interesting corollary of such results is that they yield ordinally informative proofs of normalizability for sub-systems of second-order intuitionist logic, in natural deduction style. (shrink)

This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite: (a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent, (b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them. A graph $G = \langle\eta, \eta\rangle$ with η as set (...) of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs $G = \langle\nu, \eta\rangle$ with $n = \operatorname{card}(\nu), e = \operatorname{card}(\eta)$ , do generalize to isolic ω-graphs, e.g., n - 1 ≤ e ≤ n(n - 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs. The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph. An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum. (shrink)

A nonnegative interger is called a number, a collection of numbers a set and a collection of sets a class. We write ε for the set of all numbers, o for the empty set, N(α) for the cardinality of $\alpha, \subset$ for inclusion and $\subset_+$ for proper inclusion. Let α, β 1 ,...,β k be subsets of some set ρ. Then α' stands for ρ-α and β 1 ⋯ β k for β 1 ∩ ⋯ ∩ β k . For (...) subsets α 1 ,..., α r of ρ we write: $\alpha_\sigma - \{x \in v \ (\nabla i) \lbrack i \in \sigma \Rightarrow x \in \alpha_i\rbrack\} \text{for} \sigma \subset (1, \ldots, r),\\ s_i = \sum \{N(\alpha_\sigma) \mid \sigma \subset (1,\ldots, r) \& N(\sigma) = i\}, \text{for} 0 \leqq i \leqq r$ . Note that α 0 = v, hence s 0 = N(v). If the set v is finite, the classical inclusion-exclusion principle (abbreviated IEP) states $(a) N(\alpha_1 \cup \cdots \cup \alpha_r) = \sum^r_{t=1} (-1)^{t-1} s_t = \sum_{o \subset_+\sigma \subset (1,\ldots,r)}$ (b) N(α' 1 ⋯ α' r ) = ∑ r t=0 (-1) t s t = ∑ (-1) N(σ) N (α σ ). In this paper we generalize (a) and (b) to the case where α 1 ,⋯, α r are subsets of some countable but isolated set v. Then the role of the cardinality N(α) of the set α is played by the RET (recursive equivalence type) Req α of α. These generalization of (a) and (b) are proved in § 3. Since they involve recursive distinctness, this notion is discussed in § 2. In § 4l we consider a natural extension of "the sum of the elements of a finite set σ" to the case where σ is countable. § 5 deals with valuations, i.e., certain mappings μ from classes of isolated sets into the collection λ of all isols which permit us to further generalize IEP by substituting μ(α) for $\operatorname{Req} \alpha$. (shrink)

Let Λ denote the semiring of isols. We characterize existential completeness for Nerode subsemirings of Λ, by means of a purely isol-theoretic “Σ1 separation property”. Our characterization is purely isol-theoretic in that it is formulated entirely in terms of the extensions to Λ of the Σ1 subsets of the natural numbers. Advantage is taken of a special kind of isol first conjectured to exist by Ellentuck and first proven to exist by Barback . In addition, we strengthen the negative part (...) of [13] by showing that existential completeness is not secured, for a given Nerode semiring, by either a certain “functional closure” property for the extensions of partial recursive functions or the property of “pulling in” some portion of each partial recursive fiber; these latter results are perhaps a little surprising. (shrink)

Recently, Nerode and Remmel have developed a polynomial-time version of the theory of recursive equivalence types and have defined two analogues of isolatedness for that setting. This paper examines various properties of those two analogues and investigates their relationship to additive cancellability.

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic.

Several extensions of Gödel's system TT with new forms of recursion have been designed for the purpose of giving a computational interpretation to classical analysis. One can organise many of these extensions into two groups: those based on bar recursion , which include Spector's original bar recursion, modified bar recursion and the more recent products of selections functions, or those based on open recursion which in particular include the symmetric Berardi–Bezem–Coquand functional. We relate these two groups by showing that both (...) open recursion and the BBC functional are primitive recursively equivalent to a variant of modified bar recursion. Our results, in combination with existing research, essentially complete the classification up to primitive recursive equivalence of those extensions of system TT used to give a direct computational interpretation to choice principles. (shrink)

It is shown how to restrict recursion on notation in all finite types so as to characterize the polynomial-time computable functions. The restrictions are obtained by using a ramified type structure, and by adding linear concepts to the lambda calculus.

In previous work the author has introduced a lambda calculus SLR with modal and linear types which serves as an extension of Bellantoni–Cook's function algebra BC to higher types. It is a step towards a functional programming language in which all programs run in polynomial time. In this paper we develop a semantics of SLR using BCK -algebras consisting of certain polynomial-time algorithms. It will follow from this semantics that safe recursion with arbitrary result type built up from (...) N and ⊸ as well as recursion over trees and other data structures remains within polynomial time. In its original formulation SLR supported only natural numbers and recursion on notation with first-order functional result type. (shrink)

Pure Type Systems, PTSs, were introduced as a generalization of the type systems of Barendregt's lambda cube and were designed to provide a foundation for actual proof assistants which will verify proofs. Systems of illative combinatory logic or lambda calculus, ICLs, were introduced by Curry and Church as a foundation for logic and mathematics. In an earlier paper we considered two changes to the rules of the PTSs which made these rules more like ICL rules. This led to four kinds (...) of PTSs. Most importantly PTSs are about statements of the form M:A, where M is a term and A a type. In ICLs there are no explicit types and the statements are terms. In this paper we show that for each of the four forms of PTS there is an equivalent form of ICL, sometimes if certain conditions hold. (shrink)

We refine the definition of II-computability of [12] so that oracles have a “consistent”, but natural, behaviour. We prove a Kleene Normal Form Theorem and closure of semi-recursive relations under ∃1. We also show that in this more inclusive computation theory Post's theorem in the arithmetical hierarchy still holds.