A computable analysis of variable words theorems

Liu, Lu; Monin, Benoit; Patey, Ludovic

doi:10.1090/proc/14269

A computable analysis of variable words theorems
HTML articles powered by AMS MathViewer

by Lu Liu, Benoit Monin and Ludovic Patey PDF

Proc. Amer. Math. Soc. 147 (2019), 823-834 Request permission

Abstract:

The Carlson–Simpson lemma is a combinatorial statement occurring in the proof of the Dual Ramsey theorem. Formulated in terms of variable words, it informally asserts that given any finite coloring of the strings, there is an infinite sequence with infinitely many variables such that for every valuation, some specific set of initial segments is homogeneous. Friedman, Simpson, and Montalban asked about its reverse mathematical strength. We study the computability-theoretic properties and the reverse mathematics of this statement, and relate it to the finite union theorem. In particular, we prove the Ordered Variable word for binary strings in $\textsf {ACA}_0$.

References

Timothy J. Carlson and Stephen G. Simpson, A dual form of Ramsey’s theorem, Adv. in Math. 53 (1984), no. 3, 265–290. MR 753869, DOI 10.1016/0001-8708(84)90026-4
Barbara F. Csima, Damir D. Dzhafarov, Denis R. Hirschfeldt, Carl G. Jockusch Jr, Reed Solomon, and Linda Brown Westrick, The reverse mathematics of Hindman’s theorem for sums of exactly two elements, arXiv preprint arXiv:1804.09809 (2018).
Damir D. Dzhafarov, Stephen Flood, Reed Solomon, and Linda Brown Westrick, Effectiveness for the dual Ramsey theorem, To appear. Available at http://www.math.uconn.edu/~damir/papers/dualRT.pdf, 2017.
Harvey Friedman and Stephen G. Simpson, Issues and problems in reverse mathematics, Computability theory and its applications (Boulder, CO, 1999) Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 127–144. MR 1770738, DOI 10.1090/conm/257/04031
Joseph S. Miller and Reed Solomon, Effectiveness for infinite variable words and the dual Ramsey theorem, Arch. Math. Logic 43 (2004), no. 4, 543–555. MR 2060398, DOI 10.1007/s00153-004-0216-4
Antonio Montalbán, Open questions in reverse mathematics, Bull. Symbolic Logic 17 (2011), no. 3, 431–454. MR 2856080, DOI 10.2178/bsl/1309952320
Andrei Rumyantsev and Alexander Shen, Probabilistic constructions of computable objects and a computable version of Lovász local lemma, Fund. Inform. 132 (2014), no. 1, 1–14. MR 3214660, DOI 10.3233/fi-2014-1029
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
Theodore A. Slaman, A note on dual Ramsey theorem, Unpublished, January 1997.