This book brings together philosophers, mathematicians and logicians to penetrate important problems in the philosophy and foundations of mathematics. In philosophy, one has been concerned with the opposition between constructivism and classical mathematics and the different ontological and epistemological views that are reflected in this opposition. The dominant foundational framework for current mathematics is classical logic and set theory with the axiom of choice. This framework is, however, laden with philosophical difficulties. One important alternative foundational programme that is actively pursued (...) today is predicativistic constructivism based on Martin-Löf type theory. Associated philosophical foundations are meaning theories in the tradition of Wittgenstein, Dummett, Prawitz and Martin-Löf. What is the relation between proof-theoretical semantics in the tradition of Gentzen, Prawitz, and Martin-Löf and Wittgensteinian or other accounts of meaning-as-use? What can proof-theoretical analyses tell us about the scope and limits of constructive and predicative mathematics? (shrink)

We look for a converse to a result from [N. Thapen, A model-theoretic characterization of the weak pigeonhole principle, Annals of Pure and Applied Logic 118 175–195] that if the weak pigeonhole principle fails in a model K of bounded arithmetic, then there is an end-extension of K interpretable inside K. We show that if a model J of an induction-free theory of arithmetic is interpretable inside K, then either J is isomorphic to an initial segment of K , or (...) K is isomorphic to an initial segment of J and in this case the weak pigeonhole principle fails in K. This result is formulated in terms of a theory of bounded arithmetic with a greatest element. We go on to consider structures defined by oracles, and use the probabilistic witnessing theorem for to give a general criterion for what can be proved about these using the weak pigeonhole principle. We also show that the injective WPHP is not provable in this theory in the relativized case. (shrink)

The paper relativizes the method of ordinal analysis developed for Kripke–Platek set theory to theories which have the power set axiom. We show that it is possible to use this technique to extract information about Power Kripke–Platek set theory, KP.As an application it is shown that whenever KP+AC proves a ΠP2 statement then it holds true in the segment Vτ of the von Neumann hierarchy, where τ stands for the Bachmann–Howard ordinal.

Saunders Mac Lane has drawn attention many times, particularly in his book Mathematics: Form and Function, to the system of set theory of which the axioms are Extensionality, Null Set, Pairing, Union, Infinity, Power Set, Restricted Separation, Foundation, and Choice, to which system, afforced by the principle, , of Transitive Containment, we shall refer as . His system is naturally related to systems derived from topos-theoretic notions concerning the category of sets, and is, as Mac Lane emphasises, one that is (...) adequate for much of mathematics. In this paper we show that the consistency strength of Mac Lane's system is not increased by adding the axioms of Kripke–Platek set theory and even the Axiom of Constructibility to Mac Lane's axioms; our method requires a close study of Axiom H, which was proposed by Mitchell; we digress to apply these methods to subsystems of Zermelo set theory , and obtain an apparently new proof that is not finitely axiomatisable; we study Friedman's strengthening of , and the Forster–Kaye subsystem of , and use forcing over ill-founded models and forcing to establish independence results concerning and ; we show, again using ill-founded models, that proves the consistency of ; turning to systems that are type-theoretic in spirit or in fact, we show by arguments of Coret and Boffa that proves a weak form of Stratified Collection, and that is a conservative extension of for stratified sentences, from which we deduce that proves a strong stratified version of ; we analyse the known equiconsistency of with the simple theory of types and give Lake's proof that an instance of Mathematical Induction is unprovable in Mac Lane's system; we study a simple set theoretic assertion—namely that there exists an infinite set of infinite sets, no two of which have the same cardinal—and use it to establish the failure of the full schema of Stratified Collection in ; and we determine the point of failure of various other schemata in . The paper closes with some philosophical remarks. (shrink)

The known results about Σ 1 -completeness, Σ 1 -compactness, ordinal omitting etc. are given a unified treatment, which yields many new examples. It is shown that the unifying theorem is best possible in several ways, assuming V = L.

