Journal article 1370 views 319 downloads
Ramsey’s theorem and products in the Weihrauch degrees
Damir D. Dzhafarov,
Jun Le Goh,
Denis R. Hirschfeldt,
Ludovic Patey,
Arno Pauly 
Computability, Volume: 9, Issue: 2, Pages: 85 - 110
Swansea University Author:
Arno Pauly
-
PDF | Accepted Manuscript
Download (868.04KB)
DOI (Published version): 10.3233/com-180203
Abstract
We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey’s theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey’s theorem for pairs (RT22) is Weihrauch-incomparable to the parallel product...
| Published in: | Computability |
|---|---|
| ISSN: | 2211-3568 2211-3576 |
| Published: |
IOS Press
2020
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa53985 |
| Abstract: |
We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey’s theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey’s theorem for pairs (RT22) is Weihrauch-incomparable to the parallel product of the stable Ramsey’s theorem for pairs and the cohesive principle (SRT22×COH). |
|---|---|
| Keywords: |
Computable combinatorics, Ramsey theory, computability theory, reverse mathematics |
| College: |
Faculty of Science and Engineering |
| Issue: |
2 |
| Start Page: |
85 |
| End Page: |
110 |