Journal of Mathematical Logic, Volume 23, Issue 02, August 2023. In mathematical logic there are two seemingly distinct kinds of principles called “reflection principles.” Semantic reflection principles assert that if a formula holds in the whole universe, then it holds in a set-sized model. Syntactic reflection principles assert that every provable sentence from some complexity class is true. In this paper, we study connections between these two kinds of reflection principles in the setting of second-order arithmetic. We prove that, for (...) a large swathe of theories, [math]-model reflection is equivalent to the claim that arbitrary iterations of uniform [math] reflection along countable well-orderings are [math]-sound. This result yields uniform ordinal analyzes of theories with strength between [math] and [math]. The main technical novelty of our analysis is the introduction of the notion of the proof-theoretic dilator of a theory [math], which is the operator on countable ordinals that maps the order-type of [math] to the proof-theoretic ordinal of [math]. We obtain precise results about the growth of proof-theoretic dilators as a function of provable [math]-model reflection. This approach enables us to simultaneously obtain not only [math], [math] and [math] ordinals but also reverse-mathematical theorems for well-ordering principles. (shrink)

In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions for a theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV1. We use the mentioned results to obtain some independence results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction (...) on strict $\Pi_2^{b}$ formulas proves decidability of $\Sigma_1^b$ formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves ${\rm LMIN}(\Sigma_{1}^{b})$ , then P=NP. (shrink)

I argue for the use of the adjunction operator (adding a single new element to an existing set) as a basis for building a finitary set theory. It allows a simplified axiomatization for the first-order theory of hereditarily finite sets based on an induction schema and a rigorous characterization of the primitive recursive set functions. The latter leads to a primitive recursive presentation of arithmetical operations on finite sets.

In this paper we will state and prove some comparative theorems concerning PRA and IΣ1. We shall provide a characterization of IΣ1 in terms of PRA and iterations of a class of functions. In particular, we prove that for this class of functions the difference between IΣ1 and PRA is exactly that, where PRA is closed under iterations of these functions, IΣ1 is moreover provably closed under iteration. We will formulate a sufficient condition for a model of PRA to be (...) a model of IΣ1. This condition is used to give a model-theoretic proof of Parsons’ theorem, that is, IΣ1 is Π2-conservative over PRA. We shall also give a purely syntactical proof of Parsons’ theorem. Finally, we show that IΣ1 proves the consistency of PRA on a definable IΣ1-cut. This implies that proofs in IΣ1 can have non-elementary speed up over proofs in PRA. (shrink)

Let be the fragment of elementary Peano arithmetic in which induction is restricted to -formulas. More than three decades ago, Parsons showed that the provably total functions of are exactly the primitive recursive functions. In this paper, we observe that Parsons' result is a consequence of Herbrand's theorem concerning the -consequences of universal theories. We give a self-contained proof requiring only basic knowledge of mathematical logic.

By a result of L.D. Beklemishev, the hierarchy of nested applications of the $$\Sigma _1$$ -collection rule over any $$\Pi _2$$ -axiomatizable base theory extending Elementary Arithmetic collapses to its first level. We prove that this result cannot in general be extended to base theories of arbitrary quantifier complexity. In fact, given any recursively enumerable set of true $$\Pi _2$$ -sentences, S, we construct a sound $$(\Sigma _2 \! \vee \! \Pi _2)$$ -axiomatized theory T extending S such that the (...) hierarchy of nested applications of the $$\Sigma _1$$ -collection rule over T is proper. Our construction uses some results on subrecursive degree theory obtained by L. Kristiansen. (shrink)

This paper investigates the status of the fragments of Peano Arithmetic obtained by restricting induction, collection and least number axiom schemes to formulas which are Δ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta_1}$$\end{document} provably in an arithmetic theory T. In particular, we determine the provably total computable functions of this kind of theories. As an application, we obtain a reduction of the problem whether IΔ0+¬exp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I\Delta_0 + \neg \mathit{exp}}$$\end{document} implies BΣ1\documentclass[12pt]{minimal} (...) \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${B\Sigma_1}$$\end{document} to a purely recursion-theoretic question. (shrink)

