"Weak yet strong" restrictions of Hindman's Finite Sums Theorem
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2016
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916084530020352 |
|---|---|
| author | Carlucci, Lorenzo |
| author_facet | Carlucci, Lorenzo |
| contents | We present a natural restriction of Hindman's Finite Sums Theorem that admits a simple combinatorial proof (one that does not also prove the full Finite Sums Theorem) and low computability-theoretic and proof-theoretic upper bounds, yet implies the existence of the Turing Jump, thus realizing the only known lower bound for the full Finite Sums Theorem. This is the first example of this kind. In fact we isolate a rich family of similar restrictions of Hindman's Theorem with analogous properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1610_07500 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | "Weak yet strong" restrictions of Hindman's Finite Sums Theorem Carlucci, Lorenzo Logic Combinatorics We present a natural restriction of Hindman's Finite Sums Theorem that admits a simple combinatorial proof (one that does not also prove the full Finite Sums Theorem) and low computability-theoretic and proof-theoretic upper bounds, yet implies the existence of the Turing Jump, thus realizing the only known lower bound for the full Finite Sums Theorem. This is the first example of this kind. In fact we isolate a rich family of similar restrictions of Hindman's Theorem with analogous properties. |
| title | "Weak yet strong" restrictions of Hindman's Finite Sums Theorem |
| topic | Logic Combinatorics |
| url | https://arxiv.org/abs/1610.07500 |