No Cover Image

Journal article 45 views 4 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

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