×

Thin set theorems and cone avoidance. (English) Zbl 1442.03007

The authors explore the logical, computational, and combinatorial strength of a thin set theorem, \(\mathsf{RT}^n_{<\infty ,\ell}\) that asserts that for every finite coloring of \([\mathbb N ]^n\) (the subsets of \(\mathbb N\) of size \(n\)) there is an infinite set \(H\) such that \([ H ]^n\) contains at most \(\ell\) colors. The theorem can be viewed as a problem, where each coloring instance has a solution set \(H\). A set \(A\) is \(\mathsf{RT}^n_{<\infty ,\ell}\)-encodable if there is an instance such that every solution computes \(A\).
Among the results of the paper is the following three-part complete characterization of the \(\mathsf{RT}^n_{<\infty ,\ell}\)-encodable sets, involving an unexpected appearance of \(d_n\), the \(n^{\text{th}}\) Catalan number.
(1) The \(\mathsf{RT}^n_{<\infty ,\ell}\)-encodable sets are the hyperarithmetic sets if and only if \(\ell<2^{n-1}\).
(2) The \(\mathsf{RT}^n_{<\infty ,\ell}\)-encodable sets are the arithmetic sets if and only if \(2^{n-1}\le \ell < d_n\).
(3) The \(\mathsf{RT}^n_{<\infty ,\ell}\)-encodable sets are the computable sets if and only if \(d_n \le \ell\).
The authors also show that \(\mathsf{RT}^n_{<\infty ,\ell}\) admits strong cone avoidance if and only if \(\ell \ge d_n\), and admits cone avoidance if and only if \(l \ge d_{n-1}\). Establishing these thresholds answers questions arising from the work of W. Wang [Adv. Math. 261, 1–25 (2014; Zbl 1307.03011)] on an achromatic Ramsey theorem, F. G. Dorais et al. [Trans. Am. Math. Soc. 368, No. 2, 1321–1359 (2016; Zbl 1528.03095)], and A. Montalbán [Bull. Symb. Log. 17, No. 3, 431–454 (2011; Zbl 1233.03023)]. The results extend the program of the second author [Computability 6, No. 3, 209–221 (2017; Zbl 1420.03028); Isr. J. Math. 216, No. 2, 905–955 (2016; Zbl 1368.03018)], and are used in recent work of R. Downey et al. [“Relationships between computability-theoretic properties of problems”, Preprint, arXiv:1903.04273] and the second author [“Ramsey-like theorems and moduli of computation”, Preprint, arXiv:1901.04388].

MSC:

03B30 Foundations of classical theories (including reverse mathematics)
03F35 Second- and higher-order arithmetic and fragments
03D80 Applications of computability and recursion theory
05D10 Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

References:

[1] Cholak, Peter A.; Dzhafarov, Damir D.; Hirst, Jeffry L.; Slaman, Theodore A., Generics for computable Mathias forcing, Ann. Pure Appl. Logic, 165, 9, 1418-1428 (2014) · Zbl 1320.03072 · doi:10.1016/j.apal.2014.04.011
[2] Cholak, Peter A.; Giusto, Mariagnese; Hirst, Jeffry L.; Jockusch, Carl G., Jr., Free sets and reverse mathematics. Reverse mathematics 2001, Lect. Notes Log. 21, 104-119 (2005), Assoc. Symbol. Logic, La Jolla, CA · Zbl 1092.03031
[3] Conidis, Chris J., Classifying model-theoretic properties, J. Symbolic Logic, 73, 3, 885-905 (2008) · Zbl 1160.03012 · doi:10.2178/jsl/1230396753
[4] Csima, Barbara F.; Hirschfeldt, Denis R.; Knight, Julia F.; Soare, Robert I., Bounding prime models, J. Symbolic Logic, 69, 4, 1117-1142 (2004) · Zbl 1071.03021 · doi:10.2178/jsl/1102022214
[5] Dorais, Fran\c{c}ois G.; Dzhafarov, Damir D.; Hirst, Jeffry L.; Mileti, Joseph R.; Shafer, Paul, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc., 368, 2, 1321-1359 (2016) · Zbl 1528.03095 · doi:10.1090/tran/6465
[6] Downey:2019uf Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, and Dan Turetsky, Relationships between computability-theoretic properties of problems, arXiv.org, March 2019. · Zbl 1507.03067
[7] FriedmanFom53free 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/.
[8] Groszek2007Moduli Marcia J. Groszek and Theodore A. Slaman, Moduli of computation (talk), Buenos Aires, Argentina, 2007.
[9] Jockusch, Carl G., Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic, 37, 268-280 (1972) · Zbl 0262.02042 · doi:10.2307/2272972
[10] Jockusch, Carl G., Jr.; Soare, Robert I., \( \Pi^0_1\) classes and degrees of theories, Trans. Amer. Math. Soc., 173, 33-56 (1972) · Zbl 0262.02041 · doi:10.2307/1996261
[11] Kreuzer, Alexander P., Primitive recursion and the chain antichain principle, Notre Dame J. Form. Log., 53, 2, 245-265 (2012) · Zbl 1253.03090 · doi:10.1215/00294527-1715716
[12] Montalb\'{a}n, Antonio, Open questions in reverse mathematics, Bull. Symbolic Logic, 17, 3, 431-454 (2011) · Zbl 1233.03023 · doi:10.2178/bsl/1309952320
[13] PateyCombinatorial Ludovic Patey, Combinatorial weaknesses of Ramseyan principles. In preparation. Available at http://ludovicpatey.com/media/research/combinatorial-weaknesses-draft.pdf, 2015.
[14] Patey, Ludovic, Iterative forcing and hyperimmunity in reverse mathematics. Evolving computability, Lecture Notes in Comput. Sci. 9136, 291-301 (2015), Springer, Cham · Zbl 1461.03011 · doi:10.1007/978-3-319-20028-6\_30
[15] Patey, Ludovic, Partial orders and immunity in reverse mathematics. Pursuit of the universal, Lecture Notes in Comput. Sci. 9709, 353-363 (2016), Springer, [Cham] · Zbl 1476.03005 · doi:10.1007/978-3-319-40189-8\_36
[16] Patey, Ludovic, The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math., 216, 2, 905-955 (2016) · Zbl 1368.03018 · doi:10.1007/s11856-016-1433-3
[17] Patey:2019wd Ludovic Patey, Ramsey-like theorems and moduli of computation, arXiv.org, January 2019.
[18] Rosenstein, Joseph G., Linear orderings, Pure and Applied Mathematics 98, xvii+487 pp. (1982), Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London · Zbl 0488.04002
[19] Seetapun, David; Slaman, Theodore A., On the strength of Ramsey’s theorem, Notre Dame J. Formal Logic, 36, 4, 570-582 (1995) · Zbl 0843.03034 · doi:10.1305/ndjfl/1040136917
[20] Shoenfield, J. R., On degrees of unsolvability, Ann. of Math. (2), 69, 644-653 (1959) · Zbl 0119.25105 · doi:10.2307/1970028
[21] Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Logic, xvi+444 pp. (2009), Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY · Zbl 1181.03001 · doi:10.1017/CBO9780511581007
[22] Solovay, Robert M., Hyperarithmetically encodable sets, Trans. Amer. Math. Soc., 239, 99-122 (1978) · Zbl 0411.03039 · doi:10.2307/1997849
[23] Specker, E., Ramsey’s theorem does not hold in recursive set theory. Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969), 439-442 (1971), North-Holland, Amsterdam · Zbl 0285.02038
[24] Stanley, Richard P., Catalan numbers, viii+215 pp. (2015), Cambridge University Press, New York · Zbl 1317.05010 · doi:10.1017/CBO9781139871495
[25] Wang, Wei, Some logically weak Ramseyan theorems, Adv. Math., 261, 1-25 (2014) · Zbl 1307.03011 · doi:10.1016/j.aim.2014.05.003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.