Arno Pauly

The weakness of finding descending sequences in ill-founded linear orders

2024 · arXiv (Cornell University)

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 …