Separations of theories in weak bounded arithmetic
\textit{P. Clote} and the author introduced [in: Feasible mathematics. II (to appear)] the first-order theories \(\text{TAC}^ i\), \(\text{TNC}^ i\) and TLS. \(\text{TAC}^ i\), \(\text{TNC}^ i\) and TLS correspond to \(\text{AC}^ i\), \(\text{NC}^{i+ 1}\) and LSPACE, respectively. TAC is the union of the \(\text{TAC}^ i\) and corresponds to AC. The author calls these theories, together with related theories, weak bounded arithmetic. In this paper, he proves the following separation results: (1) separation of \(\text{TLS}(\alpha)\) and \(\text{TAC}^ 1(\alpha)\); (2) separation of \(\text{TAC}(\alpha)\) and \(S^ 1_ 2(\alpha)\); (3) separation of \(\text{TNC}^ i(\alpha)\) and \(\text{TAC}^{i+ 1}(\alpha)\). \(\text{TAC}^ i(\alpha)\), \(\text{TLS}(\alpha)\), \(\text{TNC}^ i(\alpha)\) and \(\text{TAC}(\alpha)\) are obtained from \(\text{TAC}^ i\), TLS, \(\text{TNC}^ i\) and TAC, respectively, by introducing a free-order variable \(\alpha\).
- Separations of first and second order theories in bounded arithmetic
- Separating bounded arithmetical theories by Herbrand consistency
- scientific article; zbMATH DE number 2236625
- On a weak separation axiom
- On some weak separation axioms
- Structure and definability in general bounded arithmetic theories
- scientific article; zbMATH DE number 1048040
- Weak arithmetical interpretations for the logic of proofs
- Model theory of bounded arithmetic with applications to independence results
- scientific article; zbMATH DE number 29071
- Some results on cut-elimination, provable well-orderings, induction and reflection
- Separations of first and second order theories in bounded arithmetic
- Local splitters for bounded cotorsion theories
- scientific article; zbMATH DE number 2186953 (Why is no real title available?)
- A theory for Log-Space and NLIN versus co-NLIN
- An unexpected separation result in Linearly Bounded Arithmetic
- Weak theories of concatenation and minimal essentially undecidable theories. An encounter of \(\mathsf{WTC}\) and \(\mathsf{S2S}\)
- Proof-theoretic conservations of weak weak intuitionistic constructive set theories
This page was built for publication: Separations of theories in weak bounded arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1344280)
