Archive for Mathematical Logic 42 (4):303-334 (2003)

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
Keywords Legacy
Categories (categorize this paper)
DOI 10.1007/s00153-002-0169-4
Options
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: 52,792
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On the Scheme of Induction for Bounded Arithmetic Formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (3):261-302.
Existence and Feasibility in Arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
Structure and Definability in General Bounded Arithmetic Theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.
Relating the Bounded Arithmetic and Polynomial Time Hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.

View all 8 references / Add more references

Citations of this work BETA

Phase Transitions for Gödel Incompleteness.Andreas Weiermann - 2009 - Annals of Pure and Applied Logic 157 (2-3):281-296.
On the Computational Complexity of Cut-Reduction.Klaus Aehlig & Arnold Beckmann - 2010 - Annals of Pure and Applied Logic 161 (6):711-736.

View all 7 citations / Add more citations

Similar books and articles

An Ordinal Analysis of Parameter Free Π1 2-Comprehension.Michael Rathjen - 2004 - Archive for Mathematical Logic 44 (3):263-362.
Register Computations on Ordinals.Peter Koepke & Ryan Siders - 2008 - Archive for Mathematical Logic 47 (6):529-548.
Normal Forms for Elementary Patterns.Timothy J. Carlson & Gunnar Wilken - 2012 - Journal of Symbolic Logic 77 (1):174-194.
Proof Theory and Ordinal Analysis.W. Pohlers - 1991 - Archive for Mathematical Logic 30 (5-6):311-376.
Ordinal Arithmetic and $\Sigma_{1}$ -Elementarity.Timothy J. Carlson - 1999 - Archive for Mathematical Logic 38 (7):449-460.
An Ordinal Analysis of Stability.Michael Rathjen - 2004 - Archive for Mathematical Logic 44 (1):1-62.
Assignment of Ordinals to Patterns of Resemblance.Gunnar Wilken - 2007 - Journal of Symbolic Logic 72 (2):704 - 720.
Operating on the Universe.Narciso Garcia - 1988 - Archive for Mathematical Logic 27 (1):61-68.

Analytics

Added to PP index
2013-12-01

Total views
69 ( #136,251 of 2,342,397 )

Recent downloads (6 months)
1 ( #514,645 of 2,342,397 )

How can I increase my downloads?

Downloads

My notes