Non-uniformity and generalised Sacks splitting (Q1862888)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Non-uniformity and generalised Sacks splitting
scientific article

    Statements

    Non-uniformity and generalised Sacks splitting (English)
    0 references
    0 references
    0 references
    0 references
    16 October 2003
    0 references
    The problem of splitting is an important issue for Turing degrees. \textit{G. E. Sacks} showed [Ann. Math. (2) 77, 211-231, correction ibid. 78, 204 (1963; Zbl 0118.25104)] that for any computably enumerable degree, \(a\not=0\), there exist computably enumerable degrees, \(a_0,a_1\), such that \(a_0,a_1 < a\) and \(a_0 \vee a_1 = a\). \textit{S. B. Cooper} [Proc. Am. Math. Soc. 115, 461-471 (1992; Zbl 0771.03013)] extended this theorem to all levels of the \(n\)-computably enumerable degrees. In particular, this theorem holds for the Turing degrees of the difference of computably enumerable sets (i.e. d.c.e degrees). The following question arises: is there a uniform proof of splitting in the d.c.e. degrees which simultaneously subsumes the splitting theorems of Sacks and Cooper. The authors show that there exist no computable functions, \(f_1,f_2,g_1,g_2\), such that for all \(e,i \in \omega\): \((W_{f_1(e,i)} - W_{f_2(e,i)}) \leq_T (W_e - W_i)\); \((W_{g_1(e,i)} - W_{g_2(e,i)}) \leq_T (W_e - W_i)\); \((W_e - W_i) \leq_T (W_{f_1(e,i)} - W_{f_2(e,i)}) \oplus (W_{g_1(e,i)} - W_{g_2(e,i)})\); \((W_e - W_i) \not\leq_T (W_{f_1(e,i)} - W_{f_2(e,i)})\) unless \((W_e - W_i) \leq_T \emptyset\); and \((W_e - W_i) \not\leq_T (W_{g_1(e,i)} - W_{g_2(e,i)})\) unless \((W_e - W_i) \leq_T \emptyset\). Then, it follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly. The proof is given by a priority method.
    0 references
    0 references
    0 references
    Turing degrees
    0 references
    splitting and nonsplitting
    0 references
    Sacks splitting
    0 references
    Cooper splitting
    0 references
    difference of computably enumerable sets
    0 references
    d.c.e. degrees
    0 references
    0 references