×

Combinatorial unprovability proofs and their model-theoretic counterparts. (English) Zbl 1301.03062

The paper begins with a comprehensive survey of unprovability in PA of Ramsey-type combinatorial principles, and then proceeds with a model-theoretic analysis of the canonical Ramsey theorem with a largeness condition ERL, and of a version the Kanamori-McAloon principle KM. The ERL principle states that for all \(n\) and \(k\) there is an \(m\) such that for every function \(f\) defined on \([m]^n\) there is an \(H\subseteq m\), with \(|H|>\max\{\min(H),k\}\), on which \(f\) is canonical, i.e.  there is a \(v\subseteq n\) such that for all \(x_1<\cdots < x_n\) in \(H\), \(f(x_1,\dots, x_n)\) depends only on \(x_i\) for \(i\in v\). The KM\(_j\) principle is: For all \(n\) and \(k\) there is an \(m\) such that whenever \(f:[m]^n\rightarrow{\mathbb N}\) is \(j\)-regressive, i.e.  for all \(x_1<\cdots <x_n\leq m\), \(f(x_1,\dots, x_n)\in [x_{j-1}, x_j]\), then there is an \(H\subseteq m\) such that \(|H|\geq k\) and the values of \(f\) on \([H]^n\) depend only on \(x_1,\dots, x_j\).
Carlucci and Weiermann gave a combinatorial proof that ERL implies the Paris-Harrington principle PH. The present authors give a model-theoretic proof of unprovability of ERL in PA, and in the process construct a new indicator for cuts satisfying PA. A similar analysis is applied to the KM\(_j\) principle. The main results about it are summarized in the following corollary, in which the principles PH\(^n\) and KM\(^n_j\) are the relativized versions of PH and KM\(_j\) for the fixed exponent \(n\). The following statements are equivalent in \(\mathrm{I}\Sigma_1\): PH\(^{n+1}\); KM\(^{n+1}\); KM\(^{n+j}_j\); 1-Con\((\mathrm I\Sigma_n)\).

MSC:

03F30 First-order arithmetic and fragments
03B30 Foundations of classical theories (including reverse mathematics)
03C62 Models of arithmetic and set theory

References:

[1] Bovykin, A., “Several proofs of PA-unprovability,” pp. 29-43 in Logic and Its Applications , vol. 380 of Contemporary Mathematics , American Mathematical Society, Providence, 2005. · Zbl 1084.03045 · doi:10.1090/conm/380/07105
[2] Bovykin, A., “Brief introduction to unprovability,” pp. 38-64 in Logic Colloquium 2006 , Lecture Notes in Logic, Association for Symbolic Logic, Chicago, 2009.
[3] Bovykin, A., and A. Weiermann, “The strength of infinitary Ramseyan statements can be accessed by their densities,” to appear in Annals of Pure and Applied Logic . · Zbl 1422.03127
[4] Carlucci, L., G. Lee, and A. Weiermann, “Sharp thresholds for hypergraph regressive Ramsey numbers,” Journal of Combinatorial Theory, Series A , vol. 118 (2011), pp. 558-85. · Zbl 1251.05103 · doi:10.1016/j.jcta.2010.08.004
[5] Carlucci, L., G. Lee, and A. Weiermann, “Classifying the phase transition threshold for regressive Ramsey functions,” preprint, 2006.
[6] Carlucci, L., and A. Weiermann, “Classifying the phase transition for canonical Ramsey functions,” preprint, 2010.
[7] Erdös, P., and R. Rado, “A combinatorial theorem,” Journal of the London Mathematical Society , vol. 25 (1950), pp. 249-55. · Zbl 0038.15301 · doi:10.1112/jlms/s1-25.4.249
[8] Kanamori, A., and K. McAloon, “On Gödel incompleteness and finite combinatorics,” Annals of Pure and Applied Logic , vol. 33 (1987), pp. 23-41. · Zbl 0627.03041 · doi:10.1016/0168-0072(87)90074-1
[9] Kaye, R., Models of Peano Arithmetic , vol. 15 of Oxford Logic Guides , Oxford University Press, New York, 1991. · Zbl 0744.03037
[10] Lee, G., “Phase transitions in axiomatic thought,” Ph.D. dissertation, University of Münster, Münster, Germany, 2005. · Zbl 1082.03048
[11] Lefmann, H., and V. Rödl, “On canonical Ramsey numbers for complete graphs versus paths,” Journal of Combinatorial Theory, Series B , vol. 58 (1993), pp. 1-13. · Zbl 0794.05088 · doi:10.1006/jctb.1993.1025
[12] Mileti, J. R., “The canonical Ramsey theorem and computability theory,” Transactions of the American Mathematical Society , vol. 360 (2008), pp. 1309-40. · Zbl 1135.03014 · doi:10.1090/S0002-9947-07-04390-5
[13] Mills, G., “A tree analysis of unprovable combinatorial statements,” pp. 248-311 in Model Theory of Algebra and Arithmetic (Karpacz, Poland, 1978) , vol. 834 of Lecture Notes in Mathematics , Springer, Berlin, 1980. · Zbl 0472.05019 · doi:10.1007/BFb0090170
[14] Paris, J., and L. Harrington, “A mathematical incompleteness in Peano arithmetic,” pp. 1133-42 in Handbook of Mathematical Logic , edited by J. Barwise, vol. 90 of Studies in Logic and the Foundations of Mathematics , North-Holland, Amsterdam, 1977.
[15] Ramsey, F. P., “On a problem of formal logic,” Proceedings of the London Mathematical Society , vol. 30 (1930), pp. 264-86. · JFM 55.0032.04 · doi:10.1112/plms/s2-30.1.264
[16] Weiermann, A., “An application of graphical enumeration to PA,” Journal of Symbolic Logic , vol. 68 (2003), pp. 5-16. · Zbl 1041.03045 · doi:10.2178/jsl/1045861503
[17] Weiermann, A., “A classification of rapidly growing Ramsey functions,” Proceedings of the American Mathematical Society , vol. 132 (2004), pp. 553-61. · Zbl 1041.03044 · doi:10.1090/S0002-9939-03-07086-2
[18] Weiermann, A., “Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results, Annals of Pure and Applied Logic , vol. 136 (2005), pp. 189-218. · Zbl 1090.03028 · doi:10.1016/j.apal.2005.05.012
[19] Weiermann, A., and W. Van Hoof, “Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension,” Proceedings of the American Mathematical Society , vol. 140 (2012), pp. 2913-27. · Zbl 1291.03113 · doi:10.1090/S0002-9939-2011-11121-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.