Back to Search
Start Over
Lifting independence results in bounded arithmetic.
- Source :
- Archive for Mathematical Logic; 1999, Vol. 38 Issue 2, p123, 16p
- Publication Year :
- 1999
-
Abstract
- Abstract. We investigate the problem how to lift the non -- Universal quantifier SIGMA[sup b, sub 1] (alpha) -- conservativity of T[sup 2, sub 2] (alpha) over S[sup 2, sub 2] (alpha) to the expected non -- Universal quantifier SIGMA[sup b, sub i] (alpha) -- conservativity of T[sup i+1, sub 2](alpha) over S[sup i+1, sub 2] (alpha), for i > 1. We give a non-trivial refinement of the "lifting method" developed in [4, 8], and we prove a sufficient condition on a Universal quantifier SIGMA[sup b, sub 1] (f)-consequence of T[sub 2] (f) to yield the non-conservation result. Further we prove that Ramsey's theorem, a Universal quantifier SIGMA[sup b, sub 1](alpha) -- formula, is not provable in T[sup 1, sub 2] (alpha), and that Universal quantifier SIGMA[sup b, sub 1] (alpha)- conservativity of T[sup i +1, sub 2] (alpha) over T[sup i, sub 2] (alpha) implies Universal quantifier SIGMa[sup b, sub j](alpha) -- conservativity of the whole T[sub 2](alpha) over T[sup i, sub 2](alpha), for any j is greater than or equal to 2. [ABSTRACT FROM AUTHOR]
- Subjects :
- ARITHMETIC
MATHEMATICAL functions
RAMSEY theory
BINARY number system
Subjects
Details
- Language :
- English
- ISSN :
- 09335846
- Volume :
- 38
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Archive for Mathematical Logic
- Publication Type :
- Academic Journal
- Accession number :
- 4684356
- Full Text :
- https://doi.org/10.1007/s001530050118