close

Вход

Забыли?

вход по аккаунту

?

Isolation motivations and applications.

код для вставкиСкачать
Том 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
Документ
Категория
Без категории
Просмотров
2
Размер файла
277 Кб
Теги
isolation, application, motivation
1/--страниц
Пожаловаться на содержимое документа