Structure and definability in general bounded arithmetic theories
From MaRDI portal
(Redirected from Publication:1125060)
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)
