An application of graphical enumeration to PA

Journal of Symbolic Logic 68 (1):5-16 (2003)
  Copy   BIBTEX

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...

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Inequivalent representations of geometric relation algebras.Steven Givant - 2003 - Journal of Symbolic Logic 68 (1):267-310.
Elementary embedding between countable Boolean algebras.Robert Bonnet & Matatyahu Rubin - 1991 - Journal of Symbolic Logic 56 (4):1212-1229.
Slim models of zermelo set theory.A. R. D. Mathias - 2001 - Journal of Symbolic Logic 66 (2):487-496.
Monotone inductive definitions in explicit mathematics.Michael Rathjen - 1996 - Journal of Symbolic Logic 61 (1):125-146.
On the t-degrees of partial functions.Paolo Casalegno - 1985 - Journal of Symbolic Logic 50 (3):580-588.
Variations on a theme by Weiermann.Toshiyasu Arai - 1998 - Journal of Symbolic Logic 63 (3):897-925.
Undecidable extensions of Skolem arithmetic.Alexis Bès & Denis Richard - 1998 - Journal of Symbolic Logic 63 (2):379-401.

Analytics

Added to PP
2009-01-28

Downloads
41 (#339,849)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Current Research on Gödel’s Incompleteness Theorems.Yong Cheng - 2021 - Bulletin of Symbolic Logic 27 (2):113-167.
Phase transitions for Gödel incompleteness.Andreas Weiermann - 2009 - Annals of Pure and Applied Logic 157 (2-3):281-296.
Pure Σ2-elementarity beyond the core.Gunnar Wilken - 2021 - Annals of Pure and Applied Logic 172 (9):103001.

View all 11 citations / Add more citations

References found in this work

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.
On the Slowly Well Orderedness of ɛo.Toshiyasu Arai - 2002 - Mathematical Logic Quarterly 48 (1):125-130.

Add more references