Ingrassia proved that the p-generic Turing degrees are dense in the r.e. degrees and Ding De-cheng proved that the non-p-generic degrees are dense in the r.e. degrees too. But, do these two kinds of degrees have the s...Ingrassia proved that the p-generic Turing degrees are dense in the r.e. degrees and Ding De-cheng proved that the non-p-generic degrees are dense in the r.e. degrees too. But, do these two kinds of degrees have the same frequency of occurrency in every part of the r.e. degrees? In this note we give a negative answer.展开更多
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.展开更多
Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n>1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Low...Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n>1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Lowm r.e. degrees are not elementarily equivalent for n > m > 1.展开更多
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 ε.展开更多
It will be proved that given any noncappable r.e. degree a there are r.e.degrees a 0 and a 1 such that a 0,a 1a and [a 0∪a 1] is not local distributive,i.e.,there is an r.e.degree c such that [c][a 0∪a 1] and for an...It will be proved that given any noncappable r.e. degree a there are r.e.degrees a 0 and a 1 such that a 0,a 1a and [a 0∪a 1] is not local distributive,i.e.,there is an r.e.degree c such that [c][a 0∪a 1] and for any [u i][a i] and i=0,1,[c]≠[u 0]∨[u 1] where R/M is the quotient of the recursively enumerable degrees modulo the cappable degrees. Therefore, R/M is not distributive.展开更多
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.展开更多
基金Project supported by the National Natural Science Foundation of China.
文摘Ingrassia proved that the p-generic Turing degrees are dense in the r.e. degrees and Ding De-cheng proved that the non-p-generic degrees are dense in the r.e. degrees too. But, do these two kinds of degrees have the same frequency of occurrency in every part of the r.e. degrees? In this note we give a negative answer.
基金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.
文摘Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n>1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Lowm r.e. degrees are not elementarily equivalent for n > m > 1.
文摘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 ε.
文摘It will be proved that given any noncappable r.e. degree a there are r.e.degrees a 0 and a 1 such that a 0,a 1a and [a 0∪a 1] is not local distributive,i.e.,there is an r.e.degree c such that [c][a 0∪a 1] and for any [u i][a i] and i=0,1,[c]≠[u 0]∨[u 1] where R/M is the quotient of the recursively enumerable degrees modulo the cappable degrees. Therefore, R/M is not distributive.
基金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.
