No Cover Image

Journal article 181 views 19 downloads

THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS

JUN LE GOH Orcid Logo, Arno Pauly Orcid Logo, Manlio Valenti Orcid Logo

The Journal of Symbolic Logic, Pages: 1 - 35

Swansea University Authors: Arno Pauly Orcid Logo, Manlio Valenti Orcid Logo

  • 70799.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.

    Download (528.69KB)

Check full text

DOI (Published version): 10.1017/jsl.2025.10160

Abstract

We explore the Weihrauch degree of the problems “find a bad sequence in a non-well quasi order” (BS) and “find a descending sequence in an ill-founded linear order” (DS). We prove that DS is strictly Weihrauch reducible to BS, correcting our mistaken claim in [18]. This is done by separating their r...

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/cronfa70799
first_indexed 2025-10-31T10:43:48Z
last_indexed 2026-01-21T05:27:48Z
id cronfa70799
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2026-01-20T13:33:01.9933227</datestamp><bib-version>v2</bib-version><id>70799</id><entry>2025-10-31</entry><title>THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS</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><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-10-31</date><deptcode>MACS</deptcode><abstract>We explore the Weihrauch degree of the problems &#x201C;find a bad sequence in a non-well quasi order&#x201D; (BS) and &#x201C;find a descending sequence in an ill-founded linear order&#x201D; (DS). We prove that DS is strictly Weihrauch reducible to BS, correcting our mistaken claim in [18]. This is done by separating their respective first-order parts. On the other hand, we show that BS and DS have the same finitary and deterministic parts, confirming that BS and DS have very similar uniform computational strength. We prove that K&#xF6;nig&#x2019;s lemma KL and the problem wList2N,&#x2264;&#x3C9; of enumerating a given non-empty countable closed subset of 2N are not Weihrauch reducible to DS or BS, resolving two main open questions raised in [18]. We also answer the question, raised in [12], on the existence of a &#x201C;parallel quotient&#x201D; operator, and study the behavior of BS and DS under the quotient with some known problems.</abstract><type>Journal Article</type><journal>The Journal of Symbolic Logic</journal><volume>0</volume><journalNumber/><paginationStart>1</paginationStart><paginationEnd>35</paginationEnd><publisher>Cambridge University Press (CUP)</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>0022-4812</issnPrint><issnElectronic>1943-5886</issnElectronic><keywords>Weihrauch reducibility, linear orders, quasi-orders</keywords><publishedDay>29</publishedDay><publishedMonth>10</publishedMonth><publishedYear>2025</publishedYear><publishedDate>2025-10-29</publishedDate><doi>10.1017/jsl.2025.10160</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>Swansea University</funders><projectreference/><lastEdited>2026-01-20T13:33:01.9933227</lastEdited><Created>2025-10-31T10:42:05.4855300</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>JUN LE</firstname><surname>GOH</surname><orcid>0000-0002-0487-7358</orcid><order>1</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</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>70799__35852__e1c18806b327407c8ddbf3408a0bcd2b.pdf</filename><originalFilename>70799.VOR.pdf</originalFilename><uploaded>2025-12-18T15:36:09.6066770</uploaded><type>Output</type><contentLength>541377</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.</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2026-01-20T13:33:01.9933227 v2 70799 2025-10-31 THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 133b5d626ca91216041d4556dc9251fb 0000-0003-0351-3058 Manlio Valenti Manlio Valenti true false 2025-10-31 MACS We explore the Weihrauch degree of the problems “find a bad sequence in a non-well quasi order” (BS) and “find a descending sequence in an ill-founded linear order” (DS). We prove that DS is strictly Weihrauch reducible to BS, correcting our mistaken claim in [18]. This is done by separating their respective first-order parts. On the other hand, we show that BS and DS have the same finitary and deterministic parts, confirming that BS and DS have very similar uniform computational strength. We prove that König’s lemma KL and the problem wList2N,≤ω of enumerating a given non-empty countable closed subset of 2N are not Weihrauch reducible to DS or BS, resolving two main open questions raised in [18]. We also answer the question, raised in [12], on the existence of a “parallel quotient” operator, and study the behavior of BS and DS under the quotient with some known problems. Journal Article The Journal of Symbolic Logic 0 1 35 Cambridge University Press (CUP) 0022-4812 1943-5886 Weihrauch reducibility, linear orders, quasi-orders 29 10 2025 2025-10-29 10.1017/jsl.2025.10160 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University SU Library paid the OA fee (TA Institutional Deal) Swansea University 2026-01-20T13:33:01.9933227 2025-10-31T10:42:05.4855300 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science JUN LE GOH 0000-0002-0487-7358 1 Arno Pauly 0000-0002-0173-3295 2 Manlio Valenti 0000-0003-0351-3058 3 70799__35852__e1c18806b327407c8ddbf3408a0bcd2b.pdf 70799.VOR.pdf 2025-12-18T15:36:09.6066770 Output 541377 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. true eng https://creativecommons.org/licenses/by/4.0/
title THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS
spellingShingle THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS
Arno Pauly
Manlio Valenti
title_short THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS
title_full THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS
title_fullStr THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS
title_full_unstemmed THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS
title_sort THE WEAKNESS OF FINDING DESCENDING SEQUENCES IN ILL-FOUNDED LINEAR ORDERS
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
133b5d626ca91216041d4556dc9251fb
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
133b5d626ca91216041d4556dc9251fb_***_Manlio Valenti
author Arno Pauly
Manlio Valenti
author2 JUN LE GOH
Arno Pauly
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.10160
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 explore the Weihrauch degree of the problems “find a bad sequence in a non-well quasi order” (BS) and “find a descending sequence in an ill-founded linear order” (DS). We prove that DS is strictly Weihrauch reducible to BS, correcting our mistaken claim in [18]. This is done by separating their respective first-order parts. On the other hand, we show that BS and DS have the same finitary and deterministic parts, confirming that BS and DS have very similar uniform computational strength. We prove that König’s lemma KL and the problem wList2N,≤ω of enumerating a given non-empty countable closed subset of 2N are not Weihrauch reducible to DS or BS, resolving two main open questions raised in [18]. We also answer the question, raised in [12], on the existence of a “parallel quotient” operator, and study the behavior of BS and DS under the quotient with some known problems.
published_date 2025-10-29T05:33:38Z
_version_ 1856987010834628608
score 11.096295

Similar Items