Cototal enumeration degrees and their applications to effective mathematics
Cototal enumeration degrees and their applications to effective mathematics
复制标题
总枚举度及其在有效数学中的应用
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Ethan McCarthy
中科院分区：
文献类型：
--
作者：
Ethan McCarthy
如果A⊆ωe A，即A的补集是全的，则集合A≤在枚举约化下是上全的。证明了余全集的e度刻画了极大反链补的e度、2<；ω上枚举树的e度和2ω上极小子移位语言的e度。作为结果，我们得到了非平凡极小子移图灵度谱的一个刻画：它们是余全集的计数锥。从图灵度的角度来看，这提供了对最小子移位的计算能力的完整理解。我们还得到了在可计算结构理论中的一个应用，证明了余全集的计数锥刻画了实数的F-σ集的向上翻转闭包的结构谱。
A set A ⊆ ω is cototal under enumeration reducibility if A ≤e A, that is, if the complement of A is total. We show that the e-degrees of cototal sets characterize the e-degrees of maximal anti-chain complements, the e-degrees of enumeration-pointed trees on 2<ω , and the e-degrees of languages of minimal subshifts on 2ω . As a consequence, we obtain a characterization of the Turing degree spectra of nontrivial minimal subshifts: they are the enumeration cones of cototal sets. From the perspective of the Turing degrees, this provides a complete understanding of the computational power of minimal subshifts. We also obtain an application to computable structure theory, showing that the enumeration cones of cototal sets characterize those structure spectra which are Turingupward closures of Fσ sets of reals.