Switch to: References

Citations of:

The strength of sharply bounded induction requires M S P

Sedki Boughattas & Leszek Aleksander Kołodziejczyk

Annals of Pure and Applied Logic 161 (4):504-510 (2010)

Add citations

You must login to add citations.

Open induction in a bounded arithmetic for TC0.Emil Jeřábek - 2015 - Archive for Mathematical Logic 54 (3-4):359-394.details The elementary arithmetic operations +,·,≤\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${+,\cdot,\le}$$\end{document} on integers are well-known to be computable in the weak complexity class TC0, and it is a basic question what properties of these operations can be proved using only TC0-computable objects, i.e., in a theory of bounded arithmetic corresponding to TC0. We will show that the theory VTC0 extended with an axiom postulating the totality of iterated multiplication proves induction for quantifier-free formulas in the language ⟨+,·,≤⟩\documentclass[12pt]{minimal} (...) Download Export citation Bookmark 4 citations
Conservative fragments of $${{S}^{1}{2}}$$ and $${{R}^{1}{2}}$$. [REVIEW]Chris Pollett - 2011 - Archive for Mathematical Logic 50 (3):367-393.details Conservative subtheories of $${{R}^{1}_{2}}$$ and $${{S}^{1}_{2}}$$ are presented. For $${{S}^{1}_{2}}$$, a slight tightening of Jeřábek’s result (Math Logic Q 52(6):613–624, 2006) that $${T^{0}_{2} \preceq_{\forall \Sigma^{b}_{1}}S^{1}_{2}}$$ is presented: It is shown that $${T^{0}_{2}}$$ can be axiomatised as BASIC together with induction on sharply bounded formulas of one alternation. Within this $${\forall\Sigma^{b}_{1}}$$ -theory, we define a $${\forall\Sigma^{b}_{0}}$$ -theory, $${T^{-1}_{2}}$$, for the $${\forall\Sigma^{b}_{0}}$$ -consequences of $${S^{1}_{2}}$$. We show $${T^{-1}_{2}}$$ is weak by showing it cannot $${\Sigma^{b}_{0}}$$ -define division by 3. We then consider what (...) Download Export citation Bookmark
Independence results for variants of sharply bounded induction.Leszek Aleksander Kołodziejczyk - 2011 - Annals of Pure and Applied Logic 162 (12):981-990.details The theory , axiomatized by the induction scheme for sharply bounded formulae in Buss’ original language of bounded arithmetic , has recently been unconditionally separated from full bounded arithmetic S2. The method used to prove the separation is reminiscent of those known from the study of open induction.We make the connection to open induction explicit, showing that models of can be built using a “nonstandard variant” of Wilkie’s well-known technique for building models of IOpen. This makes it possible to transfer (...) Download Export citation Bookmark 2 citations
Real closures of models of weak arithmetic.Emil Jeřábek & Leszek Aleksander Kołodziejczyk - 2013 - Archive for Mathematical Logic 52 (1):143-157.details D’Aquino et al. (J Symb Log 75(1):1–11, 2010) have recently shown that every real-closed field with an integer part satisfying the arithmetic theory IΣ4 is recursively saturated, and that this theorem fails if IΣ4 is replaced by IΔ0. We prove that the theorem holds if IΣ4 is replaced by weak subtheories of Buss’ bounded arithmetic: PV or $${\Sigma^b_1-IND^{\|x\|_k}}$$. It also holds for IΔ0 (and even its subtheory IE 2) under a rather mild assumption on cofinality. On the other hand, it (...) Download Export citation Bookmark 3 citations
End-extensions of models of weak arithmetic from complexity-theoretic containments.Leszek Aleksander Kołodziejczyk - 2016 - Journal of Symbolic Logic 81 (3):901-916.details We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π1 + ¬Ω1has a proper end-extension to a model of Π1, and so Π1 + ¬Ω ⊢ BΣ1. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π1 + ¬Exp ⊢ BΣ1. Both assumptions can be modified to versions which make it possible to replace Π1 by IΔ0as the base theory.We also show that any proof that IΔ0+ ¬Exp does not (...) Download Export citation Bookmark 1 citation
(15 other versions)2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10.Uri Abraham & Ted Slaman - 2011 - Bulletin of Symbolic Logic 17 (2):272-329.details Download Export citation Bookmark
Fragments of approximate counting.Samuel R. Buss, Leszek Aleksander Kołodziejczyk & Neil Thapen - 2014 - Journal of Symbolic Logic 79 (2):496-525.details We study the long-standing open problem of giving$\forall {\rm{\Sigma }}_1^b$separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jeřábek’s theories for approximate counting and their subtheories. We show that the$\forall {\rm{\Sigma }}_1^b$Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole (...) Download Export citation Bookmark 5 citations
On the finite axiomatizability of.Chris Pollett - 2018 - Mathematical Logic Quarterly 64 (1-2):6-24.details The question of whether the bounded arithmetic theories and are equal is closely connected to the complexity question of whether is equal to. In this paper, we examine the still open question of whether the prenex version of,, is equal to. We give new dependent choice‐based axiomatizations of the ‐consequences of and. Our dependent choice axiomatizations give new normal forms for the ‐consequences of and. We use these axiomatizations to give an alternative proof of the finite axiomatizability of and to (...) Download Export citation Bookmark

1