pith. sign in

arxiv: 2508.15597 · v2 · submitted 2025-08-21 · 🧮 math.LO

Ramsey-like theorems and immunities

Ahmed Mimouni , Ludovic Patey This is my paper

Pith reviewed 2026-05-18 21:44 UTC · model grok-4.3

classification 🧮 math.LO
keywords Ramsey-like theoremscomputabilityreverse mathematicsimmunitydiagonally non-computable functionspattern avoidance2-colorings of pairs
0
0 comments X

The pith

A computable 2-coloring of pairs exists such that every infinite set avoiding any pattern computes a diagonally non-computable function relative to 0'.

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

The paper studies Ramsey-like theorems asserting that every 2-coloring of the pairs from the natural numbers admits an infinite subset whose pairs avoid a given pattern. It establishes that none of these theorems are computably trivial through a single computable coloring in which every infinite pattern-avoiding set computes a function diagonally non-computable relative to the jump of the empty set. The authors further classify the theorems according to whether they preserve various immunity notions, with the classification turning on the shape of the avoided pattern. This contributes to determining the computational and logical strength of these statements within reverse mathematics.

Core claim

For any fixed pattern there exists a computable 2-coloring of [N]^2 such that every infinite set H whose pairs avoid the pattern computes a function f satisfying f(e) ≠ Φ_e^{∅'}(e) for every e. The paper also gives a shape-based classification of patterns that determines precisely which corresponding Ramsey-like theorems preserve or fail to preserve different variants of immunity.

What carries the argument

A computable 2-coloring of [N]^2 that forces every infinite pattern-avoiding set to compute a diagonally non-computable function relative to ∅'.

If this is right

  • Each Ramsey-like theorem implies the existence of a diagonally non-computable function relative to 0' over any computable model.
  • Immunity preservation or failure provides a computability-theoretic separation between different patterns.
  • The shape classification yields a uniform method for determining the weakness of each Ramsey-like statement.
  • These results supply witnesses that no such theorem can be satisfied entirely within the computable sets.

Where Pith is reading between the lines

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

  • The same forcing technique may extend to colorings of triples or higher and to other combinatorial principles.
  • Concrete patterns such as avoiding monochromatic solutions to linear equations could be checked directly against the shape classification.
  • The immunity distinctions may interact with other computability notions such as traceability or low sets.

Load-bearing premise

The avoided patterns can be classified by shape in a manner that permits uniform computable constructions or separations for the immunity properties.

What would settle it

An explicit pattern together with a computable 2-coloring of [N]^2 in which some infinite avoiding set fails to compute any diagonally non-computable function relative to ∅'.

Figures

Figures reproduced from arXiv: 2508.15597 by Ahmed Mimouni, Ludovic Patey.

Figure 1
Figure 1. Figure 1: The two graphs represent the patterns p0 : [3]2 → 2 and p1 : [3]2 → 2, respectively defined as follows: p0(0, 1) = p0(1, 2) = 0, p0(0, 2) = 1, p1(0, 1) = p1(1, 2) = 1 and p1(0, 2) = 0. The domain {0, 1, 2} corresponding to the set of vertices is renamed {a, b, c} for readability. Statement 1.1. For every pattern p, RT2 2 (p) is the statement “Every coloring f : [N] 2 → 2 has an infinite set f-avoiding p.” … view at source ↗
read the original abstract

A Ramsey-like theorem is a statement of the form ``For every 2-coloring of $[\mathbb{N}]^2$, there exists an infinite set~$H \subseteq \mathbb{N}$ such that $[H]^2$ avoids some pattern''. We prove that none of these statements are computably trivial, by constructing a computable 2-coloring of $[\mathbb{N}]^2$ such that every infinite set avoiding any pattern computes a diagonally non-computable function relative to $\emptyset'$. We also consider multiple notions of weaknesses based of variants of immunity, and characterize the Ramsey-like theorems which preserve these notions or not, based on the shape of the avoided pattern. This is part of a larger study of the reverse mathematics of Ramsey-like theorems.

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 / 2 minor

Summary. The manuscript proves that no Ramsey-like theorem of the form 'for every 2-coloring of [ℕ]² there exists an infinite H such that [H]² avoids a fixed pattern' is computably trivial. It does so by exhibiting a single computable 2-coloring of pairs such that every infinite set avoiding the pattern computes a diagonally non-computable function relative to ∅'. The paper further classifies which such theorems preserve or fail to preserve several immunity notions, with the classification depending on the combinatorial shape of the avoided pattern (monochromatic, rainbow, or mixed finite configurations). The work is framed as part of the reverse-mathematics study of Ramsey-like statements.

Significance. If the central construction and case analysis hold, the results supply concrete computability-theoretic separations for an entire family of Ramsey-like principles. The uniform diagonalization that works for an arbitrary fixed pattern while respecting avoidance, together with the explicit case split on pattern shape for immunity preservation, gives a systematic method that can be reused in related investigations. These contributions strengthen the computability analysis of Ramsey theorems beyond the classical homogeneous-set case.

major comments (1)
  1. [§3] §3 (Construction): The diagonalization against computable approximations of potential DNC functions must be shown to remain compatible with the avoidance condition for every possible finite pattern; the current sketch leaves open whether the priority ordering or the restraint on color changes could inadvertently force a forbidden configuration when the pattern is a mixed finite set of size greater than 2.
minor comments (2)
  1. The precise inductive definition of 'pattern shape' used for the case division (monochromatic vs. rainbow vs. mixed) should be stated once, early in the paper, with a short table enumerating the representative configurations for each class.
  2. Notation for the set of all finite patterns and for the avoidance relation [H]² ⊀ P should be fixed uniformly; occasional use of informal phrases such as 'avoids any pattern' risks ambiguity when the same symbol is later reused for a specific fixed pattern.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and the specific comment on the construction. We address the point below and will revise the manuscript accordingly to strengthen the exposition.

read point-by-point responses

  1. Referee: [§3] §3 (Construction): The diagonalization against computable approximations of potential DNC functions must be shown to remain compatible with the avoidance condition for every possible finite pattern; the current sketch leaves open whether the priority ordering or the restraint on color changes could inadvertently force a forbidden configuration when the pattern is a mixed finite set of size greater than 2.

    Authors: We agree that the sketch in the current version could be expanded for clarity on this point. The construction builds the computable 2-coloring in stages using a finite-injury priority method. At each stage, when satisfying a diagonalization requirement against a computable approximation to a potential DNC function, color assignments are chosen only on pairs that do not complete any instance of the fixed forbidden pattern (monochromatic, rainbow, or mixed) with the existing finite coloring. For mixed patterns of size greater than 2, the restraint mechanism explicitly checks all relevant finite configurations before permitting a color change, ensuring no forbidden subconfiguration is introduced. The priority ordering is arranged so that higher-priority requirements act first and lower-priority ones respect the finite restraints already imposed; because patterns are finite, any potential injury is bounded and does not propagate to force a violation. We will add a dedicated lemma in the revised §3 proving that the final coloring satisfies the avoidance condition uniformly for every fixed finite pattern. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on explicit constructions and case analysis

full rationale

The paper establishes its main results through direct, uniform constructions of computable 2-colorings of [N]^2 that force infinite pattern-avoiding sets to compute DNC functions relative to 0', achieved by diagonalization against computable approximations while preserving avoidance. Immunity characterizations are obtained via separate case analyses on pattern shapes (monochromatic, rainbow, mixed finite configurations) for preservation and non-preservation. These steps are self-contained mathematical arguments with no reductions to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations; the central claims rest on independent, explicitly described constructions rather than circular equivalences to inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only; the paper relies on standard background from computability theory and reverse mathematics (e.g., definitions of DNC functions, immunity, and Ramsey-like statements) without introducing new free parameters or invented entities visible in the summary.

axioms (1)
  • standard math Standard axioms of second-order arithmetic or recursive comprehension for defining computable colorings and homogeneous sets
    Invoked implicitly when stating existence of computable colorings and infinite sets in the abstract.

pith-pipeline@v0.9.0 · 5645 in / 1195 out tokens · 33413 ms · 2026-05-18T21:44:40.110116+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

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

  1. [1]

    On the logic al strengths of partial solutions to mathematical problems

    Laurent Bienvenu, Ludovic Patey, and Paul Shafer. On the logic al strengths of partial solutions to mathematical problems. Trans. London Math. Soc. , 4(1):30–71, 2017

    work page 2017

  2. [2]

    The strength of infinita ry Ramseyan principles can be accessed by their densities

    Andrey Bovykin and Andreas Weiermann. The strength of infinita ry Ramseyan principles can be accessed by their densities. Ann. Pure Appl. Logic, 168(9):1700–1709, 2017. 36

    work page 2017

  3. [3]

    The reverse mathematics of cac for trees

    Julien Cervelle, William Gaudelier, and Ludovic Patey. The reverse mathematics of cac for trees. The Journal of Symbolic Logic , pages 1–23, 2000

    work page 2000

  4. [4]

    Cholak, Carl G

    Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman. On the strength of ramsey’s theorem for pairs. The Journal of Symbolic Logic , 66(1):1–55, 2001

    work page 2001

  5. [5]

    C. T. Chong, Theodore A. Slaman, and Yue Yang. Π 1 1-conservation of combinatorial principles weaker than Ramsey’s theorem for pairs. Adv. Math., 230(3):1060–1077, 2012

    work page 2012

  6. [6]

    Relationships between computability-th eoretic properties of problems

    Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Lud ovic Patey, and Dan Turetsky. Relationships between computability-th eoretic properties of problems. J. Symb. Log. , 87(1):47–71, 2022

    work page 2022

  7. [7]

    Downey and Denis R

    Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010

    work page 2010

  8. [8]

    Dzhafarov and Carl Mummert

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

    work page 2022

  9. [9]

    Erd˝ os and L

    P. Erd˝ os and L. Moser. On the representation of directed gra phs as unions of orderings. Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., 9:125–132, 1964

    work page 1964

  10. [10]

    Reverse mathematics and a Ramsey-type K¨ on ig’s lemma

    Stephen Flood. Reverse mathematics and a Ramsey-type K¨ on ig’s lemma. J. Symbolic Logic , 77(4):1272–1280, 2012

    work page 2012

  11. [11]

    Noam Greenberg and Joseph S. Miller. Lowness for Kurtz rando mness. J. Symbolic Logic, 74(2):665–678, 2009

    work page 2009

  12. [12]

    Hirschfeldt, Carl G

    Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Bjø rn Kjos-Hans sen, Steffen Lempp, and Theodore A. Slaman. The strength of some combinator ial principles related to Ramsey’s theorem for pairs. In Computational prospects of infinity. Part II. Presented talks , volume 15 of Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. , pages 143–161. World Sci. Publ....

    work page 2008

  13. [13]

    Hirschfeldt and Richard A

    Denis R. Hirschfeldt and Richard A. Shore. Combinatorial princip les weaker than ramsey’s theorem for pairs. Journal of Symbolic Logic , 72:171 – 206, 2007

    work page 2007

  14. [14]

    COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC

    Jeffry Lynn Hirst. COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC . ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)–The Pennsylvania State University

    work page 1987

  15. [15]

    The reverse mathema tics of unbalanced colorings of pairs

    Quentin Le Hou´ erou and Ludovic Patey. The reverse mathema tics of unbalanced colorings of pairs. In preparation, 2025. 37

    work page 2025

  16. [16]

    Ramsey-like theorems for separable permutations, 2025

    Quentin Le Hou´ erou and Ludovic Patey. Ramsey-like theorems for separable permutations, 2025

    work page 2025

  17. [17]

    C. G. Jockusch, Jr., M. Lerman, R. I. Soare, and R. M. Solovay . Recursively enumerable sets modulo iterated jumps and extensions of Arslanov ’s completeness criterion. J. Symbolic Logic , 54(4):1288–1323, 1989

    work page 1989

  18. [18]

    Jockusch, Jr

    Carl G. Jockusch, Jr. Ramsey’s theorem and recursion theor y. J. Symbolic Logic, 37:268–280, 1972

    work page 1972

  19. [19]

    Jockusch, Jr

    Carl G. Jockusch, Jr. and Robert I. Soare. Π 0 1 classes and degrees of theories. Trans. Amer. Math. Soc. , 173:33–56, 1972

    work page 1972

  20. [20]

    Mushfeq Khan and Joseph S. Miller. Forcing with Bushy Trees. arXiv:1503.08870 [math] , March 2017. arXiv: 1503.08870

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  21. [21]

    Infinite subsets of random sets of inte gers

    Bjø rn Kjos-Hanssen. Infinite subsets of random sets of inte gers. Math. Res. Lett., 16(1):103–110, 2009

    work page 2009

  22. [22]

    K olmogorov complexity and the recursion theorem

    Bjø rn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan. K olmogorov complexity and the recursion theorem. Trans. Amer. Math. Soc. , 363(10):5465–5480, 2011

    work page 2011

  23. [23]

    In search of the first-order part of Ramsey’s theorem for pairs

    Leszek Aleksander Ko/suppress lodziejczyk and Keita Yokoyama. In search of the first-order part of Ramsey’s theorem for pairs. In Connecting with computability, volume 12813 of Lecture Notes in Comput. Sci. , pages 297–

    work page

  24. [24]

    Springer, Cham, [2021] ©2021

    work page 2021

  25. [25]

    Alexander P. Kreuzer. Primitive recursion and the chain anticha in principle. Notre Dame J. Form. Log. , 53(2):245–265, 2012

    work page 2012

  26. [26]

    Separatin g principles below Ramsey’s theorem for pairs

    Manuel Lerman, Reed Solomon, and Henry Towsner. Separatin g principles below Ramsey’s theorem for pairs. J. Math. Log. , 13(2):1350007, 44, 2013

    work page 2013

  27. [27]

    Rt22 does not imply wkl0

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

    work page 2012

  28. [28]

    The reverse mathematics of the thin s et and Erd˝ os-Moser theorems.J

    Lu Liu and Ludovic Patey. The reverse mathematics of the thin s et and Erd˝ os-Moser theorems.J. Symb. Log. , 87(1):313–346, 2022

    work page 2022

  29. [29]

    SRT2 2 does not imply RT2 2 in ω -models

    Benoit Monin and Ludovic Patey. SRT2 2 does not imply RT2 2 in ω -models. Adv. Math. , 389:Paper No. 107903, 32, 2021

    work page 2021

  30. [30]

    Open questions in reverse mathematics.Bull

    Antonio Montalb´ an. Open questions in reverse mathematics.Bull. Symbolic Logic, 17(3):431–454, 2011

    work page 2011

  31. [31]

    Lowness and avoidance

    Ludovic Patey. Lowness and avoidance. preparation. url: https://ludovicpatey.com/lowness-avoidance

    work page

  32. [32]

    The reverse mathematics of Ramsey-type theorems

    Ludovic Patey. The reverse mathematics of Ramsey-type theorems . PhD thesis, Universit´ e Paris Diderot (Paris 7) Sorbonne Paris Cit´ e, 2016. 38

    work page 2016

  33. [33]

    Iterative forcing and hyperimmunity in reverse mathematics

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

    work page 2017

  34. [34]

    Ramsey-like theorems and moduli of computatio n

    Ludovic Patey. Ramsey-like theorems and moduli of computatio n. The Journal of Symbolic Logic , pages 1–26, October 2020

    work page 2020

  35. [35]

    The proof-theoretic stre ngth of Ramsey’s theorem for pairs and two colors

    Ludovic Patey and Keita Yokoyama. The proof-theoretic stre ngth of Ramsey’s theorem for pairs and two colors. Adv. Math. , 330:1034–1070, 2018

    work page 2018

  36. [36]

    David Seetapun and Theodore A. Slaman. On the strength of Ra msey’s theorem. volume 36, pages 570–582. 1995. Special Issue: Models of arithmetic

    work page 1995

  37. [37]

    Stephen G. Simpson. Partial realizations of Hilbert’s Program. The Journal of Symbolic Logic , 53(2):349–363, 1988

    work page 1988

  38. [38]

    Stephen G. Simpson. Subsystems of Second Order Arithmetic . Perspectives in Logic. Cambridge University Press, 2 edition, 2009

    work page 2009

  39. [39]

    On \Pi 1ˆ1 conservativity for \Pi 2ˆ1 theories in second order arithmetic

    Keita Yokoyama. On \Pi 1ˆ1 conservativity for \Pi 2ˆ1 theories in second order arithmetic. In 10th Asian Logic Conference , pages 375–386. World Sci. Publ., Hackensack, NJ, 2010. 39

    work page 2010