Non-uniformity and generalised Sacks splitting (Q1862888): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: On the degrees less than 0' / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Splitting Theorem for the N-R.E. Degrees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The d.r.e. degrees are not dense / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: D.R.E. Degrees and the Nondiamond Theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cupping the Recursively Enumerable Degrees by D.R.E. Degrees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3819052 / rank | |||
Normal rank |
Latest revision as of 14:06, 5 June 2024
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
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
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