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

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 wList 2 N , of enumerating a given non-empty countable closed subset of 2 N 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.1.Introduction.Linear and quasi-orders are ubiquitous structures that play an important role in all areas of mathematics.Computability theory has been successfully applied to highlight the difference between classical and effective properties of orders.A well-known example is that the simple fact that every infinite linear order contains an infinite ascending sequence or an infinite descending sequence is not computably true.A more extreme example is the existence of computable ill-founded linear orders with no hyperarithmetic descending sequence (see, e.g., [26, Lemma III.2.1]).These orders have been extensively used and studied in reverse mathematics (under the name of pseudo-well-orders) [27].We refer the reader to [11] for a more comprehensive presentation of computability-theoretical results on linear and partial orders.The natural generalization of well-orders in the context of quasi-orders is the notion of well quasi-orders: formally, a quasi-order (Q, ) is called well quasi-order (abbreviated wqo) if, for every infinite sequence (q n ) nN of elements of Q, there are i, j with i < j such that q i Q q j .This can be restated by saying that a quasi-order is a wqo if it contains no infinite bad sequences, where a (possibly finite) sequence (q n ) n is called bad if q i Q q j for every i < j.Equivalently, wqos can be defined as quasi-orders that contain no infinite descending sequence and no infinite antichain.There is an extensive literature on the theory of wqos.For an overview, we refer the reader to [22].