Journal of Symbolic Logic 59 (3):785-812 (1994)

Authors
Abstract
We investigate the theory IΔ 0 + Ω 1 and strengthen [Bu86. Theorem 8.6] to the following: if NP ≠ co-NP. then Σ-completeness for witness comparison formulas is not provable in bounded arithmetic. i.e. $I\delta_0 + \Omega_1 + \nvdash \forall b \forall c (\exists a(\operatorname{Prf}(a.c) \wedge \forall = \leq a \neg \operatorname{Prf} (z.b))\\ \rightarrow \operatorname{Prov} (\ulcorner \exists a(\operatorname{Prf}(a. \bar{c}) \wedge \forall z \leq a \neg \operatorname{Prf}(z.\bar{b})) \urcorner)).$ Next we study a "small reflection principle" in bounded arithmetic. We prove that for all sentences φ $I\Delta_0 + \Omega_1 \vdash \forall x \operatorname{Prov}(\ulcorner \forall y \leq \bar{x} (\operatorname{Prf} (y. \overline{\ulcorner \varphi \urcorner}) \rightarrow \varphi)\urcorner).$ The proof hinges on the use of definable cuts and partial satisfaction predicates akin to those introduced by Pudlak in [Pu86]. Finally, we give some applications of the small reflection principle, showing that the principle can sometimes be invoked in order to circumvent the use of provable Σ-completeness for witness comparison formulas
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275908
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: 53,634
Through your library

References found in this work BETA

Proof Theory.Gaisi Takeuti - 1990 - Studia Logica 49 (1):160-161.
On the Scheme of Induction for Bounded Arithmetic Formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (3):261-302.
The Formalization of Interpretability.Albert Visser - 1991 - Studia Logica 50 (1):81 - 105.
Bounded Arithmetic and Truth Definition.Gaisi Takeuti - 1988 - Annals of Pure and Applied Logic 39 (1):75-104.

View all 19 references / Add more references

Citations of this work BETA

Faith & Falsity.Albert Visser - 2004 - Annals of Pure and Applied Logic 131 (1):103-131.
No Escape From Vardanyan's Theorem.Albert Visser & Maartje de Jonge - 2006 - Archive for Mathematical Logic 45 (5):539-554.

Add more citations

Similar books and articles

Consequences of Arithmetic for Set Theory.Lorenz Halbeisen & Saharon Shelah - 1994 - Journal of Symbolic Logic 59 (1):30-40.
Frege's Unofficial Arithmetic.Agustín Rayo - 2002 - Journal of Symbolic Logic 67 (4):1623-1638.
Stretchings.O. Finkel & J. P. Ressayre - 1996 - Journal of Symbolic Logic 61 (2):563-585.
Classification and Interpretation.Andreas Baudisch - 1989 - Journal of Symbolic Logic 54 (1):138-159.

Analytics

Added to PP index
2009-01-28

Total views
56 ( #170,138 of 2,349,021 )

Recent downloads (6 months)
3 ( #238,484 of 2,349,021 )

How can I increase my downloads?

Downloads

My notes