Using the concept of notations for infinitary derivations we give an explanation of Takeuti's reduction steps on finite derivations (used in his consistency proof for Π1 1-CA) in terms of the more perspicious infinitary approach from [BS88].

We define a realizability interpretation of Aczel's Constructive Set Theory CZF into Explicit Mathematics. The final results are that CZF extended by Mahlo principles is realizable in corresponding extensions of T 0 , thus providing relative lower bounds for the proof-theoretic strength of the latter.

We define a type theory MLM, which has proof theoretical strength slightly greater then Rathjen's theory KPM. This is achieved by replacing the universe in Martin-Löf's Type Theory by a new universe V having the property that for every function f, mapping families of sets in V to families of sets in V, there exists a universe inside V closed under f. We show that the proof theoretical strength of MLM is $\geq \psi_{\Omega_1}\Omega_{{\rm M}+\omega}$ . This is slightly greater than (...) $|{\rm KPM}|$ , and shows that V can be considered to be a Mahlo-universe. Together with [Se96a] it follows $|{\rm MLM}|=\psi_{\Omega_1}(\Omega_{{\rm M}+\omega})$. (shrink)

The paper contains proof-theoretic investigation on extensions of Kripke-Platek set theory, KP, which accommodate first-order reflection. Ordinal analyses for such theories are obtained by devising cut elimination procedures for infinitary calculi of ramified set theory with Пn reflection rules. This leads to consistency proofs for the theories KP+Пn reflection using a small amount of arithmetic and the well-foundedness of a certain ordinal system with respect to primitive decending sequences. Regarding future work, we intend to avail ourselves of these new cut (...) elimination techniques to attain an ordinal analysis of П12 comprehension by approaching П12 comprehension through transfinite levels of reflection. (shrink)

§1. Introduction. The purpose of this paper is, in general, to report the state of the art of ordinal analysis and, in particular, the recent success in obtaining an ordinal analysis for the system of-analysis, which is the subsystem of formal second order arithmetic, Z2, with comprehension confined to-formulae. The same techniques can be used to provide ordinal analyses for theories that are reducible to iterated-comprehension, e.g.,-comprehension. The details will be laid out in [28].Ordinal-theoretic proof theory came into existence in (...) 1936, springing forth from Gentzen's head in the course of his consistency proof of arithmetic. Gentzen fostered hopes that with sufficiently large constructive ordinals one could establish the consistency of analysis, i.e., Z2. Considerable progress has been made in proof theory since Gentzen's tragic death on August 4th, 1945, but an ordinal analysis of Z2is still something to be sought. However, for reasons that cannot be explained here,-comprehension appears to be the main stumbling block on the road to understanding full comprehension, giving hope for an ordinal analysis of Z2in the foreseeable future.Roughly speaking,ordinally informativeproof theory attaches ordinals in a recursive representation system to proofs in a given formal system; transformations on proofs to certain canonical forms are then partially mirrored by operations on the associated ordinals. Among other things, ordinal analysis of a formal system serves to characterize its provably recursive ordinals, functions and functionals and can yield both conservation and combinatorial independence results. (shrink)

KPM is a subsystem of set theory designed to formalize a recursively Mahlo universe of sets. In this paper we show that a certain ordinal notation system is sufficient to measure the proof-theoretic strength ofKPM. This involves a detour through an infinitary calculus RS(M), for which we prove several cutelimination theorems. Full cut-elimination is available for derivations of $\Sigma (L_{\omega _1^c } )$ sentences, whereω 1 c denotes the least nonrecursive ordinal. This paper is self-contained, at least from a technical (...) point of view. (shrink)

This paper is an investigation into what could be a goodexplication of ``theory S is reducible to theory T''''. Ipresent an axiomatic approach to reducibility, which is developedmetamathematically and used to evaluate most of the definitionsof ``reducible'''' found in the relevant literature. Among these,relative interpretability turns out to be most convincing as ageneral reducibility concept, proof-theoreticalreducibility being its only serious competitor left. Thisrelation is analyzed in some detail, both from the point of viewof the reducibility axioms and of modal logic.

Hilbert's plan for understanding the concept of infinity required the elimination of non‐finitist machinery from proofs of finitist assertions. The failure of the original plan leads to a hierarchy of progressively less elementary, but still constructive methods instead of finitist ones . A mathematical proof of this failure requires a definition of « finitist ».—The paper sketches the three principal methods for the syntactic analysis of non‐constructive mathematics, the resulting consistency proofs and constructive interpretations, modelled on Herbrand's theorem, and their (...) mathematical and logical consequences. A characterization of finitist proofs is sketched. A remark on the completeness of the predicate calculus concludes the paper. Throughout open problems and alternative approaches are emphasized.ZusammenfassungHilbert sah das Verstehen des Begriffs des Unendlichen in der Eliminierung nichtfiniter Methoden aus Beweisen finiter Sätze. Das Versagen dieses Unternehmens führt zu einer Hierarchic progressiv weniger elementarer, aber noch konstruktiver Methoden, statt der finiten . Ein Unmöglichkeitsbeweis des ursprünglichen Planes setzt eine Definition von « finit » voraus.—Die drei wichtigsten Methoden der syntaktischen Analyse nichtkonstruktiver mathematischer Theorien, die daraus gewonnenen Widerspruchsfreiheitsbeweise and konstruktiven Interpretationen and deren mathematische and logische Anwendungen werden besprochen. Eine Prazisierung des Begriffs « finit » wird skizziert. Eine Bemerkung zur Vollstandigkeit des engeren Funktionenkalküls beschliesst die Abhandlung.—Oflene Fragen and komplementare Fragestellungen werden betont. (shrink)

