Journal of Symbolic Logic 68 (1):5-16 (2003)
For α less than ε0 let $N\alpha$ be the number of occurrences of ω in the Cantor normal form of α. Further let $\mid n \mid$ denote the binary length of a natural number n, let $\mid n\mid_h$ denote the h-times iterated binary length of n and let inv(n) be the least h such that $\mid n\mid_h \leq 2$ . We show that for any natural number h first order Peano arithmetic, PA, does not prove the following sentence: For all K there exists an M which bounds the lengths n of all strictly descending sequences $\langle \alpha_0, ..., \alpha_n\rangle$ of ordinals less than ε0 which satisfy the condition that the Norm $N\alpha_i$ of the i-th term αi is bounded by $K + \mid i \mid \cdot \mid i\mid_h$ . As a supplement to this (refined Friedman style) independence result we further show that e.g., primitive recursive arithmetic, PRA, proves that for all K there is an M which bounds the length n of any strictly descending sequence $\langle \alpha_0,..., \alpha_n\rangle$ of ordinals less than ε0 which satisfies the condition that the Norm $N\alpha_i$ of the i-th term αi is bounded by $K + \mid i \mid\cdot inv(i)$ . The proofs are based on results from proof theory and techniques from asymptotic analysis of Polya-style enumerations. Using results from Otter and from Matou $\breve$ ek and Loebl we obtain similar characterizations for finite bad sequences of finite trees in terms of Otter's tree constant 2.9557652856...
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
Proof-Theoretic Investigations on Kruskal's Theorem.Michael Rathjen & Andreas Weiermann - 1993 - Annals of Pure and Applied Logic 60 (1):49-88.
Elementary Descent Recursion and Proof Theory.Harvey Friedman & Michael Sheard - 1995 - Annals of Pure and Applied Logic 71 (1):1-45.
Citations of this work BETA
Unprovability Threshold for the Planar Graph Minor Theorem.Andrey Bovykin - 2010 - Annals of Pure and Applied Logic 162 (3):175-181.
Analytic Combinatorics, Proof-Theoretic Ordinals, and Phase Transitions for Independence Results.Andreas Weiermann - 2005 - Annals of Pure and Applied Logic 136 (1):189-218.
Phase Transitions for Gödel Incompleteness.Andreas Weiermann - 2009 - Annals of Pure and Applied Logic 157 (2):281-296.
Classifying the Phase Transition Threshold for Ackermannian Functions.Eran Omri & Andreas Weiermann - 2009 - Annals of Pure and Applied Logic 158 (3):156-162.
2004 Summer Meeting of the Association for Symbolic Logic.Wolfram Pohlers - 2005 - Bulletin of Symbolic Logic 11 (2):249-312.
Similar books and articles
On Gödel's Theorems on Lengths of Proofs I: Number of Lines and Speedup for Arithmetics.Samuel R. Buss - 1994 - Journal of Symbolic Logic 59 (3):737-756.
Variations on a Theme by Weiermann.Toshiyasu Arai - 1998 - Journal of Symbolic Logic 63 (3):897-925.
On the T-Degrees of Partial Functions.Paolo Casalegno - 1985 - Journal of Symbolic Logic 50 (3):580-588.
Monotone Inductive Definitions in Explicit Mathematics.Michael Rathjen - 1996 - Journal of Symbolic Logic 61 (1):125-146.
Slim Models of Zermelo Set Theory.A. R. D. Mathias - 2001 - Journal of Symbolic Logic 66 (2):487-496.
Elementary Embedding Between Countable Boolean Algebras.Robert Bonnet & Matatyahu Rubin - 1991 - Journal of Symbolic Logic 56 (4):1212-1229.
On the Expressibility Hierarchy of Magidor-Malitz Quantifiers.Matatyahu Rubin & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (3):542-557.
On Ideals of Subsets of the Plane and on Cohen Reals.Jacek Cichoń & Janusz Pawlikowski - 1986 - Journal of Symbolic Logic 51 (3):560-569.
Inequivalent Representations of Geometric Relation Algebras.Steven Givant - 2003 - Journal of Symbolic Logic 68 (1):267-310.
Added to index2009-01-28
Total downloads26 ( #196,850 of 2,171,800 )
Recent downloads (6 months)1 ( #326,702 of 2,171,800 )
How can I increase my downloads?