Journal of Symbolic Logic 59 (3):1001-1011 (1994)

Authors
Abstract
We construct a weak second-order theory of arithmetic which includes Weak König's Lemma (WKL) for trees defined by bounded formulae. The provably total functions (with Σ b 1 -graphs) of this theory are the polynomial time computable functions. It is shown that the first-order strength of this version of WKL is exactly that of the scheme of collection for bounded formulae
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275924
Options
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: 54,715
Through your library

References found in this work BETA

Factorization of Polynomials and °1 Induction.S. G. Simpson - 1986 - Annals of Pure and Applied Logic 31:289.

Add more references

Citations of this work BETA

Bounded Functional Interpretation.Fernando Ferreira & Paulo Oliva - 2005 - Annals of Pure and Applied Logic 135 (1):73-112.
Number Theory and Elementary Arithmetic.Jeremy Avigad - 2003 - Philosophia Mathematica 11 (3):257-284.
Forcing in Proof Theory.Jeremy Avigad - 2004 - Bulletin of Symbolic Logic 10 (3):305-333.
Groundwork for Weak Analysis.António M. Fernandes & Fernando Ferreira - 2002 - Journal of Symbolic Logic 67 (2):557-578.

View all 17 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
277 ( #28,427 of 2,386,657 )

Recent downloads (6 months)
6 ( #128,435 of 2,386,657 )

How can I increase my downloads?

Downloads

My notes