The strength of sharply bounded induction requires MSP

DOI10.1016/j.apal.2009.03.002zbMath1223.03045MaRDI 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 arithmetic; sharply bounded formulas; unconditional independence results; very weak arithmetic

Mathematics Subject Classification ID

03F30: First-order arithmetic and fragments

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03F20: Complexity of proofs

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item