No Cover Image

Journal article 205 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!
first_indexed 2020-05-15T13:07:22Z
last_indexed 2020-07-07T13:17:01Z
id cronfa53985
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2020-07-07T12:34:25.0568579</datestamp><bib-version>v2</bib-version><id>53985</id><entry>2020-04-18</entry><title>Ramsey&#x2019;s theorem and products in the Weihrauch degrees</title><swanseaauthors><author><sid>17a56a78ec04e7fc47b7fe18394d7245</sid><ORCID>0000-0002-0173-3295</ORCID><firstname>Arno</firstname><surname>Pauly</surname><name>Arno Pauly</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2020-04-18</date><deptcode>SCS</deptcode><abstract>We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey&#x2019;s theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey&#x2019;s theorem for pairs (RT22) is Weihrauch-incomparable to the parallel product of the stable Ramsey&#x2019;s theorem for pairs and the cohesive principle (SRT22&#xD7;COH).</abstract><type>Journal Article</type><journal>Computability</journal><volume>9</volume><journalNumber>2</journalNumber><paginationStart>85</paginationStart><paginationEnd>110</paginationEnd><publisher>IOS Press</publisher><issnPrint>2211-3568</issnPrint><issnElectronic>2211-3576</issnElectronic><keywords>Computable combinatorics, Ramsey theory, computability theory, reverse mathematics</keywords><publishedDay>13</publishedDay><publishedMonth>5</publishedMonth><publishedYear>2020</publishedYear><publishedDate>2020-05-13</publishedDate><doi>10.3233/com-180203</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2020-07-07T12:34:25.0568579</lastEdited><Created>2020-04-18T18:48:54.8790381</Created><authors><author><firstname>Damir D.</firstname><surname>Dzhafarov</surname><order>1</order></author><author><firstname>Jun Le</firstname><surname>Goh</surname><order>2</order></author><author><firstname>Denis R.</firstname><surname>Hirschfeldt</surname><order>3</order></author><author><firstname>Ludovic</firstname><surname>Patey</surname><order>4</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>5</order></author></authors><documents><document><filename>53985__17093__46c35448f6164a72ad603fffb6c282b2.pdf</filename><originalFilename>Products_420.pdf</originalFilename><uploaded>2020-04-18T18:50:39.0486068</uploaded><type>Output</type><contentLength>888875</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2020-07-07T12:34:25.0568579 v2 53985 2020-04-18 Ramsey’s theorem and products in the Weihrauch degrees 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2020-04-18 SCS 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). Journal Article Computability 9 2 85 110 IOS Press 2211-3568 2211-3576 Computable combinatorics, Ramsey theory, computability theory, reverse mathematics 13 5 2020 2020-05-13 10.3233/com-180203 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2020-07-07T12:34:25.0568579 2020-04-18T18:48:54.8790381 Damir D. Dzhafarov 1 Jun Le Goh 2 Denis R. Hirschfeldt 3 Ludovic Patey 4 Arno Pauly 0000-0002-0173-3295 5 53985__17093__46c35448f6164a72ad603fffb6c282b2.pdf Products_420.pdf 2020-04-18T18:50:39.0486068 Output 888875 application/pdf Accepted Manuscript true true eng
title Ramsey’s theorem and products in the Weihrauch degrees
spellingShingle Ramsey’s theorem and products in the Weihrauch degrees
Arno Pauly
title_short Ramsey’s theorem and products in the Weihrauch degrees
title_full Ramsey’s theorem and products in the Weihrauch degrees
title_fullStr Ramsey’s theorem and products in the Weihrauch degrees
title_full_unstemmed Ramsey’s theorem and products in the Weihrauch degrees
title_sort Ramsey’s theorem and products in the Weihrauch degrees
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Damir D. Dzhafarov
Jun Le Goh
Denis R. Hirschfeldt
Ludovic Patey
Arno Pauly
format Journal article
container_title Computability
container_volume 9
container_issue 2
container_start_page 85
publishDate 2020
institution Swansea University
issn 2211-3568
2211-3576
doi_str_mv 10.3233/com-180203
publisher IOS Press
document_store_str 1
active_str 0
description 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).
published_date 2020-05-13T04:25:48Z
_version_ 1733857691090026496
score 10.872848