No Cover Image

Journal article 204 views 61 downloads

Ramsey’s theorem and products in the Weihrauch degrees

Damir D. Dzhafarov, Jun Le Goh, Denis R. Hirschfeldt, Ludovic Patey, Arno Pauly Orcid Logo

Computability, Volume: 9, Issue: 2, Pages: 85 - 110

Swansea University Author: Arno Pauly Orcid Logo

Check full text

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...

Full description

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
Tags: Add Tag
No Tags, Be the first to tag this record!
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
Issue: 2
Start Page: 85
End Page: 110