Inside the Muchnik degrees, Part II : The degree structures induced by tha arithmatiral hiararchy of countably continuous functions
Inside the Muchnik degrees, Part II : The degree structures induced by tha arithmatiral hiararchy of countably continuous functions
复制标题
穆奇尼克度数内部，第二部分：由可数连续函数的算术层次结构引起的度数结构
DOI：
10.1016/j.apal.2014.03.001
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
Kojiro Higuchi and Takayuki Kihara
中科院分区：
文献类型：
--
作者：
Itagaki;K.;Shibuya;T.;Tojo;M.;Endo;R.;Kitaya;Y.;Kojiro Higuchi and Takayuki Kihara
众所周知，康托空间的任何非平凡 Π 1 0 子集的 Muchnik 度内都存在无限多个 Medvedev 度。我们揭示了这些 Muchnik 学位中与可学习性和分段可计算性相关的精细结构。对于康托空间的非空 Π 1 0 子集，我们证明存在包含无限多个有限-(Π 1 0) 2-分段度的有限-Δ 2 0-分段度，以及包含无限多个有限-Δ 2 0-分段度的有限-(Π 2 0) 2-分段度(其中(Π n 0) 2 表示两个Π n 0 集合的差)，而这三个“有限-Γ-分段”度数结构中的最大度数是重合的。此外，对于康托空间的非空Π 1 0 子集，我们还证明每个非零有限-(Π 1 0) 2-分段度包含无穷多个Medvedev（即分段）度，每个非零可数-Δ 2 0-分段度包含无穷多个有限分段度，每个非零有限-(Π 2 0) 2-可数-Δ 2 0-分段度包含无穷多个有限分段度。许多可数-Δ 2 0 分段度，并且每个非零Muchnik（即，可数-Π 2 0 分段）度包括无限多个有限-(Π 2 0) 2-可数-Δ 2 0 分段度。事实上，我们证明了康托空间的非空 Π 1 0 子集的任何非零 Medvedev 度和非零可数 Δ 2 0 分段度都具有很强的抗杯形特性。最后，我们通过证明没有一个有限 Г 分段结构是布劳威尔式的，其中 Г 是上面提到的任何 Wadge 类，获得了 Medvedev (Muchnik) 度结构和贝尔空间所有子集的有限 Г 分段度结构之间的基本差异。
It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π 1 0 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π 1 0 subsets of Cantor space, we show the existence of a finite-Δ 2 0-piecewise degree containing infinitely many finite-(Π 1 0) 2-piecewise degrees, and a finite-(Π 2 0) 2-piecewise degree containing infinitely many finite-Δ 2 0-piecewise degrees (where (Π n 0) 2 denotes the difference of two Π n 0 sets), whereas the greatest degrees in these three “finite-Γ-piecewise” degree structures coincide. Moreover, as for nonempty Π 1 0 subsets of Cantor space, we also show that every nonzero finite-(Π 1 0) 2-piecewise degree includes infinitely many Medvedev (ie, one-piecewise) degrees, every nonzero countable-Δ 2 0-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-(Π 2 0) 2-countable-Δ 2 0-piecewise degree includes infinitely many countable-Δ 2 0-piecewise degrees, and every nonzero Muchnik (ie, countable-Π 2 0-piecewise) degree includes infinitely many finite-(Π 2 0) 2-countable-Δ 2 0-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-Δ 2 0-piecewise degree of a nonempty Π 1 0 subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev (Muchnik) degree structure and the finite-Γ-piecewise degree structure of all subsets of Baire space by showing that none of the finite-Γ-piecewise structures is Brouwerian, where Γ is any of the Wadge classes mentioned above.