Annals of Pure and Applied Logic 100 (1-3):189-245 (1999)

The bounded arithmetic theories R2i, S2i, and T2i are closely connected with complexity theory. This paper is motivated by the questions: what are the Σi+1b-definable multifunctions of R2i? and when is one theory conservative over another? To answer these questions we consider theories , and where induction is restricted to prenex formulas. We also define which has induction up to the 0 or 1-ary L2-terms in the set τ. We show and and for . We show that the -multifunctions of are FPΣip and that those of are FPΣip. For -definability we get FPΣi+k+1p for all these theories. Write for the set of terms 2min,t) where ℓ is a finite product of terms in τ and tL2. We prove and we show - INDτ provided τO2. This gives a proof theoretic proof that S2iΔi+1b-LIND and -LLIND solving an open problem. For τO2, we define using weak replacement axioms and show . We show if or if or if where τ′ has an unbounded term then PH=B. We separate PΣip from PΣip for behaved ℓ and deduce theory separations. We lastly introduce a notion of a model separating two theories and derive some consequences
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(99)00008-1
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: 52,973
Through your library

References found in this work BETA

Existence and Feasibility in Arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
Bounded Arithmetic and the Polynomial Hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.

Add more references

Citations of this work BETA

Multifunction Algebras and the Provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Dynamic Ordinal Analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Bootstrapping, Part I.Sedki Boughattas & J. -P. Ressayre - 2010 - Annals of Pure and Applied Logic 161 (4):511-533.

View all 15 citations / Add more citations

Similar books and articles

Two General Results on Intuitionistic Bounded Theories.Fernando Ferreira - 1999 - Mathematical Logic Quarterly 45 (3):399-407.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
On Interpretations of Bounded Arithmetic and Bounded Set Theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Definability and Definable Groups in Simple Theories.Anand Pillay - 1998 - Journal of Symbolic Logic 63 (3):788-796.
Regularity in Models of Arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Dynamic Ordinal Analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Strengths and Weaknesses of LH Arithmetic.Chris Pollett & Randall Pruim - 2002 - Mathematical Logic Quarterly 48 (2):221-243.


Added to PP index

Total views
22 ( #450,017 of 2,344,024 )

Recent downloads (6 months)
1 ( #514,126 of 2,344,024 )

How can I increase my downloads?


My notes