This paper studies the extent to which probability functions are recursively definable. It proves, in particular, that the (absolute) probability of a statement A is recursively definable from a certain point on, to wit: from the (absolute) probabilities of certain atomic components and conjunctions of atomic components of A on, but to no further extent. And it proves that, generally, the probability of a statement A relative to a statement B is recursively definable from a certain point (...) on, to wit: from the probabilities relative to that very B of certain atomic components and conjunctions of atomic components of A, but again to no further extent. These and other results are extended to the less studied case where A and B are compounded from atomic statements by means of `` ∀ '' as well as `` ∼ '' and "&". The absolute probability functions considered are those of Kolmogorov and Carnap, and the relative ones are those of Kolmogorov, Carnap, Renyi, and Popper. (shrink)

Let KP- be the theory resulting from Kripke-Platek set theory by restricting Foundation to Set Foundation. Let G: V → V (V:= universe of sets) be a ▵0-definable set function, i.e. there is a ▵0-formula φ(x, y) such that φ(x, G(x)) is true for all sets x, and $V \models \forall x \exists!y\varphi (x, y)$ . In this paper we shall verify (by elementary proof-theoretic methods) that the collection of set functions primitive recursive in G coincides with the collection (...) of those functions which are Σ1-definable in KP- + Σ1-Foundation + ∀ x ∃!yφ (x, y). Moreover, we show that this is still true if one adds Π1-Foundation or a weak version of ▵0-Dependent Choices to the latter theory. (shrink)

Although the theory of definability had many important antecedents—such as the descriptive set theory initiated by the French semi-intuitionists in the early 1900s—the main ideas were first laid out in precise mathematical terms by Alfred Tarski beginning in 1929. We review here the basic notions of languages, explicit definability, and grammatical complexity, and emphasize common themes in the theories of definability for four important languages underlying, respectively, descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic. We (...) review the history of previous studies of the similarities and differences in the theories of definability of the first three of these four languages. A seminal role leading toward unification of the theories has been played by the separation principles introduced by Nikolai Luzin in 1927. Emphasizing analogies and driving toward further unification embracing finite-universe logic we concentrate on a simple example—the first and second separation principles for existential-universal first-order sentences . Using this as a test case for the fundamental problem of how to “finitize” arguments in classical pure logic to the finite-universe case, we are led to the analogous negative solution by using the theory of certain special graphs: a graph is - special for any positive integers m , n , p , q iff it is bipartite with m red points and n blue points and for every p -tuple of red points there is a blue point to which they are all connected . As an aside we introduce for further study a natural “Ramseyesque” increasing sequence A of positive integers, where A is the least positive integer n for which an -special graph exists. (shrink)

The paper builds on a simply typed term system ${\cal PR}^\omega $ providing a notion of partial primitive recursive functional on arbitrary Scott domains $D_\sigma$ that includes a suitable concept of parallelism. Computability on the partial continuous functionals seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (SCVR) is not reducible to partial primitive recursion. So an extension ${\cal PR}^{\omega e}$ is studied that is closed under SCVR and yet stays within the realm of subrecursiveness. The twist (...) are certain type 1 Gödel recursors ${\cal R}_k$ for simultaneous partial primitive recursion. Formally, the value ${\cal R}_k\vec{g}\vec{H} x i$ is a function $f_i$ of type $\iota \to \iota$ , however, ${\cal R}_k$ is modelled such that $f_i$ is a finite element of $D_{\iota\to\iota}$ or in other words, a partial sequence. It is shown that the Ackermann function is not definable in ${\cal PR}^{\omega e}$. (shrink)

The subject of this paper is a characterization of the $\Sigma_1$ -definable set functions of Kripke-Platek set theory with infinity and a uniform version of axiom of choice: $KP\omega+(uniform\;AC)$ . This class of functions is shown to coincide with the collection of set functionals of type 1 primitive recursive in a given choice functional and $x\mapsto\omega$ . This goal is achieved by a Gödel Dialectica-style functional interpretation of $KP\omega+(uniform\;AC)$ and a computability proof for the involved functionals.

