Bootstrapping the primitive recursive functions by only 27 colors (Q1357751)

In their paper ``A mathematical incompleteness in Peano arithmetic'' [in: J. Barwise (ed.), Handbook of mathematical logic, 1133-1142 (1977; Zbl 0443.03001)], \textit{L. Harrington} and \textit{J. Paris} showed that a certain finitary version \({\mathbf P}{\mathbf H}\) of Ramsey's Theorem is true, but unprovable in Peano's arithmetic. This is an example of Gödel's incompleteness theorem. However, unlike Gödel's consistency statement, \({\mathbf P}{\mathbf H}\) has generally been accepted to be a natural statement from arithmetic. In ``Rapidly growing Ramsey functions'' [Ann. Math., II. Ser. 113, 267-314 (1981; Zbl 0494.03027)], \textit{J. Ketonen} and \textit{R. Solovay} gave a careful analysis of the underlying growth rate of \({\mathbf P}{\mathbf H}\). As a first step in this analysis it was shown that for each increasing primitive recursive function \(f\) there exists \(n\) and a coloring of the 3-element subsets of \(\{n,n+1,n+2,\dots,f(n)\}\) such that there are no homogeneous sets \(\{s_0,s_1,s_2,\dots,s_r\}\) with \(r\geq s_0-1\). The real point is that the number of colors can always be chosen to be less than a number fixed in advance. Ketonen and Solovay defined various algebras and took a series of products, in order to obtain the required coloring. An examination of their proof shows that they used approximately 160 000 colors. However, they clearly did not try to be economical. Actually, in the work of Ketonen and Solovay the important point is that the number is finite. In this paper, I construct a concrete coloring which instead of 160 000 colors uses only 27 colors.