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

Authors
Abstract
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
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,688
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.

Analytics

Added to PP index
2013-12-01

Total views
21 ( #473,313 of 2,349,560 )

Recent downloads (6 months)
2 ( #331,095 of 2,349,560 )

How can I increase my downloads?

Downloads

My notes