We present a number of results on the structure of initial segments of models of Peano arithmetic with the arithmetic operations of addition, subtraction, multiplication, division, exponentiation and logarithm. Each of the binary operations introduced is defined in two dual ways, often with quite different results, and we attempt to systematise the issues and show how various calculations may be carried out. To understand the behaviour of addition and subtraction we introduce a notion of derivative on cuts, analogous to differentiation (...) in the calculus. Multiplication, division and other operations are described by higher order versions of derivative. The work here is presented as important preliminary work related to a nonstandard measure theory of non‐definable bounded subsets of a model of Peano arithmetic. (shrink)

The main theorem of this article is that every countable model of set theory 〈M, ∈M〉, including every well-founded model, is isomorphic to a submodel of its own constructible universe 〈LM, ∈M〉 by means of an embedding j : M → LM. It follows from the proof that the countable models of set theory are linearly pre-ordered by embeddability: if 〈M, ∈M〉 and 〈N, ∈N〉 are countable models of set theory, then either M is isomorphic to a submodel of N (...) or conversely. Indeed, these models are pre-well-ordered by embeddability in order-type exactly ω1+ 1. Specifically, the countable well-founded models are ordered under embeddability exactly in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory M is universal for all countable well-founded binary relations of rank at most OrdM; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the proof method shows that if M is any nonstandard model of PA, then every countable model of set theory — in particular, every model of ZFC plus large cardinals — is isomorphic to a submodel of the hereditarily finite sets 〈 HFM, ∈M〉 of M. Indeed, 〈 HFM, ∈M〉 is universal for all countable acyclic binary relations. (shrink)

A theoretical development is carried to establish fundamental results about rank-initial embeddings and automorphisms of countable non-standard models of set theory, with a keen eye for their sets of fixed points. These results are then combined into a “geometric technique” used to prove several results about countable non-standard models of set theory. In particular, back-and-forth constructions are carried out to establish various generalizations and refinements of Friedman’s theorem on the existence of rank-initial embeddings between countable non-standard models of the fragment (...) \ + \-Separation of \; and Gaifman’s technique of iterated ultrapowers is employed to show that any countable model of \ can be elementarily rank-end-extended to models with well-behaved automorphisms whose sets of fixed points equal the original model. These theoretical developments are then utilized to prove various results relating self-embeddings, automorphisms, their sets of fixed points, strong rank-cuts, and set theories of different strengths. Two examples: The notion of “strong rank-cut” is characterized in terms of the theory \, and in terms of fixed-point sets of self-embeddings. (shrink)

If ZFC is consistent, then the collection of countable computably saturated models of ZFC satisfies all of the Multiverse Axioms of Hamkins.

This paper presents a systematic study of the prehistory of the traditional subsystems of second-order arithmetic that feature prominently in the reverse mathematics program of Friedman and Simpson. We look in particular at: (i) the long arc from Poincar\'e to Feferman as concerns arithmetic definability and provability, (ii) the interplay between finitism and the formalization of analysis in the lecture notes and publications of Hilbert and Bernays, (iii) the uncertainty as to the constructive status of principles equivalent to Weak K\"onig's (...) Lemma, and (iv) the large-scale intellectual backdrop to arithmetical transfinite recursion in descriptive set theory and its effectivization by Borel, Lusin, Addison, and others. (shrink)

We generalize two concepts from special cases of Polish group actions to the general case. The two concepts are elementary embeddability, from model theory, and analytic sets, from the usual descriptive set theory.

Tanaka proved a powerful generalization of Friedman’s self-embedding theorem that states that given a countable nonstandard model \\) of the subsystem \ of second order arithmetic, and any element m of \, there is a self-embedding j of \\) onto a proper initial segment of itself such that j fixes every predecessor of m. Here we extend Tanaka’s work by establishing the following results for a countable nonstandard model \\ \)of \ and a proper cut \ of \:Theorem A. The (...) following conditions are equivalent: \ is closed under exponentiation. There is a self-embedding j of \\) onto a proper initial segment of itself such that I is the longest initial segment of fixed points of j.Theorem B. The following conditions are equivalent: \ is a strong cut of \ and \ There is a self-embedding j of \\) onto a proper initial segment of itself such that \ is the set of all fixed points of j. (shrink)