Finite Combinatorics and Fragments of Arithmetic
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916805743738880 |
|---|---|
| author | Wang, Wei |
| author_facet | Wang, Wei |
| contents | In fragments of first order arithmetic, definable maps on finite domains could behave very differently from finite maps. Here combinatorial properties of $Σ_{n+1}$-definable maps on finite domains are compared in the absence of $BΣ_{n+1}$. It is shown that $\mathrm{GPHP}(Σ_{n+1})$ (the $Σ_{n+1}$-instance of Kaye's General Pigeonhole Principle) lies strictly between $\mathrm{CARD}(Σ_{n+1})$ and $\mathrm{WPHP}(Σ_{n+1})$ (Weak Pigeonhole Principle for $Σ_{n+1}$-maps), and also that $\mathrm{FRT}(Σ_{n+1})$ (Finite Ramsey's Theorem for $Σ_{n+1}$-maps) does not imply $\mathrm{WPHP}(Σ_{n+1})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17943 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finite Combinatorics and Fragments of Arithmetic Wang, Wei Logic 03F30, 03C20, 03H15 In fragments of first order arithmetic, definable maps on finite domains could behave very differently from finite maps. Here combinatorial properties of $Σ_{n+1}$-definable maps on finite domains are compared in the absence of $BΣ_{n+1}$. It is shown that $\mathrm{GPHP}(Σ_{n+1})$ (the $Σ_{n+1}$-instance of Kaye's General Pigeonhole Principle) lies strictly between $\mathrm{CARD}(Σ_{n+1})$ and $\mathrm{WPHP}(Σ_{n+1})$ (Weak Pigeonhole Principle for $Σ_{n+1}$-maps), and also that $\mathrm{FRT}(Σ_{n+1})$ (Finite Ramsey's Theorem for $Σ_{n+1}$-maps) does not imply $\mathrm{WPHP}(Σ_{n+1})$. |
| title | Finite Combinatorics and Fragments of Arithmetic |
| topic | Logic 03F30, 03C20, 03H15 |
| url | https://arxiv.org/abs/2506.17943 |