Models of Bounded Arithmetic and variants of Pigeonhole Principle
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913256864481280 |
|---|---|
| author | Narusevych, Mykyta |
| author_facet | Narusevych, Mykyta |
| contents | We give elementary proof that theory $T^1_2(R)$ augmented by the weak pigeonhole principle for all $Δ^b_1(R)$-definable relations does not prove the bijective pigeonhole principle for $R$. This can be derived from known more general results but our proof yields a model of $T^1_2(R)$ in which $ontoPHP^{n+1}_n(R)$ fails for some nonstandard element $n$ while $PHP^{m+1}_m$ holds for all $Δ^b_1(R)$-definable relations and all $m \leq n^{1-ε}$, where $ε> 0$ is a fixed standard rational parameter. This can be seen as a step towards solving an open question posed by M. Ajtai. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_14713 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Models of Bounded Arithmetic and variants of Pigeonhole Principle Narusevych, Mykyta Logic We give elementary proof that theory $T^1_2(R)$ augmented by the weak pigeonhole principle for all $Δ^b_1(R)$-definable relations does not prove the bijective pigeonhole principle for $R$. This can be derived from known more general results but our proof yields a model of $T^1_2(R)$ in which $ontoPHP^{n+1}_n(R)$ fails for some nonstandard element $n$ while $PHP^{m+1}_m$ holds for all $Δ^b_1(R)$-definable relations and all $m \leq n^{1-ε}$, where $ε> 0$ is a fixed standard rational parameter. This can be seen as a step towards solving an open question posed by M. Ajtai. |
| title | Models of Bounded Arithmetic and variants of Pigeonhole Principle |
| topic | Logic |
| url | https://arxiv.org/abs/2208.14713 |