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
No references found.
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 (2009). Phase Transitions for Gödel Incompleteness. Annals of Pure and Applied Logic 157 (2):281-296.
Andreas Weiermann (2005). Analytic Combinatorics, Proof-Theoretic Ordinals, and Phase Transitions for Independence Results. Annals of Pure and Applied Logic 136 (1):189-218.
Eran Omri & Andreas Weiermann (2009). Classifying the Phase Transition Threshold for Ackermannian Functions. Annals of Pure and Applied Logic 158 (3):156-162.
Gyesik Lee (2007). A Comparison of Well-Known Ordinal Notation Systems for Ε0. Annals of Pure and Applied Logic 147 (1):48-70.
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 downloads24 ( #158,602 of 1,902,050 )
Recent downloads (6 months)10 ( #73,963 of 1,902,050 )
How can I increase my downloads?