交不可达递归可枚举度的稠密性

ISCAS OpenIR > 中科院软件所 > 中科院软件所

	交不可达递归可枚举度的稠密性
	张庆龙
	1990
学位授予单位	中国科学院软件研究所
学位	博士
学位授予地点	中国科学院软件研究所
摘要	一个递归可枚举度集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中非平凡的稠密子集。
其他摘要	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).………
页数	43
语种	中文
内容类型	学位论文
URI标识	http://ir.iscas.ac.cn/handle/311060/6834
专题	中科院软件所_中科院软件所
推荐引用方式 GB/T 7714	张庆龙. 交不可达递归可枚举度的稠密性[D]. 中国科学院软件研究所. 中国科学院软件研究所,1990.