David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
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)|
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
Michael Rathjen & Andreas Weiermann (1993). Proof-Theoretic Investigations on Kruskal's Theorem. Annals of Pure and Applied Logic 60 (1):49-88.
Harvey Friedman & Michael Sheard (1995). Elementary Descent Recursion and Proof Theory. Annals of Pure and Applied Logic 71 (1):1-45.
Citations of this work BETA
Andrey Bovykin (2010). Unprovability Threshold for the Planar Graph Minor Theorem. Annals of Pure and Applied Logic 162 (3):175-181.
Andreas Weiermann (2005). Analytic Combinatorics, Proof-Theoretic Ordinals, and Phase Transitions for Independence Results. Annals of Pure and Applied Logic 136 (1):189-218.
Andreas Weiermann (2009). Phase Transitions for Gödel Incompleteness. Annals of Pure and Applied Logic 157 (2):281-296.
Wolfram Pohlers (2005). 2004 Summer Meeting of the Association for Symbolic Logic. Bulletin of Symbolic Logic 11 (2):249-312.
Eran Omri & Andreas Weiermann (2009). Classifying the Phase Transition Threshold for Ackermannian Functions. Annals of Pure and Applied Logic 158 (3):156-162.
Similar books and articles
Samuel R. Buss (1994). On Gödel's Theorems on Lengths of Proofs I: Number of Lines and Speedup for Arithmetics. Journal of Symbolic Logic 59 (3):737-756.
Steven Givant (2003). Inequivalent Representations of Geometric Relation Algebras. Journal of Symbolic Logic 68 (1):267-310.
Jacek Cichoń & Janusz Pawlikowski (1986). On Ideals of Subsets of the Plane and on Cohen Reals. Journal of Symbolic Logic 51 (3):560-569.
Matatyahu Rubin & Saharon Shelah (1983). On the Expressibility Hierarchy of Magidor-Malitz Quantifiers. Journal of Symbolic Logic 48 (3):542-557.
Robert Bonnet & Matatyahu Rubin (1991). Elementary Embedding Between Countable Boolean Algebras. Journal of Symbolic Logic 56 (4):1212-1229.
A. R. D. Mathias (2001). Slim Models of Zermelo Set Theory. Journal of Symbolic Logic 66 (2):487-496.
Michael Rathjen (1996). Monotone Inductive Definitions in Explicit Mathematics. Journal of Symbolic Logic 61 (1):125-146.
Paolo Casalegno (1985). On the T-Degrees of Partial Functions. Journal of Symbolic Logic 50 (3):580-588.
Toshiyasu Arai (1998). Variations on a Theme by Weiermann. Journal of Symbolic Logic 63 (3):897-925.
Alexis Bés & Denis Richard (1998). Undecidable Extensions of Skolem Arithmetic. Journal of Symbolic Logic 63 (2):379-401.
Added to index2009-01-28
Total downloads25 ( #160,357 of 1,911,740 )
Recent downloads (6 months)3 ( #254,551 of 1,911,740 )
How can I increase my downloads?