Non-Uniformity and Generalised Sacks Splitting |
| |
| Authors: | S. Barry Cooper Ang Sheng Li |
| |
| Affiliation: | (1) Department of Pure Mathematics, School of Mathematics, University of Leeds, Leeds LS2 9JT, UK E-mail: s.b.cooper@leeds.ac.uk, GB;(2) Department of Pure Mathematics, School of Mathematics, University of Leeds, Leeds LS2 9JT, UK; Institute of Software, Chines Academy of Sciences, P. O. Box 8718, Beijing 100080, P. R. China E-mail: liang@ox.ios.ac.cn and angsheng@amsta.leeds.ac.uk, |
| |
| Abstract: | We show that there do not exist computable functions f 1(e, i), f 2(e, i), g 1(e, i), g 2(e, i) such that for all e, i ∈ ω, (1) $ {left( {W_{{f_{1} {left( {e,i} right)}}} - W_{{f_{2} {left( {e,i} right)}}} } right)} leqslant _{{rm T}} {left( {W_{e} - W_{i} } right)}; $ (2) $ {left( {W_{{g_{1} {left( {e,i} right)}}} - W_{{g_{2} {left( {e,i} right)}}} } right)} leqslant _{{rm T}} {left( {W_{e} - W_{i} } right)}; $ (3) $ {left( {W_{e} - W_{i} } right)} notleqslant _{{rm T}} {left( {W_{{f_{1} {left( {e,i} right)}}} - W_{{f_{2} {left( {e,i} right)}}} } right)} oplus {left( {W_{{g_{1} {left( {e,i} right)}}} - W_{{g_{2} {left( {e,i} right)}}} } right)}; $ (4) $ {left( {W_{e} - W_{i} } right)} notleqslant _{{rm T}} {left( {W_{{f_{1} {left( {e,i} right)}}} - W_{{f_{2} {left( {e,i} right)}}} } right)}{text{unless}}{left( {W_{e} - W_{i} } right)} leqslant _{{rm T}} {emptyset};{text{and}} $ (5) $ {left( {W_{e} - W_{i} } right)} leqslant _{{rm T}} {left( {W_{{g_{1} {left( {e,i} right)}}} - W_{{g_{2} {left( {e,i} right)}}} } right)}{text{unless}}{left( {W_{e} - W_{i} } right)} leqslant _{{rm T}} {emptyset}. $ It follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly. |
| |
| Keywords: | Computably enumerable (c.e.) Difference of computably enumerable sets (d.c.e. or 2-c.e.) Turing degrees Splitting and nonsplitting |
| 本文献已被 SpringerLink 等数据库收录！ |
|
