Switch to: References

Add citations

You must login to add citations.
  1. A small reflection principle for bounded arithmetic.Rineke Verbrugge & Albert Visser - 1994 - Journal of Symbolic Logic 59 (3):785-812.
    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 (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • A Simplification of a Completeness Proof of Guaspari and Solovay.Dick H. J. de Jongh - 1987 - Studia Logica 46 (2):187-192.
    The modal completeness proofs of Guaspari and Solovay for their systems R and R⁻ are improved and the relationship between R and R⁻ is clarified.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   14 citations