Indivisibility and uniform computational strength
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913896891154432 |
|---|---|
| author | Gill, Kenneth |
| author_facet | Gill, Kenneth |
| contents | A countable structure is indivisible if for every coloring with finite range there is a monochromatic isomorphic subcopy of the structure. Each indivisible structure naturally corresponds to an indivisibility problem which outputs such a subcopy given a presentation and coloring. We investigate the Weihrauch complexity of the indivisibility problems for two structures: the rational numbers $\mathbb{Q}$ as a linear order, and the equivalence relation $\mathscr{E}$ with countably many equivalence classes each having countably many members. We separate the Weihrauch degrees of both corresponding indivisibility problems from several benchmarks, showing in particular that the indivisibility problem for $\mathbb{Q}$ cannot solve the problem of finding a monochromatic rational interval given a coloring for which there is one; and that the Weihrauch degree of the indivisibility problem for $\mathscr{E}$ is strictly between those of $\mathsf{RT}^2$ and $\mathsf{SRT}^2$, two widely studied variants of Ramsey's theorem for pairs whose reverse-mathematical separation was open until recently. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_03919 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Indivisibility and uniform computational strength Gill, Kenneth Logic Logic in Computer Science Combinatorics A countable structure is indivisible if for every coloring with finite range there is a monochromatic isomorphic subcopy of the structure. Each indivisible structure naturally corresponds to an indivisibility problem which outputs such a subcopy given a presentation and coloring. We investigate the Weihrauch complexity of the indivisibility problems for two structures: the rational numbers $\mathbb{Q}$ as a linear order, and the equivalence relation $\mathscr{E}$ with countably many equivalence classes each having countably many members. We separate the Weihrauch degrees of both corresponding indivisibility problems from several benchmarks, showing in particular that the indivisibility problem for $\mathbb{Q}$ cannot solve the problem of finding a monochromatic rational interval given a coloring for which there is one; and that the Weihrauch degree of the indivisibility problem for $\mathscr{E}$ is strictly between those of $\mathsf{RT}^2$ and $\mathsf{SRT}^2$, two widely studied variants of Ramsey's theorem for pairs whose reverse-mathematical separation was open until recently. |
| title | Indivisibility and uniform computational strength |
| topic | Logic Logic in Computer Science Combinatorics |
| url | https://arxiv.org/abs/2312.03919 |