## An inside/outside Ramsey theorem and recursion theory

HTML articles powered by AMS MathViewer

- by Marta Fiori-Carones, Paul Shafer and Giovanni Soldà PDF
- Trans. Amer. Math. Soc.
**375**(2022), 1977-2024 Request permission

## Abstract:

Inspired by Ramsey’s theorem for pairs, Rival and Sands proved what we refer to as an*inside/outside Ramsey theorem*: every infinite graph $G$ contains an infinite subset $H$ such that every vertex of $G$ is adjacent to precisely none, one, or infinitely many vertices of $H$. We analyze the Rival–Sands theorem from the perspective of reverse mathematics and the Weihrauch degrees. In reverse mathematics, we find that the Rival–Sands theorem is equivalent to arithmetical comprehension and hence is stronger than Ramsey’s theorem for pairs. We also identify a weak form of the Rival–Sands theorem that is equivalent to Ramsey’s theorem for pairs. We turn to the Weihrauch degrees to give a finer analysis of the Rival–Sands theorem’s computational strength. We find that the Rival–Sands theorem is Weihrauch equivalent to the double jump of weak König’s lemma. We believe that the Rival–Sands theorem is the first natural theorem shown to exhibit exactly this strength. Furthermore, by combining our result with a result of Brattka and Rakotoniaina, we obtain that solving one instance of the Rival–Sands theorem exactly corresponds to simultaneously solving countably many instances of Ramsey’s theorem for pairs. Finally, we show that the uniform computational strength of the weak Rival–Sands theorem is weaker than that of Ramsey’s theorem for pairs by showing that a number of well-known consequences of Ramsey’s theorem for pairs do not Weihrauch reduce to the weak Rival–Sands theorem. We also address an apparent gap in the literature concerning the relationship between Weihrauch degrees corresponding to the ascending/descending sequence principle and the infinite pigeonhole principle.

## References

