A FEASIBLE THEORY FOR ANALYSIS

被引：20

作者：

FERREIRA, F

机构：

来源：

JOURNAL OF SYMBOLIC LOGIC | 1994年 / 59卷 / 03期

关键词：

D O I：

10.2307/2275924

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 function (with SIGMA1b-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.

引用

页码：1001 / 1011

页数：11

共 11 条

[1] BUCHHOLZ W, 1990, CONT MATH, V106, P51
[2] BUSS S, 1908, THESIS PRINCETON U
[3] A CONSERVATION RESULT CONCERNING BOUNDED THEORIES AND THE COLLECTION AXIOM
BUSS, SR
[J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1987, 100 (04) : 709 - 715
[4] FERREIRA F., 1988, THESIS PENNSYLVANIA
[5] FERREIRA F, UNPUB PORTUGALIAE MA
[6] FERREIRA F, 1990, CONT MATH, V106, P137
[7] JOCKUSCH CG, 1972, T AM MATH SOC, V173, P35
[8] HILBERT PROGRAM 60 YEARS LATER
SIEG, W
[J]. JOURNAL OF SYMBOLIC LOGIC, 1988, 53 (02) : 338 - 348
[9] FACTORIZATION OF POLYNOMIALS AND SIGMA-10 INDUCTION
SIMPSON, SG
SMITH, RL
[J]. ANNALS OF PURE AND APPLIED LOGIC, 1986, 31 (2-3) : 289 - 306
[10] SIMPSON SG, 1987, PROOF THEORY, P432

← 1 2 →