Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

An unprovable Ramsey-type theorem


Authors: Martin Loebl and Jaroslav Nešetřil
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] W. Buchholz and S. Wainer, Provably computable functions and fast growing hierarchy, Logic and Combinatorics (S. G. Simpson, ed.) Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 179-198. MR 891248 (88d:03109)
  • [2] E. A. Cichon, A short proof of two recently discovered independence results using recursion theoretic methods, Proc. Amer. Math. Soc. 87 (1983), 704-706. MR 687646 (84f:03049)
  • [3] R. L. Goodstein, On the restricted ordinal theorem, J. Symbolic Logic 9 (1944), 33-41. MR 0010515 (6:30a)
  • [4] A. Kanamori and K. McAloon, On Gódel incompleteness and finite combinatorics, Ann. Pure Appl. Logic 33 (1987), 23-41. MR 870685 (88i:03095)
  • [5] J. Ketonen and R. Solovay, Rapidly growing Ramsey functions, Ann. of Math. (2) 113 (1981), 267-314. MR 607894 (84c:03100)
  • [6] L. Kirby and J. Paris, Accessible independence results for Peano arithmetic, Bull. London Math. Soc. 14 (1982), 285-293. MR 663480 (83j:03096)
  • [7] M. Loebl, Large functions, thesis, Charles University, Prague, 1989.
  • [8] M. Loebl and J. Matoušek, On undecidability of the weakened Kruskal theorem, Logic and Combinatorics (S. G. Simpson, ed.), Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 275-280. MR 891253 (89b:03099)
  • [9] M. Loebl and J. Nešetřil, Linearity and unprovability of set union problem strategies, Proc. STOC, ACM, 1988.
  • [10] J. Paris, Statements independent of arithmetic, Mathematics of Ramsey Theory (J. Nešetřil and V. Rödl, eds.), Springer-Verlag, Berlin and New York, 1990, pp. 232-245. MR 1083604
  • [11] J. Paris and L. Harrington, A mathematical incompleteness in Peano arithmetic, Handbook of Mathematical Logic (J. Barwise, ed.), North-Holland, Amsterdam, 1977, pp. 1133-1142. MR 0457132 (56:15351)
  • [12] S. G. Simpson, Nonprovability of certain combinatorial finite trees, Harvey Friedman's Research in the Foundation of Mathematics (L. Harrington, M. Morley, A. Scedrov, and S. G. Simpson, eds.), North-Holland, Amsterdam, 1985, pp. 87-117. MR 835255 (87i:03122a)
  • [13] S. S. Wainer, A classification of the ordinal recursive functions, Arch. Math. Logik Grundlag. 13 (1970), 136-153. MR 0294134 (45:3207)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03F30

Retrieve articles in all journals with MSC: 03F30


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1992-1095225-4
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society