pith. sign in

arxiv: 2412.11598 · v3 · submitted 2024-12-16 · 🧮 math.LO · math.CO

Ramsey-like theorems for the Schreier barrier

Lorenzo Carlucci , Oriola Gjetaj , Quentin Le Hou\'erou , Ludovic Levy Patey This is my paper

Pith reviewed 2026-05-23 07:16 UTC · model grok-4.3

classification 🧮 math.LO math.CO
keywords Schreier barrierThin Set theoremFree Set theoremRainbow Ramsey theoremcomputability theoryreverse mathematicsexactly omega-large setsTuring jumps
0
0 comments X

The pith

The exactly ω-large Thin Set and Free Set theorems code ∅^(ω) but the Rainbow Ramsey version does not code the halting set.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper generalizes three classical Ramsey theorems to colorings of the Schreier barrier, which consists of finite sets s where the size equals one plus the minimum element. It proves these generalizations and measures their computational strength using Turing jumps. The Thin Set and Free Set versions turn out to be powerful enough to compute the ω-th jump of the empty set. In contrast, the Rainbow Ramsey version remains computable from the halting set at most. This distinction reveals how the choice of Ramsey principle interacts with the barrier structure in terms of information coding.

Core claim

The authors show that generalizations of the Thin Set and Free Set theorems to colorings of exactly ω-large sets can code the ω-th jump of the empty set, whereas the generalization of the Rainbow Ramsey theorem does not code even the halting set.

What carries the argument

The Schreier barrier, the collection of finite sets s ⊆ ℕ with |s| = 1 + min(s), serving as the domain for the colorings in the generalized theorems.

If this is right

  • The Thin Set theorem on the Schreier barrier yields sets computing ∅^(ω).
  • The Free Set theorem on the Schreier barrier yields sets computing ∅^(ω).
  • The Rainbow Ramsey theorem on the Schreier barrier does not yield sets computing the halting problem.
  • These results are obtained via computability-theoretic constructions and reverse mathematics.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This separation may indicate that additive principles like Thin and Free Set interact more strongly with the size constraint of the barrier than multiplicative ones like Rainbow.
  • Similar analyses could be performed for other combinatorial barriers to see if the coding power pattern persists.
  • Applications might arise in understanding the computability of homogeneous sets in infinite combinatorics beyond standard Ramsey theory.

Load-bearing premise

That the chosen generalizations to colorings of the Schreier barrier faithfully capture the spirit of the original Free Set, Thin Set, and Rainbow Ramsey theorems.

What would settle it

A specific coloring of the Schreier barrier for which every thin homogeneous set fails to compute ∅^(ω) would falsify the coding claim for the Thin Set version.

Figures

Figures reproduced from arXiv: 2412.11598 by Lorenzo Carlucci, Ludovic Levy Patey, Oriola Gjetaj, Quentin Le Hou\'erou.

