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
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 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.
Keywords: Weihrauch reducibility, linear orders, quasi-orders
College: Faculty of Science and Engineering
Funders: Swansea University
Start Page: 1
End Page: 35

Similar Items