- Eric P. Astor, Damir D. Dzhafarov, Reed Solomon, and Jacob Suggs,
*The uniform content of partial and linear orders*, Ann. Pure Appl. Logic**168**(2017), no. 6, 1153–1171. MR**3628269**, DOI 10.1016/j.apal.2016.11.010 - Vasco Brattka and Guido Gherardi,
*Weihrauch degrees, omniscience principles and weak computability*, J. Symbolic Logic**76**(2011), no. 1, 143–176. MR**2791341**, DOI 10.2178/jsl/1294170993 - Vasco Brattka, Guido Gherardi, and Alberto Marcone,
*The Bolzano-Weierstrass theorem is the jump of weak Kőnig’s lemma*, Ann. Pure Appl. Logic**163**(2012), no. 6, 623–655. MR**2889550**, DOI 10.1016/j.apal.2011.10.006 - Vasco Brattka, Guido Gherardi, and Arno Pauly,
*Weihrauch complexity in computable analysis*, Handbook of computability and complexity in analysis, Theory Appl. Comput., Springer, Cham, [2021] ©2021, pp. 367–417. MR**4300761**, DOI 10.1007/978-3-030-59234-9_{1}1 - Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer,
*On the uniform computational content of computability theory*, Theory Comput. Syst.**61**(2017), no. 4, 1376–1426. MR**3712309**, DOI 10.1007/s00224-017-9798-1 - Vasco Brattka and Arno Pauly,
*On the algebraic structure of Weihrauch degrees*, Log. Methods Comput. Sci.**14**(2018), no. 4, Paper No. 4, 36. MR**3868998**, DOI 10.1080/10724117.2007.11974704 - Vasco Brattka and Tahina Rakotoniaina,
*On the uniform computational content of Ramsey’s theorem*, J. Symb. Log.**82**(2017), no. 4, 1278–1316. MR**3743611**, DOI 10.1017/jsl.2017.43 - Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman,
*On the strength of Ramsey’s theorem for pairs*, J. Symbolic Logic**66**(2001), no. 1, 1–55. MR**1825173**, DOI 10.2307/2694910 - Peter A. Cholak, Carl G. Jockusch Jr., and Theodore A. Slaman,
*Corrigendum to: “On the strength of Ramsey’s theorem for pairs” [MR1825173]*, J. Symbolic Logic**74**(2009), no. 4, 1438–1439. MR**2583829**, DOI 10.2178/jsl/1254748700 - C. T. Chong, Theodore A. Slaman, and Yue Yang,
*The metamathematics of stable Ramsey’s theorem for pairs*, J. Amer. Math. Soc.**27**(2014), no. 3, 863–892. MR**3194495**, DOI 10.1090/S0894-0347-2014-00789-X - François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer,
*On uniform relationships between combinatorial problems*, Trans. Amer. Math. Soc.**368**(2016), no. 2, 1321–1359. MR**3430365**, DOI 10.1090/tran/6465 - Damir D. Dzhafarov,
*Strong reductions between combinatorial principles*, J. Symb. Log.**81**(2016), no. 4, 1405–1431. MR**3579116**, DOI 10.1017/jsl.2016.1 - Marta Fiori-Carones, Alberto Marcone, Paul Shafer, and Giovanni Soldà,
*(Extra)ordinary equivalences with the ascending/descending sequence principle*, 2021. preprint arXiv:2107.02531. 33pp. - Harvey Friedman,
*Some systems of second order arithmetic and their use*, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974) Canad. Math. Congress, Montreal, Que., 1975, pp. 235–242. MR**0429508** - Martin Gavalec and Peter Vojtáš,
*Remarks to a modification of Ramsey-type theorems*, Comment. Math. Univ. Carolin.**21**(1980), no. 4, 727–738. MR**597762** - Petr Hájek and Pavel Pudlák,
*Metamathematics of first-order arithmetic*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998. Second printing. MR**1748522** - E. Herrmann,
*Infinite chains and antichains in computable partial orderings*, J. Symbolic Logic**66**(2001), no. 2, 923–934. MR**1833487**, DOI 10.2307/2695053 - Denis R. Hirschfeldt,
*Slicing the truth*, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, vol. 28, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. On the computable and reverse mathematics of combinatorial principles; Edited and with a foreword by Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin and Yue Yang. MR**3244278** - Denis R. Hirschfeldt and Carl G. Jockusch Jr.,
*On notions of computability-theoretic reduction between $\Pi _2^1$ principles*, J. Math. Log.**16**(2016), no. 1, 1650002, 59. MR**3518779**, DOI 10.1142/S0219061316500021 - Denis R. Hirschfeldt, Carl G. Jockusch Jr., Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman,
*The strength of some combinatorial principles related to Ramsey’s theorem for pairs*, Computational prospects of infinity. Part II. Presented talks, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 15, World Sci. Publ., Hackensack, NJ, 2008, pp. 143–161. MR**2449463**, DOI 10.1142/9789812796554_{0}008 - Denis R. Hirschfeldt and Richard A. Shore,
*Combinatorial principles weaker than Ramsey’s theorem for pairs*, J. Symbolic Logic**72**(2007), no. 1, 171–206. MR**2298478**, DOI 10.2178/jsl/1174668391 - Jeffry Lynn Hirst,
*COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC*, ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)–The Pennsylvania State University. MR**2635978** - Carl G. Jockusch Jr.,
*Ramsey’s theorem and recursion theory*, J. Symbolic Logic**37**(1972), 268–280. MR**376319**, DOI 10.2307/2272972 - Carl G. Jockusch Jr. and Robert I. Soare,
*$\Pi ^{0}_{1}$ classes and degrees of theories*, Trans. Amer. Math. Soc.**173**(1972), 33–56. MR**316227**, DOI 10.1090/S0002-9947-1972-0316227-0 - Carl Jockusch and Frank Stephan,
*A cohesive set which is not high*, Math. Logic Quart.**39**(1993), no. 4, 515–530. MR**1270396**, DOI 10.1002/malq.19930390153 - Manuel Lerman, Reed Solomon, and Henry Towsner,
*Separating principles below Ramsey’s theorem for pairs*, J. Math. Log.**13**(2013), no. 2, 1350007, 44. MR**3125903**, DOI 10.1142/S0219061313500074 - Jiayi Liu,
*${\mathsf {RT}}^2_2$ does not imply ${\mathsf {WKL}}_0$*, J. Symbolic Logic**77**(2012), no. 2, 609–620. MR**2963024**, DOI 10.2178/jsl/1333566640 - Lu Liu,
*Cone avoiding closed sets*, Trans. Amer. Math. Soc.**367**(2015), no. 3, 1609–1630. MR**3286494**, DOI 10.1090/S0002-9947-2014-06049-2 - Joseph Roy Mileti,
*Partition theorems and computability theory*, ProQuest LLC, Ann Arbor, MI, 2004. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. MR**2706695** - Benoit Monin and Ludovic Patey,
*$\mathsf {SRT}^2_2$ does not imply $\mathsf {RT}^2_2$ in $\omega$-models*, Adv. Math.**389**(2021), Paper No. 107903, 32. MR**4288219**, DOI 10.1016/j.aim.2021.107903 - André Nies,
*Computability and randomness*, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR**2548883**, DOI 10.1093/acprof:oso/9780199230761.001.0001 - Ludovic Patey,
*Partial orders and immunity in reverse mathematics*, Computability**7**(2018), no. 4, 323–339. MR**3877170**, DOI 10.3233/com-170071 - Ludovic Patey and Keita Yokoyama,
*The proof-theoretic strength of Ramsey’s theorem for pairs and two colors*, Adv. Math.**330**(2018), 1034–1070. MR**3787563**, DOI 10.1016/j.aim.2018.03.035 - Ivan Rival and Bill Sands,
*On the adjacency of vertices to the vertices of an infinite subgraph*, J. London Math. Soc. (2)**21**(1980), no. 3, 393–400. MR**577715**, DOI 10.1112/jlms/s2-21.3.393 - Joseph G. Rosenstein,
*Linear orderings*, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR**662564** - David Seetapun and Theodore A. Slaman,
*On the strength of Ramsey’s theorem*, Notre Dame J. Formal Logic**36**(1995), no. 4, 570–582. Special Issue: Models of arithmetic. MR**1368468**, DOI 10.1305/ndjfl/1040136917 - Stephen G. Simpson,
*Subsystems of second order arithmetic*, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR**2517689**, DOI 10.1017/CBO9780511581007 - Robert I. Soare,
*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921**, DOI 10.1007/978-3-662-02460-7 - E. Specker,
*Ramsey’s theorem does not hold in recursive set theory*, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 439–442. MR**0278941** - Klaus Weihrauch,
*The degrees of discontinuity of some translators between representations of the real numbers*, Berkeley, California, 1992. - Klaus Weihrauch,
*The TTE-interpretation of three hierarchies of omniscience principles*, Hagen, 1992.