Figure 1
Figure 1. Figure 1: Studied statements from the perspectives of Computability Theory [PITH_FULL_IMAGE:figures/full_fig_p029_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Studied statements from the perspective of Weihrauch analysis. A [PITH_FULL_IMAGE:figures/full_fig_p030_2.png] view at source ↗
read the original abstract

The family of finite subsets $s$ of the natural numbers such that $|s|=1+\min s$ is known as the Schreier barrier in combinatorics and Banach Space theory, and as the family of exactly $\omega$-large sets in Logic. We formulate and prove the generalizations of Friedman's Free Set and Thin Set theorems and of Rainbow Ramsey's theorem to colorings of the Schreier barrier. We analyze the strength of these theorems from the point of view of Computability Theory and Reverse Mathematics. Surprisingly, the exactly $\omega$-large counterparts of the Thin Set and Free Set theorems can code $\emptyset^{(\omega)}$, while the exactly $\omega$-large Rainbow Ramsey theorem does not code the halting set.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper formulates and proves generalizations of Friedman's Free Set and Thin Set theorems and the Rainbow Ramsey theorem to colorings of the Schreier barrier (exactly ω-large sets). It then analyzes the computability-theoretic strength of these statements, claiming that the Thin Set and Free Set versions can code ∅^(ω) while the Rainbow Ramsey version does not code the halting set 0'.

Significance. If the chosen generalizations faithfully extend the classical theorems while preserving their combinatorial content, the reported separation between coding ∅^(ω) and failing to code even 0' would be a notable contribution to the computability analysis of Ramsey-like principles at the ω level, distinguishing the behavior of thin/free set principles from rainbow principles in this setting.

major comments (1)
  1. [Introduction / Definitions of generalizations] The central coding claims (Thin Set/Free Set coding ∅^(ω) vs. Rainbow Ramsey not coding 0') are load-bearing on the specific definitions of the 'exactly ω-large' generalizations. The manuscript should include an explicit argument (e.g., in the introduction or the section defining the generalizations) showing that these definitions preserve the key combinatorial features of the original theorems for colorings of pairs or infinite sets; without this, the separation could be an artifact of the formulation rather than a robust phenomenon.
minor comments (1)
  1. The abstract states the results clearly but the full manuscript should provide more detail on the exact statements of the generalized theorems (e.g., the precise uniformity or minimality conditions on the barrier colorings) to allow verification of the faithfulness assumption.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed reading and the constructive suggestion regarding the justification of our generalizations. We agree that an explicit discussion will strengthen the manuscript and clarify that the observed separation is not an artifact of the formulation.

read point-by-point responses

  1. Referee: [Introduction / Definitions of generalizations] The central coding claims (Thin Set/Free Set coding ∅^(ω) vs. Rainbow Ramsey not coding 0') are load-bearing on the specific definitions of the 'exactly ω-large' generalizations. The manuscript should include an explicit argument (e.g., in the introduction or the section defining the generalizations) showing that these definitions preserve the key combinatorial features of the original theorems for colorings of pairs or infinite sets; without this, the separation could be an artifact of the formulation rather than a robust phenomenon.

    Authors: We agree that an explicit justification is valuable. The definitions are the direct, standard extensions in which 'infinite' or 'pair' is replaced by 'exactly ω-large' (i.e., members of the Schreier barrier). This is the canonical way to lift classical Ramsey-type statements to barriers, as done in the literature on Ramsey theory for barriers (e.g., in the work of Galvin-Prikry and subsequent developments). The combinatorial content is preserved because the free-set and thin-set properties are expressed in terms of avoiding monochromatic structures on the chosen sets, and the rainbow condition likewise concerns distinct colors on the chosen ω-large sets. We will add a short paragraph in the introduction (and a brief remark in Section 2) spelling out this preservation, thereby addressing the concern that the separation might be formulation-dependent. revision: yes

Circularity Check

0 steps flagged

No circularity: new formulations and direct proofs

full rationale

The paper explicitly formulates new generalizations of the Thin Set, Free Set, and Rainbow Ramsey theorems to colorings of the Schreier barrier (exactly ω-large sets) and derives their computability-theoretic strength via direct proofs in reverse mathematics and computability. No quoted step equates a claimed prediction or theorem to its own inputs by definition, fitted parameter, or self-citation chain. The central separation (coding ∅^(ω) vs. not coding 0') follows from the stated combinatorial properties of the new statements rather than reducing tautologically to the choice of generalization. This is self-contained original work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is situated in reverse mathematics and computability theory, so it rests on the standard background axioms of those fields; no free parameters, ad-hoc axioms, or invented entities are mentioned in the abstract.

axioms (1)
  • standard math Standard axioms of second-order arithmetic (or ZFC) as used in reverse mathematics and computability theory
    The strength analysis is performed from the point of view of Computability Theory and Reverse Mathematics.

pith-pipeline@v0.9.0 · 5654 in / 1157 out tokens · 25034 ms · 2026-05-23T07:16:43.968885+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · 1 internal anchor

  1. [1]

    Caract´ erisation du type d’ordre des barri` eres de Nash- Williams.Publ

    Marc Assous. Caract´ erisation du type d’ordre des barri` eres de Nash- Williams.Publ. D´ ep. Math. (Lyon), 11(4):89–106, 1974

    work page 1974

  2. [2]

    Reduc- tions of well-ordering principles to combinatorial theorems.arXiv preprint arXiv:2401.04451, 2024

    Lorenzo Carlucci, Leonardo Mainardi, and Konread Zdanowski. Reduc- tions of well-ordering principles to combinatorial theorems.arXiv preprint arXiv:2401.04451, 2024

    work page arXiv 2024

  3. [3]

    The strength of Ramsey’s theo- rem for coloring relatively large sets.J

    Lorenzo Carlucci and Konrad Zdanowski. The strength of Ramsey’s theo- rem for coloring relatively large sets.J. Symb. Log., 79(1):89–102, 2014

    work page 2014

  4. [4]

    Thin set theorems and cone avoidance

    Peter Cholak and Ludovic Patey. Thin set theorems and cone avoidance. Trans. Amer. Math. Soc., 373(4):2743–2773, 2020

    work page 2020

  5. [5]

    Cholak, Mariagnese Giusto, Jeffry L

    Peter A. Cholak, Mariagnese Giusto, Jeffry L. Hirst, and Carl G. Jockusch, Jr. Free sets and reverse mathematics. InReverse mathematics 2001, volume 21 ofLect. Notes Log., pages 104–119. Assoc. Symbol. Logic, La Jolla, CA, 2005

    work page 2001

  6. [6]

    A recursion theoretic analysis of the clopen Ramsey theorem

    Peter Clote. A recursion theoretic analysis of the clopen Ramsey theorem. The Journal of symbolic logic, 49(2):376–400, 1984

    work page 1984

  7. [7]

    A generalization of the limit lemma and clopen games.Journal of Symbolic Logic, 51(2):273–291, 1986

    Peter Clote. A generalization of the limit lemma and clopen games.Journal of Symbolic Logic, 51(2):273–291, 1986

    work page 1986

  8. [8]

    Csima and Joseph R

    Barbara F. Csima and Joseph R. Mileti. The strength of the rainbow ramsey theorem.The Journal of Symbolic Logic, 74(4):1310–1324, 2009

    work page 2009

  9. [9]

    Dorais, Damir D

    Fran¸ cois G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer. On uniform relationships between combinatorial prob- lems.Trans. Amer. Math. Soc., 368(2):1321–1359, 2016

    work page 2016

  10. [10]

    Dzhafarov

    Damir D. Dzhafarov. Strong reductions between combinatorial principles. J. Symb. Log., 81(4):1405–1431, 2016

    work page 2016

  11. [11]

    Dzhafarov and Carl Mummert.Reverse mathematics—problems, reductions, and proofs

    Damir D. Dzhafarov and Carl Mummert.Reverse mathematics—problems, reductions, and proofs. Theory and Applications of Computability. Springer, Cham, [2022]©2022

    work page 2022

  12. [12]

    Farmaki and S

    V. Farmaki and S. Negrepontis. Schreier sets in Ramsey theory.Trans. Amer. Math. Soc., 360(2):849–880, 2008. 31

    work page 2008

  13. [13]

    Harvey Friedman and Stephen G. Simpson. Issues and problems in reverse mathematics. InComputability theory and its applications (Boulder, CO, 1999), volume 257 ofContemp. Math., pages 127–144. Amer. Math. Soc., Providence, RI, 2000

    work page 1999

  14. [14]

    Borel sets and Ramsey’s theorem.The Journal of Symbolic Logic, 38:193–198, 1973

    Fred Galvin and Karel Prikry. Borel sets and Ramsey’s theorem.The Journal of Symbolic Logic, 38:193–198, 1973

    work page 1973

  15. [15]

    Li- belli, Band 185

    Gerhard Gentzen.Die Widerspruchsfreiheit der reinen Zahlentheorie. Li- belli, Band 185. Wissenschaftliche Buchgesellschaft, Darmstadt, 1967

    work page 1967

  16. [16]

    Perspectives in Mathematical Logic

    Petr H´ ajek and Pavel Pudl´ ak.Metamathematics of first-order arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1998. Second printing

    work page 1998

  17. [17]

    Hirschfeldt.Slicing the truth, volume 28 ofLecture Notes Se- ries

    Denis R. Hirschfeldt.Slicing the truth, volume 28 ofLecture Notes Se- ries. Institute for Mathematical Sciences. National University of Singapore. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. On the computable and reverse mathematics of combinatorial principles, Edited and with a foreword by Chitat Chong, Qi Feng, Theodore A. Slaman, W...

    work page 2015

  18. [18]

    Jockusch

    Carl G. Jockusch. Ramsey’s theorem and recursion theory.The Journal of Symbolic Logic, 37(2):268–280, 1972

    work page 1972

  19. [19]

    Sur une caract´ erisation des alephs.Fund

    Casimir Kuratowski. Sur une caract´ erisation des alephs.Fund. Math., 38:14–17, 1951

    work page 1951

  20. [20]

    RT22 does not imply WKL0.The Journal of Symbolic Logic, 77(2):609–620, 2012

    Jiayi Liu. RT22 does not imply WKL0.The Journal of Symbolic Logic, 77(2):609–620, 2012

    work page 2012

  21. [21]

    Cone avoiding closed sets.Trans

    Lu Liu. Cone avoiding closed sets.Trans. Amer. Math. Soc., 367(3):1609– 1630, 2015

    work page 2015

  22. [22]

    The Reverse Mathematics of the Thin Set and Erd˝ os-Moser Theorems.Journal of Symbolic Logic, 87(1):313–346, 2022

    Lu Liu and Ludovic Patey. The Reverse Mathematics of the Thin Set and Erd˝ os-Moser Theorems.Journal of Symbolic Logic, 87(1):313–346, 2022

    work page 2022

  23. [23]

    Wqo and bqo theory in subsystems of second order arithmetic

    Alberto Marcone. Wqo and bqo theory in subsystems of second order arithmetic. InReverse mathematics 2001, volume 21 ofLect. Notes Log., pages 303–330. Assoc. Symbol. Logic, La Jolla, CA, 2005

    work page 2001

  24. [24]

    Open questions in reverse mathematics.Bulletin of Symbolic Logic, 17(03):431–454, 2011

    Antonio Montalb´ an. Open questions in reverse mathematics.Bulletin of Symbolic Logic, 17(03):431–454, 2011. Publisher: Cambridge Univ Press

    work page 2011

  25. [25]

    C. St. J. A. Nash-Williams. On better-quasi-ordering transfinite sequences. Proc. Cambridge Philos. Soc., 64:273–290, 1968

    work page 1968

  26. [26]

    A mathematical incompleteness in Peano Arithmetic

    Jeff Paris and Leo Harrington. A mathematical incompleteness in Peano Arithmetic. In Jon Barwise, editor,Handbook of mathematical logic, pages 90–1133. North-Holland, 1977. 32

    work page 1977

  27. [27]

    Somewhere over the rainbow Ramsey theorem for pairs

    Ludovic Patey. Somewhere over the rainbow ramsey theorem for pairs. arXiv preprint arXiv:1501.07424, 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  28. [28]

    The weakness of being cohesive, thin or free in reverse mathematics.Israel J

    Ludovic Patey. The weakness of being cohesive, thin or free in reverse mathematics.Israel J. Math., 216(2):905–955, 2016

    work page 2016

  29. [29]

    Iterative forcing and hyperimmunity in reverse mathemat- ics.Computability, 6(3):209–221, 2017

    Ludovic Patey. Iterative forcing and hyperimmunity in reverse mathemat- ics.Computability, 6(3):209–221, 2017

    work page 2017

  30. [30]

    Sur les pr´ emeilleurordres.Annales de l’institut Fourier, 22(2):1–19, 1972

    Maurice Pouzet. Sur les pr´ emeilleurordres.Annales de l’institut Fourier, 22(2):1–19, 1972

    work page 1972

  31. [31]

    Partition theorems for systems of finite subsets of integers.Discrete Math., 39(1):67–73, 1982

    Pavel Pudl´ ak and Vojtˇ ech R¨ odl. Partition theorems for systems of finite subsets of integers.Discrete Math., 39(1):67–73, 1982

    work page 1982

  32. [32]

    David Seetapun and Theodore A. Slaman. On the strength of Ramsey’s theorem. volume 36, pages 570–582. 1995. Special Issue: Models of arith- metic

    work page 1995

  33. [33]

    Simpson.Subsystems of second order arithmetic

    Stephen G. Simpson.Subsystems of second order arithmetic. Perspectives in Logic. Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, second edition, 2009

    work page 2009

  34. [34]

    Princeton University Press, Princeton, 2010

    Stevo Todorcevic.Introduction to Ramsey Spaces. Princeton University Press, Princeton, 2010

    work page 2010

  35. [35]

    Some logically weak Ramseyan theorems.Adv

    Wei Wang. Some logically weak Ramseyan theorems.Adv. Math., 261:1–25, 2014. 33

    work page 2014