FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
复制标题
通过无根据的线性顺序查找降序序列
DOI：
10.1017/jsl.2021.15
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Manlio Valenti
中科院分区：
文献类型：
--
作者：
Jun Le Goh;A. Pauly;Manlio Valenti
Abstract In this work we investigate the Weihrauch degree of the problem Decreasing Sequence (
$\mathsf {DS}$
) of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence (
$\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 {\Gamma }$
-presented orders, where
$\boldsymbol {\Gamma }$
is a Borel pointclass or
$\boldsymbol {\Delta }^1_1$
,
$\boldsymbol {\Sigma }^1_1$
,
$\boldsymbol {\Pi }^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.
Abstract In this work we investigate the Weihrauch degree of the problem Decreasing Sequence (
$\mathsf {DS}$
) of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence (
$\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 {\Gamma }$
-presented orders, where
$\boldsymbol {\Gamma }$
is a Borel pointclass or
$\boldsymbol {\Delta }^1_1$
,
$\boldsymbol {\Sigma }^1_1$
,
$\boldsymbol {\Pi }^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.
某些三阶原理的 Weihrauch 可还原性
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
Hiroki Tsutsui;Naoki Yanagisawa;Yuu Sawai;Shuka Ikematsu;Hideyuki Arata;Tetsuya Higashiyama;Michitaka Notaguchi;浦 鐘月 清水 優樹;Takayuki Kihara
通讯作者：
Takayuki Kihara