## Additional Information

**Marta Fiori-Carones**- Affiliation: Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
- MR Author ID: 1437660
- ORCID: 0000-0002-5972-0542
- Email: marta.fioricarones@outlook.it
**Paul Shafer**- Affiliation: School of Mathematics, University of Leeds, Leeds LS2 9JT, United Kingdom
- MR Author ID: 920651
- ORCID: 0000-0001-5386-9218
- Email: p.e.shafer@leeds.ac.uk
**Giovanni Soldà**- Affiliation: School of Mathematics, University of Leeds, Leeds LS2 9JT, United Kingdom
- ORCID: 0000-0003-4903-3623
- Email: giovanni.a.solda@gmail.com
- Received by editor(s): June 30, 2020
- Received by editor(s) in revised form: August 11, 2021
- Published electronically: December 23, 2021
- Additional Notes: This project was partially supported by a grant from the John Templeton Foundation (
*A new dawn of intuitionism: mathematical and philosophical advances*ID 60842). Additionally, Fiori-Carones was partially supported by the Italian PRIN 2017 grant*Mathematical Logic: models, sets, computability*. The opinions expressed in this work are those of the authors and do not necessarily reflect the views of the John Templeton Foundation. - © Copyright 2021 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**375**(2022), 1977-2024 - MSC (2020): Primary 03B30, 03D30, 03F35
- DOI: https://doi.org/10.1090/tran/8561
- MathSciNet review: 4378086