Complementing cappable degrees in the difference hierarchy

Rod Downey; Angsheng Li; Guohua Wu

doi:10.1016/j.apal.2003.10.002

Complementing cappable degrees in the difference hierarchy

Rod Downey
, Angsheng Li
, Guohua Wu^*

^*此作品的通讯作者

Victoria University of Wellington
CAS - Institute of Software

科研成果: 期刊稿件 › 文章 › 同行评审

4 引用（Scopus）

摘要

We prove that for any computably enumerable (c.e.) degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c ∪.d = 0 ′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.

源语言	英语
页（从-至）	101-118
页数	18
期刊	Annals of Pure and Applied Logic
卷	125
期	1-3
DOI	https://doi.org/10.1016/j.apal.2003.10.002
出版状态	已出版 - 2月 2004
已对外发布	是

访问文件

10.1016/j.apal.2003.10.002

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{71ea558638014887bfe88366bd60c7b8,

title = "Complementing cappable degrees in the difference hierarchy",

abstract = "We prove that for any computably enumerable (c.e.) degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c ∪.d = 0 ′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.",

keywords = "Cappable degrees, Complements, Isolation pairs",

author = "Rod Downey and Angsheng Li and Guohua Wu",

year = "2004",

month = feb,

doi = "10.1016/j.apal.2003.10.002",

language = "英语",

volume = "125",

pages = "101--118",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Complementing cappable degrees in the difference hierarchy

AU - Downey, Rod

AU - Li, Angsheng

AU - Wu, Guohua

PY - 2004/2

Y1 - 2004/2

N2 - We prove that for any computably enumerable (c.e.) degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c ∪.d = 0 ′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.

AB - We prove that for any computably enumerable (c.e.) degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c ∪.d = 0 ′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.

KW - Cappable degrees

KW - Complements

KW - Isolation pairs

UR - https://www.scopus.com/pages/publications/0742324358

U2 - 10.1016/j.apal.2003.10.002

DO - 10.1016/j.apal.2003.10.002

M3 - 文章

AN - SCOPUS:0742324358

SN - 0168-0072

VL - 125

SP - 101

EP - 118

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 1-3

ER -