Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T15:37:48.519Z Has data issue: false hasContentIssue false
  • English
  • Français

An application of graphical enumeration to PA*

Published online by Cambridge University Press:  12 March 2014

Andreas Weiermann
Andreas Weiermann*
Affiliation:
Institut Für Mathematische Logik und, Grundlagenforschung der Westfälischen Wilhelms-Universität Münster, Einsteinstr. 62, D-48149 Münster., Germany, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

For α less than ε0 let Nα be the number of occurrences of ω in the Cantor normal form of α. Further let ∣n∣ denote the binary length of a natural number n, let ∣n∣h denote the h-times iterated binary length of n and let inv(n) be the least h such that ∣n∣h ≤ 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 〈α0, …, αn〉 of ordinals less than ε0 which satisfy the condition that the Norm Nαi of the i-th term αi is bounded by K + ∣i∣ · ∣i∣i.

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 〈α0, …, αn〉 of ordinals less than ε0 which satisfies the condition that the Norm Nαi of the i-th term αi is bounded by K + ∣i∣ · 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šek and Loebl we obtain similar characterizations for finite bad sequences of finite trees in terms of Otter's tree constant 2.9557652856.…

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 68 , Issue 1 , March 2003 , pp. 5 - 16
Copyright
Copyright © Association for Symbolic Logic 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

Research supported by a Heisenberg-Fellowship of the Deutsche Forschungsgemeinschaft.

References

REFERENCES

[1]Arai, T., On the slowly well orderedness of ε 0, Mathematical Logic Quarterly, vol. 48 (2002), pp. 125–130.3.0.CO;2-N>CrossRefGoogle Scholar
[2]Burris, S. N., Number theoretic density and logical limit laws, Mathematical Surveys and Monographs, vol. 86, American Mathematical Society.Google Scholar
[3]Friedman, H. and Sheard, M., Elementary descent recursion and proof theory, Annals of Pure and Applied Logic, vol. 71 (1995), pp. 1–45.CrossRefGoogle Scholar
[4]Hardy, G. H. and Ramanujan, S., Asymptotic formulae for the distribution of integers of various types, Proceedings of the London Mathematical Society, vol. 16 (1917), pp. 112–132.CrossRefGoogle Scholar
[5]Kruskal, J. B., Well-quasi-orderings, the tree theorem, and Vázsonyi's conjecture, Transactions of the American Mathematical Society, vol. 95 (1960), pp. 210–225.Google Scholar
[6]Loebl, M. and J.Matoušek, , On undecidability of the weakened Kruskal theorem, Logic and combinatorics (Arcata, California, 1985), American Mathematical Society, Providence, RI, 1987, pp. 275–280.CrossRefGoogle Scholar
[7]J. Matoušek, and Nešetřil, J., Invitation to Discrete Mathematics, The Clarendon Press, Oxford, New York, 1998.CrossRefGoogle Scholar
[8]Newman, D. J., Analytic Number Theory, Springer, New York, 1998.Google Scholar
[9]Otter, R., The number of trees, Annals of Mathematics, vol. 49 (1948), pp. 583–599.CrossRefGoogle Scholar
[10]Rathjen, M. and Weiermann, A., Proof-theoretic investigations on Kruskal's theorem, Annals of Pure and Applied Logic, vol. 60 (1993), pp. 49–88.CrossRefGoogle Scholar
[11]Riordan, J., The enumeration of trees by height and diameter, IBM Journal of Research and Development, vol. 4 (1960), pp. 473–478.CrossRefGoogle Scholar
[12]K.Schütte, , Proof Theory, Springer, Berlin, 1977.CrossRefGoogle Scholar
[13]Simpson, S. G., Non-provability of certain combinatorial properties of finite trees, Harvey Friedman's research on the foundations of mathematics, North-Holland, Amsterdam, 1985, pp. 87–117.CrossRefGoogle Scholar
[14]Smith, R., The consistency strength of some finite forms of the Higman and Kruskal theorems, Harvey Friedman's research on the foundations of mathematics, North-Holland, Amsterdam, 1985, pp. 119–136.CrossRefGoogle Scholar
[15]Weiermann, A., What makes a (point-wise) subrecursive hierarchy slow growing?, Sets and proofs (Leeds, 1997), Cambridge University Press, Cambridge, 1999, pp. 403–423.CrossRefGoogle Scholar
[16]Yamashita, M., Asymptotic estimation of the number of trees, Transactions of the Institute of Electronics and Communication Engineering of Japan, vol. 62-A (1979), pp. 128–135, in Japanese.Google Scholar