Dynamic ordinal analysis |
| |
Authors: | Arnold Beckmann |
| |
Institution: | 1.Institut für Mathematische Logik und Grundlagenforschung, Westf?lische Wilhelms-Universit?t, Einsteinstr. 62, 48149 Münster, Germany. e-mail: Arnold.Beckmann@math.uni-muenster.de,DE |
| |
Abstract: | Dynamic ordinal analysis is ordinal analysis for weak arithmetics like fragments of bounded arithmetic. In this paper we
will define dynamic ordinals – they will be sets of number theoretic functions measuring the amount of sΠ
b
1(X) order induction available in a theory. We will compare order induction to successor induction over weak theories. We will
compute dynamic ordinals of the bounded arithmetic theories sΣ
b
n
(X)−L
m
IND for m=n and m=n+1, n≥0. Different dynamic ordinals lead to separation. In this way we will obtain several separation results between these relativized
theories. We will generalize our results to further languages extending the language of bounded arithmetic.
Received: 27 April 2001 /
Published online: 19 December 2002
The results for sΣ
b
n
(X)−L
m
IND are part of the authors dissertation 3]; the results for sΣ
b
m
(X)−L
m+1
IND base on results of ARAI 1].
Mathematics Subject Classification (2000): Primary 03F30; Secondary 03F05, 03F50
Key words or phrases: Dynamic ordinal – Bounded arithmetic – Proof-theoretic ordinal – Order induction – Semi-formal system – Cut-elimination |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|