Bounding and Nonbounding Minimal Pairs in the Enumeration Degrees

, , &
Journal of Symbolic Logic 70 (3):741 - 766 (2005)
  Copy   BIBTEX

Abstract

We show that every nonzero $\Delta _{2}^{0}$ e-degree bounds a minimal pair. On the other hand, there exist $\Sigma _{2}^{0}$ e-degrees which bound no minimal pair

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1122038912

Links

PhilArchive



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

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

Bounding minimal degrees by computably enumerable degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.
On minimal pairs of enumeration degrees.Kevin McEvoy & S. Barry Cooper - 1985 - Journal of Symbolic Logic 50 (4):983-1001.
On a problem of Cooper and Epstein.Shamil Ishmukhametov - 2003 - Journal of Symbolic Logic 68 (1):52-64.
Properly $\Sigma _{2}^{0}$ Enumeration Degrees and the High/Low Hierarchy.Matthew Giorgi, Andrea Sorbi & Yue Yang - 2006 - Journal of Symbolic Logic 71 (4):1125 - 1144.
On the Definable Ideal Generated by Nonbounding C.E. Degrees.Liang Yu & Yue Yang - 2005 - Journal of Symbolic Logic 70 (1):252 - 270.
The Π₃-Theory of the $\Sigma _{2}^{0}$ -Enumeration Degrees Is Undecidable.Thomas F. Kent - 2006 - Journal of Symbolic Logic 71 (4):1284 - 1302.
Bounding Nonsplitting Enumeration Degrees.Thomas F. Kent & Andrea Sorbi - 2007 - Journal of Symbolic Logic 72 (4):1405 - 1417.
Noncappable enumeration degrees below 0'e. [REVIEW]S. Barry Cooper & Andrea Sorbi - 1996 - Journal of Symbolic Logic 61 (4):1347 - 1363.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
A Hyperimmune Minimal Degree and an ANR 2-Minimal Degree.Mingzhong Cai - 2010 - Notre Dame Journal of Formal Logic 51 (4):443-455.
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.
Jumps of quasi-minimal enumeration degrees.Kevin McEvoy - 1985 - Journal of Symbolic Logic 50 (3):839-848.

Analytics

Added to PP
2010-08-24

Downloads
53 (#300,268)

6 months
19 (#134,856)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
In memoriam: Barry Cooper 1943–2015.Andrew Lewis-Pye & Andrea Sorbi - 2016 - Bulletin of Symbolic Logic 22 (3):361-365.

Add more citations

References found in this work

Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
Enumeration Reducibility Using Bounded Information: Counting Minimal Covers.S. Barry Cooper - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (6):537-560.

Add more references