Michael Rathjen

In ordinal analysis of impredicative theories so‐called collapsing functions are of central importance. Unfortunately, the definition procedure of these functions makes essential use of uncountable cardinals whereas the notation system that they call into being corresponds to a recursive ordinal. It has long been claimed that, instead, one should manage to develop such functions directly on the basis of admissible ordinals. This paper is meant to show how this can be done. Interpreting the collapsing functions as operating directly on admissible sets also renders a new and perspicuous approach to well‐ordering proofs possible. MSC: 03F15, 03F35.

It has long been known that (classical) Peano arithmetic is, in some strong sense, “equivalent” to the variant of (classical) Zermelo–Fraenkel set theory (including choice) in which the axiom of infinity is replaced by its negation. The intended model of the latter is the set of hereditarily finite sets. The connection between the theories is so tight that they may be taken as notational variants of each other. Our purpose here is to develop and establish a constructive version of this. We present an intuitionistic theory of the hereditarily finite sets, and show that it is definitionally equivalent to Heyting Arithmetic HA, in a sense to be made precise. Our main target theory, the intuitionistic small set theory SST is remarkably simple, and intuitive. It has just one non-logical primitive, for membership, and three straightforward axioms plus one axiom scheme. We locate our theory within intuitionistic mathematics generally.

Feferman proved in 1962 [6] that any arithmetical theorem is a consequence of a suitable transfinite iteration of full uniform reflection of $\mathsf {PA}$. This result is commonly known as Feferman’s completeness theorem. The purpose of this paper is twofold. On the one hand this is an expository paper, giving two new proofs of Feferman’s completeness theorem that, we hope, shed light on this mysterious and often overlooked result. On the other hand, we combine one of our proofs with results from computable structure theory due to Ash and Knight to give sharp bounds on the order types of well-orders necessary to attain the completeness for levels of the arithmetical hierarchy.

It has long been known that (classical) Peano arithmetic is, in some strong sense, “equivalent” to the variant of (classical) Zermelo–Fraenkel set theory (including choice) in which the axiom of infinity is replaced by its negation. The intended model of the latter is the set of hereditarily finite sets. The connection between the theories is so tight that they may be taken as notational variants of each other. Our purpose here is to develop and establish a constructive version of this. We present an intuitionistic theory of the hereditarily finite sets, and show that it is definitionally equivalent to Heyting Arithmetic, in a sense to be made precise. Our main target theory, the intuitionistic small set theory is remarkably simple, and intuitive. It has just one non-logical primitive, for membership, and three straightforward axioms plus one axiom scheme. We locate our theory within intuitionistic mathematics generally.

Constructive mathematics – mathematics in which ‘there exists’ always means ‘we can construct’ – is enjoying a renaissance. Fifty years on from Bishop’s groundbreaking account of constructive analysis, constructive mathematics has spread out to touch almost all areas of mathematics and to have profound influence in theoretical computer science. This handbook gives the most complete overview of modern constructive mathematics, with contributions from leading specialists surveying the subject’s myriad aspects. Major themes include: constructive algebra and geometry, constructive analysis, constructive topology, constructive logic and foundations of mathematics, and computational aspects of constructive mathematics. A series of introductory chapters provides graduate students and other newcomers to the subject with foundations for the surveys that follow. Edited by four of the most eminent experts in the field, this is an indispensable reference for constructive mathematicians and a fascinating vista of modern constructivism for the increasing number of researchers interested in constructive approaches.

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

We characterize the proof-theoretic strength of systems of explicit mathematics with a general principle asserting the existence of least fixed points for monotone inductive definitions, in terms of certain systems of analysis and set theory. In the case of analysis, these are systems which contain the Σ12-axiom of choice and Π12-comprehension for formulas without set parameters. In the case of set theory, these are systems containing the Kripke-Platek axioms for a recursively inaccessible universe together with the existence of a stable ordinal. In all cases, the exact strength depends on what forms of induction are admitted in the respective systems

The paper investigates inaccessible set axioms and their consistency strength in constructive set theory. In ZFC inaccessible sets are of the form Vκ where κ is a strongly inaccessible cardinal and Vκ denotes the κth level of the von Neumann hierarchy. Inaccessible sets figure prominently in category theory as Grothendieck universes and are related to universes in type theory. The objective of this paper is to show that the consistency strength of inaccessible set axioms heavily depend on the context in which they are embedded. The context here will be the theory CZF− of constructive Zermelo–Fraenkel set theory but without -Induction. Let INAC be the statement that for every set there is an inaccessible set containing it. CZF−+INAC is a mathematically rich theory in which one can easily formalize Bishop style constructive mathematics and a great deal of category theory. CZF−+INAC also has a realizability interpretation in type theory which gives its theorems a direct computational meaning. The main result presented here is that the proof theoretic ordinal of CZF−+INAC is a small ordinal known as the Feferman–Schütte ordinal Γ0.

