Independence of Ramsey theorem variants using 𝜖₀

Friedman, Harvey; Pelupessy, Florian

doi:10.1090/proc12759

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