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 Δ20, e-degree bounds a minimal pair. On the other hand, there exist Σ20, 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,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

Bounding and Nonbounding Minimal Pairs in the Enumeration Degrees.S. Barry Cooper, Angsheng Li, Andrea Sorbi & Yue Yang - 2005 - Journal of Symbolic Logic 70 (3):741 - 766.
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.
A minimal pair joining to a plus cupping Turing degree.Dengfeng Li & Angsheng Li - 2003 - Mathematical Logic Quarterly 49 (6):553-566.
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.
Bounding Nonsplitting Enumeration Degrees.Thomas F. Kent & Andrea Sorbi - 2007 - Journal of Symbolic Logic 72 (4):1405 - 1417.
Bounding minimal degrees by computably enumerable degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.
The minimal e-degree problem in fragments of Peano arithmetic.M. M. Arslanov, C. T. Chong, S. B. Cooper & Y. Yang - 2005 - Annals of Pure and Applied Logic 131 (1-3):159-175.
On the Symmetric Enumeration Degrees.Charles M. Harris - 2007 - Notre Dame Journal of Formal Logic 48 (2):175-204.
Bounding Minimal Degrees by Computably Enumerable Degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.
On a problem of Cooper and Epstein.Shamil Ishmukhametov - 2003 - Journal of Symbolic Logic 68 (1):52-64.
A Hyperimmune Minimal Degree and an ANR 2-Minimal Degree.Mingzhong Cai - 2010 - Notre Dame Journal of Formal Logic 51 (4):443-455.
Infima in the d.r.e. degrees.D. Kaddah - 1993 - Annals of Pure and Applied Logic 62 (3):207-263.
Cupping and noncupping in the enumeration degrees of ∑20 sets.S. Barry Cooper, Andrea Sorbi & Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (3):317-342.
On minimal pairs of enumeration degrees.Kevin McEvoy & S. Barry Cooper - 1985 - Journal of Symbolic Logic 50 (4):983-1001.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.

Analytics

Added to PP
2017-02-21

Downloads
13 (#1,006,512)

6 months
5 (#652,053)

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.

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