## Independence of Ramsey theorem variants using $\varepsilon _0$

HTML articles powered by AMS MathViewer

- by Harvey Friedman and Florian Pelupessy PDF
- Proc. Amer. Math. Soc.
**144**(2016), 853-860 Request permission

## 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

- Toshiyasu Arai,
*Introduction to proof theory*, on his Kobe University homepage: http://kurt.scitec.kobe-u.ac.jp/~arai/. - Wilfried Buchholz, Homepage: http://www.mathematik.uni-muenchen.de/~buchholz/.
- Samuel R. Buss (ed.),
*Handbook of proof theory*, Studies in Logic and the Foundations of Mathematics, vol. 137, North-Holland Publishing Co., Amsterdam, 1998. - 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 - 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**, DOI 10.1007/978-3-540-73147-4_{1} - 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** - Harvey M. Friedman,
*Adjacent Ramsey theory*, Preprint (2010): https://u.osu.edu/ friedman.8/foundational-adventures/downloadable-manuscripts/. - 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 - Martin Loebl and Jaroslav Ne et il,
*An unprovable Ramsey-type theorem*, Proc. Amer. Math. Soc.**116**(1992), no.Â 3, 819â€“824. MR**1095225**, DOI 10.1090/S0002-9939-1992-1095225-4 - 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** - Jeff Paris and Leo Harrington,
*A Mathematical Incompleteness in Peano Arithmetic*, in Handbook for Mathematical Logic (Ed. J. Barwise) Amsterdam, Netherlands: North-Holland, 1977. - Wolfram Pohlers,
*Proof theory*, Lecture Notes in Mathematics, vol. 1407, Springer-Verlag, Berlin, 1989. An introduction. MR**1026933**, DOI 10.1007/978-3-540-46825-7

## Additional Information

**Harvey Friedman**- Affiliation: Department of Mathematics, Ohio State University, Room 754, Mathematics Building, 231 West 18th Avenue, Columbus, Ohio 43210
- MR Author ID: 69465
- Email: friedman@math.ohio-state.edu
**Florian Pelupessy**- Affiliation: Mathematical Institute, Tohoku University, 6-3, Aoba, Aramaki, Aoba-ku, Sendai 980-8578, Japan
- Email: florian.pelupessy@operamail.com
- 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
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**144**(2016), 853-860 - MSC (2010): Primary 03F30; Secondary 03F15, 03D20, 05C55
- DOI: https://doi.org/10.1090/proc12759
- MathSciNet review: 3430859