A computable analysis of variable words theorems

DOI10.1090/PROC/14269MaRDI QIDQ4644466zbMATH OpenOpenAlexWikidataFDO

Authors Lu Liu, Benoit Monin, Ludovic Patey

Publication date 7 January 2019

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.11219

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35) Permutations, words, matrices (05A05)

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 ACA0.

Recommendations

• Effectiveness for infinite variable words and the dual Ramsey theorem
• A density version of the Carlson-Simpson theorem
• On the strength of Ramsey's theorem for pairs
• Partition theorems for left and right variable words
• On the uniform computational content of Ramsey's theorem

Cites work

• A dual form of Ramsey's theorem
• Effectiveness for infinite variable words and the dual Ramsey theorem
• scientific article; zbMATH DE number 1531925 (Why is no real title available?)
• Open questions in reverse mathematics
• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• Subsystems of second order arithmetic
• The reverse mathematics of Hindman's theorem for sums of exactly two elements

Cited in

(5)

• Effectiveness for the dual Ramsey theorem
• Partition theorems for left and right variable words
• Partition Theorems for Spaces of Variable Words
• A density version of the Carlson-Simpson theorem
• Effectiveness for infinite variable words and the dual Ramsey theorem

This page was built for publication: A computable analysis of variable words theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4644466)