Weihrauch reducibility between Ramsey-type theorems and well-ordering principles at the level of $Σ^0_2$-induction: A pilot study
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915639365468160 |
|---|---|
| author | Carlucci, Lorenzo Celli, Giordano |
| author_facet | Carlucci, Lorenzo Celli, Giordano |
| contents | We study the relations under Weihrauch reducibility of the well-ordering preservation principle for the operator $X \mapsto X^ω$ and the Ordered Ramsey Theorem. Both principles are known to be equivalent to $Σ^0_2$-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 \mapsto 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 \mapsto X^ω$ are Weihrauch-incomparable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21481 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weihrauch reducibility between Ramsey-type theorems and well-ordering principles at the level of $Σ^0_2$-induction: A pilot study Carlucci, Lorenzo Celli, Giordano Logic Combinatorics 03B30, 03D30, 05C55, 06A75 We study the relations under Weihrauch reducibility of the well-ordering preservation principle for the operator $X \mapsto X^ω$ and the Ordered Ramsey Theorem. Both principles are known to be equivalent to $Σ^0_2$-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 \mapsto 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 \mapsto X^ω$ are Weihrauch-incomparable. |
| title | Weihrauch reducibility between Ramsey-type theorems and well-ordering principles at the level of $Σ^0_2$-induction: A pilot study |
| topic | Logic Combinatorics 03B30, 03D30, 05C55, 06A75 |
| url | https://arxiv.org/abs/2511.21481 |