Π⁰₄ conservation of a Carlson-Simpson lemma for 1-variable words

2026/07/30 by Quentin Le Houérou, Ludovic Patey
Mathematics · #math.LO #msc:03B30 #msc:03F35 #msc:05D10

paper · pdf

33 pages

arxiv created 2026/07/30 · arxiv updated 2026/07/31

Abstract

Carlson and Simpson proved that for every finite coloring of the 1-variable words over a finite alphabet~A, there is an infinite ω-variable word on which all the 1-variable words are monochromatic. This statement for ℓ-colorings, written CSL¹_ℓ, is known to be strictly weaker than ACA₀. We prove that RCA₀ + CSL¹₂ is a ∀ Π⁰₄-conservative extension of RCA₀ + BSigma₂. Among its consequences, it implies that neither the indivisibility of the universal triangle-free Henson graph for 2-colorings, nor the tree theorem for pairs and two colors, imply Σ⁰₂-induction. This answers a question of Chong, Li, Wang and Yang.

Citations

• Π⁰₄ conservation of the Ordered Variable Word theorem
• The reverse mathematics of Carlson's theorem for located words
• Carlson-Simpson's lemma and applications in reverse mathematics
• Conservation Strength of The Infinite Pigeonhole Principle for Trees
• Big Ramsey degrees using parameter spaces
• Milliken's tree theorem and its applications: a computability-theoretic perspective
• Ramsey's theorem for pairs, collection, and proof size
• Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs
• A computable analysis of variable words theorems
• Effectiveness for the Dual Ramsey Theorem
• The Ramsey theory of the universal homogeneous triangle-free graph Part II: Exact big Ramsey degrees
• Coloring trees in reverse mathematics
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• The strength of the tree theorem for pairs in reverse mathematics
• A Simple Proof and Some Difficult Examples for Hindman's Theorem
• Hindman's Theorem: An Ultrafilter Argument in Second Order Arithmetic

Related

• Π⁰₄ conservation of the Ordered Variable Word theorem
• A computable analysis of variable words theorems
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• A Coloring Problem for Infinite Words
• Conservation Strength of The Infinite Pigeonhole Principle for Trees