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^*

^*Corresponding author for this work

Victoria University of Wellington
CAS - Institute of Software

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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.

Original language	English
Pages (from-to)	101-118
Number of pages	18
Journal	Annals of Pure and Applied Logic
Volume	125
Issue number	1-3
DOIs	https://doi.org/10.1016/j.apal.2003.10.002
State	Published - Feb 2004
Externally published	Yes

Keywords

Cappable degrees
Complements
Isolation pairs

Access to Document

10.1016/j.apal.2003.10.002

Cite this

@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 -

Complementing cappable degrees in the difference hierarchy

Abstract

Keywords

Access to Document

Other files and links

Cite this