The class of all recursive functions fails to possess a natural hierarchical structure, generated predicatively from "within". On the other hand, many (proof-theoretically significant) sub-recursive classes do. This paper attempts to measure the limit of predicative generation in this context, by classifying and characterizing those (predictably terminating) recursive functions which can be successively defined according to an autonomy condition of the form: allow recursions only over well-orderings which have already been "coded" at previous levels. The question is: how can (...) a recursion code a well-ordering? The answer lies in Girard's theory of dilators, but is reworked here in a quite different and simplified framework specific to our purpose. The "accessible" recursive functions thus generated turn out to be those provably recursive in $(\prod_{1}^{1}-CA)_{0}$. (shrink)

§1. Introduction. Natural sets that can be enumerated by a computable function always seem to be either actually computable or of the same complexity as the Halting Problem, the complete r.e. set K. The obvious question, first posed in Post [1944] and since then called Post's Problem is then just whether there are r.e. sets which are neither computable nor complete, i.e., neither recursive nor of the same Turing degree as K?Let be the r.e. degrees, i.e., the r.e. sets (...) modulo the equivalence relation of equicomputable with the partial order induced by Turing computability. This structure is a partial order with least element 0, the degree of the computable sets, and greatest element 1 or 0′, the degree of K. Post's problem then asks if there are any other elements of.The solution of Post's problem by Friedberg [1957] and Muchnik [1956] was followed by various algebraic or order theoretic results that were interpreted as saying that the structure was in some way well behaved:Theorem 1.1. Every countable partial ordering or even uppersemilattice can be embedded into.Theorem 1.2. For every nonrecursive r.e. degreeathere are r.e. degreesb, c < asuch thatb ∨ c = a.Theorem 1.3. For every pair of nonrecursive r.e. degreesa < bthere is an r.e. degreecsuch thata < c < b. (shrink)

We present a well-defined generalisation of the core to coalitional games with externalities, where the value of a deviation is given by an endogenous response, the solution (if nonempty: the core) of the residual game.

We define, in the spirit of Fenstad [2], a higher type computation theory, and show that countable recursion over the continuous functionals forms such a theory. We also discuss Hyland's proposal from [4] for a scheme with which to supplement S1-S9, and show that this augmented set of schemes fails to generate countable recursion. We make another proposal to which the methods of this section do not apply.

It is shown how the strong ordinal notation systems that figure in proof theory and have been previously defined by employing large cardinals, can be developed directly on the basis of their recursively large counterparts. Thereby we provide a completely new approach to well-ordering proofs as will be exemplified by determining the proof-theoretic ordinal of the systemKPM of [R91].

A type-structure of partial effective functionals over the natural numbers, based on a canonical enumeration of the partial recursive functions, is developed. These partial functionals, defined by a direct elementary technique, turn out to be the computable elements of the hereditary continuous partial objects; moreover, there is a commutative system of enumerations of any given type by any type below (relative numberings). By this and by results in [1] and [2], the Kleene-Kreisel countable functionals and the hereditary effective operations (...) (HEO) are easily characterized. (shrink)

A new proof is given of the celebrated theorem of M. Davis, H. Putnam and J. Robinson concerning exponential Diophantine representation of recursively enumerable predicates. The proof goes by induction on the defining scheme of a partial recursive function.

The idea of this paper is to approach linear orderings as generalized ordinals and to study how they are made from their initial segments. First we look at how the equality of two linear orderings can be expressed in terms of equality of their initial segments. Then we shall use similar methods to define functions by recursion with respect to the initial segment relation. Our method is based on the use of a game where smaller and smaller initial segments of (...) linear orderings are considered. The length of the game is assumed to exceed that of the descending sequences of elements of the linear orderings considered. By use of such game-theoretical methods we can for example extend the recursive definitions of the operations of sum, product and exponentiation of ordinals in a unique and natural way for arbitrary linear orderings. Extensions coming from direct limits do not satisfy our game-theoretic requirements in general. We also show how our recursive definitions allow very simple constructions for fixed points of functions, giving rise to certain interesting linear orderings. (shrink)

