An application of graphical enumeration to PA
Journal of Symbolic Logic 68 (1):5-16 (2003)
| Abstract | 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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,709 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesSamuel 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.
Toshiyasu Arai (1998). Variations on a Theme by Weiermann. Journal of Symbolic Logic 63 (3):897-925.
Paolo Casalegno (1985). On the T-Degrees of Partial Functions. Journal of Symbolic Logic 50 (3):580-588.
Michael Rathjen (1996). Monotone Inductive Definitions in Explicit Mathematics. Journal of Symbolic Logic 61 (1):125-146.
A. R. D. Mathias (2001). Slim Models of Zermelo Set Theory. Journal of Symbolic Logic 66 (2):487-496.
Robert Bonnet & Matatyahu Rubin (1991). Elementary Embedding Between Countable Boolean Algebras. Journal of Symbolic Logic 56 (4):1212-1229.
Matatyahu Rubin & Saharon Shelah (1983). On the Expressibility Hierarchy of Magidor-Malitz Quantifiers. Journal of Symbolic Logic 48 (3):542-557.
Jacek Cichoń & Janusz Pawlikowski (1986). On Ideals of Subsets of the Plane and on Cohen Reals. Journal of Symbolic Logic 51 (3):560-569.
Steven Givant (2003). Inequivalent Representations of Geometric Relation Algebras. Journal of Symbolic Logic 68 (1):267-310.
Alexis Bés & Denis Richard (1998). Undecidable Extensions of Skolem Arithmetic. Journal of Symbolic Logic 63 (2):379-401.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
