# A small reflection principle for bounded arithmetic

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

 Authors Rineke (Laurina Christina) Verbrugge University of Groningen 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 Logic and Philosophy of Logic (categorize this paper) DOI 10.2307/2275908 Options Edit this record Mark as duplicate Export citation Request removal from index

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,634

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)

## 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.

## 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.

## 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.