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

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
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: 65,811
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.

View all 19 citations / Add more citations

Similar books and articles


Added to PP index

Total views
279 ( #35,626 of 2,463,174 )

Recent downloads (6 months)
1 ( #449,391 of 2,463,174 )

How can I increase my downloads?


My notes