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)



Independence of Ramsey theorem variants using $ \varepsilon_0$

Authors: Harvey Friedman and Florian Pelupessy
Journal: Proc. Amer. Math. Soc. 144 (2016), 853-860
MSC (2010): Primary 03F30; Secondary 03F15, 03D20, 05C55
Published electronically: June 26, 2015
MathSciNet review: 3430859
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that Friedman's finite adjacent Ramsey theorem is unprovable in Peano Arithmetic, and give a new proof of the unprovability of the Paris-Harrington theorem in $ \mathrm {PA}$. We also determine the status of these theorems for each dimension. It is to be noted that the finite adjacent Ramsey theorem for dimension $ d$ is equivalent to the Paris-Harrington theorem for dimension $ d+1$.

References [Enhancements On Off] (What's this?)

  • [1] Toshiyasu Arai, Introduction to proof theory, on his Kobe University homepage:
  • [2] Wilfried Buchholz, Homepage:
  • [3] Samuel R. Buss (ed.), Handbook of proof theory, Studies in Logic and the Foundations of Mathematics, vol. 137, North-Holland Publishing Co., Amsterdam, 1998.
  • [4] 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 (84f:03049),
  • [5] Nachum Dershowitz and Georg Moser, The hydra battle revisited, Rewriting computation and proof, Lecture Notes in Comput. Sci., vol. 4600, Springer, Berlin, 2007, pp. 1-27. MR 2392300 (2009d:68076),
  • [6] Harvey M. Friedman, Internal finite tree embeddings, Reflections on the foundations of mathematics (Stanford, CA, 1998), Lect. Notes Log., vol. 15, Assoc. Symbol. Logic, Urbana, IL, 2002, pp. 60-91. MR 1943303 (2003m:03109)
  • [7] Harvey M. Friedman, Adjacent Ramsey theory, Preprint (2010): friedman.8/foundational-adventures/downloadable-manuscripts/.
  • [8] Jussi Ketonen and Robert Solovay, Rapidly growing Ramsey functions, Ann. of Math. (2) 113 (1981), no. 2, 267-314. MR 607894 (84c:03100),
  • [9] Laurie Kirby and Jeff Paris, Accessible independence results for Peano arithmetic, Bull. London Math. Soc. 14 (1982), no. 4, 285-293. MR 663480 (83j:03096),
  • [10] Martin Loebl and Jaroslav Nešetřil, An unprovable Ramsey-type theorem, Proc. Amer. Math. Soc. 116 (1992), no. 3, 819-824. MR 1095225 (93a:03067),
  • [11] J. B. Paris, A hierarchy of cuts in models of arithmetic, Model theory of algebra and arithmetic (Proc. Conf., Karpacz, 1979), Lecture Notes in Math., vol. 834, Springer, Berlin-New York, 1980, pp. 312-337. MR 606791 (84e:03085)
  • [12] Jeff Paris and Leo Harrington, A Mathematical Incompleteness in Peano Arithmetic, in Handbook for Mathematical Logic (Ed. J. Barwise) Amsterdam, Netherlands: North-Holland, 1977.
  • [13] Wolfram Pohlers, Proof theory, Lecture Notes in Mathematics, vol. 1407, Springer-Verlag, Berlin, 1989. An introduction. MR 1026933 (91h:03078)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03F30, 03F15, 03D20, 05C55

Retrieve articles in all journals with MSC (2010): 03F30, 03F15, 03D20, 05C55

Additional Information

Harvey Friedman
Affiliation: Department of Mathematics, Ohio State University, Room 754, Mathematics Building, 231 West 18th Avenue, Columbus, Ohio 43210

Florian Pelupessy
Affiliation: Mathematical Institute, Tohoku University, 6-3, Aoba, Aramaki, Aoba-ku, Sendai 980-8578, Japan

Keywords: Finite adjacent Ramsey, Paris--Harrington, Hydra battles, Ramsey theory, unprovability, independence, Peano Arithmetic, Cantor normal form, Hardy hierarchy, fundamental sequences
Received by editor(s): February 8, 2013
Received by editor(s) in revised form: January 19, 2015
Published electronically: June 26, 2015
Additional Notes: This research was partially supported by the John Templeton Foundation grant ID #36297 and an Ohio State University Presidential Research Grant. The opinions expressed here are those of the author and do not necessarily reflect the views of the John Templeton Foundation.
Communicated by: Mirna Džamonja
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society