Institutional Repository
| 交不可达递归可枚举度的稠密性 | |
| 张庆龙 | |
| 1990 | |
| Degree Grantor | 中国科学院软件研究所 |
| Degree Level | 博士 |
| Place of Degree Grantor | 中国科学院软件研究所 |
| English Abstract | 一个递归可枚举度集A approx= R(所有r.e.度所成的集合)的闭包CL(A)定义为最小集B满足(i) A is contained in B, (ii) a, b, ∈ B(a ∪ b ∈ B), 和(iii) n ≥ 0 a_0, …, a_n ∈ B(a_0 ∩ … ∩ a_n 存在 → a_0 ∩ … ∩ a_n ∈ B). 一个r.e. 度a是交不可达的如果不存在A is contained in R 使得a ∈ CL(A) 且A ∩ R(≤ a) = φ;否则,a是交可达的。易知交不可达度是非分枝度。P. A. Fejer 和 T. A. Slaman 分别使用O'' 和 O'''优先方法证明了非分枝度和分枝度在R中是稠密的。这样,非分枝度和分枝度将R划分成两个集合,每一个均在JoinsF生成R - {0} (因而是R 的一个自冈构基)且是R中非平凡的可定义稠密子集。本文使用O''优先方法证明了交不可达度在R中是稠密的。作为一个推论,交不可达度和交可达度也将R划分成两个集合,每一个均在JoinS下生成R-{0}(因而是R的一个自同构基)且是R中非平凡的稠密子集。 |
| Abstract | The closure CL(A) of A is contained in R (the set of all r.e. degrees) is the smallest set B such that (i) A is contained in B, (ii) a, b ∈ B(a ∪ b ∈ B), and (iii) n ≥ 0 a_0, …, a_n ∈ B(a_0 ∩ … ∩ a_n exists → a_0 ∩ … ∩ a_n ∈ B). An r.e. degree a is meet-inaccessible if there is no set A is contained in R such that a ∈ CL(A) and A ∩ R(≤ a) = φ. Otherwise, a is meet-accessible. It is easily known that meet-inaccessible degrees are nonbranching degrees. P. A. Fejer and T. A. Slaman Proved respectively the density of the nonbranching degrees and branching degrees, using the 0~(II)-priority and 0~(III)-priority constructions. So, the nonbranching degrees and branching degrees give a partition of R into two sets, either of which is a nontrivial definable dense subset of R and generates R-{0} under joins (thus an automorphism base of R). In this paper it is shown that the meet-inaccessible degrees are dense in R. The construction is an 0~(II)-priority construction. As a consequence, the meet-inaccessible degrees and meet-accessible degrees give another partition of R into two sets, either of which is a nontrivial dense subset of R and generates R-{0} under joins (thus an automorphism base of R).……… |
| Pages | 43 |
| Language | 中文 |
| Content Type | 学位论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/6834 |
| Collection | 中科院软件所_中科院软件所 |
| Recommended Citation GB/T 7714 | 张庆龙. 交不可达递归可枚举度的稠密性[D]. 中国科学院软件研究所. 中国科学院软件研究所,1990. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment