On a conjecture of Lempp (Q1570019)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On a conjecture of Lempp
scientific article

    Statements

    On a conjecture of Lempp (English)
    0 references
    0 references
    25 October 2000
    0 references
    We first prove that there exist computably enumerable (c.e.) degrees \({\mathbf a}\) and \({\mathbf b}\) such that \({\mathbf a}\nleq{\mathbf b}\), and for any c.e. degree \({\mathbf u}\), if \({\mathbf u}\leq {\mathbf a}\) and \({\mathbf u}\) is cappable, then \({\mathbf u}\leq {\mathbf b}\), so refuting a conjecture of S. Lempp [cf. \textit{T. A. Slaman}, ``Questions in recursion theory'', in: S. B. Cooper et al. (eds.), Computability, enumerability, unsolvability. Directions in recursion theory (Cambridge Univ. Press), Lond. Math. Soc. Lect. Note Ser. 224, 333-347 (1996; Zbl 0834.03012)]; secondly, we prove that: (A. Li and D. Wang) there is no uniform construction to build a nonzero cappable degree below a nonzero c.e. degree, that is, there is no computable function \(f\) such that for all \(e\in\omega\), (i) \(W_{f(e)}\leq_T W_e\), (ii) \(W_{f(e)}\) has a cappable degree, and (iii) \(W_{f(e)} \nleq_T\emptyset\) unless \(W_e\leq_T \emptyset\).
    0 references
    0 references
    computably enumerable degrees
    0 references
    cappable degree
    0 references
    0 references
    0 references
    0 references