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), 29132927
MSC (2010):
Primary 03F30; Secondary 03D20, 03C62, 05D10
Published electronically:
December 1, 2011
MathSciNet review:
2910777
Fulltext 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 ParisHarrington theorem. For a given numbertheoretic 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 ParisHarrington 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), 553561) 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
(47 #3224)
 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
(2011m:05328), 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, NorthHolland Publishing Co., Amsterdam, 1984. MR 795592
(87g:04002)
 4.
Matt
Fairtlough and Stanley
S. Wainer, Hierarchies of provably recursive functions,
Handbook of proof theory, Stud. Logic Found. Math., vol. 137,
NorthHolland, Amsterdam, 1998, pp. 149–207. MR 1640327
(2000a:03063), 10.1016/S0049237X(98)800189
 5.
Jussi
Ketonen and Robert
Solovay, Rapidly growing Ramsey functions, Ann. of Math. (2)
113 (1981), no. 2, 267–314. MR 607894
(84c:03100), 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
(2009e:05307), 10.1016/j.jcta.2007.12.006
 7.
H.
Lefmann, A note on Ramsey numbers, Studia Sci. Math. Hungar.
22 (1987), no. 14, 445–446. MR 932230
(89d:05132)
 8.
Handbook of mathematical logic, NorthHolland Publishing Co.,
AmsterdamNew YorkOxford, 1977. Edited by Jon Barwise; With the
cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S.
Troelstra; Studies in Logic and the Foundations of Mathematics, Vol. 90. MR 0457132
(56 #15351)
 9.
Andreas
Weiermann, A classification of rapidly growing
Ramsey functions, Proc. Amer. Math. Soc.
132 (2004), no. 2,
553–561 (electronic). MR 2022381
(2004m:03211), 10.1090/S0002993903070862
 10.
Andreas
Weiermann, Classifying the provably total functions of PA,
Bull. Symbolic Logic 12 (2006), no. 2, 177–190.
MR
2223920 (2006k:03129)
 1.
 H. L. Abbott. A note on Ramsey's theorem: Canad. Math. Bull. 15 (1972) 910. MR 0314673 (47:3224)
 2.
 L. Carlucci, G. Lee and A. Weiermann. Sharp thresholds for hypergraph regressive Ramsey numbers Journal of Combinatorial Theory, Series A, 118(2) (2011), 558585. MR 2739504
 3.
 P. Erdős, A. Hajnal, A. Máté and R.Rado. Combinatorial set theory: Partition relations for cardinals. Studies in Logic and the Foundations of Mathematics, 106. NorthHolland, 1984. MR 795592 (87g:04002)
 4.
 M. V. Fairtlough and S. S. Wainer. Hierarchies of provably recursive functions, Chapter III in S. Buss (ed.), Handbook of proof theory, Studies in Logic, Vol. 137, Elsevier Science BV (1998), 149207. MR 1640327 (2000a:03063)
 5.
 J. Ketonen and R. Solovay. Rapidly growing Ramsey functions. Annals of Mathematics (2), 113 (1981), 267314. MR 607894 (84c:03100)
 6.
 M. Kojman, G. Lee, E. Omri and A. Weiermann. Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers. Journal of Combinatorial Theory A 115(6) (2008), 10361055. MR 2423347 (2009e:05307)
 7.
 H. Lefmann. A note on Ramsey numbers. Studia Scientiarum Mathematicarum Hungarica 22 (1987), 445446. MR 932230 (89d:05132)
 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 11331142. NorthHolland, 1977. MR 0457132 (56:15351)
 9.
 A. Weiermann. A classification of rapidly growing Ramsey functions. Proc. Amer. Math. Soc., 132(2) (2004), 553561. MR 2022381 (2004m:03211)
 10.
 A. Weiermann. Classifying the provably total functions of PA, Bull. Symbolic Logic (12)2 (2006), 177190. MR 2223920 (2006k:03129)
Similar Articles
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, B9000 Ghent, Belgium
Email:
Andreas.Weiermann@UGent.be
Wim Van Hoof
Affiliation:
Department of Mathematics, Ghent University, Krijgslaan 281 S22, B9000 Ghent, Belgium
Email:
Wim.Vanhoof@UGent.be
DOI:
http://dx.doi.org/10.1090/S000299392011111213
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.
