Mathematical Logic Quarterly 51 (2):191-200 (2005)
AbstractThe theories Si1 and Ti1 are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i, a Σbi+1-formula TOPi, which expresses a form of the total ordering principle, is exhibited that is provable in Si+11 , but unprovable in Ti1. This is in contrast with the classical situation, where Si+12 is conservative over Ti2 w. r. t. Σbi+1-sentences. The independence results are proved by translations into propositional logic, and using lower bounds for corresponding propositional proof systems
Similar books and articles
Added to PP
Historical graph of downloads
Citations of this work
No citations found.
References found in this work
Structure and definability in general bounded arithmetic theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.
Witnessing functions in bounded arithmetic and search problems.Mario Chiari & Jan Krajíček - 1998 - Journal of Symbolic Logic 63 (3):1095-1115.
A Note on Conservativity Relations among Bounded Arithmetic Theories.Russell Impagliazzo & Jan Krajíček - 2002 - Mathematical Logic Quarterly 48 (3):375-377.
Witnessing Functions in Bounded Arithmetic and Search Problems.Mario Chiari & Jan Krajíček - 1998 - Journal of Symbolic Logic 63 (3):1095-1115.