Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
复制标题
偏度和密度问题第 2 部分：Σ2 集合的枚举度是稠密的。
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
S. Cooper
中科院分区：
文献类型：
--
作者：
S. Cooper
与Rogers[3]一样，我们将偏度视为枚举度的符号变体（也就是说，函数的偏度与其图的枚举度一致）。我们在[1]中证明了没有最小偏度。本文的目的是证明0′以下的偏度（即Σ2偏函数的偏度）是密集的。由此可见，Σ2集合在枚举度中所起的作用与图灵度中递归可枚举集合所起的作用类似。当然，这些技术与证明递归可枚举图灵度的Sacks密度定理（见[4，第20页]）所需的技术非常不同。符号和术语与[1]相似。特别地，We, Dx, < m, n >， ψe分别是在给定的正则集合的标准列表中的正则集合e，正则索引为x的有限集合，（m, n）的递归码和枚举算子e（由We导出）的符号。递归近似等也定义在[1]中。定理1。如果B和C是Σ2sets的数字，并且B≰e C，则存在一个带证明的e算子Θ。我们枚举一个e算子Θ以满足条件列表：设{Bs∣s≥0}，{Cs∣s≥0}分别是对B、C的近似的递归序列，对于每个矩阵，∈B⇔（∃s*）（∀s≥s*）（∀s∈B）和∈C⇔（∃s*）（∀s≥s*）（∀s∈C）。
As in Rogers [3], we treat the partial degrees as notational variants of the enumeration degrees (that is, the partial degree of a function is identified with the enumeration degree of its graph). We showed in [1] that there are no minimal partial degrees. The purpose of this paper is to show that the partial degrees below 0′ (that is, the partial degrees of the Σ2 partial functions) are dense. From this we see that the Σ2 sets play an analagous role within the enumeration degrees to that played by the recursively enumerable sets within the Turing degrees. The techniques, of course, are very different to those required to prove the Sacks Density Theorem (see [4, p. 20]) for the recursively enumerable Turing degrees. Notation and terminology are similar to those of [1]. In particular, We, Dx, 〈m, n〉, ψe are, respectively, notations for the e th r.e. set in a given standard listing of the r.e. sets, the finite set whose canonical index is x, the recursive code for (m, n) and the e th enumeration operator (derived from We). Recursive approximations etc. are also defined as in [1]. Theorem 1. If B and C are Σ2sets of numbers, and B ≰e C, then there is an e-operator Θ with Proof. We enumerate an e-operator Θ so as to satisfy the list of conditions: Let {Bs ∣ s ≥ 0}, {Cs ∣ s ≥ 0} be recursive sequences of approximations to B, C respectively, for which, for each х, х ∈ B ⇔ (∃s*)(∀s ≥ s*)(х ∈ Bs) and х ∈ C ⇔ (∃s*)(∀s ≥ s*)(х ∈ Cs).