Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures
Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures
复制标题
将超算术层次结构的级别实现为可计算结构上关系的度谱
DOI：
10.1305/ndjfl/1071505769
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Walker M. White
中科院分区：
文献类型：
--
作者：
D. Hirschfeldt;Walker M. White
我们构建一类关系的可计算结构的度谱形成自然类的程度。给定任意可计算序数α和强于或等于m-约简的约简r，我们证明了如何构造一个具有内在α-不变关系的结构，该关系的度谱由所有非平凡α-r-度组成。我们扩展了这个构造，以证明<$α可以被<$α或<$α替换。
We construct a class of relations on computable structures whose degree spectra form natural classes of degrees. Given any computable ordinal α and reducibility r stronger than or equal to m-reducibility, we show how to construct a structure with an intrinsically Σα invariant relation whose degree spectrum consists of all nontrivial Σα r-degrees. We extend this construction to show that Σα can be replaced by either Πα or ∆α.