Largeness notions and polytime translation for ∀ Σ 3 0 \forall\Sigma^{0}_{3} -consequences of 𝖱𝖳 2 2 \mathsf{RT}^{2}_{2}
Quentin Le Houérou, Ludovic Patey · 2026
Read Largeness notions and polytime translation for ∀ Σ 3 0 \forall\Sigma^{0}_{3} -consequences of 𝖱𝖳 2 2 \mathsf{RT}^{2}_{2} by Quentin Le Houérou, Ludovic Patey (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-11906.txt.
Description
Proving that one logical theory conservatively extends another often hinges on largeness notions that measure how much combinatorial structure a set contains. Quentin Le Houérou and one co-author introduce a variant of parameterized largeness and obtain polynomial bounds, using a tree partition theorem based on Milliken tree theorem. Through forcing interpretation, any proof of a universal statement in the stronger theory can be translated into a proof in the weaker theory. The cost is only a polynomial increase in size.
The result concerns Ramsey theory for pairs and weak König lemma, theories whose relationship has been studied through conservation results. The polynomial size bound turns a qualitative conservation claim into a quantitative one: translations exist and they do not blow up proofs uncontrollably. For reverse mathematics, that precision matters, since the cost of moving between theories is itself informative.
Catalog record
| CREATOR | Quentin Le Houérou, Ludovic Patey |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-11906