Let Iπ2 denote the fragment of Peano Arithmetic obtained by restricting the induction scheme to parameter free Π2Π2 formulas. Answering a question of R. Kaye, L. Beklemishev showed that the provably total computable functions of Iπ2 are, precisely, the primitive recursive ones. In this work we give a new proof of this fact through an analysis of certain local variants of induction principles closely related to Iπ2. In this way, we obtain a more direct answer to Kaye's question, avoiding the (...) metamathematical machinery needed for Beklemishev's original proof.Our methods are model-theoretic and allow for a general study of Iπn+1 for all n≥0n≥0. In particular, we derive a new conservation result for these theories, namely that Iπn+1 is πn+2 -conservative over IΣn for each n≥1n≥1. (shrink)

A polynomial time ultrapower is a structure given by the set of polynomial time computable functions modulo some ultrafilter. They model the universal theory \ of all polynomial time functions. Generalizing a theorem of Hirschfeld :111–126, 1975), we show that every countable model of \ is isomorphic to an existentially closed substructure of a polynomial time ultrapower. Moreover, one can take a substructure of a special form, namely a limit polynomial time ultrapower in the classical sense of Keisler Ultrafilters across (...) mathematics, contemporary mathematics vol 530, pp 163–179. AMS, New York, 1963). Using a polynomial time ultrapower over a nonstandard Herbrand saturated model of \ we show that \ is consistent with a formal statement of a polynomial size circuit lower bound for a polynomial time computable function. This improves upon a recent result of Krajíček and Oliveira, 2017). (shrink)

is a fragment of first-order aritlimetic so weak that it cannot prove the totality of an iterated exponential fimction. Surprisingly, however, the theory is remarkably robust. I will discuss formal results that show that many theorems of number theory and combinatorics are derivable in elementary arithmetic, and try to place these results in a broader philosophical context.

Paul Cohen’s method of forcing, together with Saul Kripke’s related semantics for modal and intuitionistic logic, has had profound effects on a number of branches of mathematical logic, from set theory and model theory to constructive and categorical logic. Here, I argue that forcing also has a place in traditional Hilbert-style proof theory, where the goal is to formalize portions of ordinary mathematics in restricted axiomatic theories, and study those theories in constructive or syntactic terms. I will discuss the aspects (...) of forcing that are useful in this respect, and some sample applications. The latter include ways of obtaining conservation results for classical and intuitionistic theories, interpreting classical theories in constructive ones, and constructivizing model-theoretic arguments. (shrink)

The notion of a function from ℕ to ℕ defined by recursion on ordinal notations is fundamental in proof theory. Here this notion is generalized to functions on the universe of sets, using notations for well orderings longer than the class of ordinals. The generalization is used to bound the rate of growth of any function on the universe of sets that is Σ1-definable in Kripke–Platek admissible set theory with an axiom of infinity. Formalizing the argument provides an ordinal analysis.

At the turn of the nineteenth century, mathematics exhibited a style of argumentation that was more explicitly computational than is common today. Over the course of the century, the introduction of abstract algebraic methods helped unify developments in analysis, number theory, geometry, and the theory of equations; and work by mathematicians like Dedekind, Cantor, and Hilbert towards the end of the century introduced set-theoretic language and infinitary methods that served to downplay or suppress computational content. This shift in emphasis away (...) from calculation gave rise to concerns as to whether such methods were meaningful, or appropriate to mathematics. The discovery of paradoxes stemming from overly naive use of set-theoretic language and methods led to even more pressing concerns as to whether the modern methods were even consistent. This led to heated debates in the early twentieth century and what is sometimes called the “crisis of foundations.” In lectures presented in 1922, David Hilbert launched his Beweistheorie, or Proof Theory, which aimed to justify the use of modern methods and settle the problem of foundations once and for all. This, Hilbert argued, could be achieved as follows. (shrink)

Algebraic proofs of the cut-elimination theorems for classical and intuitionistic logic are presented, and are used to show how one can sometimes extract a constructive proof and an algorithm from a proof that is nonconstructive. A variation of the double-negation translation is also discussed: if ϕ is provable classically, then ¬(¬ϕ)nf is provable in minimal logic, where θnf denotes the negation-normal form of θ. The translation is used to show that cut-elimination theorems for classical logic can be viewed as special (...) cases of the cut-elimination theorems for intuitionistic logic. (shrink)