Archive for Mathematical Logic 50 (5-6):643-660 (2011)

Abstract
We propose two admissible closures ${\mathbb{A}({\sf PTCA})}$ and ${\mathbb{A}({\sf PHCA})}$ of Ferreira’s system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) ${\mathbb{A}({\sf PTCA})}$ is conservative over PTCA with respect to ${\forall\exists\Sigma^b_1}$ sentences, and (ii) ${\mathbb{A}({\sf PHCA})}$ is conservative over full bounded arithmetic PHCA for ${\forall\exists\Sigma^b_{\infty}}$ sentences. This yields that (i) the ${\Sigma^b_1}$ definable functions of ${\mathbb{A}({\sf PTCA})}$ are the polytime functions, and (ii) the ${\Sigma^b_{\infty}}$ definable functions of ${\mathbb{A}({\sf PHCA})}$ are the functions in the polynomial time hierarchy
Keywords Polynomial time computable arithmetic  Kripke Platek set theory  Second order arithmetic
Categories (categorize this paper)
ISBN(s)
DOI 10.1007/s00153-011-0238-7
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 50,118
Through your library

References found in this work BETA

The Provably Terminating Operations of the Subsystem of Explicit Mathematics.Dieter Probst - 2011 - Annals of Pure and Applied Logic 162 (11):934-947.
The Strength of Extensionality II—Weak Weak Set Theories Without Infinity.Kentaro Sato - 2011 - Annals of Pure and Applied Logic 162 (8):579-646.
Elementary Explicit Types and Polynomial Time Operations.Daria Spescha & Thomas Strahm - 2009 - Mathematical Logic Quarterly 55 (3):245-258.

View all 9 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
A Feasible Theory for Analysis.Fernando Ferreira - 1994 - Journal of Symbolic Logic 59 (3):1001-1011.
Time Polynomial in Input or Output.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (3):1083-1088.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
HC of an Admissible Set.Sy D. Friedman - 1979 - Journal of Symbolic Logic 44 (1):95-102.
Groundwork for Weak Analysis.António M. Fernandes & Fernando Ferreira - 2002 - Journal of Symbolic Logic 67 (2):557-578.
⊃E is Admissible in “True” Relevant Arithmetic.Robert K. Meyer - 1998 - Journal of Philosophical Logic 27 (4):327-351.
⊃E is Admissible in “True” Relevant Arithmetic.Robert K. Meyer - 1998 - Journal of Philosophical Logic 27 (4):327 - 351.

Analytics

Added to PP index
2013-10-27

Total views
56 ( #164,120 of 2,324,569 )

Recent downloads (6 months)
1 ( #679,828 of 2,324,569 )

How can I increase my downloads?

Downloads

My notes