The paper builds on both a simply typed term system ${\cal PR}^\omega$ and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains $D_\rho$ supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions ${\cal PR}^{\omega e}$ and PTWP $^e$ are studied that (...) are closed under scvr. The twist are certain type 1 Gödel recursors ${\cal R}_k$ for simultaneous partial primitive recursion. Formally, ${\cal R}_k\vec{g}\vec{H}xi$ denotes a function $f_i \in D_{\iota\to\iota}$ , however, ${\cal R}_k$ is modelled such that $f_i$ is finite, or in other words, a partial sequence. As for PTWP $^e$ , the concept of type $\iota\to\iota$ writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP $^e$ -computable functionals coincide with those definable in ${\cal PR}^{\omega e}$ plus a constant for sequential minimisation. In particular, the functionals definable in ${\cal PR}^{\omega e}$ denoted ${\cal R}^{\omega e}$ can be characterised by a subclass of PTWP $^e$ -computable functionals denoted ${\rm PPR}^{\omega e}$ . Moreover, hierarchies of strictly increasing classes ${\cal R}^{\omega e}_n$ in the style of Heinermann and complexity classes ${\rm PPR}^{\omega e}_n$ are introduced such that $\forall n\ge 0. {\cal R}^{\omega e}_n ={\rm PPR}^{\omega e}_n$ . These results extend those for ${\cal PR}^\omega$ and PTWP [Nig94]. Finally, scvr is employed to define for each type $\sigma$ the enumeration functional $E^\sigma$ of all finite elements of $D_\sigma$. (shrink)

The last Episode wasn’t about logic or formal theories at all: it was about common-or-garden arithmetic and the informal notion of computability. We noted that addition can be defined in terms of repeated applications of the successor function. Multiplication can be defined in terms of repeated applications of addition. The exponential and factorial functions can be defined, in different ways, in terms of repeated applications of multiplication. There’s already a pattern emerging here! The main task in (...) the last Episode was to get clear about this pattern. So first we said more about the idea of defining one function in terms of repeated applications of another function. Tidied up, that becomes the idea of defining a function by primitive recursion (Defn. 27). (shrink)

We use two logical resources, namely, the notion of recursively defined function and the Benardete-Yablo paradox, together with some inherent features of causality and time, as usually conceived, to derive two results: that no ungrounded causal chain exists and that time has a beginning.

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.

Let N, O and S denote the set of nonnegative integers, the graph of the constant 0 function and the graph of the successor function respectively. For sets $P, Q, R \subseteq N^2$ operations of transposition, composition, and bracketing are defined as follows: $P^\cup = \{\langle x, y\rangle | \langle y, x\rangle \epsilon P\}, PQ = \{\langle x, z\rangle| \exists y\langle x, y\rangle \epsilon P & \langle y, z\rangle \epsilon Q\}$ , and [ P, Q, R] = (...) ∪n ε M(PnQR n). THEOREM. The class of recursively enumerable subsets of N2 is the smallest class of sets with O and S as members and closed under transposition, composition, and bracketing. This result is derived from a characterization by Julia Robinson of the class of general recursive functions of one variable in terms of function composition and "definition by general recursion." A key step in the proof is to show that if a function F is defined by general recursion from functions A, M, P and R then F = [ P∪, A∪ M, R]. The above definitions of the transposition, composition, and bracketing operations on subsets of N2 can be generalized to subsets of X2 for an arbitrary set X. In this abstract setting it is possible to show that the bracket operation can be defined in terms of K, L, transposition, composition, intersection, and reflexive transitive closure where K: X → X and L: X → X are functions for decoding pairs. (shrink)

Schwichtenberg showed that the System T definable functionals are closed under a rule-like version Spector’s bar recursion of lowest type levels 0 and 1. More precisely, if the functional Y which controls the stopping condition of Spector’s bar recursor is T-definable, then the corresponding bar recursion of type levels 0 and 1 is already T-definable. Schwichtenberg’s original proof, however, relies on a detour through Tait’s infinitary terms and the correspondence between ordinal recursion for α < ε₀ and primitive recursion over (...) finite types. This detour makes it hard to calculate on given concrete system T input, what the corresponding system T output would look like. In this paper we present an alternative (more direct) proof based on an explicit construction which we prove correct via a suitably defined logical relation. We show through an example how this gives a straightforward mechanism for converting bar recursive definitions into T-definitions under the conditions of Schwichtenberg’s theorem. Finally, with the explicit construction we can also easily state a sharper result: if Y is in the fragment Tᵢ then terms built from BR^ℕ,σ for this particular Y are definable in the fragment T_i+max{1,level(σ)}+2. (shrink)

