An ω-REA set forming a minimal pair with 0~′

Article type: Research Article

Authors: Gerdes, Peter^{; *}

Affiliations: Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA. gerdes@invariant.org; http://invariant.org

Correspondence: [*] Corresponding author. gerdes@invariant.org.

Abstract: It is easy to see that no n-REA set can form a (non-trivial) minimal pair with 0~′ and only slightly more difficult to observe that no ω-REA set can form a (non-trivial) minimal pair with 0~″. Shore has asked whether this can be improved to show that no ω-REA set forms a (non-trivial) minimal pair with 0~′. We show that no such improvement is possible by constructing an ω-REA set C with 0~<TC⩽T0~″ forming a minimal pair with 0~′. We then show that no α-REA set (for any notation α) can form a (non-trivial) minimal pair with 0~″.

Keywords: REA, ω-REA, Turing reducible, computability, minimal pair

DOI: 10.3233/COM-180191

Journal: Computability, vol. 9, no. 1, pp. 37-50, 2020