论文标题
通过不基定的线性订单查找下降序列
Finding descending sequences through ill-founded linear orders
论文作者
论文摘要
在这项工作中，我们调查了问题的Weihrauch程度$ \ mathsf {ds} $通过给定的不良线性订单找到无限的下降序列，这是由问题$ \ m athssf {bs} $共享的，该序列通过给定的非电池quasi-porder找到了不好的序列。我们表明，尽管难以解决（它具有没有超氧化解决方案的可计算输入），但在均匀的计算强度方面，$ \ mathsf {ds} $却相当薄弱。为了使后者确切，我们介绍了Weihrauch学位的确定性部分的概念。 We then generalize $\mathsf{DS}$ and $\mathsf{BS}$ by considering $\boldsymbolΓ$-presented orders, where $\boldsymbolΓ$ is a Borel pointclass or $\boldsymbolΔ^1_1$, $\boldsymbolΣ^1_1$, $\boldsymbolΠ^1_1$.我们研究获得的$ \ Mathsf {ds} $ - 层次结构和$ \ Mathsf {bs} $ - 与（有效的）Baire层次结构相比，问题的层次结构，并表明它们不会在任何有限级别上崩溃。
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 $\boldsymbolΓ$-presented orders, where $\boldsymbolΓ$ is a Borel pointclass or $\boldsymbolΔ^1_1$, $\boldsymbolΣ^1_1$, $\boldsymbolΠ^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.