We show that Spector's “restricted” form of bar recursion is sufficient (over system T) to define Spector's search functional. This new result is then used to show that Spector's restricted form of bar recursion is in fact as general as the supposedly more general form of bar recursion. Given that these two forms of bar recursion correspond to the (explicitly controlled) iterated products of selection function and quantifiers, it follows that this iterated product of selection functions is T‐equivalent to (...) the corresponding iterated product of quantifiers. (shrink)

Zaionc, M., λ-Definability on free algebras, Annals of Pure and Applied Logic 51 279-300. A λ-language over a simple type structure is considered. There is a natural isomorphism which identifies free algebras with nonempty second-order types. If A is a free algebra determined by the signature SA = [α1,...,αn], then by a type τA we mean τ1,...,τn→0 where τi=0αi→0. It can be seen that closed terms of the type τA reflex constructions in the algebra A. Therefore any term of the (...) type n→τA defines some n-ary mapping in algebra A. The problem is to characterize λ-definable mappings in any free algebra. It is proved that the set of λ-definable operations is the minimal set that contains constant functions and projections and is closed under composition and limited recursion. This result is a generalization of the result of Schwichtenberg and Statman which characterize the λ-definable functions over the natural number type →, i.e algebra [1, 0], as well as of the result of Zaionc for λ-definable word operations over type n→, i.e algebra [1,...,1,0], and of the results about λ-definable tree operations , i.e in algebra [2, 0]. Some of the examples in Section 5 are based on a publication of Zaionc. (shrink)

We define a class of so-called ∑-sets as a natural closure of recursively enumerable sets Wn under the relation “∈” and study its properties.

We develop the concepts of recursively nowhere dense sets and sets that are recursively of first category and study closed sets of points in light of Baire's Category Theorem. Our theorems are primarily concerned with exdomains of recursive quantum functions and hence with avoidable points . An avoidance function is a recursive function which can be used to expel avoidable points from domains of recursive quantum functions. We define an avoidable set of points to be an (...) arbitrary subset of the avoidable points of a single avoidance function, and we study an effective union of such sets which we call a piecemeal avoidable set. We note that each of ‘the set of recursive points’ and ‘the set of avoidable points’ is of first category but not recursively of first category. We show an exdomain exists which is recursively nowhere dense, as well as one that is nowhere dense but not recursively nowhere dense. After establishing that every exdomain is recursively of first category, we prove that given any fixed exdomain, there is another exdomain, which while dense in the underlying space, is disjoint from the fixed exdomain. Finally, we show how to build a recursive sequence of recursive quantum functions that have mutually disjoint, dense exdomains. (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)

We introduce a system of simply typed lambda terms and show that a rather comprehensive class of recursion equations on streams or non-wellfounded trees can be solved in our system. Moreover certain conditions are presented which guarantee that the defined functionals are primitive recursive. As a major example we give a co-recursive treatment of Mints’ continuous cut-elimination operator.

We model infinite regress structures — not arguments — by means of ungrounded recursively defined functions in order to show that no such structure can perform the task of providing determination to the items composing it, that is, that no determination process containing an infinite regress structure is successful.

We model infinite regress structures -not arguments- by means of ungrounded recursively defined functions in order to show that no such structure can perform the task of providing determination to the items composing it, that is, that no determination process containing an infinite regress structure is successful.

A realizability notion that employs only primitive recursive functions is defined, and, relative to it, the soundness of the fragment of Heyting Arithmetic (HA) in which induction is restricted to Σ 0 1 formulae is proved. A dual concept of falsifiability is proposed and an analogous soundness result is established for a further restricted fragment of HA.

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)

