The strength of sharply bounded induction requires MSP

DOI10.1016/j.apal.2009.03.002zbMath1223.03045OpenAlexW2024677584MaRDI QIDQ636290

Sedki Boughattas, Leszek Aleksander Kołodziejczyk

Publication date: 26 August 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2009.03.002

zbMATH Keywords

bounded arithmeticsharply bounded formulasunconditional independence resultsvery weak arithmetic

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (8)

FRAGMENTS OF APPROXIMATE COUNTING ⋮ Real closures of models of weak arithmetic ⋮ On the finite axiomatizability of ⋮ END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS ⋮ 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10 ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Independence results for variants of sharply bounded induction ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bootstrapping. I
• Multifunction algebras and the provability of \(PH\downarrow\)
• Well-behaved principles alternative to bounded induction
• The strength of sharply bounded induction
• A Model-Theoretic Property of Sharply Bounded Formulae, with some Applications

This page was built for publication: The strength of sharply bounded induction requires MSP