Mathematical Logic Quarterly 51 (1):73-76 (2005)

It is shown that the feasibly constructive arithmetic theory IPV does not prove LMIN, unless the polynomial hierarchy CPV-provably collapses. It is proved that PV plus LMIN intuitionistically proves PIND. It is observed that PV + PIND does not intuitionistically prove NPB, a scheme which states that the extended Frege systems are not polynomially bounded
Keywords Kripke model  IPV  length minimization  extended Frege system  polynomial induction
Categories (categorize this paper)
DOI 10.1002/malq.200410008
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,247
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

Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.

Add more citations

Similar books and articles

Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
On Two Questions About Feasibly Constructive Arithmetic.Morteza Moniri - 2003 - Mathematical Logic Quarterly 49 (4):425.
The Strength of Sharply Bounded Induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
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.
Time Polynomial in Input or Output.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (3):1083-1088.
A New "Feasible" Arithmetic.Stephen Bellantoni & Martin Hofmann - 2002 - Journal of Symbolic Logic 67 (1):104-116.


Added to PP index

Total views
16 ( #642,655 of 2,448,588 )

Recent downloads (6 months)
1 ( #449,192 of 2,448,588 )

How can I increase my downloads?


My notes