Journal article 119 views 8 downloads

THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES

DAMIR D. DZHAFAROV, REED SOLOMON Orcid Logo, Manlio Valenti Orcid Logo

The Journal of Symbolic Logic, Pages: 1 - 23

Swansea University Author: Manlio Valenti Orcid Logo

  • 69108.VOR.pdf

    PDF | Version of Record

    © The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (CC BY).

    Download (344.94KB)

Check full text

DOI (Published version): 10.1017/jsl.2025.11

Abstract

We study versions of the tree pigeonhole principle, TT1, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether TT1 is Π11-conservative over the ordin...

Full description

Published in: The Journal of Symbolic Logic
ISSN: 0022-4812 1943-5886
Published: Cambridge University Press (CUP) 2025
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa69108
first_indexed 2025-03-17T09:54:46Z
last_indexed 2025-04-11T05:22:14Z
id cronfa69108
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2025-04-10T13:41:43.4593267</datestamp><bib-version>v2</bib-version><id>69108</id><entry>2025-03-17</entry><title>THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES</title><swanseaauthors><author><sid>133b5d626ca91216041d4556dc9251fb</sid><ORCID>0000-0003-0351-3058</ORCID><firstname>Manlio</firstname><surname>Valenti</surname><name>Manlio Valenti</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2025-03-17</date><deptcode>MACS</deptcode><abstract>We study versions of the tree pigeonhole principle, TT1, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether TT1 is &#x3A0;11-conservative over the ordinary pigeonhole principle, RT1. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike RT1, the problem TT1 is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of TT1.</abstract><type>Journal Article</type><journal>The Journal of Symbolic Logic</journal><volume>0</volume><journalNumber/><paginationStart>1</paginationStart><paginationEnd>23</paginationEnd><publisher>Cambridge University Press (CUP)</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>0022-4812</issnPrint><issnElectronic>1943-5886</issnElectronic><keywords>tree pigeonhole principle, Weihrauch reducibility, computable analysis</keywords><publishedDay>11</publishedDay><publishedMonth>2</publishedMonth><publishedYear>2025</publishedYear><publishedDate>2025-02-11</publishedDate><doi>10.1017/jsl.2025.11</doi><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm>SU Library paid the OA fee (TA Institutional Deal)</apcterm><funders>D.D.D. and D.R.S. were partially supported by a Focused Research Group grant from the National Science Foundation of the United States, DMS-1854355.</funders><projectreference/><lastEdited>2025-04-10T13:41:43.4593267</lastEdited><Created>2025-03-17T09:45:02.4290821</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>REED</firstname><surname>SOLOMON</surname><orcid>0000-0001-7574-204x</orcid><order>2</order></author><author><firstname>Manlio</firstname><surname>Valenti</surname><orcid>0000-0003-0351-3058</orcid><order>3</order></author></authors><documents><document><filename>69108__33923__92e9f9c33a9b456f8854d7810d3437f0.pdf</filename><originalFilename>69108.VOR.pdf</originalFilename><uploaded>2025-04-01T15:42:15.3012032</uploaded><type>Output</type><contentLength>353220</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>&#xA9; The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (CC BY).</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2025-04-10T13:41:43.4593267 v2 69108 2025-03-17 THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES 133b5d626ca91216041d4556dc9251fb 0000-0003-0351-3058 Manlio Valenti Manlio Valenti true false 2025-03-17 MACS We study versions of the tree pigeonhole principle, TT1, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether TT1 is Π11-conservative over the ordinary pigeonhole principle, RT1. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike RT1, the problem TT1 is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of TT1. Journal Article The Journal of Symbolic Logic 0 1 23 Cambridge University Press (CUP) 0022-4812 1943-5886 tree pigeonhole principle, Weihrauch reducibility, computable analysis 11 2 2025 2025-02-11 10.1017/jsl.2025.11 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University SU Library paid the OA fee (TA Institutional Deal) D.D.D. and D.R.S. were partially supported by a Focused Research Group grant from the National Science Foundation of the United States, DMS-1854355. 2025-04-10T13:41:43.4593267 2025-03-17T09:45:02.4290821 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science DAMIR D. DZHAFAROV 1 REED SOLOMON 0000-0001-7574-204x 2 Manlio Valenti 0000-0003-0351-3058 3 69108__33923__92e9f9c33a9b456f8854d7810d3437f0.pdf 69108.VOR.pdf 2025-04-01T15:42:15.3012032 Output 353220 application/pdf Version of Record true © The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (CC BY). true eng https://creativecommons.org/licenses/by/4.0/
title THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
spellingShingle THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
Manlio Valenti
title_short THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
title_full THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
title_fullStr THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
title_full_unstemmed THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
title_sort THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
author_id_str_mv 133b5d626ca91216041d4556dc9251fb
author_id_fullname_str_mv 133b5d626ca91216041d4556dc9251fb_***_Manlio Valenti
author Manlio Valenti
author2 DAMIR D. DZHAFAROV
REED SOLOMON
Manlio Valenti
format Journal article
container_title The Journal of Symbolic Logic
container_volume 0
container_start_page 1
publishDate 2025
institution Swansea University
issn 0022-4812
1943-5886
doi_str_mv 10.1017/jsl.2025.11
publisher Cambridge University Press (CUP)
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 versions of the tree pigeonhole principle, TT1, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether TT1 is Π11-conservative over the ordinary pigeonhole principle, RT1. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike RT1, the problem TT1 is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of TT1.
published_date 2025-02-11T11:35:10Z
_version_ 1831729428500054016
score 11.058631