Mathematical Logic Quarterly 49 (4):425 (2003)

IPV is the intuitionistic theory axiomatized by Cook's equational theory PV plus PIND on NP-formulas. Two extensions of IPV were introduced by Buss and by Cook and Urquhart by adding PIND for formulas of the form A ∨ B, respectively ¬¬A, where A is NP and x is not free in B. Cook and Urquhart posed the question of whether these extensions are proper. We show that in each of the two cases the extension is proper unless the polynomial hierarchy collapses
Keywords Kripke model  negative translation  First‐order arithmetic  polynomial hierarchy  polynomial induction  NP‐formula
Categories (categorize this paper)
DOI 10.1002/malq.200310045
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: 63,133
External links

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)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Admissible Closures of Polynomial Time Computable Arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5-6):643-660.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
A New "Feasible" Arithmetic.Stephen Bellantoni & Martin Hofmann - 2002 - Journal of Symbolic Logic 67 (1):104-116.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
The Strength of Sharply Bounded Induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
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.


Added to PP index

Total views
24 ( #453,504 of 2,448,218 )

Recent downloads (6 months)
1 ( #451,050 of 2,448,218 )

How can I increase my downloads?


My notes