×

zbMATH — the first resource for mathematics

A computable analysis of variable words theorems. (English) Zbl 06997852
Summary: 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 \(\mathsf {ACA}_0\).
MSC:
03B30 Foundations of classical theories (including reverse mathematics)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Carlson, Timothy J.; Simpson, Stephen G., A dual form of Ramsey’s theorem, Adv. in Math., 53, 3, 265-290, (1984) · Zbl 0564.05005
[2] Csima2018reverse Barbara F. Csima, Damir D. Dzhafarov, Denis R. Hirschfeldt, Carl G. Jockusch Jr, Reed Solomon, and Linda Brown Westrick, \emph The reverse mathematics of Hindman’s theorem for sums of exactly two elements, arXiv preprint arXiv:1804.09809 (2018).
[3] Dzhafarov2017Effectiveness Damir D. Dzhafarov, Stephen Flood, Reed Solomon, and Linda Brown Westrick, \emph Effectiveness for the dual Ramsey theorem, To appear. Available at \urlhttp://www.math.uconn.edu/ damir/papers/dualRT.pdf, 2017.
[4] Friedman, Harvey; Simpson, Stephen G., Issues and problems in reverse mathematics. Computability theory and its applications, Boulder, CO, 1999, Contemp. Math. 257, 127-144, (2000), Amer. Math. Soc., Providence, RI · Zbl 0967.03050
[5] Miller, Joseph S.; Solomon, Reed, Effectiveness for infinite variable words and the dual Ramsey theorem, Arch. Math. Logic, 43, 4, 543-555, (2004) · Zbl 1059.03068
[6] Montalb\'an, Antonio, Open questions in reverse mathematics, Bull. Symbolic Logic, 17, 3, 431-454, (2011) · Zbl 1233.03023
[7] Rumyantsev, Andrei; Shen, Alexander, Probabilistic constructions of computable objects and a computable version of Lov\'asz local lemma, Fund. Inform., 132, 1, 1-14, (2014) · Zbl 1317.68131
[8] 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
[9] Slaman1997note Theodore A. Slaman, \emph A note on dual Ramsey theorem, Unpublished, January 1997.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.