## Thin set theorems and cone avoidance

HTML articles powered by AMS MathViewer

- by Peter Cholak and Ludovic Patey PDF
- Trans. Amer. Math. Soc.
**373**(2020), 2743-2773 Request permission

## Abstract:

The thin set theorem $\operatorname {\mathsf {RT}}^n_{<\infty ,\ell }$ asserts the existence, for every $k$-coloring of the subsets of natural numbers of size $n$, of an infinite set of natural numbers, all of whose subsets of size $n$ use at most $\ell$ colors. Whenever $\ell = 1$, the statement corresponds to Ramsey’s theorem. From a computational viewpoint, the thin set theorem admits a threshold phenomenon, in that whenever the number of colors $\ell$ is sufficiently large with respect to the size $n$ of the tuples, the thin set theorem admits strong cone avoidance.

Let $d_0, d_1, \dots$ be the sequence of Catalan numbers. For $n \geq 1$, $\operatorname {\mathsf {RT}}^n_{<\infty , \ell }$ admits strong cone avoidance if and only if $\ell \geq d_n$ and cone avoidance if and only if $\ell \geq d_{n-1}$. We say that a set $A$ is *$\operatorname {\mathsf {RT}}^n_{<\infty , \ell }$-encodable* if there is an instance of $\operatorname {\mathsf {RT}}^n_{<\infty , \ell }$ such that every solution computes $A$. The $\operatorname {\mathsf {RT}}^n_{<\infty , \ell }$-encodable sets are precisely the hyperarithmetic sets if and only if $\ell < 2^{n-1}$, the arithmetic sets if and only if $2^{n-1} \leq \ell < d_n$, and the computable sets if and only if $d_n \leq \ell$.

## References

- Peter A. Cholak, Damir D. Dzhafarov, Jeffry L. Hirst, and Theodore A. Slaman,
*Generics for computable Mathias forcing*, Ann. Pure Appl. Logic**165**(2014), no. 9, 1418–1428. MR**3210076**, DOI 10.1016/j.apal.2014.04.011 - Peter A. Cholak, Mariagnese Giusto, Jeffry L. Hirst, and Carl G. Jockusch Jr.,
*Free sets and reverse mathematics*, Reverse mathematics 2001, Lect. Notes Log., vol. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005, pp. 104–119. MR**2185429** - Chris J. Conidis,
*Classifying model-theoretic properties*, J. Symbolic Logic**73**(2008), no. 3, 885–905. MR**2444274**, DOI 10.2178/jsl/1230396753 - Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight, and Robert I. Soare,
*Bounding prime models*, J. Symbolic Logic**69**(2004), no. 4, 1117–1142. MR**2135658**, DOI 10.2178/jsl/1102022214 - 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 - Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, and Dan Turetsky,
*Relationships between computability-theoretic properties of problems*, arXiv.org, March 2019. - Harvey M. Friedman,
*Fom:53:free sets and reverse math and fom:54:recursion theory and dynamics*, Available at https://www.cs.nyu.edu/pipermail/fom/. - Marcia J. Groszek and Theodore A. Slaman,
*Moduli of computation*(talk), Buenos Aires, Argentina, 2007. - 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 - Alexander P. Kreuzer,
*Primitive recursion and the chain antichain principle*, Notre Dame J. Form. Log.**53**(2012), no. 2, 245–265. MR**2925280**, DOI 10.1215/00294527-1715716 - Antonio Montalbán,
*Open questions in reverse mathematics*, Bull. Symbolic Logic**17**(2011), no. 3, 431–454. MR**2856080**, DOI 10.2178/bsl/1309952320 - Ludovic Patey,
*Combinatorial weaknesses of Ramseyan principles*. In preparation. Available at http://ludovicpatey.com/media/research/combinatorial-weaknesses-draft.pdf, 2015. - Ludovic Patey,
*Iterative forcing and hyperimmunity in reverse mathematics*, Evolving computability, Lecture Notes in Comput. Sci., vol. 9136, Springer, Cham, 2015, pp. 291–301. MR**3382369**, DOI 10.1007/978-3-319-20028-6_{3}0 - Ludovic Patey,
*Partial orders and immunity in reverse mathematics*, Pursuit of the universal, Lecture Notes in Comput. Sci., vol. 9709, Springer, [Cham], 2016, pp. 353–363. MR**3535177**, DOI 10.1007/978-3-319-40189-8_{3}6 - Ludovic Patey,
*The weakness of being cohesive, thin or free in reverse mathematics*, Israel J. Math.**216**(2016), no. 2, 905–955. MR**3557471**, DOI 10.1007/s11856-016-1433-3 - Ludovic Patey,
*Ramsey-like theorems and moduli of computation*, arXiv.org, January 2019. - 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 - J. R. Shoenfield,
*On degrees of unsolvability*, Ann. of Math. (2)**69**(1959), 644–653. MR**105355**, DOI 10.2307/1970028 - 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 M. Solovay,
*Hyperarithmetically encodable sets*, Trans. Amer. Math. Soc.**239**(1978), 99–122. MR**491103**, DOI 10.1090/S0002-9947-1978-0491103-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** - Richard P. Stanley,
*Catalan numbers*, Cambridge University Press, New York, 2015. MR**3467982**, DOI 10.1017/CBO9781139871495 - Wei Wang,
*Some logically weak Ramseyan theorems*, Adv. Math.**261**(2014), 1–25. MR**3213294**, DOI 10.1016/j.aim.2014.05.003

## Additional Information

**Peter Cholak**- Affiliation: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana, 46556
- MR Author ID: 290865
- ORCID: 0000-0002-6547-5408
- Email: Peter.Cholak.1@nd.edu
**Ludovic Patey**- Affiliation: Institut Camille Jordan, Université Claude Bernard Lyon 1, 43 boulevard du 11 novembre 1918, F-69622 Villeurbanne Cedex, France
- MR Author ID: 1102703
- ORCID: 0000-0002-0304-7926
- Email: ludovic.patey@computability.fr
- Received by editor(s): December 3, 2018
- Received by editor(s) in revised form: March 15, 2019, August 19, 2019, and August 29, 2019
- Published electronically: January 7, 2020
- Additional Notes: The first author was partially supported by a grant from the Simons Foundation (#315283) and NSF Conference grants (DMS-1640836 and DMS-1822193)
- © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**373**(2020), 2743-2773 - MSC (2010): Primary 03B30
- DOI: https://doi.org/10.1090/tran/7987
- MathSciNet review: 4069232