Journal article 119 views 8 downloads
THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES
The Journal of Symbolic Logic, Pages: 1 - 23
Swansea University Author:
Manlio Valenti
-
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)
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...
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 Π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>© 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 |