An unprovable Ramsey-type theorem
HTML articles powered by AMS MathViewer
- by Martin Loebl and Jaroslav Nešetřil PDF
- Proc. Amer. Math. Soc. 116 (1992), 819-824 Request permission
Abstract:
We present a new proof of the Paris-Harrington unprovable (in PA) version of Ramsey’s theorem. This also yields a particularly short proof of the Ketonen-Solovay result on rapidly growing Ramsey functions.References
- 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. MR 891248, DOI 10.1090/conm/065/891248
- 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. MR 687646, DOI 10.1090/S0002-9939-1983-0687646-0
- R. L. Goodstein, On the restricted ordinal theorem, J. Symbolic Logic 9 (1944), 33–41. MR 10515, DOI 10.2307/2268019
- Akihiro Kanamori and Kenneth McAloon, On Gödel incompleteness and finite combinatorics, Ann. Pure Appl. Logic 33 (1987), no. 1, 23–41. MR 870685, DOI 10.1016/0168-0072(87)90074-1
- Jussi Ketonen and Robert Solovay, Rapidly growing Ramsey functions, Ann. of Math. (2) 113 (1981), no. 2, 267–314. MR 607894, DOI 10.2307/2006985
- Laurie Kirby and Jeff Paris, Accessible independence results for Peano arithmetic, Bull. London Math. Soc. 14 (1982), no. 4, 285–293. MR 663480, DOI 10.1112/blms/14.4.285 M. Loebl, Large functions, thesis, Charles University, Prague, 1989.
- 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. MR 891253, DOI 10.1090/conm/065/891253 M. Loebl and J. Nešetřil, Linearity and unprovability of set union problem strategies, Proc. STOC, ACM, 1988.
- Jeff Paris, Combinatorial statements independent of arithmetic, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 232–245. MR 1083604, DOI 10.1007/978-3-642-72905-8_{1}6
- Handbook of mathematical logic, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland Publishing Co., Amsterdam, 1977. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra. MR 457132
- 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. MR 835255, DOI 10.1016/S0049-237X(09)70156-9
- S. S. Wainer, A classification of the ordinal recursive functions, Arch. Math. Logik Grundlag. 13 (1970), 136–153. MR 294134, DOI 10.1007/BF01973619
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 116 (1992), 819-824
- MSC: Primary 03F30
- DOI: https://doi.org/10.1090/S0002-9939-1992-1095225-4
- MathSciNet review: 1095225