Notre Dame Journal of Formal Logic 46 (4):407-417 (2005)

Saeed Salehi
University of Tabriz
A polynomially bounded recursive realizability, in which the recursive functions used in Kleene's realizability are restricted to polynomially bounded functions, is introduced. It is used to show that provably total functions of Ruitenburg's Basic Arithmetic are polynomially bounded (primitive) recursive functions. This sharpens our earlier result where those functions were proved to be primitive recursive. Also a polynomially bounded schema of Church's Thesis is shown to be polynomially bounded realizable. So the schema is consistent with Basic Arithmetic, whereas it is inconsistent with Heyting Arithmetic
Keywords provably total function   Basic Arithmetic   Basic Logic   realizability
Categories (categorize this paper)
DOI 10.1305/ndjfl/1134397659
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: 62,363
Through your library

References found in this work BETA

On the Scheme of Induction for Bounded Arithmetic Formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (3):261-302.
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.

View all 9 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Elementary Realizability.Zlatan Damnjanovic - 1997 - Journal of Philosophical Logic 26 (3):311-339.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Strictly Primitive Recursive Realizability, I.Zlatan Damnjanovic - 1994 - Journal of Symbolic Logic 59 (4):1210-1227.
0-1 Laws for Recursive Structures.E. Grädel & A. Malmström - 1999 - Archive for Mathematical Logic 38 (4-5):205-215.
Bounded Modified Realizability.Fernando Ferreira & Ana Nunes - 2006 - Journal of Symbolic Logic 71 (1):329 - 346.
Multiple Realizability.Eric Funkhouser - 2007 - Philosophy Compass 2 (2):303–315.
A General Notion of Realizability.Lars Birkedal - 2002 - Bulletin of Symbolic Logic 8 (2):266-282.


Added to PP index

Total views
10 ( #869,694 of 2,445,401 )

Recent downloads (6 months)
1 ( #457,259 of 2,445,401 )

How can I increase my downloads?


My notes