A Feasible Theory for Analysis

Ferreira, Fernando

J. Symbolic Logic, Tome 59 (1994) no. 1, p. 1001-1011 / Harvested from Project Euclid

Résumé

We construct a weak second-order theory of arithmetic which includes Weak Konig's Lemma (WKL) for trees defined by bounded formulae. The provably total functions (with $\Sigma^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.

Publié le : 1994-09-14
Classification:

@article{1183744564,
     author = {Ferreira, Fernando},
     title = {A Feasible Theory for Analysis},
     journal = {J. Symbolic Logic},
     volume = {59},
     number = {1},
     year = {1994},
     pages = { 1001-1011},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744564}
}

Ferreira, Fernando. A Feasible Theory for Analysis. J. Symbolic Logic, Tome 59 (1994) no. 1, pp.  1001-1011. http://gdmltest.u-ga.fr/item/1183744564/