We study punctual categoricity on a cone and intrinsically punctual functions and obtain complete structural characterizations in terms of model-theoretic notions. As a corollary, we answer a question of Bazhenov, Downey, Kalimullin, and Melnikov by showing that relational structures are not punctually universal. We will also apply this characterisation to derive an algebraic characterisation of relatively punctually categorical mono-unary structures.

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 define the concept of a system function language which is a language generated by a system function. We identify system function languages with recursively enumerable sets which are non-simple and co-infinite. We then define restricted system function languages and identify them with recursive sets which are co-infinite. Finally we state and prove some independence and dependence relationships between system function languages and some of the more well-known decision problems. MSC: 03D05, (...) 03D20, 03D25. (shrink)

The set of unary functions of complexity classes defined by using bounded primitive recursion is inductively characterized by means of bounded iteration. Elementary unary functions, linear space computable unary functions and polynomial space computable unary functions are then inductively characterized using only composition and bounded iteration.

In the first author's thesis [10], a sequential language, LRT, for real number computation is investigated. That thesis includes a proof that all polynomials are programmable, but that work comes short of giving a complete characterization of the expressive power of the language even for first-order functions. The technical problem is that LRT is non-deterministic. So a natural characterization of its expressive power should be in terms of relations rather than in terms of functions. In [2], Brattka examines a formalization (...) of recursive relations in the style of Kleene's recursive functions on the natural numbers. This paper is an expanded version of [13] which establishes the expressive power of LRTp, a variant of LRT, in terms of Brattka's recursive relations. Because Brattka already did the work of establishing the precise connection between his recursive relations and Type 2 Theory of Effectivity, we thus obtain a complete characterization of first-order definability in LRTp. (shrink)

Extending Gödel's Dialectica interpretation, we provide a functional interpretation of classical theories of positive arithmetic inductive definitions, reducing them to theories of finite-type functionals defined using transfinite recursion on well-founded trees.

Local connectedness functions for (κ, 1)-simplified morasses, localisations of the coupling function c studied in [M96, §1], are defined and their elementary properties discussed. Several different, useful, canonical ways of arriving at the functions are examined. This analysis is then used to give explicit formulae for generalisations of the local distance functions which were defined recursively in [K00], leading to simple proofs of the principal properties of those functions. It is then extended to the properties of (...) local connectedness functions in the context of κ-M-proper forcing for sucessor κ. The functions are shown to enjoy substantial strengthenings of the properties (particularly the ∆-properties) hitherto proved for both c and for Todorcevic’s ρ-functions in the special case κ = ω1. A couple of examples of the use of local connectedness functions in consort with κ-M-proper forcing are then given. (shrink)

Let F be a signature and R a strictly orthogonal rewrite system on ground terms of F . We give an effective proof of a bounding condition for R , based on a detailed analysis of how terms are transformed during the rewrite process, which allows us to give recursive bounds on the derivation lengths of terms. We give a syntactic characterisation of the Grzegorczyk hierarchy and a rewriting schema for calculating its functions. As a consequence of this, using results (...) of Elias Tahhan–Bittar, it can be shown that, for n⩾3 , the derivation length functions for functions in Grzegorczyk class E n belong to Grzegorczyk class E n+1 . We also give recursive bounds for the derivation lengths of functions defined by parameter recursion. (shrink)

In 1958 Gödel published his Dialectica interpretation, which reduces classical arithmetic to a quantifier-free theory T axiomatizing the primitive recursive functionals of finite type. Here we extend Gödel's T to theories Pn of “predicative” functionals, which are defined using Martin-Löf's universes of transfinite types. We then extend Gödel's interpretation to the theories of arithmetic inductive definitions IDn, so that each IDn is interpreted in the corresponding Pn. Since the strengths of the theories IDn are cofinal in the ordinal Γ0, (...) as a corollary this analysis provides an ordinal-free characterization of the <Γ0-recursive functions. (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)

