New bounds on the strength of some restrictions of Hindman's Theorem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2017
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910290185027584 |
|---|---|
| author | Carlucci, Lorenzo Kołodziejczyk, Leszek Aleksander Lepore, Francesco Zdanowski, Konrad |
| author_facet | Carlucci, Lorenzo Kołodziejczyk, Leszek Aleksander Lepore, Francesco Zdanowski, Konrad |
| contents | We prove upper and lower bounds on the effective content and logical strength for a variety of natural restrictions of Hindman's Finite Sums Theorem. For example, we show that Hindman's Theorem for sums of length at most 2 and 4 colors implies $\mathsf{ACA}_0$. An emerging {\em leitmotiv} is that the known lower bounds for Hindman's Theorem and for its restriction to sums of at most 2 elements are already valid for a number of restricted versions which have simple proofs and better computability- and proof-theoretic upper bounds than the known upper bound for the full version of the theorem. We highlight the role of a sparsity-like condition on the solution set, which we call apartness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1701_06095 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | New bounds on the strength of some restrictions of Hindman's Theorem Carlucci, Lorenzo Kołodziejczyk, Leszek Aleksander Lepore, Francesco Zdanowski, Konrad Logic Combinatorics We prove upper and lower bounds on the effective content and logical strength for a variety of natural restrictions of Hindman's Finite Sums Theorem. For example, we show that Hindman's Theorem for sums of length at most 2 and 4 colors implies $\mathsf{ACA}_0$. An emerging {\em leitmotiv} is that the known lower bounds for Hindman's Theorem and for its restriction to sums of at most 2 elements are already valid for a number of restricted versions which have simple proofs and better computability- and proof-theoretic upper bounds than the known upper bound for the full version of the theorem. We highlight the role of a sparsity-like condition on the solution set, which we call apartness. |
| title | New bounds on the strength of some restrictions of Hindman's Theorem |
| topic | Logic Combinatorics |
| url | https://arxiv.org/abs/1701.06095 |