Mathematical Logic Quarterly 51 (2):191-200 (2005)

Abstract
The 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
Keywords Bounded Arithmetic  propositional proof system
Categories (categorize this paper)
DOI 10.1002/malq.200410019
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 51,304
Through your library

References found in this work BETA

Structure and Definability in General Bounded Arithmetic Theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.
Dynamic Ordinal Analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Analytics

Added to PP index
2013-11-03

Total views
20 ( #485,401 of 2,330,096 )

Recent downloads (6 months)
2 ( #393,046 of 2,330,096 )

How can I increase my downloads?

Downloads

My notes