Cupping partners of an element in an upper semilattice with a greatest element 1 are those joining the element to 1. We define a congruence relation on such an upper semilattice by considering the elements having the ...Cupping partners of an element in an upper semilattice with a greatest element 1 are those joining the element to 1. We define a congruence relation on such an upper semilattice by considering the elements having the same cupping partners as equivalent. It is interesting that this congruence relation induces a non-dense quotient structure of computably enumerable Turing degrees. Another main interesting phenomenon in this article is that on the computably enumerable degrees, this relation is different from that modulo the noncuppable ideal, though they define a same equivalent class for the computable Turing degree.展开更多
A computably enumerable (c.e.,for short)degree a is called plus cupping,if every c.e. degree x with 0<x≤a is cuppable.Let PC be the set of all plus cupping degrees.In the present paper,we show that PC is not close...A computably enumerable (c.e.,for short)degree a is called plus cupping,if every c.e. degree x with 0<x≤a is cuppable.Let PC be the set of all plus cupping degrees.In the present paper,we show that PC is not closed under the join operation ∨ by constructing two plus cupping degrees which join to a high degree. So by the Harringtons noncupping theorem,PC is not an ideal of ε.展开更多
We show that there do not exist computable fimetions f_1(e,i).f_2(e,i).g_1(e,i),g_2(e,i)such that for all e,i ∈ω, (1)(W_(f_1)(e,i)-W_(f_2)(e,i))≤T(W_e-W_1): (2)(W_(g_1)(e,i)-W_(g_2)(e,i))≤T(W_e-W_i): (3)(W_w-W_i)...We show that there do not exist computable fimetions f_1(e,i).f_2(e,i).g_1(e,i),g_2(e,i)such that for all e,i ∈ω, (1)(W_(f_1)(e,i)-W_(f_2)(e,i))≤T(W_e-W_1): (2)(W_(g_1)(e,i)-W_(g_2)(e,i))≤T(W_e-W_i): (3)(W_w-W_i)≤T(W_(f_1)(e,i)-W_(f_2)(e,i))⊕(W_(g_1)(e,i)-W_(g_2)(e,i)): (4)(W_e-W_i)T(W_(f_1)(e,i)-W_(f_2)(e,i))uuless(W_e-W_i)≤T:and (5)(W_e-W_i)T(E_(g_1)(e,i)-W_(g_2)(e,i))unless(W_w-W_i)≤T. It follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly.展开更多
(i) Call a c.e. degree b anti-cupping relative to x, if there is a c.e. a < b such that for any c.e. w, w x implies a ∪ w b ∪ x.(ii) Call a c.e. degree b everywhere anti-cupping (e.a.c.), if it is anti-cupping re...(i) Call a c.e. degree b anti-cupping relative to x, if there is a c.e. a < b such that for any c.e. w, w x implies a ∪ w b ∪ x.(ii) Call a c.e. degree b everywhere anti-cupping (e.a.c.), if it is anti-cupping relative to x for each c.e. degree x.By a tree method, we prove that every high c.e. degree has e.a.c. property by extending Harrington's anti-cupping theorem.展开更多
基金This work was partially supported by the National Natural Science Foundation of China (Grant Nos. 10410638 and 10471060)
文摘Cupping partners of an element in an upper semilattice with a greatest element 1 are those joining the element to 1. We define a congruence relation on such an upper semilattice by considering the elements having the same cupping partners as equivalent. It is interesting that this congruence relation induces a non-dense quotient structure of computably enumerable Turing degrees. Another main interesting phenomenon in this article is that on the computably enumerable degrees, this relation is different from that modulo the noncuppable ideal, though they define a same equivalent class for the computable Turing degree.
文摘A computably enumerable (c.e.,for short)degree a is called plus cupping,if every c.e. degree x with 0<x≤a is cuppable.Let PC be the set of all plus cupping degrees.In the present paper,we show that PC is not closed under the join operation ∨ by constructing two plus cupping degrees which join to a high degree. So by the Harringtons noncupping theorem,PC is not an ideal of ε.
基金supported by EPSRC Research Grant"Turing Definability"No.GR/M 91419(UK)+1 种基金partially supported by NSF Grant No.69973048supported by NSF Major Grant No.19931020 of P.R.CHINA
文摘We show that there do not exist computable fimetions f_1(e,i).f_2(e,i).g_1(e,i),g_2(e,i)such that for all e,i ∈ω, (1)(W_(f_1)(e,i)-W_(f_2)(e,i))≤T(W_e-W_1): (2)(W_(g_1)(e,i)-W_(g_2)(e,i))≤T(W_e-W_i): (3)(W_w-W_i)≤T(W_(f_1)(e,i)-W_(f_2)(e,i))⊕(W_(g_1)(e,i)-W_(g_2)(e,i)): (4)(W_e-W_i)T(W_(f_1)(e,i)-W_(f_2)(e,i))uuless(W_e-W_i)≤T:and (5)(W_e-W_i)T(E_(g_1)(e,i)-W_(g_2)(e,i))unless(W_w-W_i)≤T. It follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly.
基金supported by“863”project and the National Natural Science Foundation of China.
文摘(i) Call a c.e. degree b anti-cupping relative to x, if there is a c.e. a < b such that for any c.e. w, w x implies a ∪ w b ∪ x.(ii) Call a c.e. degree b everywhere anti-cupping (e.a.c.), if it is anti-cupping relative to x for each c.e. degree x.By a tree method, we prove that every high c.e. degree has e.a.c. property by extending Harrington's anti-cupping theorem.
