Finding descending sequences through ill-founded linear orders

Abstract

In this work we investigate the Weihrauch degree of the problem $\mathsf{DS}$ of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem $\mathsf{BS}$ of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf{DS}$, despite being hard to solve (it has computable inputs with no hyperarithmetic solution), is rather weak in terms of uniform computational strength. To make the latter precise, we introduce the notion of the deterministic part of a Weihrauch degree. We then generalize $\mathsf{DS}$ and $\mathsf{BS}$ by considering $\mathbf{\Gamma }$-presented orders, where $\mathbf{\Gamma }$ is a Borel pointclass or ${\mathbf{\Delta }}_1^1$, ${\mathbf{\Sigma }}_1^1$, ${\mathbf{\Pi }}_1^1$. We study the obtained $\mathsf{DS}$-hierarchy and $\mathsf{BS}$-hierarchy of problems in comparison with the (effective) Baire hierarchy and show that they do not collapse at any finite level.

arXiv commentAdded errata. The problems $\mathsf{DS}$ and $\mathsf{BS}$ are not Weihrauch-equivalent, and the separation has been proved in arXiv:2401.11807. Please check the errata for the full list of changes

References in corpus (11)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Probabilistic Computability and Choice
• A comparison of concepts from computable analysis and effective descriptive set theory
• On the logical strength of Nash-Williams' theorem on transfinite sequences
• Finite choice, convex choice and finding roots
• On the Uniform Computational Content of Ramsey's Theorem
• Completion of Choice
• Weihrauch goes Brouwerian
• The maximal linear extension theorem in second order arithmetic
• Enumeration degrees and non-metrizable topology

Cited by in corpus (4)

• Algebraic properties of the first-order part of a problem
• The tree pigeonhole principle in the Weihrauch degrees
• Indivisibility and uniform computational strength
• The Weihrauch lattice at the level of ${\mathbf{\Pi }}_1^1{-\mathsf{CA}}_0$: the Cantor-Bendixson theorem