Title of article :
Complementing cappable degrees in the difference hierarchy
Original Research Article
Author/Authors :
Rod Downey، نويسنده , , Angsheng Li، نويسنده , , Guohua Wu، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Abstract :
We prove that for any computably enumerable (c.e.) degree View the MathML source, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree View the MathML source such that View the MathML source and View the MathML source. 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
Journal title :
Annals of Pure and Applied Logic
Journal title :
Annals of Pure and Applied Logic