Complementing cappable degrees in the difference hierarchy

, &
Annals of Pure and Applied Logic 125 (1-3):101-118 (2004)
  Copy   BIBTEX

Abstract

We prove that for any computably enumerable 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

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2003.10.002

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Quasi-complements of the cappable degrees.Guohua Wu - 2004 - Mathematical Logic Quarterly 50 (2):189.
Bounding cappable degrees.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (5):311-352.
Cappable recursively enumerable degrees and Post's program.Klaus Ambos-Spies & André Nies - 1992 - Archive for Mathematical Logic 32 (1):51-56.
Infima of d.r.e. degrees.Jiang Liu, Shenling Wang & Guohua Wu - 2010 - Archive for Mathematical Logic 49 (1):35-49.
On a conjecture of Lempp.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (4):281-309.
Relative enumerability in the difference hierarchy.Marat M. Arslanov, Geoffrey L. Laforte & Theodore A. Slaman - 1998 - Journal of Symbolic Logic 63 (2):411-420.
Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees.Klaus Ambos-Spies & Ding Decheng - 1994 - Mathematical Logic Quarterly 40 (3):287-317.
Bounded query classes and the difference hierarchy.Richard Beigel, William I. Gasarch & Louise Hay - 1989 - Archive for Mathematical Logic 29 (2):69-84.
The existence of high nonbounding degrees in the difference hierarchy.Chi Tat Chong, Angsheng Li & Yue Yang - 2006 - Annals of Pure and Applied Logic 138 (1):31-51.
Nonhemimaximal degrees and the high/low hierarchy.Fang Chengling & Wu Guohua - 2012 - Journal of Symbolic Logic 77 (2):433-446.
Bounding computably enumerable degrees in the Ershov hierarchy.Angsheng Li, Guohua Wu & Yue Yang - 2006 - Annals of Pure and Applied Logic 141 (1):79-88.
The computably enumerable degrees are locally non-cappable.Matthew B. Giorgi - 2004 - Archive for Mathematical Logic 43 (1):121-139.

Analytics

Added to PP
2014-01-16

Downloads
15 (#919,495)

6 months
6 (#522,885)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

A minimal pair of recursively enumerable degrees.C. E. M. Yates - 1966 - Journal of Symbolic Logic 31 (2):159-168.
The d.r.e. degrees are not dense.S. Cooper, Leo Harrington, Alistair Lachlan, Steffen Lempp & Robert Soare - 1991 - Annals of Pure and Applied Logic 55 (2):125-151.
Minimal pairs and high recursively enumerable degrees.S. B. Cooper - 1974 - Journal of Symbolic Logic 39 (4):655-660.
Bounding minimal pairs.A. H. Lachlan - 1979 - Journal of Symbolic Logic 44 (4):626-642.

View all 15 references / Add more references