Structure and definability in general bounded arithmetic theories
From MaRDI portal
The paper is devoted to the study of bounded arithmetic theories. The main problems studied are motivated by the following questions: (1) What are the \(\Sigma^b_{i+1}\)-definable multifunctions of \(R^i_2\)? (2) When is one theory conservative over another? To answer these questions, versions of the theories \(R^i_2\), \(S^i_2\) and \(T^i_2\) with induction restricted to prenex formulas are introduced and studied.
Recommendations
- Arithmetical definability over finite structures
- scientific article; zbMATH DE number 1048040
- scientific article; zbMATH DE number 3941526
- Sprague-Grundy theory in bounded arithmetic
- scientific article; zbMATH DE number 5267925
- Model theory of bounded arithmetic with applications to independence results
- A Note on Conservativity Relations among Bounded Arithmetic Theories
- Generalized quantifier and a bounded arithmetic theory for LOGCFL
- On the provability logic of bounded arithmetic
- On explicit definability in arithmetic
Cited in
(24)- Separations of theories in weak bounded arithmetic
- Multifunction algebras and the provability of PH
- Well-behaved principles alternative to bounded induction
- Circuit principles and weak pigeonhole variants
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Models of replacement schemes
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- scientific article; zbMATH DE number 440477 (Why is no real title available?)
- A Characterisation of the Relations Definable in Presburger Arithmetic
- scientific article; zbMATH DE number 5778051 (Why is no real title available?)
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- A Characterisation of Definable NP Search Problems in Peano Arithmetic
- Restricted polynomial induction versus ordinary induction
- Constructivizable and non-constructivizable formal arithmetic structures
- Generalized r-cohesiveness and the arithmetical hierarchy: a correction to “Generalized cohesiveness”
- On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
- Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
- The computational power of bounded arithmetic from the predicative viewpoint
- Consequences of the provability of NP ⊆ P/poly
- A list of arithmetical structures complete with respect to the first-order definability
- Preservation theorems and restricted consistency statements in bounded arithmetic
- Bootstrapping. I
- On the computational complexity of cut-reduction
- \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly
This page was built for publication: Structure and definability in general bounded arithmetic theories
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1125060)
