The Weakness of Finding Descending Sequences in Ill-Founded Linear Orders

We prove that the Weihrauch degree of the problem of finding a bad sequence in a non-well quasi order ( \(\textsf{BS}\) ) is strictly above that of finding a descending sequence in an ill-founded linear order ( \(\textsf{DS}\) ). This corrects our mistaken claim in [8], which stated that they are Weihrauch equivalent. We prove that König’s lemma \(\textsf{KL}\) and the problem \(\textsf{wList}_{2^{\mathbb {N}},\le \omega }\) of enumerating a given non-empty countable closed subset of \(2^\mathbb {N}\) are not Weihrauch reducible to \(\textsf{DS}\) either, resolving two main open questions raised in [8].