The notion of proof-theoretical or finitistic reduction of one theory to another has a long tradition. Feferman and Sieg (Buchholz et al., Iterated inductive definitions and subsystems of analysis. Springer, Berlin, 1981, Chap. 1) and Feferman in (J Symbol Logic 53:364–384, 1988) made first steps to delineate it in more formal terms. The first goal of this paper is to corroborate their view that this notion has the greatest explanatory reach and is superior to others, especially in the context of foundational theories, i.e., theories devised for the purpose of formalizing and presenting various chunks of mathematics.A second goal is to address a certain puzzlement that was expressed in Feferman’s title of his Clermont-Ferrand lectures at the Logic Colloquium 1994: “How is it that finitary proof theory became infinitary?” Hilbert’s aim was to use proof theory as a tool in his finitary consistency program to eliminate the actual infinite in mathematics from proofs of real statements. Beginning in the 1950s, however, proof theory began to employ infinitary methods. Infinitary rules and concepts, such as ordinals, entered the stage. In general, the more that such infinitary methods were employed, the farther did proof theory depart from its initial aims and methods, and the closer did it come instead to ongoing developments in recursion theory, particularly as generalized to admissible sets; in both one makes use of analogues of regular cardinals, as well as “large” cardinals (inaccessible, Mahlo, etc.). (Feferman 1994). The current paper aims to explain how these infinitary tools, despite appearances to the contrary, can be formalized in an intuitionistic theory that is finitistically reducible to (actually Π 2 0 $$\Pi ^0_2$$ -conservative over) intuitionistic first order arithmetic, also known as Heyting arithmetic. Thus we have a beautiful example of Hilbert’s program at work, exemplifying the Hilbertian goal of moving from the ideal to the real by eliminating ideal elements.

Gerhard Gentzen has been described as logic’s lost genius, whom Gödel called a better logician than himself. This work comprises articles by leading proof theorists, attesting to Gentzen’s enduring legacy to mathematical logic and beyond. The contributions range from philosophical reflections and re-evaluations of Gentzen’s original consistency proofs to the most recent developments in proof theory. Gentzen founded modern proof theory. His sequent calculus and natural deduction system beautifully explain the deep symmetries of logic. They underlie modern developments in computer science such as automated theorem proving and type theory.

Especially nice models of intuitionistic set theories are realizability models $V$, where $\mathcal A$ is an applicative structure or partial combinatory algebra. This paper is concerned with the preservation of various choice principles in $V$ if assumed in the underlying universe $V$, adopting Constructive Zermelo–Fraenkel as background theory for all of these investigations. Examples of choice principles are the axiom schemes of countable choice, dependent choice, relativized dependent choice and the presentation axiom. It is shown that any of these axioms holds in $V$ for every applicative structure $\mathcal A$ if it holds in the background universe.1 It is also shown that a weak form of the countable axiom of choice, $\textbf{AC}^{\boldsymbol{\omega, \omega }}$, is rendered true in any $V$ regardless of whether it holds in the background universe. The paper extends work by McCarty and Rathjen.

In Feferman’s work, explicit mathematics and theories of generalized inductive definitions play a central role. One objective of this article is to describe the connections with Martin–Löf type theory and constructive Zermelo–Fraenkel set theory. Proof theory has contributed to a deeper grasp of the relationship between different frameworks for constructive mathematics. Some of the reductions are known only through ordinal-theoretic characterizations. The paper also addresses the strength of Voevodsky’s univalence axiom. A further goal is to investigate the strength of intuitionistic theories of generalized inductive definitions in the framework of intuitionistic explicit mathematics that lie beyond the reach of Martin–Löf type theory.

In this article we provide an intrinsic characterization of the famous Howard–Bachmann ordinal in terms of a natural well-partial-ordering by showing that this ordinal can be realized as a maximal order type of a class of generalized trees with respect to a homeomorphic embeddability relation. We use our calculations to draw some conclusions about some corresponding subsystems of second order arithmetic. All these subsystems deal with versions of light-face Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varPi ^1_1$$\end{document}-comprehension.