Том 154, кн. 2 УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОО УНИВЕСИТЕТА Физико-математические науки 2012 UDK 510.532 ISOLATION: MOTIVATIONS AND APPLICATIONS G. Wu, M.M. Yamaleev Abstrat In this paper, we briey review the origins of the isolation phenomenon and its appliations. We disuss a stronger notion of double bubbles. We also show reent ahievements in the study of lattie embeddings with the help of the isolation property. Key words: Turing degrees, Ershov hierarhy, isolated degrees, lattie embeddings. Introdution n + 1 -.e. a if a < d is the greatest n + 1 -.e. degrees, for n ? 1 , an be obtained, in a nonuniform way, from Kaddah's thesis, where inma of n -.e. degrees in dierent levels of the Ershov hierarhy are onsidered. The ase when n = 1 was rst An n -.e. degree degree below d. d is isolated by an n -.e. degree The existene of suh isolated proposed expliitly by Cooper and Yi in their paper [1?, and the general ase, i.e. when n ? 1, was studied by LaForte in [2?. A reent onstrution of bubbles of Arslanov, Kalimullin and Lempp in [3? also gives rise to the existene of isolated degrees, and it is attempting to extend suh bubble onstrutions to show that dierent (nite) levels in the Ershov hierarhy are not elementary equivalent. In this paper, we briey review the origins of the isolation phenomenon and how variants of this phenomenon an be applied to study loal and global properties of the Ershov hierarhy. In Setion 1, we rst show how to obtain isolated degrees from Kaddah's thesis, and then give a brief desription of early development in this area. In Setion 2, we onsider isolation from side, a property that was used by Yang and Yu to show that the .e. degrees is not a has been extended to n -.e. ?1 substruture of d..e. degrees. This phenomenon degrees by Cai, Shore and Slaman [4?. We are onerned with those nonisolated degrees that an be isolated from side, whih are nontrivial extensions of Cooper and Yi's isolated degrees. In Setion 3, we give a diret onstrution of a bubble, a work of Arslanov, Kalimullin and Lempp. That is, we will provide a onstrution of a d..e. degree below d d and a .e. degree a < d suh that every d..e. degree e a . Obviously, d is isolated by a . We believe that, like the is omparable with isolation phenomenon, the bubble phenomenon is an important tool for studying the strutural properties of the Ershov hierarhy. In Setion 4, we show reent development of appliations of isolation to lattie embeddings. This projet was initiated by Wu in his thesis [5? and has ome to a highlight in a reent work of Fang, Liu and Wu, who proved in [6? that any nonzero appable .e. degree an have a d..e. degree with almost universal upping property as its omplement. Our notation and terminology are standard and generally follow Soare [7?. We suggest the readers to refer Cooper's paper [8? and Arslanov's paper [9? for the general idea on loal degree theory. ISOLATION: MOTIVATIONS AND APPLICATIONS 205 1. Kaddah's work and isolation A Turing degree is properly d..e. if it ontains a d..e. set, but no .e. set. Cooper proved in [10? the existene of properly d..e. degrees, and Lahlan observed that any nonzero d..e. degree bounds a nonzero .e. degree. That is, given a d..e. set an eetive approximation {Ds : s ? ?} , D with the assoiated set L(D) = {hx, si : x ? Ds ? D} D , while D is .e. in L(D) . If D is .e. and {Ds : s ? ?} is an eetive enumeration of D , then L(D) is empty. On the other hand, if D has proper d..e. degree, then L(D) is not omputable. L(D) is alled the Lahlan set of D with referene to the enumeration {Ds : s ? ?} . Lahlan's observation is .e., and is Turing reduible to shows that the d..e. degrees are downwards dense, whih is also true for the .e. degrees. However, the d..e. degrees are not dense, and hene these two degree strutures are not elementarily equivalent. Theorem 1 (Nondensity Theorem for D2 [11?). There exists a maximal d..e. degree d < 0? , and hene the d..e. degrees are not dense. The fat that these strutures are not elementarily equivalent was rst proved by Arslanov [12? and Downey [13?, who proved that any nonzero d..e. degree is uppable, and that the diamond lattie an be embedded into the d..e. degrees preserving 0 and 1, respetively. In ontrast to this nondensity theorem, Ishmukhametov [14? and, independently, Cooper and Yi [1? proved that any nonempty interval [a, d] , a with .e., ontains innitely many d..e. degrees, a weak density theorem of d..e. degrees. Theorem 2 [1, 14?. If d is a d..e. degree and a < d is a .e. degree, then there is a d..e. degree c between a and d . Here we annot require the degree a d..e. degree d>a c a and d . This an be obtained above be .e., as there are a .e. degree suh that no .e. degree is between a and from the following theorem of Kaddah. Theorem 3 [15?. Every low .e. degree is branhing in the d..e. degrees. Let a be a low, nonbranhing, .e. degree, and let d, e be two d..e. degrees above a suh that a is the inmum of d and e in the d..e. degrees. Then one of the intervals (a, d) , (a, e) ontains no .e. degrees, as a is assumed to be nonbranhing. Cooper and Yi rst notied this strutural phenomenon and proposed the notion of isolation expliitly in their paper [1?. Denition 1 [1?. A d..e. degree greatest .e. degree below degree a. d. d is isolated by a .e. degree A d..e. degree d a if a<d is the is isolated if it is isolated by some .e. A d..e. degree is nonisolated if it is not isolated. After showing the existene of the isolated degrees, Cooper and Yi ontinued to show the existene of the nonisolated degrees, where a d..e. degree if no .e. degree below d an isolate d. d is nonisolated Cooper and Yi atually proved the existene of a properly d..e. degree as a minimal upper bound of a uniformly .e. sequene of degrees, an even stronger result. These two kinds of degrees are proved to be dense in the .e. degrees. Theorem 4 [1618?. Both the isolated d..e. degrees and the nonisolated d..e. degrees are dense in the .e. degrees. G. WU, M.M. YAMALEEV 206 Theorem 4 says that the isolated degrees ould be as lose to the isolating degrees as wanted. Ishmukhametov and Wu proved that in terms of the high/low hierarhy, the isolated d..e. degree and the isolating degree an be quite far from eah other. Theorem 5 [19, 20?. There is a high d..e. degree d isolated by a low .e. degree c . Suh a .e. degree c an be found below any nonzero .e. degree a . Cooper [21? proved in 1974 that any high .e. degree bounds a minimal pair, and hene no high .e. an be nonbounding. However, there do exist high d..e. nonbounding ??? degrees, as rst onstruted by Chong, Li and Yang in [22? by a fairly ompliated 0 argument. Theorem 5 an provide another proof of this result, as if we rst take a nonbounding degree, and then apply Theorem 5 to obtain d also nonbounding, whih implies that c and d. Obviously, a as c is is also nonbounding (and also high). In [18?, Arslanov, Lempp and Shore showed the existene of the nonisolating degrees, and proved that these degrees are downwards dense in the .e. degrees, and an our in every jump lass. In ontrast to this, Cooper, Salts and Wu proved in [23? that the nonisolating degrees are upwards dense in the .e. degrees. Furthermore, Salts proved in [24? that the nonisolating degrees are not dense in the .e. degrees. Theorem 6 [24?. There is an interval of .e. degrees, [a, c] , eah of whih isolates a d..e. degree. 1 Reent work of Wu and Yamaleev c is, above an be high and a shows that suh an interval an be large. That an be low. Lahlan [25? proved in 1966 that the inmum of two .e. degrees in the .e. degrees ?02 degrees oinide. In ontrast to this, in [15?, Kaddah proved that the inma of n -.e. degrees in the n -.e. degrees an be and the inmum of two .e. degrees in the n -.e. dierent from that of these two degrees in the (n + 1) -.e. degrees. Theorem 7 [15?. For eah n ? 2 , there are n -.e. degrees d, e suh that they have f as inmum in the n -.e. degrees, and there is an (n + 1) -.e. degree x with f < x < d, e . is isolated by x shows that d (n + 1) -.e. degrees. Following Cooper 2 the n -.e. degrees. Liu, Wang and Wu x dense in the .e. degrees. This isolation This implies isolation at higher levels in the Ershov hierarhy, as and e do not have f as their inmum in the and Yi, we an say that x proved that suh isolation pairs, and f in f , are result was proved previously by LaForte in [2? by a dierent approah. 2. Variants of isolation Arslanov's upping theorem shows that the strutures of the .e degrees and the d..e degrees dier at ?3 level, and Cooper et al.'s proof of the existene of inomplete maximal d..e. degrees, and Downey's diamond theorem show that these two strutures dier at ?1 ?2 level. It beomes interesting to onsider whether two strutures dier at level. a, b, c form a Slaman triple if b 6? c , and for any w ? a , w ? b ? c . It is easy to hek that a and b above form Say that nonzero .e. degrees nonzero .e. degree a minimal pair, and Shore and Slaman proved in 1993 that every high .e. degree bounds a Slaman triple. In 1983, Slaman proved the following strengthened version of Slaman triples. 1 A large interval of isolating degrees, in preparation. 2 An alternative approah of isolated (n + 1) -.e. degrees, in preparation. ISOLATION: MOTIVATIONS AND APPLICATIONS 207 Theorem 8 (Slaman 1983). There are .e. degrees a, b, c and a ?02 degree d with 0 < d < a suh that (1) a, b, c form a Slaman triple, (2) d ? b 6? c . Theorem 8 says that no nonzero .e. degree c 6? w ? b , while there is a nonzero ?02 degree d is a ?1 property, whih provides a ?1 dierene w below below a has the property that a that has this property. This 0 between the .e. degrees and the ?2 degrees. In [26?, Yang and Yu proved that the .e. degrees and the d..e. degrees also dier at ?1 level, by modifying this proof of Slaman, where another parameter is introdued to handle the degrees of Lahlan's sets of d, if d is d..e. Theorem 9 [26?. There are .e. degrees a, b, c, e and a d..e. degree d < a suh that d ? b 6? c , d 6? e , and for any .e. degree w < a , either w ? b ? c or w ? e . This proof was reently extended by Cai, Shore and Slaman to prove that for any m < n, the m -.e. degrees is not a ?1 -substruture of the n -.e. degrees. Theorem 10 [4?. There are .e. degrees a, b, c, e and an (n + 1) -.e. degree d < a suh that d ? b 6? c , d 6? e , and for any n -.e. degree v < a , either v ? b ? c or v ? e. These two results give rise to another isolation. That is, all the are isolated, or bounded, by .e. degree e. n -.e. degrees below d Note that we have two ases: either there is n -.e. degrees) or e annot be below d n = 1 , and in the latter ase, we say that d..e. degree d is isolated from side nontrivially: d itself is nonisolated, and there is a .e. degree e inomparable with d , bounding all the .e. degrees below d . We omment here that in the results mentioned above, it is hard to insert e below d . That is, it is hard to make d isolated. For Cai, Shore and Slaman's result, for n ? 2 , if we really want to move e below d , then e annot be .e. anymore, and we will make it n -.e. (this is what we want). suh an e below d (d is isolated by e in the ( d is nonisolated). We onsider the ase when In the following, we show how to onstrut a d..e. degree isolated from side nontrivially. We will build d..e. sets B, D and a .e. set C satisfying the following requirements: G : B ?T C, PeD : D 6= ?C e , e PeB : B 6= ?W ? We 6= ?B e e , We Q e : ?B e = We ? (? c.e. Ue ?T B)(?i)(Ue 6= ?i ), Re : ?eB?D = We ? ??e (?B e = We ), h?, ?, W i for whih ? , W is a .e. set. Let b, c, d be the Turing degrees of B, C and B ? D , respetively. By the Q -requiB rement, b ? c . All the P -requirements ensure that b is a properly d..e. degree, and hene b < c . By the Q -strategies, b is nonisolated. The R -strategies ensure that all the .e. degrees below d are also below b , hene below c . Aording to Wu [5?, d is where ? {h?e , ?e , We i : e ? ?} is a standard enumeration of all are partial omputable funtionals and pseudo-isolated. G -requirement, we onstrut a p.. funtional ? suh that B = ?C , and for a number x , if we put a number x into B , or extrat it from B , at a stage s , we always put ?(x)[s] into C automatially. Obviously, ? is totally dened. D B A Pe -strategy is a standard Friedberg Muhnik strategy, and a Pe -strategy is a strategy used in the onstrution of proper d..e. degrees. An Re -strategy is similar For the G. WU, M.M. YAMALEEV 208 to an isolation strategy. That is, we hek at every expansionary stage whether ?B e and We agree, and if not, suppose they dier at x , then we extrat relevant numbers out B?D of D to reover a omputation ?e (x) to a previous one, whih has value 0. This B?D reates a disagreement between ?e and We , and the requirement is satised. B A Qe -strategy, ? say, attempts to onstrut a .e. set Ue suh that if We = ?e , then We Ue ?T B and for all i ? ? , Ue 6= ?i . Dene ? -expansionary stages in a standard way, and ? has two outomes: 0 and 1 , where 0 stands for the ase that there are innitely many ? -expansionary stages, and 1 for the other ase. Suppose that ? has outome 0. The onstrution of Ue will be arried out by Qe 's ? substrategies, Se,i , i ? ? , whih are arranged in the one below ? h0i : e Se,i : Ue 6= ?W i . Let ? be an Se,i -strategy. Then B e ?W or between We and ?e . i ? tries to gure out a disagreement between Ue and (1) Choose x as a fresh number. (2) Wait for a stage s suh that W ?i,se,s (x) ?= 0 and s We,s ? ?i,s (x) = ?B e,s ? ?i,s (x). If this never happens, then x is a witness to the suess of Se,i .) ( (3) Put x into Ue and (4) Wait for a stage s? W B. Protet B ? s from other strategies. suh that ? ?i,se,s (x) ?= 1 ? and B We,s? ? ?i,s (x) = ?e,ss?? ? ?i,s (x). If this never happens, then again x is a witness to the suess of Se,i . If it ? e happens, then the hange in ?W i (x) between stages s and s an only be brought about by a hange in We ? ?i,s (x) , whih is irreversible sine We is a .e. set.) ( (5) Remove x from B and protet B ? s from other strategies. Now x is a permanent witness to the suess of Se,i beause ( B ?B e ? ?i,s (x) = ?e,s ? ?i,s (x) = We,s ? ?i,s (x) 6= We ? ?i,s (x). That is, taking x from B leads to a global win on Qe , and Ue is no longer needed, so we don't need to are about the loss of B -permission for x (whih is left in Ue ).) In the onstrution, sine we are onstruting B d..e., the R -strategy is a little B more ompliated than the standard isolation strategy. Suppose that ?? (x) gets dened B at stage s0 , and a P (or an S )-strategy ? with lower priority enumerates a number z < ?? (x) into B at a stage s1 > s0 . This enumeration fores (and allows) us to ?? (x) to a larger number, ?? (x)[s1 ] . Later, at stage s2 , to get a disagreement, ? , or its mother node, takes z out, and thus ?? (x) returns to its denition at stage s0 . Suh a variation does no harm to the disagreement strategy of R -strategy, ? say. B Suppose that ? observes at some stage between s1 and s2 that ?? (x) is inorret and performs the disagreement strategy; then ? will be initialized, and so ? has no hane to take z out. In this ase, s2 does not exist. In ase that s2 does exist, and ? nds lift ISOLATION: MOTIVATIONS AND APPLICATIONS an inorretness of stage s0 , ?B ? (x) s 3 > s2 , at stage sine at stage s2 , ?? (x) 209 returns to that of we have Bs2 ? ?e,s0 = Bs0 ? ?e,s0 . Now by the fat that ?? (x)[s3 ] = s0 , we have Bs3 ? ?e,s0 = Bs0 ? ?e,s0 . This guarantees the suess of d disagreement strategy. is also below but not below d. Note that d is nonisolated, as if a b<d bounds all the d , then b . As b is nonisolated, there is a .e. degree e below b (hene below d ) a . Wu proved in [27? that the pseudo-isolated d..e. degrees are dense .e. degrees below a ? 's above is alled a pseudo-isolated degree, as a d..e. degree is a .e. degree below in the .e. degrees. 3. Double bubbles: a stronger notion In this setion, we onsider a phenomenon alled bubbles, whih was disovered by Arslanov, Kalimullin and Lempp in their work [3?. A basi fat about isolation is that a isolates d if and only if a and d have the same lower ones in the .e. degrees. Extending this onept, we onsider the ase when all the d..e. degrees below omparable with d are a. Fix a d..e. degree d . Let L(d) be the olletion of all Lahlan sets L(D) , where D is a d..e. set in d . It's easy to see that d is isolated by a if and only if eah X ? L(d) has its degree deg (X) ? a . In [28?, Ishmukhametov proved that there exist a .e. degree a and a d..e. degree d suh that L(d) ? a , and alled suh degrees d exat degrees. Obviously, all exat degrees are isolated by the degree of Lahlan sets. Ishmukhametov also proved in [28? that there exist isolated non-exat degrees. Say that two nonzero d..e. degrees the d..e. degrees below interval (a, d) and a d d and a are omparable with (together with a. 0) form a bubble if all Obviously, any d..e. degree in the also form a bubble. Arslanov, Kalimullin and Lempp in their reent work [3? proved the existene of suh a bubble and that the degree a in any bubble must be .e. The onstrution has speial diulties and it is still unknown whether suh a strutural phenomenon an be ombined with other properties (in a similar way like isolated degrees, see, e.g., reent work of Wu [29? and his joint works with Fang and Liu [6? and [30?). Arslanov, Kalimullin and Lempp also proved in [3? the following important theorem. Theorem 11 [3?. Let D and A be d..e. sets with D T A , and X be a .e. set suh that X ?T D, A T X , and both D and A are .e. in X . Then there exists a d..e. set U with X ?T U ?T D , and U and A are Turing inomparable. Theorem 11 implies that for any bubble pair d is relatively enumerable in and above x a < d, by Saks splitting theorem (avoiding the upper one of stritly above a. That is, x and a the .e. degrees should be above or equal to are the same, and d a ), we have that x suh that a . However, x annot be is an exat degree, and hene isolated. The proof of the existene of exat d..e. degrees is simpler than the one for bubbles. One property of bubbles is that the splittings of the top d..e. degree of a bubble a<d are always above a. A related topi, nonsplittability avoiding upper ones, was rst proposed by Cooper and Li in [31?. Denition 2. (1) a splitting Given d..e degrees x0 , x1 of d is a < d, nontrivial if d xi for i = 0, 1 ; G. WU, M.M. YAMALEEV 210 d is splittable above a if a ? xi for i = 0, 1 ; (2) there exist a nontrivial splitting of d = x0 ? x1 suh that (3) d is splittable avoiding the upper one of a d = x0 ? x1 suh that a xi for i = 0, 1 . Note that if d if there exists a nontrivial splitting of is nonsplittable avoiding the upper one of splittable avoiding the upper one of any degree a Yamaleev proved that if between them, then d and d e below a. a, then d is also non- On the other hand, in [32?, are properly d..e. degrees and there is no .e. degree an always be splittable avoiding the upper one of a. a<d This result is interesting due to the following reason. Assume that both d..e. degrees and eah d..e. degree in the interval upper one of if a<d a; then we all this interval a form a bubble, then (a, d] (a, d] are is nonsplittable avoiding the nonsplitting interval. (It is easy to see that is a nonsplitting interval.) Saks' splitting theorem (avoiding upper ones) implies that no .e. degree is in this interval. By Yamaleev's a result mentioned above, is .e., and hene d is isolated by a. Below we provide a sketh of the proof of a bubble, whih ontains all features of onstrutions of d..e. degrees whih are nonsplittable avoiding upper ones and also onstrutions of nonsplitting intervals. Theorem 12 [3?. There exist a .e. degree a and a d..e. degree d suh that 0 < a < d and any d..e. degree u ? d is omparable with a . Sketh of proof. .e. set A In the sketh, we will provide the basi idea of onstruting and d..e. set these strategies. A and D , inluding individual strategies and the interations between D are onstruted to meet the following requirements: Pe : A 6= ?e , Se : D 6= ?A e , U Re : Ue = ?A?D ? (Ue = ?A e e ? A = ?e ) , where {h?e , ?e , ?e i}e?? is an eetive enumeration of all p.. funtionals, and is an eetive enumeration of all d..e. sets. Obviously, if quirements, then the degrees of A and A?D A and D {Ue }e?? satisfy these re- form a bubble, as wanted. Later we will often omit indies. P -requirement and an S -requirement an be satised by the Friedberg Muhnik R -strategy, we assume that there are innitely A?D many expansionary stages (approximating U = ? ), and we try rst to build a p.. funtional ? at these stages. It an happen that some S -strategy below it enumerates A?D a number x into D , and this enumeration an hange omputation ? (y) , hene A allowing U to hange at y . We ould not hange ? (y) sine it requires hanges of A on small numbers. In the onstrution of isolated degrees, we just need to extrat x from D , making U (y) 6= ?A?D (y) . In our onstrution, if U (y) hanges from 1 to 0, i.e. y leaves U , then we at in the same way: extrat x from D , making U (y) = 0 6= 1 = ?A?D (y) , and hene satisfy this R -requirement. However, if U (y) hanges from 0 to 1, i.e. y enters U , we ould not just simply extrat x out of D , as U (y) an hange from 1 to 0 later, and our eort on diagonalization fails. So if we see that U (y) hanges from 0 to 1, A strategy (or a variant of it). For an instead of making diagonalization immediately, we will turn to extend the denition U of ? on more arguments, z say, with y less than the ? -use. If later we want to U enumerate z into A , we will need to fore y out of U to undene ? (z) , and we make A?D it by extrating x from D to reover ? (y) = 0 , and now either y keeps in U (we A?D get U (y) = 1 6= 0 = ? (y) ) or y leaves U and we have ?U (z) undened, and we an now enumerate z into A. ISOLATION: MOTIVATIONS AND APPLICATIONS 211 R -strategy has three outomes ?, ?, f in with order ? <L ? <L f in . If there are f in is the orret outome. Otherwise, A there are innitely many expansionary stages, and if from some stage on, ? keeps orret in the remainder of the onstrution, then ? is the orret outome. If eah A U version of ? appears inorret, then ? will be dened innitely many times, and ? is the orret outome. Note that whenever ? -outome appears to be orret, the A A urrent version of ? beomes invalid, and we will start a new version of ? . For onveniene, we use x as witnesses for S -strategies (an be enumerated into D and perhaps removed out later), z as witnesses for P -strategies (an be enumerated into A ) and y for elements of U (an be in or not in U ). As desribed before, if an S -strategy, ? say, is working below the outome ? of an R -strategy, ? say, then ? works in a standard FriedbergMuhnik manner, trying to nd a witness x to satisfy the requirement. If the enumeration of x auses U (y) A dierent from ? (y) , without loss of generality, we assume that U (y) hanges from 0 U to 1, then ? will have outome ? , i.e. ? tries to extend ? on more arguments. A P -strategy, ? say, below the outome ? of an R -strategy ? , tries to enumerate U its witness z into A . ? annot enumerate z into A immediately if ? (z) is dened, as 0, at the moment. Here is the point: when ? hooses z as its witness, ? has outome ? , whih is aused by an enumeration of an S -strategy, say ? (below outome ? ), at a stage s , whih makes U (y) to hange from 0 to 1. Obviously, when z is seleted, z is seleted muh bigger, and espeially z > s . Now if ? wants to enumerate z into A , then the ation is to extrat x out of D and also enumerate z into A simultaneously. Of ourse, we an enumerate z later, after we see that U (y) hanges bak to 0. We prefer to enumerate z into A at the same time when we extrat x out of D , as z > s , A?D whih is bigger than the use in ? (y)[s] . If U (y) does not hange bak to 0, then A?D (x) = 0 6= 1 = U (y) , and the R -requirement is satised. Otherwise, we win as ? ?U (z) (and also ?U (s) ) is undened, whih makes ? 's enumerations into A onsistent. As U is assumed to be d..e., after y leaves U , it an never ome bak. Due to this, U one ? enumerates z into A , z remains in A , as ? (z) will be redened as 1 later and forever. The situation is quite dierent for the ase when U is 3-.e., as desribed An only nitely many expansionary stages, then in [3?. We now onsider more ompliated interations among several strategies. ? P below ? -outome of R2 below ? -outome of R1 . A A generi ase is that after we put a number x2 into D , ?1 is dened at some 1 1 point y , and extrating x2 from D may now hange U1 (y ) , and the ation desribed D d..e. The D , besides enumerating z into A , we also enumerate into A a number s , the stage at whih x2 is enumerated into D . Enumerating z into A is for the sake of the P -strategy, and enumerating s into A is to A undene ?1 (y) , whih are dened after stage s . This idea is exatly the same as that in the onstrution of isolated degrees, to maintain the onsisteny between R -strategies. We use s(x) to denote the stage at whih x is enumerated into D . It is a routine to A show that for a partiular n , ?1 (n) an be undened in this way by at most nitely A?D many times, whih ensures that if ?1 (n) onverges, then ?A 1 (n) is dened. above to reover a omputation does not apply here, as we are making idea here is that whenever we extrat a number x2 from ? P below ? -outomes of R2 and R1 . ?1 and ?2 to denote the ? -outomes of R -strategies ?1 ?2 , respetively, where ?2 is below outome ?1 . Let ? be a P -strategy below ?2 's outome ?2 . We now desribe how ? works below these two ? -outomes. For simpliity, we use and G. WU, M.M. YAMALEEV 212 R -strategy, when it turns to have outome ? , it is aused by S -strategy below outome ? . Here is the idea: when an S strategy ?2 below ?2 's outome ?2 sees that ?A i2 (x2 ) onverges to 0, at stage s1 say, instead of enumerating x2 into D immediately, it waits for the next time when ?2 is visited again, whih will atually show that an S -strategy, ?1 say, below ?1 's outome ?1 , already enumerates a witness x1 , being seleted after stage s1 . Note that at this stage, s(x1 ) is bigger than the uses of all omputations seeing at stage s1 . Now assume that ?2 is visited again at stage s2 , then at this stage, ?2 enumerates x2 into D , so s(x2 ) = s2 . Without loss of generality, suppose that this enumeration leads ?2 to have outome ?2 , and ? selets a number z as its witness. We then assoiate z with x1 and x2 , whih means that enumerating z into A and extrating x1 and x2 out of D should happen at the same time. Thus, we have x2 < x1 < s(x1 ) < s(x2 ) < z . Assume later that ? wants to enumerate z into A ; it will do so and at the same time extrat both x2 , x1 from D and enumerate s(x1 ), s(x2 ) into A . As disussed before, if we have a new ?1 -expansionary stage, then U1 should have a hange on the assoiated U1 U1 U1 number, y1 say, whih undenes ?1 (s(x1 )) , ?1 (s(x2 )) and ?1 (z) . Also, if we have a new ?2 -expansionary stage later, then U2 has a hange on y2 say, whih undenes U2 U2 2 ?U 2 (s(x2 )) , ?2 (s(x1 )) and ?2 (z) . This nested proedure is the ore part of the onstrution of bubbles, and the idea an be generalized to a ase when ? is working below ? -outome of several R -strategies. Reall that for any an enumeration of some In [3?, Arslanov, Kalimullin and Lempp atually proved the existene of 3-bubbles, a generalization of double bubbles. Denition 3. Let d, e, f 3-bubble in D3 if any 3-.e. degree Say that these degrees form a omparable with both e and 0 < d < e < f. u < f is omparable be 3-.e. degrees with degrees form a weak 3-bubble d in D3 if any 3-.e. degree Say that these with u<f e and d. is either or inomparable with both of them. Theorem 11 implies that weak 3-bubbles do not exist in D2 . In [3?, Arslanov, Kalimullin and Lempp atually proved that degrees f , e, d in the weak 3-bubbles an be 3-.e., d..e. and .e., respetively. In the following, we show that suh weak 3-bubbles are atually 3-bubbles, so the onstrution given in [3? produes a 3-bubble. f are omparable with e and d . Suppose f , but not omparable with e and d . Then g ?d would be d..e. and g ? d > d , whih would imply that g ? d > e , as g is not below e . By assumption that f , e, d form a weak 3-bubble in D3 , we know that g ? d, e, d also form a weak 3-bubble in D3 , whih is also a weak 3-bubble in D2 , a ontradition. We now assume that h is a 3-.e. degree below f but inomparable with e and d . Then h is a properly 3-.e. degree, and degrees of Lahlan sets of those 3-.e. sets in h are d..e., and hene are omparable with e and d . Let u be a degree of the Lahlan set of a 3-.e. set in h . Then u is not above d , as otherwise, h would be also above d , whih is impossible. As a onsequene, u is below d . Now onsider h ? d , whih is 3-.e and relative enumerable in and above d . As here, we assume that d given as a .e. degree, by a well-known result of Arslanov, LaForte First, we show that all d..e. degrees below not, and let g be a d..e. degree below and Slaman in [33? that the lass of the d..e. degrees oinides with the intersetion of ? -.e. degrees and the lass of the 2-REA degrees, we know that h ? d h ? d > d , and hene h ? d is omparable with e . As h itself is inomparable with e , h ? d is above e . Thus, h ? d, e, d form a weak 3-bubble in D3 , whih is also a weak 3-bubble in D2 . A ontradition again. This ompletes the proof. the lass of the is d..e. Note that ISOLATION: MOTIVATIONS AND APPLICATIONS 213 4. Isolation, upping and diamond embeddings In this setion, we show how to use isolation phenomenon to provide alternative proofs of several known results of upping properties and diamond embeddings. In [11?, Cooper, Harrington, Lahlan, Lempp and Soare proved the existene of an inomplete, maximal d..e. degree ups every .e. degree not below it to d . This result 0? . In ontrast, is strong, as it implies that d Li, Song and Wu proved in [34? ? the existene of an inomplete ? -r.e. degree upping every nonzero r.e. degree to 0 . These degrees are said to have the universal upping property. In terms of the Ershov hierarhy, Li, Song and Wu's result is optimal. In [30?, Liu and Wu proposed a upping property for the d..e. degrees, where a d..e. d degree has the almost universal upping property if it ups every .e. degree not 0? . The maximal d.r.e. degree onstruted by Cooper et al. does have this below it to property. However, ompared to the onstrution of inomplete maximal d.r.e. degrees, the onstrution of d..e. degrees with almost universal upping property is muh easier. d b < d. In [30?, Liu and Wu onstruted a d..e. degree d suh that is also isolated by a .e. degree with the almost upping property Theorem 13. There is an almost universal upping d..e. degree d and a .e. degree b < d suh that b is the greatest .e. degree below d . D , a nonreursive .e. set B We ?T B or B ? D ? We ?T ?? . To prove Theorem 13, we will onstrut a d..e. set suh that (i) D 6?T B , (ii) for any .e. set We , either That is, the onstruted sets need to satisfy the isolation requirements and also the following upping requirements: e Re : K = ?B,D,W ? We = ?B e e , where ?e and ?e are p.. funtionals onstruted by us. Here K is a xed reative set. Note that the R -requirements ensure that B?D has the almost universal upping property. Re -strategy. For onveniene, we write ?? for ?e(?) and W? for We(?) . B,D,W? ? will onstrut a partial omputable (p..) funtional ?? suh that K = ?? , and if ? fails, due to the ations of the isolation strategies, then an isolation strategy will show that W? ?T B . ?? is onstruted as follows: Let ? be an A. At a stage s, dene B,D,W? ?? not dened, and the use B,D,W? (z)[s] = Ks (z) for those z < s with ?? ?? (z)[s] is seleted as a fresh number. B,D,W? B. If ?? (z)[s] ? = 6 Ks (z) , then we put B,D,W? ?? (z) for the least z < s . In the onstrution, to orret many z. ?, ? ?? (z)[s] into may enumerate uses D (z)[s] to undene the urrent ?? (z) into D for innitely ? and those isolation These enumerations an ause diret onits between strategies, ? say, below ? , whih want to preserve omputations. This type of interation is an important omponent of the whole onstrution. be an isolation strategy. The basi idea of ? is to onstrut a p.. funtional ?B,D is total, then ?? is well-dened ? B and omputes W? orretly. If later, at an ? -expansionary stage, we see that ?? (y) and W? (y) dier at an argument y say, we will then fore a disagreement between ?B,D (y) 6= W? (y) . ? Let ?? ? at expansionary stages to ensure that if ? has three outomes f, d ? , with priority ? <L f <L d . Here f denotes ? -expansionary stages and ? does not reate any and that there are only nitely many G. WU, M.M. YAMALEEV 214 disagreement, and d ? denotes that there are innitely many denotes the outome that and ? ? -expansionary sueeds in reating a disagreement between stages. ??B?D W? . A ruial ation of ? is that when a number, another number, for example, the stage when z z say, is removed from is put into D, D, then is enumerated into B simultaneously. This ation an ensure that all the isolation strategies work onsistently. R -strategy. R -strategy and an isolation strategy respetively, with ? ? ? . As mentioned in a single R -strategy, a disagreement reated by ? ould be destroyed by ? 's enumerations into D . Also, when ? has ? as its outome, ? may enumerate ?(n) into D as n enters K . Now ? may see an opportunity to diagonalize by extrating ?(n) from D , and ? annot do this as ? would be injured by this extration. B?D To avoid this, when ? sees a omputation ?? (y) and wants to preserve it, ? needs to make this omputation lear of the ?? -uses, by applying the apriious method, an argument rst introdued by Lahlan in his nonsplitting theorem. That is, when ? is rst visited, it piks a number k? as its threshold, and whenever a number k ? k? B,D,W? enters K , we enumerate the urrent ?? (k) -use into D to undene ?? (k) , and also reset ? by anelling all the parameters assoiated to ? , exept for the parameter k? . ? aims to dene a p.. funtional ?B ?? with the purpose that if ? annot satisfy the B assoiated isolation requirement, then ??? should be total and omputes W? orretly. This will satisfy the R? -requirement. Suppose that after stage s , ? is not reset and suppose that at a stage t > s , ? sees a potential witness y for its disagreement argument, then ? puts ?? (k? )[t] into D rst, to start an attak on ? , by dening We now onsider the interation between one isolation strategy and one ? Let and ? be an ?B ?? ? ?? (k? )[t] = W?,t ? ?? (k? )[t] t. W? hanges below ?? (k? )[t] after stage t , at an ? -expansionary stage t? > t say, then ? performs the disagreement argument by removing numbers out of D , inluding ?? (k? )[t] , to reover omputation ??B?D (y) to ??B?D (y)[s? ] , where s? is the stage at B whih ?? (y) is dened, as indiated above. This W? -hange lifts the value of ?? (z) ? for those z ? k? , and hene, after stage t , the enumeration of the ?? -uses will not B?D aet the omputation ?? (x) . That is, the attak is ompleted at stage t? , and ? passes the threshold k? for ? . On the other hand, if W? has no hanges below ?? (k? )[t] after stage t , then the attak assoiated with ?? (k? )[t] keeps ative until a new attak is ativated. If innitely B many suh attaks are started, then ??? is dened as a total funtion and omputes W? orretly, and hene We is omputable in B . In this situation, ? has four possible outomes: with use If f: There are only nitely many d: ? ?: passes its threshold k? ?, stages. and a disagreement is reated. ? -expansionary stages, and only nitely ?B ? is total and omputes W? orretly. There are innitely many are started. In this ase, g? : for ? -expansionary many attaks Innitely many attaks are started in the onstrution, and ? never passes its B threshold k? for ? . ??? is total and omputes W? orretly. The R? -requirement B,D,W? is satised. ?? (p? ) In this ase, diverges. ISOLATION: MOTIVATIONS AND APPLICATIONS Let ? 215 g? , then ? knows that ?? (p? ) -uses goes ??B?D (y) at a stage s is ? -believable if ? is a bak-up strategy for ? , then by using be any strategy below the outome to innity, and we say that a omputation ?? (p? )[s] is bigger than the use ?? (y)[s] . If only ? -believable omputations, ? an satisfy the orresponding requirement in the standard way, as after ? sees at ? -believable omputations, ? 's further enumerations into D will not aet these omputations. This basi idea an be generalized to the situation when one isolation strategy is working below several R -strategies, where an attak of ? needs to pass several thresh- olds. Please refer to [30? for further development. In [30?, Liu and Wu also proved that b an be appable. This implies that any d..e. degree below d , together with 0 and 0? , form a diamond. b and any d..e. degree above This isolation feature allows Fang, Liu and Wu to improve a result of Downey, Li and Wu in [35?. Fang, Liu and Wu proved reently that for any nonzero appable c , there is a d..e. degree d with almost universal upping property and b < d suh that b isolates d and that c and b form a minimal pair. By applying this result twie, rst to c and then to b , we have d and b rst, and then e and a suh that e has almost universal upping property and a < e isolates e , and a and b form a minimal pair. Now for any nonzero .e. degree w , w ups either e or d , ? or both, to 0 . Obviously, this result has Li ,Yi upping theorem as a diret orollary. .e. degree a .e. degree Both authors are supported by NTU grant RG37/09, M52110101. The seond author is supported by RFBR (Projets 09-01-97010, 10-01-00399), ADTP Development of the Sienti Potential of Higher Shool of the Russian Federal Ageny of Eduation (Grant 2.1.1/5367), Federal Target Grant Sienti and Eduational Personnel of Innovation of Russia (Government ontrat No. П 269). езюме . Ву, М.М. Ямалеев. Изолированность: обоснования и приложения. В статье рассматриваются еномен изолированной степени и его приложения к исследованию свойств степеней их иерархии Ершова. Анализируются степени, образующие ѕвосьмеркуї (более сильный вариант изолированной степени), а также демонстрируются последние достижения в изучении вложимости решеток при помощи свойства изолированности. Ключевые слова: вложения решеток. тьюринговые степени, иерархия Ершова, изолированные степени, References 1. Cooper S.B., Yi X. Isolated d.r.e. degrees // Preprint series (University of Leeds, Dept. of Pure Math.). ? 1995. ? No 17. ? 25 p. 2. LaForte G. Isolation in the CEA hierarchy // Arch. Math. Logic. ? 2005. ? V. 44, No 2. ? P. 227?244. 3. Arslanov M., Kalimullin I., Lempp S. On Downey?s conjecture // J. Symbolic Logic. ? 2010. ? V. 75, No 2. ? P. 401?441. 4. Cai M., Shore R.A., Slaman T.A. The n-r.e. degrees: undecidability and ?1 substructures // J. Math. Logic. ? 2012. ? V. 12, No 1. ? P 1250005-1?1250005-30. 5. Wu G. Structural Properties of d.c.e. degrees and presentations of c.e. reals: PhD Thesis. ? Wellington: Victoria University of Wellington, 2002. 6. Fang C., Liu J., Wu G. Cupping and diamond embeddings: a unifying approach // Lecture Notes in Computer Science. ? 2011. ? V. 6735. ? P. 71?80. 216 G. WU, M.M. YAMALEEV 7. Soare R.I. Recursively enumerable sets and degrees. ? Heidelberg: Springer-Verlag, 1987. ? 437 p. 8. Cooper S.B. Local degree theory // Handbook of Computability Theory (Studies in Logic and the Foundations of Mathematics, V. 140) / Ed. by E.R. Griffor. ? Amsterdam: NorthHolland, 1999. ? P. 121?153. 9. Arslanov M. Open questions about the n -c.e. degrees // M. Lerman, P.A. Cholak, S. Lempp, R.A. Shore (Eds.) Computability Theory and Its Applications: Current Trends and Open Problems: Proc. 1999 AMS-IMS-SIAM Joint Summer Res. Conf. (Contemporary Mathematics, V. 257). ? Providence, RI: Amer. Math. Soc., 2000. ? P. 15?22 10. Cooper S.B. Degrees of Unsolvability: PhD Thesis. ? Leicester: University of Leicester, 1971. 11. Cooper S.B., Harrington L., Lachlan A.H., Lempp S., Soare R.I. The d.r.e. degrees are not dense // Ann. Pure Appl. Logic. ? 1991. ? V. 55., No 2. ? P. 125?151. 12. Arslanov M. Structural properties of the degrees below 0? // Dokl. Acad. Nauk SSSR. ? 1985. ? V. 283. ? P. 270?273. 13. Downey R. D.r.e. degrees and the nondiamond theorem // Bull. London Math. Soc. ? 1989. ? V. 21. ? P. 43?50. 14. Ishmukhametov Sh. D.r.e. sets, their degrees and index sets: PhD Thesis. ? Novosibirsk, 1986. 15. Kaddah D. Infima in the d.r.e. degrees // Ann. Pure Appl. Logic. ? 1993. ? V. 62. ? P. 207?263. 16. Ding D., Qian L. Isolated d.r.e. degrees are dense in r.e. degree structure // Arch. Math. Logic. ? 1996. ? V. 36, No 1. ? P. 1?10. 17. LaForte G. The isolated d.r.e. degrees are dense in the r.e. degrees // Math. Logic Quart. ? 1996. ? V. 42. ? P. 83?103. 18. Arslanov M.M., Lempp S., Shore R.A. On isolating r.e. and isolated d-r.e. degrees // Computability, enumerability, unsolvability (London Mathematical Society, Lecture Note Series, No. 224) / Ed. by S.B. Cooper, T.A. Slaman, S.S. Wainer. ? Cambridge: Cambridge Univ. Press, 1996. ? V. 224. ? P. 61?80. 19. Ishmukhametov Sh., Wu G. Isolation and the high/low hierarchy // Arch. Math. Logic. ? 2002. ? V. 41, No 3. ? P. 259?266. 20. Li A., Wu G., Yang Y. Bounding computably enumerable degrees in the Ershov hierarchy // Ann. Pure Appl. Logic. ? 2006. ? V. 141, No 1?2. ? P. 79?88. 21. Cooper S.B. Minimal pairs and high recursively enumerable degrees // J. Symbolic Logic. ? 1974. ? V. 39, No 4. ? P. 655?660. 22. Chong C.T., Li A., Yang Y. The existence of high nonbounding degrees in the difference hierarchy // Ann. Pure Appl. Logic. ? 2006. ? V. 138, No 1?3. ? P. 31?51. 23. Cooper S.B., Salts M.C., Wu G. The non-isolating degrees are upwards dense in the computably enumerable degrees // Theory and Applications of Models of Computation, Proc. 5th Int. Conf. TAMC 2008 (Lecture Notes in Computer Science, V. 4978). ? Berlin; Heidelberg: Springer-Verlag, 2008. ? P. 588?596. 24. Salts M. An interval of computably enumerable isolating degrees // Math. Logic Quart. ? 1999. ? V. 45. ? P. 59?72. 25. Lachlan A.H. Lower bounds for pairs of recursively enumerable degrees // Proc. London Math. Soc. ? 1966. ? V. 16. ? P. 537?569. ISOLATION: MOTIVATIONS AND APPLICATIONS 217 26. Yang Y., Yu L. On ?1 -structural differences among finite levels of the Ershov hierarchy // J. Symbolic Logic. ? 2006. ? V. 71, No 4. ? P. 1223?1236. 27. Wu G. On the density of the pseudo-isolated degrees // Proc. London Math. Soc. ? 2004. ? V. 88, No 2. ? P. 273?288. 28. Ishmukhametov Sh. On the r.e. predecessors of d.r.e. degrees // Arch. Math. Logic. ? 1999. ? V. 38, No 6. ? P. 373?386. 29. Wu G. Isolation and lattice embeddings // J. Symbolic Logic. ? 2002. ? V. 67, No 3. ? P. 1055?1064. 30. Liu J., Wu G. An almost-universal cupping degree // J. Symbolic Logic. ? 2011. ? V. 76, No 4. ? P. 1137?1152. 31. Cooper S.B., Li A. Splitting and cone avoidance in the d.c.e. degrees // Sci. China, Ser. A. ? 2002. ? V. 45, No 9. ? P. 1135?1146. 32. Yamaleev M.M. Splitting in 2-computably enumerable degrees with avoiding cones // Russian Mathematics (Izv. Vuz. Mat.). ? 2009. ? V. 53, No 6. ? P. 63?66. 33. Arslanov M., LaForte G., Slaman T. Relative enumerability in the difference hierarchy // J. Symbolic Logic. ? 1998. ? V. 63, No 2. ? P. 411?420. 34. Li A., Song Y., Wu G. Universal cupping degrees // Theory and Applications of Models of Computation, Proc. 3rd Int. Conf. TAMC 2006 (Lecture Notes in Computer Science, V. 3959). ? Berlin; Heidelberg: Springer-Verlag, 2006. ? P. 721?730. 35. Downey R.G., Li A., Wu G. Complementing cappable degrees in the difference hierarchy // Ann. Pure Appl. Logic. ? 2004. ? V. 125, No 1?3. ? P. 101?118. Поступила в редакцию 01.02.12 Wu, Guohua PhD in Mathematis, Assoiate Professor, Shool of Physial and Mathematial Sienes, Nanyang Tehnologial University, Singapore. Ву, охуа доктор математических наук, адъюнкт-проессор Школы изических и математических наук Наньянского технологического университета, Сингапур. E-mail: guohuantu.edu.sg Yamaleev, Mars Mansurovih Candidate of Physial and Mathematial Sienes, Researh Fellow, Shool of Physial and Mathematial Sienes, Nanyang Tehnologial University, Singapore; Researh Fellow, Lobahevsky Institute of Mathematis and Mehanis, Kazan Federal University, Kazan, Russia. Ямалеев Марс Мансурович кандидат изико-математических наук, научный сотрудник Школы изических и математических наук Наньянского технологического университета, Сингапур; научный сотрудник Института математики и механики им. Н.И. Лобачевского Казанского (Приволжского) едерального университета, г. Казань, оссия. E-mail: ymarsntu.edu.sg, marsiam2yandex.ru

1/--страниц