We establish by elementary proof-theoretic means the conservativeness of two subsystems of analysis over primitive recursive arithmetic. The one subsystem was introduced by Friedman [6], the other is a strengthened version of a theory of Minc [14]; each has been shown to be of considerable interest for both mathematical practice and metamathematical investigations. The foundational significance of such conservation results is clear: they provide a direct finitist justification of the part of mathematical practice formalizable in these subsystems. The results (...) are generalized to relate a hierarchy of subsystems, all contained in the theory of arithmetic properties, to a corresponding hierarchy of fragments of arithmetic. The proof theoretic tools employed there are used to re-establish in a uniform, elementary way relationships between various fragments of arithmetic due to Parsons, Paris and Kirby, and Friedman. (shrink)

By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the Πn+1-sentences true in the standard model is the only consistent Πn+1-theory which extends the scheme of induction for parameter free Πn+1-formulas. Motivated by this result, we present a systematic study of extensions of bounded quantifier complexity of fragments of first-order Peano Arithmetic. Here, we improve that result and show that this property describes a general phenomenon valid for parameter free schemes. As a consequence, (...) we obtain results on the quantifier complexity, finite axiomatizability and relative strength of schemes for Δn+1-formulas. (shrink)

Allen, B., Arithmetizing Uniform NC, Annals of Pure and Applied Logic 53 1–50. We give a characterization of the complexity class Uniform NC as an algebra of functions on the natural numbers which is the closure of several basic functions under composition and a schema of recursion. We then define a fragment of bounded arithmetic, and, using our characterization of Uniform NC, show that this fragment is capable of proving the totality of all of the functions in Uniform NC. (...) Lastly, in the spirit of Buss, we show that any function which is definable by a ∑b1-formula in our theory is a function which is in Uniform NC. (shrink)

This paper presents new constructions of models of Hume's Principle and Basic Law V with restricted amounts of comprehension. The techniques used in these constructions are drawn from hyperarithmetic theory and the model theory of fields, and formalizing these techniques within various subsystems of second-order Peano arithmetic allows one to put upper and lower bounds on the interpretability strength of these theories and hence to compare these theories to the canonical subsystems of second-order arithmetic. The main results of (...) this paper are: (i) there is a consistent extension of the hyperarithmetic fragment of Basic Law V which interprets the hyperarithmetic fragment of second-order Peano arithmetic, and (ii) the hyperarithmetic fragment of Hume's Principle does not interpret the hyperarithmetic fragment of second-order Peano arithmetic, so that in this specific sense there is no predicative version of Frege's Theorem. (shrink)

Frege Arithmetic (FA) is the second-order theory whose sole non-logical axiom is Hume’s Principle, which says that the number of F s is identical to the number of Gs if and only if the F s and the Gs can be one-to-one correlated. According to Frege’s Theorem, FA and some natural definitions imply all of second-order Peano Arithmetic. This paper distinguishes two dimensions of impredicativity involved in FA—one having to do with Hume’s Principle, the other, with the underlying (...) second-order logic—and investigates how much of Frege’s Theorem goes through in various partially predicative fragments of FA. Theorem 1 shows that almost everything goes through, the most important exception being the axiom that every natural number has a successor. Theorem 2 shows that the Successor Axiom cannot be proved in the theories that are predicative in either dimension. (shrink)

Turing progressions have been often used to measure the proof-theoretic strength of mathematical theories: iterate adding consistency of some weak base theory until you “hit” the target theory. Turing progressions based on n-consistency give rise to a \ proof-theoretic ordinal \ also denoted \. As such, to each theory U we can assign the sequence of corresponding \ ordinals \. We call this sequence a Turing-Taylor expansion or spectrum of a theory. In this paper, we relate Turing-Taylor expansions of sub-theories (...) of Peano Arithmetic to Ignatiev’s universal model for the closed fragment of the polymodal provability logic \. In particular, we observe that each point in the Ignatiev model can be seen as Turing-Taylor expansions of formal mathematical theories. Moreover, each sub-theory of Peano Arithmetic that allows for a Turing-Taylor expansion will define a unique point in Ignatiev’s model. (shrink)

