Separations of theories in weak bounded arithmetic
type: Item
instance of: scholarly article
title: Separations of theories in weak bounded arithmetic
zbMATH Open document ID: 0816.03026
DOI: 10.1016/0168-0072(94)00008-Q
author: Gaisi Takeuti
published in: Annals of Pure and Applied Logic
publication date: 1995-07-20T00:00:00Z
review text: \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\).
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 720936
zbMATH Keywords: weak bounded arithmetic
zbMATH Keywords: separation
reviewed by: M.Tetruashvili
MaRDI profile type: Publication
cites work: Q3794177
cites work: Q4035303
cites work: Q4850548
cites work: Bounded arithmetic and the polynomial hierarchy
Recommended article: Separations of first and second order theories in bounded arithmetic
Recommended article: Separating bounded arithmetical theories by Herbrand consistency
Recommended article: Q5711876
Recommended article: On a weak separation axiom
Recommended article: On some weak separation axioms
Recommended article: Structure and definability in general bounded arithmetic theories
Recommended article: Q4348126
Recommended article: Weak arithmetical interpretations for the Logic of Proofs
Recommended article: Q5393641
Recommended article: Q3986565
description: scientific article; zbMATH DE number 720936