Non-Uniformity and Generalised Sacks Splitting |
| |
Authors: | S Barry Cooper Ang Sheng Li |
| |
Institution: | (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)} \not\leqslant _{{\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)} \not\leqslant _{{\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 等数据库收录! |
|