A Counterexample to Polynomially Bounded Realizability of Basic Arithmetic

, &
Notre Dame Journal of Formal Logic 60 (3):481-489 (2019)
  Copy   BIBTEX

Abstract

We give a counterexample to the claim that every provably total function of Basic Arithmetic is a polynomially bounded primitive recursive function.

Categories

Keywords

Reprint years

DOI

10.1215/00294527-2019-0013

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

Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
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.
Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ibid., vol. 52 , pp. 143–153. - Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Ibid., vol. 75 , pp. 67–77. - Domenico Zambella. Notes on polynomially bounded arithmetic. The journal of symbolic logic, vol. 61 , pp. 942–966. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
An Independence Result on Weak Second Order Bounded Arithmetic.Satoru Kuroda - 2001 - Mathematical Logic Quarterly 47 (2):183-186.
Provably total functions of Basic Arithemtic.Saeed Salehi - 2003 - Mathematical Logic Quarterly 49 (3):316.
Finite reverse mathematics.Harvey Friedman - manuscript
Elementary realizability.Zlatan Damnjanovic - 1997 - Journal of Philosophical Logic 26 (3):311-339.
Confined modified realizability.Gilda Ferreira & Paulo Oliva - 2010 - Mathematical Logic Quarterly 56 (1):13-28.
Minimal realizability of intuitionistic arithmetic and elementary analysis.Zlatan Damnjanovic - 1995 - Journal of Symbolic Logic 60 (4):1208-1241.
Upper bounds on complexity of Frege proofs with limited use of certain schemata.Pavel Naumov - 2006 - Archive for Mathematical Logic 45 (4):431-446.
Extracting Algorithms from Intuitionistic Proofs.Fernando Ferreira & António Marques - 1998 - Mathematical Logic Quarterly 44 (2):143-160.
Intuitionistic formal theories with realizability in subrecursive classes.Anatoly Petrovich Beltiukov - 1997 - Annals of Pure and Applied Logic 89 (1):3-15.
Infinitely Peano differentiable functions in polynomially bounded o-minimal structures.Andreas Fischer - 2010 - Annals of Pure and Applied Logic 161 (12):1520-1524.

Analytics

Added to PP
2019-07-04

Downloads
30 (#521,181)

6 months
13 (#184,769)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Basic Predicate Calculus.Wim Ruitenburg - 1998 - Notre Dame Journal of Formal Logic 39 (1):18-46.
Provably total functions of Basic Arithemtic.Saeed Salehi - 2003 - Mathematical Logic Quarterly 49 (3):316.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
An Introduction to Basic Arithmetic.Mohammad Ardeshir & Bardyaa Hesaam - 2008 - Logic Journal of the IGPL 16 (1):1-13.

Add more references