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

Abstract We explore the Weihrauch degree of the problems “find a bad sequence in a non-well quasi order” ( $\mathsf {BS}$ ) and “find a descending sequence in an ill-founded linear order” ( $\mathsf {DS}$ ). We prove that $\mathsf {DS}$ is strictly Weihrauch reducible to $\mathsf {BS}$ , correcting our mistaken claim in [18]. This is done by separating their respective first-order parts. On the other hand, we show that $\mathsf {BS}$ and $\mathsf {DS}$ have the same finitary and deterministic parts, confirming that $\mathsf {BS}$ and $\mathsf {DS}$ have very similar uniform computational strength. We prove that König’s lemma $\mathsf {KL}$ and the problem $\mathsf {wList}_{{2^{\mathbb {N}}},\leq \omega }$ of enumerating a given non-empty countable closed subset of ${2^{\mathbb {N}}}$ are not Weihrauch reducible to $\mathsf {DS}$ or $\mathsf {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 $\mathsf {BS}$ and $\mathsf {DS}$ under the quotient with some known problems.