Free sets, thin sets and rainbows for barriers
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910191890464768 |
|---|---|
| author | Carlucci, Lorenzo Gjetaj, Oriola |
| author_facet | Carlucci, Lorenzo Gjetaj, Oriola |
| contents | We formulate and prove the generalizations of Friedman's free set and thin set theorems and of the rainbow Ramsey theorem to colorings of barriers. We analyze the strength of these theorems from the point of view of computability theory proving some upper and lower bounds on the complexity of solutions for computable instances and some uniform computable reductions. We obtain as corollaries some proof-theoretical results on the logical strength of the theorems, in the spirit of reverse mathematics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03523 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Free sets, thin sets and rainbows for barriers Carlucci, Lorenzo Gjetaj, Oriola Logic We formulate and prove the generalizations of Friedman's free set and thin set theorems and of the rainbow Ramsey theorem to colorings of barriers. We analyze the strength of these theorems from the point of view of computability theory proving some upper and lower bounds on the complexity of solutions for computable instances and some uniform computable reductions. We obtain as corollaries some proof-theoretical results on the logical strength of the theorems, in the spirit of reverse mathematics. |
| title | Free sets, thin sets and rainbows for barriers |
| topic | Logic |
| url | https://arxiv.org/abs/2605.03523 |