Induction rules in bounded arithmetic

DOI10.1007/S00153-019-00702-WzbMATH Open1471.03082arXiv1809.10718OpenAlexW3104721635MaRDI QIDQ2309507FDOQ2309507

Authors: Emil Jeřábek 

Publication date: 1 April 2020

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Abstract: We study variants of Buss's theories of bounded arithmetic axiomatized by induction schemes disallowing the use of parameters, and closely related induction inference rules. We put particular emphasis on $hatP{i}_i^b$ induction schemes, which were so far neglected in the literature. We present inclusions and conservation results between the systems (including a witnessing theorem for $T_2^i$ and $S_2^i$ of a new form), results on numbers of instances of the axioms or rules, connections to reflection principles for quantified propositional calculi, and separations between the systems.

Full work available at URL: https://arxiv.org/abs/1809.10718

Recommendations

• scientific article; zbMATH DE number 3880682
• scientific article; zbMATH DE number 218509
• Restricted polynomial induction versus ordinary induction
• Well-behaved principles alternative to bounded induction
• Existentially Closed Models and Conservation Results in Bounded Arithmetic

zbMATH Keywords

bounded arithmeticreflection principleinduction rulepartial conservativityparameter-free induction

Mathematics Subject Classification ID

Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Notes on polynomially bounded arithmetic
• Logical foundations of proof complexity
• Parameter free induction and provably total computable functions
• Diophantine induction
• Title not available (Why is that?)
• The provably total search problems of bounded arithmetic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Consequences of the provability of NP ⊆ P/poly
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Quantified propositional calculi and fragments of bounded arithmetic
• Title not available (Why is that?)
• Induction rules, reflection principles, and provably recursive functions
• On parameter free induction schemas
• Relating the bounded arithmetic and polynomial time hierarchies
• Lifting independence results in bounded arithmetic
• Fragments of Bounded Arithmetic and Bounded Query Classes
• On theories of bounded arithmetic for \(\mathrm{NC}^1\)
• Witnessing functions in bounded arithmetic and search problems
• Functions provably total in $I^{-}Σ_{n}$
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Local induction and provably total computable functions
• Approximate counting by hashing in bounded arithmetic
• On Σ₁‐definable Functions Provably Total in I ∏
• Simulating non-prenex cuts in quantified propositional calculus
• Existentially Closed Models and Conservation Results in Bounded Arithmetic
• Title not available (Why is that?)

Cited In (11)

• An induction principle for consequence in arithmetic universes
• Universal Induction and True Universal Arithmetic
• Finite multiplicity theorems for induction and restriction
• Title not available (Why is that?)
• Unprovability results for clause set cycles
• Restricted polynomial induction versus ordinary induction
• Title not available (Why is that?)
• Restricted polynomial induction versus parameter free ordinary induction
• Induction and Skolemization in saturation theorem proving
• Well-behaved principles alternative to bounded induction
• Title not available (Why is that?)

This page was built for publication: Induction rules in bounded arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2309507)