Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension

Authors:
Andreas Weiermann and Wim Van Hoof

Journal:
Proc. Amer. Math. Soc. **140** (2012), 2913-2927

MSC (2010):
Primary 03F30; Secondary 03D20, 03C62, 05D10

DOI:
https://doi.org/10.1090/S0002-9939-2011-11121-3

Published electronically:
December 1, 2011

MathSciNet review:
2910777

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This article is concerned with investigations on a phase transition which is related to the (finite) Ramsey theorem and the Paris-Harrington theorem. For a given number-theoretic function , let be the least natural number such that for all colourings of the -element subsets of with at most colours there exists a subset of such that has constant value on all -element subsets of and such that the cardinality of is not smaller than . If is a constant function with value , then is equal to the usual Ramsey number ; and if is the identity function, then is the corresponding Paris-Harrington number, which typically is much larger than . In this article we give for all a sharp classification of the functions for which the function grows so quickly that it is no longer provably total in the subsystem of Peano arithmetic, where the induction scheme is restricted to formulas with at most -quantifiers. Such a quick growth will in particular happen for any function growing at least as fast as (where is fixed) but not for the function . (Here denotes the functional inverse of the tower function.) To obtain such results and even sharper bounds we employ certain suitable transfinite iterations of *nonconstructive* lower bound functions for Ramsey numbers. Thereby we improve certain results from the article *A classification of rapidly growing Ramsey numbers* (PAMS 132 (2004), 553-561) of the first author, which were obtained by employing *constructive* ordinal partitions.

**1.**H. L. Abbott,*A note on Ramsey’s theorem*, Canad. Math. Bull.**15**(1972), 9–10. MR**0314673**, https://doi.org/10.4153/CMB-1972-002-5**2.**Lorenzo Carlucci, Gyesik Lee, and Andreas Weiermann,*Sharp thresholds for hypergraph regressive Ramsey numbers*, J. Combin. Theory Ser. A**118**(2011), no. 2, 558–585. MR**2739504**, https://doi.org/10.1016/j.jcta.2010.08.004**3.**Paul Erdős, András Hajnal, Attila Máté, and Richard Rado,*Combinatorial set theory: partition relations for cardinals*, Studies in Logic and the Foundations of Mathematics, vol. 106, North-Holland Publishing Co., Amsterdam, 1984. MR**795592****4.**Matt Fairtlough and Stanley S. Wainer,*Hierarchies of provably recursive functions*, Handbook of proof theory, Stud. Logic Found. Math., vol. 137, North-Holland, Amsterdam, 1998, pp. 149–207. MR**1640327**, https://doi.org/10.1016/S0049-237X(98)80018-9**5.**Jussi Ketonen and Robert Solovay,*Rapidly growing Ramsey functions*, Ann. of Math. (2)**113**(1981), no. 2, 267–314. MR**607894**, https://doi.org/10.2307/2006985**6.**Menachem Kojman, Gyesik Lee, Eran Omri, and Andreas Weiermann,*Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers*, J. Combin. Theory Ser. A**115**(2008), no. 6, 1036–1055. MR**2423347**, https://doi.org/10.1016/j.jcta.2007.12.006**7.**H. Lefmann,*A note on Ramsey numbers*, Studia Sci. Math. Hungar.**22**(1987), no. 1-4, 445–446. MR**932230****8.**J. B. Paris and L. Harrington.

A mathematical incompleteness in Peano arithmetic.

In J. Barwise, ed., Handbook of Mathematical Logic, volume 90 of Studies in Logic and the Foundations of Mathematics, pages 1133-1142. North-Holland, 1977. MR**0457132 (56:15351)****9.**Andreas Weiermann,*A classification of rapidly growing Ramsey functions*, Proc. Amer. Math. Soc.**132**(2004), no. 2, 553–561. MR**2022381**, https://doi.org/10.1090/S0002-9939-03-07086-2**10.**Andreas Weiermann,*Classifying the provably total functions of PA*, Bull. Symbolic Logic**12**(2006), no. 2, 177–190. MR**2223920**

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

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

Additional Information

**Andreas Weiermann**

Affiliation:
Department of Mathematics, Ghent University, Krijgslaan 281 S22, B-9000 Ghent, Belgium

Email:
Andreas.Weiermann@UGent.be

**Wim Van Hoof**

Affiliation:
Department of Mathematics, Ghent University, Krijgslaan 281 S22, B-9000 Ghent, Belgium

Email:
Wim.Vanhoof@UGent.be

DOI:
https://doi.org/10.1090/S0002-9939-2011-11121-3

Keywords:
Ramsey theorem,
rapidly growing Ramsey functions,
fast growing hierarchies,
Peano arithmetic

Received by editor(s):
May 16, 2008

Received by editor(s) in revised form:
January 22, 2011, and March 4, 2011

Published electronically:
December 1, 2011

Communicated by:
Julia Knight

Article copyright:
© Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.