It is well known that number theory can be interpreted in the usual set theories, e.g. ZF, NF and their extensions. The problem I posed for myself was to see if, conversely, a reasonably strong set theory could be interpreted in number theory. The reason I am interested in this problem is, simply, that number theory is more basic or more concrete than set theory, and hence a more concrete foundation for mathematics. A partial solution to the problem was accomplished (...) by WTN in [2], where it was shown that a predicative set theory could be interpreted in a natural extension of pure number theory, PN, (i.e. classical first-order Peano Arithmetic). In this paper, we go a step further by showing that a reasonably strong fragment of predicative set theory can be interpreted in PN itself. We then make an attempt to show how to develop predicative fragments of mathematics in PN.If one wishes to know what is meant by reasonably strong and fragment please read on. (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.

This paper presents proof that Buss's S22 can prove the consistency of a fragment of Cook and Urquhart's PV from which induction has been removed but substitution has been retained. This result improves Beckmann's result, which proves the consistency of such a system without substitution in bounded arithmetic S12. Our proof relies on the notion of "computation" of the terms of PV. In our work, we first prove that, in the system under consideration, if an equation is proved and (...) either its left- or right-hand side is computed, then there is a corresponding computation for its right- or left-hand side, respectively. By carefully computing the bound of the size of the computation, the proof of this theorem inside a bounded arithmetic is obtained, from which the consistency of the system is readily proven. This result apparently implies the separation of bounded arithmetic because Buss and Ignjatović stated that it is not possible to prove the consistency of a fragment of PV without induction but with substitution in Buss's S12. However, their proof actually shows that it is not possible to prove the consistency of the system, which is obtained by the addition of propositional logic and other axioms to a system such as ours. On the other hand, the system that we have considered is strictly equational, which is a property on which our proof relies. (shrink)

We characterize the collapse of Buss' bounded arithmetic in terms of the provable collapse of the polynomial time hierarchy. We include also some general model-theoretical investigations on fragments of bounded arithmetic.

In Frege’s logicism, numbers are logical objects in the sense that they are extensions of certain concepts. Frege’s logical system is inconsistent, but Richard Heck showed that its restriction to predicative quantification is consistent. This predicative fragment is, nevertheless, too weak to develop arithmetic. In this paper, I will consider an extension of Heck’s system with impredicative quantifiers. In this extended system, both predicative and impredicative quantifiers co-exist but it is only permissible to take extensions of concepts formulated in (...) the predicative fragment of the language. This system is consistent. Moreover, it proves the principle of reducibility applied to concepts true of only finitely many objects. With the aid of this form of reducibility, it is possible to develop arithmetic in a thoroughly Fregean way. (shrink)

We investigate the possibility to characterize (multi) functions that are Σ b i -definable with small i (i = 1, 2, 3) in fragments of bounded arithmetic T 2 in terms of natural search problems defined over polynomial-time structures. We obtain the following results: (1) A reformulation of known characterizations of (multi)functions that are Σ b 1 - and Σ b 2 -definable in the theories S 1 2 and T 1 2 . (2) New characterizations of (multi)functions (...) that are Σ b 2 - and Σ b 3 -definable in the theory T 2 2 . (3) A new non-conservation result: the theory T 2 2 (α) is not ∀Σ b 1 (α)-conservative over the theory S 2 2 (α). To prove that the theory T 2 2 (α) is not ∀Σ b 1 (α)-conservative over the theory S 2 2 (α), we present two examples of a Σ b 1 (α)-principle separating the two theories: (a) the weak pigeonhole principle WPHP (a 2 , f, g) formalizing that no function f is a bijection between a 2 and a with the inverse g, (b) the iteration principle Iter (a, R, f) formalizing that no function f defined on a strict partial order ( $\{0,\dots,a\}$ , R) can have increasing iterates. (shrink)

We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates—which are strongly related to definability in the monadic SOA (second-order arithmetic) without × or + , respectively. As a consequence, we obtain a very direct proof for ${\Pi^1_1}$ -completeness of (...) Presburger, and also Skolem, arithmetic with a free unary predicate, generalize it to all ${\Pi^1_n}$ -levels, and give an alternative description of the analytical hierarchy without × or + . Here ‘direct’ means that one explicitly m-reduces the truth of ${\Pi^1_1}$ -formulae in SOA to the truth in the extended structures. Notice that for the case of Presburger arithmetic, the ${\Pi^1_1}$ -completeness was already known, but the proof was indirect and exploited some special ${\Pi^1_1}$ -completeness results on so-called recurrent nondeterministic Turing machines—for these reasons, it was hardly able to shed any light on definability issues or possible generalizations. (shrink)

We consider fragments of uniform reflection for formulas in the analytic hierarchy over theories of second order arithmetic. The main result is that for any second order arithmetic theory $T_0$ extending $\mathsf {RCA}_0$ and axiomatizable by a $\Pi ^1_{k+2}$ sentence, and for any $n\geq k+1$, $$\begin{align*}T_0+ \mathrm{RFN}_{\varPi^1_{n+2}} \ = \ T_0 + \mathrm{TI}_{\varPi^1_n}, \end{align*}$$ $$\begin{align*}T_0+ \mathrm{RFN}_{\varSigma^1_{n+1}} \ = \ T_0+ \mathrm{TI}_{\varPi^1_n}^{-}, \end{align*}$$ where T is $T_0$ augmented with full induction, and $\mathrm {TI}_{\varPi ^1_n}^{-}$ denotes the schema of (...) transfinite induction up to $\varepsilon _0$ for $\varPi ^1_n$ formulas without set parameters. (shrink)

We study the relative strength of the two axioms Every Pell equation has a nontrivial solution Exponentiation is total over weak fragments, and we show they are equivalent over IE1. We then define the graph of the exponential function using only existentially bounded quantifiers in the language of arithmetic expanded with the symbol #, where # = x[log2y]. We prove the recursion laws of exponentiation in the corresponding fragment.

In [Boccuni 2010], a predicative fragment of Frege’s blv augmented with Boolos’ unrestricted plural quantification is shown to interpret pa2. The main disadvantage of that axiomatisation is that it does not recover Frege Arithmetic fa because of the restrictions imposed on the axioms. The aim of the present article is to show how [Boccuni 2010] can be consistently extended so as to interpret fa and consequently pa2 in a way that parallels Frege’s. In that way, the presented system will (...) be compared with the system pe in [Ferreira 2018] and some relevant differences between the two will be highlighted. (shrink)

In the first section of this paper we show that i Π1 ≡ W⌝⌝lΠ1 and that a Kripke model which decides bounded formulas forces iΠ1 if and only if the union of the worlds in any path in it satisflies IΠ1. In particular, the union of the worlds in any path of a Kripke model of HA models IΠ1. In the second section of the paper, we show that for equivalence of forcing and satisfaction of Πm-formulas in a linear Kripke (...) model deciding Δ0-formulas it is necessary and sufficient that the model be Σm-elementary. This implies that if a linear Kripke model forces PEMprenex, then it forces PEM. We also show that, for each n ≥ 1, iΦn does not prove ℋ(IΠn's are Burr's fragments of HA. (shrink)

We systematically study conservation theorems on theories of semi-classical arithmetic, which lie in-between classical arithmetic $\mathsf {PA}$ and intuitionistic arithmetic $\mathsf {HA}$. Using a generalized negative translation, we first provide a structured proof of the fact that $\mathsf {PA}$ is $\Pi _{k+2}$ -conservative over $\mathsf {HA} + {\Sigma _k}\text {-}\mathrm {LEM}$ where ${\Sigma _k}\text {-}\mathrm {LEM}$ is the axiom scheme of the law-of-excluded-middle restricted to formulas in $\Sigma _k$. In addition, we show that this conservation theorem is (...) optimal in the sense that for any semi-classical arithmetic T, if $\mathsf {PA}$ is $\Pi _{k+2}$ -conservative over T, then ${T}$ proves ${\Sigma _k}\text {-}\mathrm {LEM}$. In the same manner, we also characterize conservation theorems for other well-studied classes of formulas by fragments of classical axioms or rules. This reveals the entire structure of conservation theorems with respect to the arithmetical hierarchy of classical principles. (shrink)

Global properties of canonical derivability predicates in Peano Arithmetic) are studied here by means of a suitable propositional modal logic GL. A whole book [1] has appeared on GL and we refer to it for more information and a bibliography on GL. Here we propose a sequent calculus for GL and, by exhibiting a good proof procedure, prove that such calculus admits the elimination of cuts. Most of standard results on GL are then easy consequences: completeness, decidability, finite model (...) property, interpolation and the fixed point theorem. (shrink)

We define classes Φnof formulae of first-order arithmetic with the following properties:(i) Everyφϵ Φnis classically equivalent to a Πn-formula (n≠ 1, Φ1:= Σ1).(ii)(iii)IΠnandiΦn(i.e., Heyting arithmetic with induction schema restricted to Φn-formulae) prove the same Π2-formulae.We further generalize a result by Visser and Wehmeier. namely that prenex induction within intuitionistic arithmetic is rather weak: After closing Φnboth under existential and universal quantification (we call these classes Θn) the corresponding theoriesiΘnstill prove the same Π2-formulae. In a second part we (...) consideriΔ0plus collection-principles. We show that both the provably recursive functions and the provably total functions ofare polynomially bounded. Furthermore we show that the contrapositive of the collection-schema gives rise to instances of the law of excluded middle and hence. (shrink)

The lack of specific arithmetical axioms in Book VII has puzzled historians of mathematics. It is hardly possible in our view to ascribe to the Greeks a conscious undertaking to axiomatize arithmetic. The view that associates the beginnings of the axiomatization of arithmetic with the works of Grassman [1861], Dedekind [1888] and Peano [1889] seems to be more plausible. In this connection a number of interesting historical problems have been raised, for instance, why arithmetic was axiomatized so (...) late. This question was first posed and quite conclusively answered by Yanovskaja [1956]. Her major and quite conclusive argument was that “algorithms in arithmetic have absolute character, while in geometry we have to do with reducibility algorithms”. In this paper we are going to draw attention on certain peculiarities of the construction of the arithmetical Books of Euclid’s "Elements" and show that Euclidean arithmetic is constructed by effective procedures. In spite of the use of inference by reductio ad absurdum and methods equivalent to mathematical induction, Euclidean arithmetic retains its finitary character. It is not full arithmetic, but a finitary fragment of classical arithmetic, and thereby there was not any internal reason for its axiomatization. (shrink)

Using a slight generalization, due to Palmgren, of sheaf semantics, we present a term-model construction that assigns a model to any first-order intuitionistic theory. A modification of this construction then assigns a nonstandard model to any theory of arithmetic, enabling us to reproduce conservation results of Moerdijk and Palmgren for nonstandard Heyting arithmetic. Internalizing the construction allows us to strengthen these results with additional transfer rules; we then show that even trivial transfer axioms or minor strengthenings of these (...) rules destroy conservativity over HA. The analysis also shows that nonstandard HA has neither the disjunction property nor the explicit definability property. Finally, careful attention to the complexity of our definitions allows us to show that a certain weak fragment of intuitionistic nonstandard arithmetic is conservative over primitive recursive arithmetic. (shrink)

IΣ n andBΣ n are well known fragments of first-order arithmetic with induction and collection forΣ n formulas respectively;IΣ n 0 andBΣ n 0 are their second-order counterparts. RCA0 is the well known fragment of second-order arithmetic with recursive comprehension;WKL 0 isRCA 0 plus weak König's lemma. We first strengthen Harrington's conservation result by showing thatWKL 0 +BΣ n 0 is Π 1 1 -conservative overRCA 0 +BΣ n 0 . Then we develop some model theory inWKL (...) 0 and illustrate the use of formalized model theory by giving a relatively simple proof of the fact thatIΣ 1 provesBΣ n+1 to be Π n+2-conservative overIΣ n . Finally, we present a proof-theoretic proof of the stronger fact that theΠ n+2 conservation result is provable already inIΔ 0 + superexp. ThusIΣ n+1 proves 1-Con (BΣ n+1) andIΔ 0 +superexp proves Con (IΣ n )↔Con(BΣ n+1). (shrink)

The standard style of argument used to prove that a theory is unde- cidable relies on certain consistency assumptions, usually that some fragment or other is negation consistent. In a non-paraconsistent set- ting, this amounts to an assumption that the theory is non-trivial, but these diverge when theories are couched in paraconsistent logics. Furthermore, there are general methods for constructing inconsistent models of arithmetic from consistent models, and the theories of such inconsistent models seem likely to differ in terms (...) of complexity. In this paper, I begin to explore this terrain, working, particularly, in incon- sistent theories of arithmetic couched in three-valued paraconsistent logics which have strong (i.e. detaching) conditionals. (shrink)

Using a slight generalization, due to Palmgren, of sheaf semantics, we present a term-model construction that assigns a model to any first-order intuitionistic theory. A modification of this construction then assigns a nonstandard model to any theory of arithmetic, enabling us to reproduce conservation results of Moerdijk and Palmgren for nonstandard Heyting arithmetic. Internalizing the construction allows us to strengthen these results with additional transfer rules; we then show that even trivial transfer axioms or minor strengthenings of these (...) rules destroy conservativity over HA. The analysis also shows that nonstandard HA has neither the disjunction property nor the explicit definability property. Finally, careful attention to the complexity of our definitions allows us to show that a certain weak fragment of intuitionistic nonstandard arithmetic is conservative over primitive recursive arithmetic. (shrink)

We give a corrected proof of the main result in the paper [2] mentioned in the title.

There has been a recent interest in hierarchical generalizations of classic incompleteness results. This paper provides evidence that such generalizations are readily obtainable from suitably formulated hierarchical versions of the principles used in the original proofs. By collecting such principles, we prove hierarchical versions of Mostowski’s theorem on independent formulae, Kripke’s theorem on flexible formulae, Woodin’s theorem on the universal algorithm, and a few related results. As a corollary, we obtain the expected result that the formula expressing “$\mathrm {T}$is$\Sigma _n$-ill” (...) is a canonical example of a$\Sigma _{n+1}$formula that is$\Pi _{n+1}$-conservative over$\mathrm {T}$. (shrink)

We consider the problem whether the $\forall \Sigma _{1}^{b}$ theorems of the fragments $T_{2}^{a}$ form a strictly increasing hierarchy. We shall show a link to some results about the lengths of proofs in predicate logic that supports the conjecture that the hierarchy is strictly increasing.

We determine the strictly positive fragment $\textsf{QPL}^+(\textsf{HA})$ of the quantified provability logic $\textsf{QPL}(\textsf{HA})$ of Heyting Arithmetic. We show that $\textsf{QPL}^+(\textsf{HA})$ is decidable and that it coincides with $\textsf{QPL}^+(\textsf{PA})$, which is the strictly positive fragment of the quantified provability logic of of Peano Arithmetic. This positively resolves a previous conjecture of the authors described in [ 14 ]. On our way to proving these results, we carve out the strictly positive fragment $\textsf{PL}^+(\textsf{HA})$ of the provability logic $\textsf{PL}(\textsf{HA})$ of Heyting (...) Arithmetic, provide a simple axiomatization, and prove it to be sound and complete for two types of arithmetical interpretations. The simple fragments presented in this paper should be contrasted with a recent result by Mojtahedi [ 43 ], where an axiomatization for $\textsf{PL}(\textsf{HA})$ is provided. This axiomatization, although decidable, is of considerable complexity. (shrink)

The complexity class of [Formula: see text]-polynomial local search problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 ≤ i ≤ k + 1, the [Formula: see text]-definable functions of [Formula: see text] are characterized in terms of [Formula: see text]-PLS problems. These [Formula: see text]-PLS problems can be defined in a weak base theory such as [Formula: see text], and proved to be total in [Formula: see text]. Furthermore, (...) the [Formula: see text]-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new [Formula: see text]-principle that is conjectured to separate [Formula: see text] and [Formula: see text]. (shrink)

We construct ω-framed Kripke models of i∀1 and iΠ1 non of whose worlds satisfies ∀x∃y(x=2y∨x=2y+1) and ∀x,y∃zExp(x, y, z) respectively. This will enable us to show that i∀1 does not prove ¬¬∀x∃y(x=2y∨x=2y+1) and iΠ1 does not prove ¬¬∀x, y∃zExp(x, y, z). Therefore, i∀1⊬¬¬lop and iΠ1⊬¬¬iΣ1. We also prove that HA⊬lΣ1 and present some remarks about iΠ2.

We study the minimal enumeration degree problem in models of fragments of Peano arithmetic () and prove the following results: in any model M of Σ2 induction, there is a minimal enumeration degree if and only if M is a nonstandard model. Furthermore, any cut in such a model has minimal e-degree. By contrast, this phenomenon fails in the absence of Σ2 induction. In fact, whether every Σ2 cut has minimal e-degree is independent of the Σ2 bounding principle.

We formalize the notion of Herbrand Consistency in an appropriate way for bounded arithmetics, and show the existence of a finite fragment of IΔ0 whose Herbrand Consistency is not provable in IΔ0. We also show the existence of an IΔ0-derivable Π1-sentence such that IΔ0 cannot prove its Herbrand Consistency.

Samuel R. Buss and Aleksandar Ignjatović. Unprovability of Consistency Statements in Fragments of Bounded Arithmetic.

The complete characterisation of order types of non-standard models of Peano arithmetic and its extensions is a famous open problem. In this paper, we consider subtheories of Peano arithmetic (both with and without induction), in particular, theories formulated in proper fragments of the full language of arithmetic. We study the order types of their non-standard models and separate all considered theories via their possible order types. We compare the theories with and without induction and observe that (...) the theories without induction tend to have an algebraic character that allows model constructions by closing a model under the relevant algebraic operations. (shrink)

A fragment with the same provably recursive functions as n iterated inductive definitions is obtained by restricting second order arithmetic in the following way. The underlying language allows only up to n + 1 nested second order quantifications and those are in such a way, that no second order variable occurs free in the scope of another second order quantifier. The amount of induction on arithmetical formulae only affects the arithmetical consequences of these theories, whereas adding induction for arbitrary (...) formulae increases the strength by one inductive definition. (shrink)

Solovay proved (Israel J Math 25(3–4):287–304, 1976) that the propositional provability logic of any ∑2-sound recursively enumerable extension of PA is characterized by the propositional modal logic GL. By contrast, Montagna proved in (Notre Dame J Form Log 25(2):179–189, 1984) that predicate provability logics of Peano arithmetic and Bernays–Gödel set theory are different. Moreover, Artemov proved in (Doklady Akademii Nauk SSSR 290(6):1289–1292, 1986) that the predicate provability logic of a theory essentially depends on the choice of a binumeration of (...) the theory which is used to construct the provability predicate. In this paper, we compare predicate provability logics of I∑ n ’s. For a binumeration α(x) of a recursive theory T, let PL α(T) be the predicate provability logic of T defined by α(x). We prove that for any natural numbers i, j such that 0 < i < j, there exists a ∑1 binumeration α(x) of some recursive axiomatization of I∑ i such that ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsupseteq \bigcap_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ and ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsubseteq \bigcup_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ , where β(x) ranges over all ∑1 binumerations of recursive axiomatizations of I∑ j. (shrink)