Weihrauch reducibility between Ramsey-type theorems and well-ordering principles at the level of Σ⁰₂-induction: A pilot study

2025/11/26 by Lorenzo Carlucci, Carlucci, Lorenzo, Giordano Celli +1
Computer Science · Mathematics · #03B30 #03D30 #05C55 #06A75 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Mathematical and Theoretical Analysis

paper · pdf · doi:10.48550/arxiv.2511.21481

openalex publication_date 2025/11/26 · openalex created_date 2025/11/28 · openalex updated_date 2026/07/28

Abstract

We study the relations under Weihrauch reducibility of the well-ordering preservation principle for the operator X ↦ X^ω and the Ordered Ramsey Theorem. Both principles are known to be equivalent to Σ⁰₂-induction in Reverse Mathematics. We show that the Ordered Ramsey Theorem is Weihrauch-equivalent to the parallel product of the well-ordering preservation principle for the operator X ↦ X^ω and the Eventually Constant Tail principle. By previous work from Pauly, Pradic and Soldà, the Ordered Ramsey Theorem is known to be Weihrauch-equivalent to the parallel product of the Eventually Constant Tail principle and the parallelization of the jump of the Limited Principle of Omniscience. We show that the latter pinciple and the well-ordering preservation principle for X ↦ X^ω are Weihrauch-incomparable.

Citations

• Reductions of well-ordering principles to combinatorial theorems
• On the Weihrauch degree of the additive Ramsey theorem
• Combinatorial principles equivalent to weak induction

Related

• Reductions of well-ordering principles to combinatorial theorems
• Ramsey's theorem and products in the Weihrauch degrees
• Well-Ordering Principles in Proof Theory and Reverse Mathematics
• Higman's lemma is stronger for better quasi orders
• Well ordering principles and bar induction