In this paper we discuss extensions of Feferman's theory T 0 for explicit mathematics by the so-called limit and Mahlo axioms and present a novel approach to constructing natural recursion-theoretic models for systems of explicit mathematics which is based on nonmonotone inductive definitions.

In this collection of essays written over a period of twenty years, Solomon Feferman explains advanced results in modern logic and employs them to cast light on significant problems in the foundations of mathematics. Most troubling among these is the revolutionary way in which Georg Cantor elaborated the nature of the infinite, and in doing so helped transform the face of twentieth-century mathematics. Feferman details the development of Cantorian concepts and the foundational difficulties they engendered. He argues that the freedom (...) provided by Cantorian set theory was purchased at a heavy philosophical price, namely adherence to a form of mathematical platonism that is difficult to support. -/- Beginning with a previously unpublished lecture for a general audience, Deciding the Undecidable, Feferman examines the famous list of twenty-three mathematical problems posed by David Hilbert, concentrating on three problems that have most to do with logic. Other chapters are devoted to the work and thought of Kurt Gödel, whose stunning results in the 1930s on the incompleteness of formal systems and the consistency of Cantors continuum hypothesis have been of utmost importance to all subsequent work in logic. Though Gödel has been identified as the leading defender of set-theoretical platonism, surprisingly even he at one point regarded it as unacceptable. -/- In his concluding chapters, Feferman uses tools from the special part of logic called proof theory to explain how the vast part--if not all--of scientifically applicable mathematics can be justified on the basis of purely arithmetical principles. At least to that extent, the question raised in two of the essays of the volume, Is Cantor Necessary?, is answered with a resounding no. -/- This volume of important and influential work by one of the leading figures in logic and the foundations of mathematics is essential reading for anyone interested in these subjects. (shrink)

Part of the ambiguity lies in the various points of view from which this question might be considered. The crudest di erence lies between the point of view of the working mathematician and that of the logician concerned with the foundations of mathematics. Now some of my fellow mathematical logicians might protest this distinction, since they consider themselves to be just more of those \working mathematicians". Certainly, modern logic has established itself as a very respectable branch of mathematics, and there (...) are quite a few highly technical journals in logic, such as The Journal of Sym-. (shrink)

With this manifesto, John Dupré systematically attacks the ideal of scientific unity by showing how its underlying assumptions are at odds with the central conclusions of science itself.

This comprehensive monograph is a cornerstone in the area of mathematical logic and related fields. Focusing on Gentzen-type proof theory, the book presents a detailed overview of creative works by the author and other 20th-century logicians that includes applications of proof theory to logic as well as other areas of mathematics. 1975 edition.

Stephen George Simpson. with definition 1.2.3 and the discussion following it. For example, taking 90(n) to be the formula n §E Y, we have an instance of comprehension, VYEIXVn(n€X<—>n¢Y), asserting that for any given set Y there exists a ...

This volume contains articles covering a broad spectrum of proof theory, with an emphasis on its mathematical aspects. The articles should not only be interesting to specialists of proof theory, but should also be accessible to a diverse audience, including logicians, mathematicians, computer scientists and philosophers. Many of the central topics of proof theory have been included in a self-contained expository of articles, covered in great detail and depth. The chapters are arranged so that the two introductory articles come first; (...) these are then followed by articles from core classical areas of proof theory; the handbook concludes with articles that deal with topics closely related to computer science. (shrink)

The dissertation studies the mathematical strength of strict constructivism, a finitistic fragment of Bishop's constructivism, and explores its implications in the philosophy of mathematics. ;It consists of two chapters and four appendixes. Chapter 1 presents strict constructivism, shows that it is within the spirit of finitism, and explains how to represent sets, functions and elementary calculus in strict constructivism. Appendix A proves that the essentials of Bishop and Bridges' book Constructive Analysis can be developed within strict constructivism. Appendix B further (...) develops, within strict constructivism, the essentials of the functional analysis applied in quantum mechanics, including the spectral theorem, Stone's theorem, and the self-adjointness of some common quantum mechanical operators. Some comparisons with other related work, in particular, a comparison with S. Simpson's partial realization of Hilbert's program, and a discussion of the relevance of M. B. Pour-El and J. I. Richards' negative results in recursive analysis are given in Appendix C. ;Chapter 2 explores the possible philosophical implications of these technical results. It first suggests a fictionalistic account for the ontology of pure mathematics. This leaves a puzzle about how truths about fictional mathematical entities are applicable to science. The chapter then explains that for those applications of mathematics that can be reduced to applications of strict constructivism, fictional entities can be eliminated in the applications and the puzzle of applicability can be resolved. Therefore, if strict constructivism were essentially sufficient for all scientific applications, the applicability of mathematics of mathematics in science would be accountable. The chapter then argues that the reduction of mathematics to strict constructivism also reduces the epistemological question about mathematics to that about elementary arithmetic. The dissertation ends with a suggestion that a proper epistemological basis for arithmetic is perhaps a mixture of Mill's empiricism and the Kantian views. (shrink)