In recent years, proof theoretic transformations that are based on extensions of monotone forms of Gödel’s famous functional interpretation have been used systematically to extract new content from proofs in abstract nonlinear analysis. This content consists both in effective quantitative bounds as well as in qualitative uniformity results. One of the main ineffective tools in abstract functional analysis is the use of sequential forms of weak compactness. As we recently verified, the sequential form of weak compactness for bounded closed and (...) convex subsets of an abstract Hilbert space can be carried out in suitable formal systems that are covered by existing metatheorems developed in the course of the proof mining program. In particular, it follows that the monotone functional interpretation of this weak compactness principle can be realized by a functional Ω∗ definable from bar recursion of lowest type. While a case study on the analysis of strong convergence results that are based on weak compactness indicates that the use of the latter seems to be eliminable, things apparently are different for weak convergence theorems such as the famous Baillon nonlinear ergodic theorem. For this theorem we recently extracted an explicit bound on a metastable version of this theorem that is primitive recursive relative to Ω∗.In the current paper we for the first time give the construction of Ω∗ . As a corollary to the fine analysis of the use of bar recursion in this construction we obtain that Ω∗ elevates arguments in Tn at most to resulting functionals in Tn+2 . In particular, one can conclude from this that our bound on Baillon’s theorem is at least definable in T4. (shrink)

Let R be a real closed field, and X⊆Rm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X\subseteq R^m}$$\end{document} semi-algebraic and 1-dimensional. We consider complete first-order theories of modules over the ring of continuous semi-algebraic functions X→R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X\to R}$$\end{document} definable with parameters in R. As a tool we introduce -piecewise vector bundles on X and show that the category of piecewise vector bundles on X is equivalent to the category of syzygies of (...) finitely generated submodules of free modules. We give an explicit method to determine the Baur–Monk invariants of free modules in terms of pre-piecewise vector bundles. When R is a recursive real closed field this yields the decidability of the theory of free modules. Where it makes sense, we address the same questions for continuous definable functions in o-minimal expansions of a real closed field. From the free module case we are able to deduce generalisations of some results to arbitrary modules over the ring. We present a geometrically motivated quantifier elimination result down to the level of positive primitive formulae with a certain block decomposition of the matrix of coefficients. (shrink)

A new games model of the language FPC, a type theory with products, sums, function spaces and recursive types, is described. A definability result is proved, showing that every finite element of the model is the interpretation of some term of the language.

In [1] the class of safe recursive functions over an arbitrary structure is defined. We prove that in this class, one cannot define a total pairing function independently of the structure.

The Dialectica-style functional interpretation of Kripke-Platek set theory with infinity ( $\hbox{\sf KP} \omega$ ) given in [1] uses a choice functional (which is not a definable set function of ( $hbox{\sf KP} \omega$ ). By means of a Diller-Nahm-style interpretation (cf. [4]) it is possible to eliminate the choice functional and give an interpretation by set functionals primitive recursive in $x\mapsto\omega$ . This yields the following characterization: The class of $\Sigma$ -definable set functions of $\hbox{\sf KP} \omega$ coincides (...) with the collection of set functionals of type 1 primitive recursive in $x\mapsto \omega$. (shrink)

We define an applicative theoryCL 2 similar to combinatory logic which can be interpreted in classes of functions possessing an enumerating function. In contrast to the models of classical combinatory logic, it is not necessarily assumed that the enumerating function itself belongs to that function class. Thereby we get a variety of possible models including e. g. the classes of primitive recursive, recursive, elementary, polynomial-time comptable ofɛ 0-recursive functions.We show that inCL 2 a major part of the (...) metatheory of enumerated classes of functions can be developed. Namely, a kind of λ-abstraction can be defined and abstract versions of theS n m - and (Primitive) Recursion Theorems are proved. Thereby, a closer analysis of the phenomenon of the different recursion theorems is achieved.A theory closely related toCL 2 can be used to replace the applicative part of Feferman's theories for explicit mathematics. So this work can be seen as an answer to Feferman's question to formulate a theory for explicit mathematics in which operations can be interpreted as primitive recursive or even more feasible ones.Finally it is shown that the proof-theoretical strength of various theoreies for explicit mathematics is preserved when replacing the applicative part of the theories by our theory together with an operation for primitive recursion. (shrink)