Two General Results on Intuitionistic Bounded Theories

Mathematical Logic Quarterly 45 (3):399-407 (1999)
  Copy   BIBTEX

Abstract

We study, within the framework of intuitionistic logic, two well-known general results of bounded arithmetic. Firstly, Parikh's theorem on the existence of bounding terms for the provably total functions. Secondly, the result which states that adding the scheme of bounded collection to bounded theories does not yield new II2 consequences

Categories

Keywords

Reprint years

DOI

10.1002/malq.19990450310

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Provably recursive functions of constructive and relatively constructive theories.Morteza Moniri - 2010 - Archive for Mathematical Logic 49 (3):291-300.
On End‐Extensions of Models of ¬exp.Fernando Ferreira - 1996 - Mathematical Logic Quarterly 42 (1):1-18.
Separations of first and second order theories in bounded arithmetic.Masahiro Yasumoto - 2005 - Archive for Mathematical Logic 44 (6):685-688.
A Remark on Independence Results for Sharply Bounded Arithmetic.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (4):568-570.
A Model‐Theoretic Property of Sharply Bounded Formulae, with some Applications.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (2):205-215.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
Strict $${\Pi^1_1}$$ -reflection in bounded arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.
A note on the E1 collection scheme and fragments of bounded arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2010 - Mathematical Logic Quarterly 56 (2):126-130.
On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories.Leszek Aleksander Kołodziejczyk - 2006 - Journal of Symbolic Logic 71 (2):624 - 638.
Bounded Scott Set Saturation.Alex M. McAllister - 2002 - Mathematical Logic Quarterly 48 (2):245-259.
A Note on Conservativity Relations among Bounded Arithmetic Theories.Russell Impagliazzo & Jan Krajíček - 2002 - Mathematical Logic Quarterly 48 (3):375-377.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.

Analytics

Added to PP
2014-01-16

Downloads
18 (#814,090)

6 months
2 (#1,240,909)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

Existence and feasibility in arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
Extracting Algorithms from Intuitionistic Proofs.Fernando Ferreira & António Marques - 1998 - Mathematical Logic Quarterly 44 (2):143-160.

Add more references