An unprovable Ramsey-type theorem. (English) Zbl 0773.05098
A new proof of the Paris-Harrington unprovable (in PA) version of Ramsey’s theorem is presented. This yields a particularly short proof of the Ketonen-Solovay result on rapidly growing Ramsey functions.
Reviewer: M.Loebl and J.Nešetřil
MSC:
| 05D10 | Ramsey theory |
| 03F30 | First-order arithmetic and fragments |
| 05A17 | Combinatorial aspects of partitions of integers |
References:
| [1] | Wilfried Buchholz and Stan Wainer, Provably computable functions and the fast growing hierarchy, Logic and combinatorics (Arcata, Calif., 1985) Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 179 – 198. · Zbl 0635.03056 · doi:10.1090/conm/065/891248 |
| [2] | E. A. Cichon, A short proof of two recently discovered independence results using recursion theoretic methods, Proc. Amer. Math. Soc. 87 (1983), no. 4, 704 – 706. · Zbl 0512.03028 |
| [3] | R. L. Goodstein, On the restricted ordinal theorem, J. Symbolic Logic 9 (1944), 33 – 41. · Zbl 0060.02306 · doi:10.2307/2268019 |
| [4] | Akihiro Kanamori and Kenneth McAloon, On Gödel incompleteness and finite combinatorics, Ann. Pure Appl. Logic 33 (1987), no. 1, 23 – 41. · Zbl 0627.03041 · doi:10.1016/0168-0072(87)90074-1 |
| [5] | Jussi Ketonen and Robert Solovay, Rapidly growing Ramsey functions, Ann. of Math. (2) 113 (1981), no. 2, 267 – 314. · Zbl 0494.03027 · doi:10.2307/2006985 |
| [6] | Laurie Kirby and Jeff Paris, Accessible independence results for Peano arithmetic, Bull. London Math. Soc. 14 (1982), no. 4, 285 – 293. · Zbl 0501.03017 · doi:10.1112/blms/14.4.285 |
| [7] | M. Loebl, Large functions, thesis, Charles University, Prague, 1989. |
| [8] | Martin Loebl and Jiří Matoušek, On undecidability of the weakened Kruskal theorem, Logic and combinatorics (Arcata, Calif., 1985) Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 275 – 280. · Zbl 0634.03038 · doi:10.1090/conm/065/891253 |
| [9] | M. Loebl and J. Nešetřil, Linearity and unprovability of set union problem strategies, Proc. STOC, ACM, 1988. · Zbl 0874.68135 |
| [10] | Jeff Paris, Combinatorial statements independent of arithmetic, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 232 – 245. · Zbl 0724.03025 · doi:10.1007/978-3-642-72905-8_16 |
| [11] | Handbook of mathematical logic, North-Holland Publishing Co., Amsterdam-New York-Oxford, 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. |
| [12] | Stephen G. Simpson, Nonprovability of certain combinatorial properties of finite trees, Harvey Friedman’s research on the foundations of mathematics, Stud. Logic Found. Math., vol. 117, North-Holland, Amsterdam, 1985, pp. 87 – 117. , https://doi.org/10.1016/S0049-237X(09)70156-9 Stephen G. Simpson, Nichtbeweisbarkeit von gewissen kombinatorischen Eigenschaften endlicher Bäume, Arch. Math. Logik Grundlag. 25 (1985), no. 1-2, 45 – 65 (German, with English summary). · Zbl 0598.03045 · doi:10.1007/BF02007556 |
| [13] | S. S. Wainer, A classification of the ordinal recursive functions, Arch. Math. Logik Grundlagenforsch. 13 (1970), 136 – 153. · Zbl 0228.02027 · doi:10.1007/BF01973619 |
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.
