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

CREATORQuentin Le Houérou, Ludovic Patey
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-11906

Browse the full library · About the Tower of Babel