Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A computable analysis of variable words theorems


Authors: Lu Liu, Benoit Monin and Ludovic Patey
Journal: Proc. Amer. Math. Soc. 147 (2019), 823-834
MSC (2010): Primary 03B30
DOI: https://doi.org/10.1090/proc/14269
Published electronically: November 5, 2018
MathSciNet review: 3894920
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

References

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03B30

Retrieve articles in all journals with MSC (2010): 03B30


Additional Information

Lu Liu
Affiliation: Department of Mathematics, Central South University, ChangSha 410083, People’s Republic of China
MR Author ID: 980145
Email: g.jiayi.liu@gmail.com

Benoit Monin
Affiliation: Département d’Informatique, Faculté des Sciences et Technologie, LACL, 61 avenue du Général de Gaulle, 94010 Créteil Cedex, France
MR Author ID: 1024056
Email: benoit.monin@computability.fr

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): November 6, 2017
Received by editor(s) in revised form: November 7, 2017, May 20, 2018, and June 2, 2018
Published electronically: November 5, 2018
Communicated by: Heike Mildenberger
Article copyright: © Copyright 2018 American Mathematical Society