Bounding computably enumerable degrees in the Ershov hierarchy
文献类型：期刊论文
| 作者 | Li AS ; Wu GH ; Yang Ye |
| 刊名 | Annals of Pure and Applied Logic
 |
| 出版日期 | 2006 |
| 卷号 | 141期号:40180页码:79-88 |
| 关键词 | computably enumerable degrees highness Ershov hierarchy DRE DEGREES |
| 通讯作者 | Wu ; GH (通讯作者) ; Nanyang Technol Univ ; Sch Math & Phys Sci ; Div Math Sci ; Singapore 639798 ; Singapore |
| 收录类别 | SCI ; SCIENCEDIRECT |
| 公开日期 | 2010-08-23 |
| 附注 | Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper； we study the c.e. predecessors of d.c.e. degrees； and prove that given a nonzero d.c.e. degree a； there is a c.e. degree b below a and a high d.c.e. degree d > b such that b bounds all the c.e. degrees below d. This result gives a unified approach to some seemingly unrelated results. In particular； it has the following two known theorems as corollaries: (1) there is a low c.e. degree isolating a high d.c.e. degree [S. Ishmukhametov； G. Wu； Isolation and the high/low hierarchy； Arch. Math. Logic 41 (2002) 259-266]; (2) there is a high d.c.e. degree bounding no minimal pairs [C.T Chong； A. Li； Y Yang； The existence of high nonbounding degrees in the difference hierarchy； Ann. Pure Appl. Logic 138 (2006) 31-51]. (c) 2005 Elsevier B.V. All rights reserved. |
| 源URL | [http://124.16.136.157/handle/311060/3810]  |
| 专题 | 软件研究所_基础软件国家工程研究中心_期刊论文 |
| 推荐引用方式 GB/T 7714 | Li AS,Wu GH,Yang Ye. Bounding computably enumerable degrees in the Ershov hierarchy[J]. Annals of Pure and Applied Logic,2006,141(40180):79-88. |
| APA | Li AS,Wu GH,&Yang Ye.(2006).Bounding computably enumerable degrees in the Ershov hierarchy.Annals of Pure and Applied Logic,141(40180),79-88. |
| MLA | Li AS,et al."Bounding computably enumerable degrees in the Ershov hierarchy".Annals of Pure and Applied Logic 141.40180(2006):79-88. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。