Fraïssé's conjecture, partial impredicativity and well-ordering principles, part I
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917699430383616 |
|---|---|
| author | Freund, Anton |
| author_facet | Freund, Anton |
| contents | Fraïssé's conjecture (proved by Laver) is implied by the $Π^1_1$-comprehension axiom of reverse mathematics, as shown by Montalbán. The implication must be strict for reasons of quantifier complexity, but it seems that no better bound has been known. We locate such a bound in a hierarchy of Suzuki and Yokoyama, which extends Towsner's framework of partial impredicativity. Specifically, we show that Fraïssé's conjecture is implied by a principle of pseudo $Π^1_1$-comprehension. As part of the proof, we introduce a cofinite version of the $Δ^0_2$-Ramsey theorem, which may be of independent interest. We also relate pseudo $Π^1_1$-comprehension to principles of pseudo $β$-model reflection (due to Suzuki and Yokoyama) and reflection for $ω$-models of transfinite induction (studied by Rathjen and Valencia-Vizcaíno). In a forthcoming companion paper, we characterize pseudo $Π^1_1$-comprehension by a well-ordering principle, to get a transparent combinatorial bound for the strength of Fraïssé's conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13485 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fraïssé's conjecture, partial impredicativity and well-ordering principles, part I Freund, Anton Logic 6A07, 03B30, 03F35 Fraïssé's conjecture (proved by Laver) is implied by the $Π^1_1$-comprehension axiom of reverse mathematics, as shown by Montalbán. The implication must be strict for reasons of quantifier complexity, but it seems that no better bound has been known. We locate such a bound in a hierarchy of Suzuki and Yokoyama, which extends Towsner's framework of partial impredicativity. Specifically, we show that Fraïssé's conjecture is implied by a principle of pseudo $Π^1_1$-comprehension. As part of the proof, we introduce a cofinite version of the $Δ^0_2$-Ramsey theorem, which may be of independent interest. We also relate pseudo $Π^1_1$-comprehension to principles of pseudo $β$-model reflection (due to Suzuki and Yokoyama) and reflection for $ω$-models of transfinite induction (studied by Rathjen and Valencia-Vizcaíno). In a forthcoming companion paper, we characterize pseudo $Π^1_1$-comprehension by a well-ordering principle, to get a transparent combinatorial bound for the strength of Fraïssé's conjecture. |
| title | Fraïssé's conjecture, partial impredicativity and well-ordering principles, part I |
| topic | Logic 6A07, 03B30, 03F35 |
| url | https://arxiv.org/abs/2406.13485 |