No Access

On the existence of a strong minimal pair

George Barmpalias

State Key Lab of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, P. R. China

School of Mathematics, Statistics and Operations Research, Victoria University, Wellington, New Zealand

Search for more papers by this author

Mingzhong Cai

Department of Mathematics, Dartmouth College, Hanover, NH 03755, USA

Search for more papers by this author

Steffen Lempp

Department of Mathematics, University of Wisconsin, Madison, WI 53706, USA

Search for more papers by this author

, and

Theodore A. Slaman

Department of Mathematics, University of California, Berkeley, CA 94720, USA

Search for more papers by this author

https://doi.org/10.1142/S0219061315500038Cited by:2 (Source: Crossref)

Abstract

We show that there is a strong minimal pair in the computably enumerable (c.e.) Turing degrees, i.e. a pair of nonzero c.e. degrees a and b such that a∩b = 0 and for any nonzero c.e. degree x ≤ a, b ∪ x ≥ a.

Keywords:

AMSC: 03D25

References

K. Ambos-Spies and M. Lerman , J. Symbolic Logic 51 , 257 ( 1986 ) . Crossref, Web of Science, Google Scholar
G. Barmpalias, Review of Lerman's "A framework for priority arguments", Lecture Notes in Logic, Vol. 34 (Cambridge University Press, NY, 2010, xvi + 176 pp.) Bull. Symbolic Logic 17 (2011) 464–467 . Google Scholar
P. A. Fejer and R. Soare, Logic Year 1979–1980: University of Connecticut (Springer-Verlag, 1981) pp. 49–62. Crossref, Google Scholar
L. Harrington and S. Shelah , Bull. Amer. Math. Soc. (N.S.) 6 , 79 ( 1982 ) . Crossref, Web of Science, Google Scholar
A. H. Lachlan , Proc. London Math. Soc. (3) 16 , 537 ( 1966 ) . Crossref, Web of Science, Google Scholar
A. H. Lachlan , Ann. Math. Logic 9 , 307 ( 1975 ) . Crossref, Google Scholar
S. Lempp, M. Lerman and D. R. Solomon, Lecture Notes in Logic 27 (Association for Symbolic Logic, La Jolla, CA, 2006) pp. 206–229. Google Scholar
S. Lempp , A. Nies and T. A. Slaman , Trans. Amer. Math. Soc. 350 , 2719 ( 1998 ) . Crossref, Web of Science, Google Scholar
M. Lerman , Ann. Pure Appl. Logic 101 , 275 ( 2000 ) . Crossref, Web of Science, Google Scholar
M. Lerman , A Framework for Priority Arguments , Lecture Notes in Logic 34 ( Cambridge University Press , 2010 ) . Crossref, Google Scholar
G. E. Sacks , Degrees of Unsolvability, Annals of Mathematics Studies ( Princeton University Press , Princeton, NJ , 1963 ) . Google Scholar
G. E. Sacks , Ann. of Math. (2) 77 , 211 ( 1963 ) . Crossref, Web of Science, Google Scholar
G. E. Sacks , Ann. of Math. (2) 80 , 300 ( 1964 ) . Crossref, Web of Science, Google Scholar
J. R. Shoenfield , Ann. Pure Appl. Logic 50 , 191 ( 1990 ) . Crossref, Web of Science, Google Scholar
R. Shore and T. A. Slaman , J. Symbolic Logic 58 , 824 ( 1993 ) . Crossref, Web of Science, Google Scholar
T. A. Slaman and R. I. Soare , Ann. of Math. (2) 154 , 1 ( 2001 ) . Crossref, Web of Science, Google Scholar
R. I. Soare , Recursively Enumerable Sets and Degrees , Perspectives in Mathematical Logic ( Springer-Verlag , Berlin , 1987 ) . Crossref, Google Scholar
C. E. M. Yates , J. Symbolic Logic 31 , 159 ( 1966 ) . Crossref, Web of Science, Google Scholar