End extensions of models of linearly bounded arithmetic

被引：8

作者：

Zambella, D ^{[1
]}

机构：

[1] Univ Amsterdam, Fac Wiskunde & Informat, Dept Math & Comp Sci, NL-1018 TV Amsterdam, Netherlands

来源：

ANNALS OF PURE AND APPLIED LOGIC | 1997年 / 88卷 / 2-3期

关键词：

bounded arithmetic; end extensions;

D O I：

10.1016/S0168-0072(97)00026-2

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that every model of I Delta(0) has all end extension to a model of a theory (extending Buss' S-2(0)) where log-space computable function are formalizable. We also show the existence of an isomorphism between models of I Delta(0) and models of linear arithmetic LA (i.e., second-order Presburger arithmetic with finite comprehension for bounded formulas).

引用

页码：263 / 277

页数：15

共 10 条

[1] COMBINATORIAL PRINCIPLES IN ELEMENTARY NUMBER-THEORY
BERARDUCCI, A
INTRIGILA, B
[J]. ANNALS OF PURE AND APPLIED LOGIC, 1991, 55 (01) : 35 - 50
[2] RELATING THE BOUNDED ARITHMETIC AND POLYNOMIAL-TIME HIERARCHIES
BUSS, SR
[J]. ANNALS OF PURE AND APPLIED LOGIC, 1995, 75 (1-2) : 67 - 77
[3] HAJEK P, 1993, METAMATHEMATICS 1 OR
[4] Krajicek Jan, 1995, BOUNDED ARITHMETIC P
[5] COUNTING DELTA-O SETS
PARIS, J
WILKIE, A
[J]. FUNDAMENTA MATHEMATICAE, 1987, 127 (01) : 67 - 76
[6] PROVABILITY OF THE PIGEONHOLE PRINCIPLE AND THE EXISTENCE OF INFINITELY MANY PRIMES
PARIS, JB
WILKIE, AJ
WOODS, AR
[J]. JOURNAL OF SYMBOLIC LOGIC, 1988, 53 (04) : 1235 - 1244
[7] TAKEUTI G, 1993, ARITHMETIC PROOF THE, P364
[8] ON THE SCHEME OF INDUCTION FOR BOUNDED ARITHMETIC FORMULAS
WILKIE, AJ
PARIS, JB
[J]. ANNALS OF PURE AND APPLIED LOGIC, 1987, 35 (03) : 261 - 302
[9] WILKIE AJ, 1989, METHODOLOGY PHILOS S, V8, P143
[10] Notes on polynomially bounded arithmetic
Zambella, D
[J]. JOURNAL OF SYMBOLIC LOGIC, 1996, 61 (03) : 942 - 966

← 1 →