An independence of the MIN principle from the PHP principle
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916014242922496 |
|---|---|
| author | Narusevych, Mykyta |
| author_facet | Narusevych, Mykyta |
| contents | The minimization principle $\textsf{MIN}(\triangleleft)$ studied in bounded arithmetic says that a strict linear ordering $\triangleleft$ on any finite interval $[0,\dots,n)$ has the minimal element. We shall prove that bounded arithmetic theory $\textsf{T}^1_2(\triangleleft)$ augmented by instances of the pigeonhole principle for all $Δ^b_1(\triangleleft)$ formulas does not prove $\textsf{MIN}(\triangleleft)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_14930 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An independence of the MIN principle from the PHP principle Narusevych, Mykyta Logic Logic in Computer Science The minimization principle $\textsf{MIN}(\triangleleft)$ studied in bounded arithmetic says that a strict linear ordering $\triangleleft$ on any finite interval $[0,\dots,n)$ has the minimal element. We shall prove that bounded arithmetic theory $\textsf{T}^1_2(\triangleleft)$ augmented by instances of the pigeonhole principle for all $Δ^b_1(\triangleleft)$ formulas does not prove $\textsf{MIN}(\triangleleft)$. |
| title | An independence of the MIN principle from the PHP principle |
| topic | Logic Logic in Computer Science |
| url | https://arxiv.org/abs/2406.14930 |