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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,270

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

Extracting Algorithms from Intuitionistic Proofs.Fernando Ferreira & António Marques - 1998 - Mathematical Logic Quarterly 44 (2):143-160.
Provably total functions of intuitionistic bounded arithmetic.Victor Harnik - 1992 - Journal of Symbolic Logic 57 (2):466-477.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Provably recursive functions of constructive and relatively constructive theories.Morteza Moniri - 2010 - Archive for Mathematical Logic 49 (3):291-300.
Asymmetric Interpretations for Bounded Theories.Andrea Cantini - 1996 - Mathematical Logic Quarterly 42 (1):270-288.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
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.
Generalized quantifier and a bounded arithmetic theory for LOGCFL.Satoru Kuroda - 2007 - Archive for Mathematical Logic 46 (5-6):489-516.
A Bounded Translation of Intuitionistic Propositional Logic into Basic Propositional Logic.Mojtaba Aghaei & Mohammad Ardeshir - 2000 - Mathematical Logic Quarterly 46 (2):195-206.
Polynomial induction and length minimization in intuitionistic bounded arithmetic.Morteza Moniri - 2005 - Mathematical Logic Quarterly 51 (1):73-76.

Analytics

Added to PP
2014-01-16

Downloads
22 (#978,081)

6 months
4 (#1,260,583)

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