Ramsey’s theorem and products in the Weihrauch degrees

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

doi:10.3233/com-180203

Journal article 802 views 163 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)

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	2023-01-11T14:31:49Z
id	cronfa53985
recordtype	SURis
fullrecord	<?xml version="1.0"?><rfc1807><datestamp>2022-12-05T12:42:32.0959742</datestamp><bib-version>v2</bib-version><id>53985</id><entry>2020-04-18</entry><title>Ramsey’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’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).</abstract><type>Journal Article</type><journal>Computability</journal><volume>9</volume><journalNumber>2</journalNumber><paginationStart>85</paginationStart><paginationEnd>110</paginationEnd><publisher>IOS Press</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><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/><funders/><projectreference/><lastEdited>2022-12-05T12:42:32.0959742</lastEdited><Created>2020-04-18T18:48:54.8790381</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><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	2022-12-05T12:42:32.0959742 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 2022-12-05T12:42:32.0959742 2020-04-18T18:48:54.8790381 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science 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
college_str	Faculty of Science and Engineering
hierarchytype
hierarchy_top_id	facultyofscienceandengineering
hierarchy_top_title	Faculty of Science and Engineering
hierarchy_parent_id	facultyofscienceandengineering
hierarchy_parent_title	Faculty of Science and Engineering
department_str	School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
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:07:15Z
_version_	1763753523351126016
score	11.016235

Ramsey’s theorem and products in the Weihrauch degrees

Similar Items