Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A classification of rapidly growing Ramsey functions

Author: Andreas Weiermann
Journal: Proc. Amer. Math. Soc. 132 (2004), 553-561
MSC (2000): Primary 03F30; Secondary 03D20, 03C62, 05D10
Published electronically: August 19, 2003
MathSciNet review: 2022381
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $f$ be a number-theoretic function. A finite set $X$ of natural numbers is called $f$-large if $card(X)\geq f(min(X))$. Let $PH_f$ be the Paris Harrington statement where we replace the largeness condition by a corresponding $f$-largeness condition. We classify those functions $f$ for which the statement $PH_f$ is independent of first order (Peano) arithmetic $PA$. If $f$ is a fixed iteration of the binary length function, then $PH_f$ is independent. On the other hand $PH_{\log^*}$ is provable in $PA$. More precisely let $f_\alpha(i):= {\lvert i \rvert}_{H_\alpha^{-1}(i)}$where $\mid i\mid_h$ denotes the $h$-times iterated binary length of $i$ and $H_\alpha^{-1}$ denotes the inverse function of the $\alpha$-th member $H_\alpha$of the Hardy hierarchy. Then $PH_{f_\alpha}$ is independent of $PA$ (for $\alpha\leq \varepsilon_0$) iff $\alpha=\varepsilon_0$.

References [Enhancements On Off] (What's this?)

  • 1. T. Arai: On the slowly well orderedness of $\varepsilon_{0}$, Mathematical Logic Quarterly 48 (2002), 125-130. MR 2003a:03061
  • 2. B. Blankertz and A. Weiermann: How to characterize provably total functions by the Buchholz operator method. Springer Lecture Notes in Logic 6 (1996), 205-213. MR 98c:03116
  • 3. W. Buchholz: On rapidly growing Ramsey functions. Technical report, München 1991.
  • 4. W. Buchholz, A. Cichon and A. Weiermann: A uniform approach to fundamental sequences and hierarchies. Mathematical Logic Quarterly 40 (1994), 273-286. MR 95g:03035a
  • 5. W. Buchholz and S. Wainer: Provably computable functions and the fast growing hierarchy. Logic and combinatorics, Contemporary Mathematics 65, American Mathematical Society, Providence, RI, 1987, 179-198. MR 88d:03109
  • 6. P. Erdös and R. Rado: Combinatorial theorems on classifications of subsets of a given set. Proceedings of the London Math. Society III Ser. 2., (1952), 417-439. MR 16:455d
  • 7. H. Friedman: ``Perfect'' statements. Posting the FOM email list from 05.02.1999: http://
  • 8. H. Friedman and M. Sheard: Elementary descent recursion and proof theory. Annals of Pure and Applied Logic 71 (1995), 1-45. MR 96c:03110
  • 9. R. L. Graham, B. L. Rothschild and J. H. Spencer: Ramsey theory. John Wiley and Sons, 1990. MR 90m:05003
  • 10. A. Kanamori and K. McAloon: On Gödel incompleteness and finite combinatorics. Annals of Pure and Applied Logic 33 (1987), 23-41. MR 88i:03095
  • 11. R. Kaye: Models of Peano arithmetic. Oxford Logic Guides 15. The Clarendon Press, Oxford University Press, 1991. MR 92k:03034
  • 12. J. Ketonen and R. Solovay: Rapidly growing Ramsey functions. Annals of Mathematics (2) 113 (1981), 267-314. MR 84c:03100
  • 13. J. Paris and L. Harrington: A mathematical incompleteness in Peano arithmetic, Handbook of Mathematical Logic (J. Barwise, ed.), North-Holland, Amsterdam, 1977, 1133-1142. MR 56:15351
  • 14. M. Loebl and J. Nesetril: An unprovable Ramsey-type theorem. Report No. 89598-OR, ISSN 0724-3138 (1989). Published in: Proceedings of the American Mathematical Society 116 (1992), 819-824. MR 93a:03067
  • 15. H. E. Rose: Subrecursion: Functions and Hierarchies. The Clarendon Press, Oxford University Press, 1984. MR 86g:03004
  • 16. S. S. Wainer: A classification of the ordinal recursive functions. Archiv für Mathematische Logik und Grundlagenforschung 13 (1970), 136-153. MR 45:3207
  • 17. A. Weiermann: How to characterize provably total functions by local predicativity, Journal of Symbolic Logic 61 (1996), 52-69. MR 97d:03075
  • 18. A. Weiermann: An application of graphical enumeration to $PA$, Journal of Symbolic Logic 68, no. 1 (2003), 5-16.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03F30, 03D20, 03C62, 05D10

Retrieve articles in all journals with MSC (2000): 03F30, 03D20, 03C62, 05D10

Additional Information

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
Address at time of publication: Department of Mathematics, P.O. Box 80.010, 3508 TA Utrecht, The Nederlands

Keywords: Paris Harrington theorem, rapidly growing Ramsey functions, independence results, fast growing hierarchies, Peano arithmetic
Received by editor(s): February 21, 2002
Received by editor(s) in revised form: July 4, 2002, and September 26, 2002
Published electronically: August 19, 2003
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society