On bounded m-reducibilities

On bounded m-reducibilities

Gespeichert in:
Bibliographische Detailangaben
Datum:2005
1. Verfasser: Belyaev, V.N.
Format: Artikel
Sprache:English
Veröffentlicht: Інститут прикладної математики і механіки НАН України 2005
Schriftenreihe:Algebra and Discrete Mathematics
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/156616
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:On bounded m-reducibilities / V.N. Belyaev // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 2. — С. 1–19. — Бібліогр.: 7 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-156616
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-1566162025-02-10T01:15:17Z On bounded m-reducibilities Belyaev, V.N. 2005 Article On bounded m-reducibilities / V.N. Belyaev // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 2. — С. 1–19. — Бібліогр.: 7 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 03D20, 03D25, 03D30. https://nasplib.isofts.kiev.ua/handle/123456789/156616 en Algebra and Discrete Mathematics application/pdf Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
format Article
author Belyaev, V.N.
spellingShingle Belyaev, V.N.
On bounded m-reducibilities
Algebra and Discrete Mathematics
author_facet Belyaev, V.N.
author_sort Belyaev, V.N.
title On bounded m-reducibilities
title_short On bounded m-reducibilities
title_full On bounded m-reducibilities
title_fullStr On bounded m-reducibilities
title_full_unstemmed On bounded m-reducibilities
title_sort on bounded m-reducibilities
publisher Інститут прикладної математики і механіки НАН України
publishDate 2005
url https://nasplib.isofts.kiev.ua/handle/123456789/156616
citation_txt On bounded m-reducibilities / V.N. Belyaev // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 2. — С. 1–19. — Бібліогр.: 7 назв. — англ.
series Algebra and Discrete Mathematics
work_keys_str_mv AT belyaevvn onboundedmreducibilities
first_indexed 2025-12-02T10:30:04Z
last_indexed 2025-12-02T10:30:04Z
_version_ 1850392082881970176
fulltext Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 2. (2005). pp. 1 – 19 c© Journal “Algebra and Discrete Mathematics” On bounded m-reducibilities Vladimir N. Belyaev Communicated by V.V. Kirichenko Abstract. Conditions for classes F1,F0 of non-decreasing total one-place arithmetic functions to define reducibility ≤m [R 1 R0 ] � {(A,B)|A,B ⊆ N & (∃ r.f. h)(∃f1 ∈ F1)(∃f0 ∈ F0) [A ≤h m B & f0 E h E f1]} where k E l means that function l ma- jors function k almost everywhere are studied. It is proved that the system of these reducibilities is highly ramified, and examples are constructed which differ drastically ≤m [R 1 R0 ] from the standard m-reducibility with respect to systems of degrees. Indecomposable and recursive degrees are considered. 1. Introduction In this paper we consider the consequences for m-reducibility enforced by the restrictions on the volume of oracle access. We mean using of reducibilities with imposing not time or zonal but information restrictions on the access to oracles. Analogous limitations (only upper restrictions) for Turing reducibilities were considered in [4]. We adopt the standard notation [6]. Additionally, CA is the charac- teristic function of set A. I is the identity function on N, i.e., I(x) = x, x ∈ N. As a shorthand, r.f. is often used instead total recursive func- tion. We and ϕe are respectively the recursively enumerable (r.e.) set and the partial recursive function with the index e. We write f E g, when ∃x0∀y[y > x0 ⇒ f(y) 6 g(y)]. We call g as majorant almost everywhere for function f, and f – minorant almost everywhere for g. 2000 Mathematics Subject Classification: 03D20, 03D25, 03D30. Key words and phrases: bounded reducibilities, degrees of unsolvability, singu- lar reducibility, cylinder, indecomposable degree. Jo u rn al A lg eb ra D is cr et e M at h .2 On bounded m-reducibilities T (T+) is the class of all total (non-decreasing) functions f : N → N. T+,∞ is the class of all functions from T+ with an infinite set of values. Let Ri ⊆ T+, i = 0, 1. For any total function f we define two functions: e1f (x) = max{f(y)|y 6 x}, e0f (x) = min{f(y)|x 6 y}. Lemma 1. If f is a r.f. then e1f is non-decreasing r.f. and e0f is non- decreasing limit r.f. Proof. The first statement is trivial. e0f (x) = lim t→∞ h(x, t), where h(x, t) = min{f(x′)|x 6 x′ 6 t}. Let us introduce the main definition: ≤m [R 1 R0 ] {(A,B) ∈ 2N × 2N : ∃ r.f. f ∃h1 ∈ R1 ∃h0 ∈ R0[A ≤f m B & h0 E e0f & e1f E h1]}. It is obvious that ≤m [R 1 R0 ] ⊆≤m . We will call the relation ≤m [R 1 R0 ] as a bounded m-reducibility with upper and low restrictions if this relation is reflexive and transitive. Here R1, R0 are the classes of upper and low restrictions respectively. As a shorthand, we refer to them as upper and low classes. The introducing of low restrictions allows to estimate the complexity of reduced set by the complexity of the oracle and transfers (in some sense) the structure of reduced set on the oracle. For example, it is impossible to reduce an infinite recursive set to an immune set when the low bound of reduction belongs to T+,∞. The rest of the paper is organized as follows. Section 2 introduces additional concepts and results about structural properties of introduced reducibilities. The reflexivity and transitivity of bounded reducibilities are considered in section 3. In sections 4, 6 and 7 we consider some types of introduced reducibilities with respect of systems of unsolvability degrees. In section 5 we consider some algebraic features of the system of bounded reducibilities. 2. Classes of upper and low restrictions Let A,B ⊆ T+. We write A E1 B if (∀f ∈ A)(∃g ∈ B)[f E g] and A E0 B if (∀g ∈ B)(∃f ∈ A)[f E g]. Lemma 2. (1) For Bi ⊆ T+ and Ai ⊆ T+ (i = 0, 1) such that B1 E1 A1 & A0 E0 B0 the inclusion ≤m [B 1 B0 ] ⊆≤m [A 1 A0 ] holds. Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 3 (2) Every relation ≤m [R 1 R0 ] can be formed by countable subclasses R1, R0 of T+. Proof. Indeed, let C ≤m [B 1 B0 ] D. Therefore by the main definition (∃h1 ∈ B1)(∃h0 ∈ B0)[C ≤f m D & h0 E e0f & h1 D e1f ]. By the lemma’s conditions (∃g0 ∈ A0)(∃g1 ∈ A1)[g0 E h0 & g1 D h1] true. Hence [C ≤f m D & (g0 E e0f ) & (e1f E g1)] holds due to transitivity of E , i.e. C ≤m [A 1 A0 ]D. At last, the second statement holds because {eif |f r.f., i = 0, 1} are countable sets. Further we consider classes R0,R1 defining the relations ≤m [R 1 R0 ] as countable unless otherwise is specified. Corollary 1. There exists h?, l? ∈ T+ such that ≤m=≤m [h ? l? ]. Proof. As it is easy to see, l? can be defined in the following way: ∀x l?(x) = 0. We can use an arbitrary non-decreasing total majorant of the class of all r.f. Let h(x, t) = max{ϕi(y)|i 6 x, y 6 x, ϕi(y) ↓ for t steps}. It is clear that h?(x) = lim t→∞ h(x, t) is total and majors almost everywhere all the r.f. 3. Reflexivity and transitivity As it was defined in the beginning, only reflexive and transitive relations could be bounded reducibilities. We begin this section with the following lemma. Lemma 3. Let R ⊆ T+. (1) If {f} 6E1 R holds for a r.f. f with an infinite set of values then there exist A,B ⊆ N such that A ≤f m B & A 6≤m [R T+ ]B. (2) If e0f ∈ T+,∞,R 6E0 {e0f} holds for a r.f. f , then there exist A,B ⊆ N such that A ≤f m B & A 6≤m [T + R ]B. Proof. (1) Let f0, f1, . . . be enumeration of all r.f. with infinite repetitions such that e1f0 , e 1 f1 , . . . have a minorants in R1. Let gn D e1fn , n ∈ N holds for gn ∈ R1. Since {f} 51 R1, we have ∀n ∈ N[f 5 gn]. For every n there exists an infinite sequence of numbers xn0 < xn1 < xn2 < . . . such that: e1fn (xnk) 6 gn(x n k) < f(xnk) < f(xnk+1), k ∈ N; Jo u rn al A lg eb ra D is cr et e M at h .4 On bounded m-reducibilities (the last inequality is possible for f has an infinite set of values) and ∀y[e1fn (y + xn0 ) 6 gn(y + xn0 )]. Let us choose σ : N → N in such a way that ∀n[f(xnσ(n)) > gn(x n σ(n)) & xnσ(n) < xn+1 σ(n+1)]. Define B f(A), A ⊂ {xn σ(n)| n ∈ N}. Next, let us suppose CA is defined on the initial segment [0, xn−1 σ(n−1)]. Now we define CA(xnσ(n)) = 1 ⇔ fn(x n σ(n)) 6∈ B. It is possible, since f(xn σ(n)) > e1fn (xn σ(n)) and the definition of CA(xn σ(n)) does not influence inclusion fn(x n σ(n)) into B. It is clear that A ≤f m B but A 6≤fn m B, since otherwise xn σ(n) brings a contradiction. (2) Let (ri)i∈N be a list of r.f. such that R E0 {e0ri |i ∈ N}. If this list is empty then the lemma is proven. By the condition ∀i[e0ri 6E e0f ] holds. Hence ∀i[ri 6E f ]. That is, there exist infinitely many numbers zik, k = 0, 1, . . . , such that ∀k[ri(z i k) > f(zik)] for every i ∈ N. Now choose a subsequence (yis)s∈N from a sequence (zik)k∈N in such a way that ∀s[ri(y i s) > f(yis)] & ∀s[ri(y i s) < f(yis+1)], i.e., the following systems of inequalities holds · · · < f(yis) < ri(y i s) < f(yis+1) < ri(y i s+1) < . . . There exists a function σ : N → N and a diagonal sequence yi σ(i) such that the following systems of inequalities hold for any i f(yiσ(i)) < ri(y i σ(i)) < f(yi+1 σ(i+1)) < ri+1(y i+1 σ(i+1)). Let us construct the set B by choosing exactly one number from the pair {f(yi σ(i)), ri(y i σ(i))} for all i ∈ N. Next, define the set A as A f−1(B). Thus A ≤f m B. However, as it is easy to see, ∀i[A 6≤ri m B]. Therefore, A ≤f m B &A 6≤m [T + R ] B. Theorem 1. For any R1,R0 ∈ T+ a relation ≤m [R 1 R0 ] is reflexive iff R0 E0 {I} E1 R1. Proof. Sufficiency is obvious, for A ≤m [R 1 R0 ]A with the reducing function I. Necessity. If I has no minorant in R0 then by Lemma 3 there exist A,B ⊆ N such that A ≤I m B, i.e. A = B, but A 6≤m [T + R0 ]A. The same situation occurs when there is no majorant in R1 for I. Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 5 In paper [2] the following theorem was proved. Theorem 2. ≤m [R 1 R0 ]is transitive iff (∀ r.f. f, g)[{e1f , e 1 g} E1 R1 & R0 E0 {e0f , e 0 g} ⇒ {e1f , e 1 g ∈ T+,∞ ⇒ (∃H1 ∈ R1)[e1f◦g E H1]} & {e0f , e 0 g ∈ T+,∞ ⇒ (∃H0 ∈ R0)[H0 E e0f◦g]}] & {(∃d ∈ N)[R0 E0 {d} E1 R1 ⇒ (∀d ∈ N)[R0 E0 {d} E1 R1]]}. Remark 1. In according with the above results it is possible to choose (1) countable systems of non-decreasing total recursive functions that majorize I almost everywhere as upper classes of restrictions and (2) countable systems of a e0f -type (where f is a r.f.) limit recursive functions from T+ that minor I almost everywhere as low classes of restrictions. Let us refer to the such systems as reduced classes. We say reduced classes R0 and R1 are transitive when they define a reducibility, i.e., ≤m [R 1 R0 ] is a reflexive and transitive relation. Corollary 2. (1) Upper reduced class R is a transitive class iff ∀f, g ∈ R ∃h ∈ R s.t.f ◦ g E h. (2) Let R be a low reduced class. If ∀f, g ∈ R ∃h ∈ R s.t. h E f ◦ g then R is a transitive class. Proof. The first statement is obvious by criterion of transitivity. For any r.f. t the inequality t > e0t holds. In additional, if t ∈ T+ then t = e0t . Hence e0f ◦ e 0 g 6 f ◦ g. Next, if t 6 h then e0t 6 e0h. Therefore e0f ◦ e 0 g 6 e0f◦g for any total f, g. Consequently, if e0f ◦ e 0 g has a minorant then e0f◦g has too. This corollary is useful in constructing of concrete bounded reducibil- ities that are considered in the following sections. 4. Singular reducibilities In this section we consider the one-element classes which form reducibili- ties. We refer to them as singular classes. And as a shorthand, we refer to such reducibilities as singular reducibilities. They will play an important role further. Jo u rn al A lg eb ra D is cr et e M at h .6 On bounded m-reducibilities Let f, g ∈ T+, f > g. Let us define f̂g(0) = f(0) and f̂g(x+ 1) = { f̂g(x), f̂g(x) > g(x+ 1), f(x+ 1), f̂g(x) < g(x+ 1). We say function g is a h-hybrid if it is equal to ĥg or ĝh almost everywhere. We say x is a minimal point of function t : N → N iff (∀y > x)[t(y) > t(x)]. Denote by Mt the set of all minimal points of t. Lemma 4. Let f̂g is defined. (1) f̂g ∈ T+. (2) g ≤ f̂g ≤ f . (3) If g E I E f then f̂g ◦ f̂g = f̂g almost everywhere. (4) (∀h ∈ T+)[h = ĥh]. (5) For all h, g ∈ T+ if h E g and g ◦ g E h ◦ g or g E h and h ◦ g E g ◦ g then there exists h-hybrid function f such that h E g E f or f E g E h respectively. In additional, if h is equal to I almost everywhere then g is I-hybrid. Proof. (1),(2) Obvious. (3) By the definition f̂g is a stair-like non-decreasing function. Let us consider an equivalence relation x ≡� fg y ⇔ f̂g(x) = f̂g(y). Starting with some x′ every ≡� fg -equivalence class is a segment of N which includes (since g E I E f) the value of f̂g at its elements. That is f̂g ◦ f̂g = f̂g almost everywhere. (4) Obvious. (5) Let us consider the case g E h & h ◦ g E g ◦ g. By the non- decreasing of g, h the equality h ◦ g = g ◦ g holds almost everywhere. Thus h and g are equal on Mg almost everywhere. We assume |Mg| = ∞ (the case |Mg| <∞ is obvious.) Let {xk|k ∈ N} be an enumeration of Mg in increasing order. Then the system of segments Nk = {y|xk 6 y < xk+1}, k ∈ N is a partition of N. Next, define f(x) = g(xk), x ∈ Nk, k ∈ N. Now the statement is obvious. At last, let h = I almost everywhere. Then g = g ◦ g almost every- where. Let us consider a sufficiently large x ∈ Mg such that g(x) = g ◦ g(x). Then x + 1 > g(x + 1) > g(x). Next, if x + 1 > g(x + 1) then g(x + 1) 6 x and, therefore, g(x + 1) > g(g(x + 1)). Obtained contra- diction holds the equality g = I for all sufficiently large x + 1, x ∈ Mg. Hence, g is I-hybrid. Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 7 Theorem 3. For every transitive upper and low classes R1,R0 ⊆ T+ and every f, g ∈ T+ such that g E I E f the following relations are reducibilities: ≤m [ � fI R0 ], ≤m [R 1 � Ig ]. Proof. Since f, g ∈ T+ then f̂I, Îg ∈ T+, Îg E I E f̂I by the Lemma 4. And in according with the third point the classes {f̂I} and {Îg} are closed with respect to superpositions. Hence, the result holds by Theo- rem 1 and 2. Theorem 4. (1) Upper reduced singular class is transitive iff it consist of hybrid func- tion ĥI for some r.f. h. (2) If low reduced singular transitive class consists of function e0h, where h is a r.f. then e0t◦t = e0h = e0t , where t = min(h, I). If e0h is I- hybrid, where h is a such r.f. that h E I, then {e0h} is a singular transitive low class. Proof. (1) At first, let us consider an upper class {f}. The function f is a non-decreasing r.f. and by Corollary 2 I E f, f ◦ f E f holds. Hence, f is a I-hybrid by Lemma 4(5). (2) Let us suppose {e0h} is given singular reduced transitive class. By the criterion of reflexivity e0h E I must hold. Next, if t = min(h, I) then from e0h E I the equality e0t = e0h is true almost everywhere. Indeed, the values of functions h, e0h are equal on all sufficiently large x ∈ Mh and not exceed x. But t and h take on the same values at such x. We assume e0t ∈ T+,∞ (otherwise e0t is hybrid obviously.) Next, we have e0t E e0t◦t by the condition of transitivity. Let x be a large enough in Mh again. From t(x) = h(x) = e0h(x) = e0t (x) the inequality t(t(x)) 6 e0t (x) follows. If the last inequality is a strict one for infinitely many elements of Mh then we have the contradiction with e0t E e0t◦t. That is e0t and e0t◦t must be equal almost everywhere on Mh (= Mt). Hence, e0t = e0t◦t almost everywhere. It is well known that the set of minimal points of some r.f. is hy- perimmune or recursive. In the latter case e0h is recursive too. Then, since e0h is non-decreasing and by the condition of transitivity the rela- tion e0h E e0h ◦ e 0 h must hold. Thus, e0h is I-hybrid by Lemma 4(5). The last statement of the theorem was actually proved in Theorem 3. Some functions can form singular classes not being hybrid. For exam- ple, the total majorant of the class of all r.f. forms the upper transitive Jo u rn al A lg eb ra D is cr et e M at h .8 On bounded m-reducibilities singular class. Analogously, the total minorant h ∈ T+,∞ of all e0f ∈ T+,∞ (f is a r.f.) forms the low transitive singular class. 5. The hierarchy of reducibilities We saw that bounded m-reducibilities are partially ordered by the re- lation of inclusion. In this section we study the poset. We denote by M the set of bounded reducibilities and by ⊆ the considered relation on M. By Remark 1 for every bounded m-reducibility there is an equal ≤m [F 1 F0 ]-reducibility, where F1,F0 are reduced classes. Let us consider arbitrary reducibilities ≤α=≤m [A 1 A0 ] and ≤β=≤m [B 1 B0 ], where Ai,Bi are reduced classes (i = 0, 1). By Lemma 2 and 3 it is possible to show, that 1) ≤α⊆≤β if and only if A1 E1 B1, B0 E0 A0, so that, 2) ≤α=≤β if and only if B1 E1 A1, A0 E0 B0 & A1 E1 B1, B0 E0 A0 Define ∨ and ∧ on M as follows: ≤α ∧ ≤β ≤m [ � C1 � C0 ], where C1, C0 are subclasses of T+ C1 {f |f − r.f., I E f ∃g ∈ A1 ∃h ∈ B1 : f E g & f E h}, C0 {f |f − limit r.f., I D f ∃g ∈ A0 ∃h ∈ B0 : f D g & f D h}, and F̃ is the closure of F under composition. Define similarly ∨ : ≤α ∨ ≤β ≤m [ � D1 � D0 ], where D1, D0 are subclasses of T+ D1 {f |f − r.f., I E f [∃g ∈ A1, f E g] ∨ [∃h ∈ B1 : f E h]}, D0 {f |f − limit r.f., I D f [∃g ∈ A0, f D g] ∨ [∃h ∈ B0 : f D h]}. Observe that I ∈ Ci and I ∈ Di (i = 0, 1), so classes in definition are not empty. The proof of the following lemma is obvious: Lemma 5. For every ≤α,≤β∈ M 1) ≤α ∨ ≤β∈ M, ≤α ∧ ≤β∈ M; 2) ≤α⊆≤α ∨ ≤β, ≤α ∧ ≤β⊆≤α . Example. Let R denote the set of all even integers. Then functions x + CR(x) and x+ CR(x) are I-hybrid and relations ≤α ≤m [ {I+CR} {I} ] and ≤α ≤m [ {I+C R } {I} ] are reducibilities by Theorem 3. It is easy to see that ≤α ∧ ≤β=≤m [ {I} {I}], ≤α ∨ ≤β=≤m [I + {I}], Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 9 where I+ {I + c|c ∈ N}. The first reducibility is minimal element of M. Let ≤γ ≤m [C 1 C0 ], Ci are reduced classes (i = 0, 1) and ≤γ is some up- per bound for ≤α and ≤β . This means that A1 E1 C1, B1 E1 C1, C0 E0 A0, C0 E0 B0. Now, let ≤λ= ≤m [D 1 D0 ], where ≤λ ≤α ∨ ≤β . Let us show that D1 E1 C1, C0 E0 D0. Really, in the opposite case there is a function f from D1 such that f 5 C1. But f = f1 · f2 . . . fn−1 · fn and ∀i = 1, n ∃hi : [hi ∈ A1 ∨ hi ∈ B1] & fi E hi holds by the definition of D1. On the other hand ∀i = 1, n ∃ci : ci ∈ C1 : ci D hi. Thus f E h1 · h2 . . . hn−1 · hn E c1 · c2 . . . cn−1 · cn Since C1 must contain the majorant for the composition of arbitrary own elements, we have ∃c∗ ∈ C1 : c1 · c2 . . . cn−1 · cn E c∗, therefore f E c∗ E C1. Analogously C0 E0 D0. Therefore, ≤λ⊆≤γ and ≤λ is the least upper bound for ≤α and ≤β . Analogously, let ≤γ ≤m [C 1 C0 ], Ci are reduced classes (i = 0, 1) and ≤γ is some lower bound for reducibilities ≤α and ≤β . This means that A1 D1 C1, B1 D1 C1, C0 D0 A0, C0 D0 B0. Now, let ≤λ=≤m [D 1 D0 ], where ≤λ ≤α ∧ ≤β . Let us show that D1 D1 C1, C0 D0 D0. Really, let c ∈ C1. By condition there are a ∈ A1, b ∈ B1 such that c E a and c E b. Then f = min(a, b) belongs to D1 and c E f. Similarly, it can be proved C0 D0 D0. Therefore ≤γ⊆≤λ and ≤λ is the greatest lower bound for ≤α and ≤β . Thus the following proposition has been proved: Proposition 1. M is lattice under ∨ and ∧ . Denote this lattice as L. We saw that L has the greatest element – the unbounded m-reducibility and the least element – the reducibility ≤m [ {I} {I}]. Let us consider other features of L. It is easy to see the relation ≤m [T + T+,∞ ] is reducibility. It plays an important role, so we introduce special notation ≤m∗ ≤m [T + T+,∞ ] and will call it as m∗-reducibility. Theorem 5. L has unique co-atom. L has no atoms. Proof. In opposite to the latter statement assume that ≤m [A 1 A0 ] is an atom in L. Then at least in one of the classes A1 or A0 there is a function a and infinite recursive set R such that one from the following take place: ∀x ∈ R a(x) > x if a ∈ A1 ∀x ∈ R a(x) < x if a ∈ A0 Jo u rn al A lg eb ra D is cr et e M at h .10 On bounded m-reducibilities Assume a ∈ A0. Define R1 {r(2i)|i ∈ N}, where r(i) runs through R. Now, define a′ = I − CR1 , B0 {a′}. Then a′ is I-hybrid and ≤m [A 1 B0 ] is a reducibility. In additional ≤m [A 1 B0 ] ⊆≤m [A 1 A0 ] and ≤m [A 1 B0 ] 6=≤m [A 1 A0 ]. The latter holds by Lemma 3. Obvious, ≤m [A 1 B0 ] 6=≤m [ {I} {I}]. In order to prove the first statement we note that reducibility ≤m [F 1 F0 ] can include m∗-reducibility only if F0 E0 T+,∞. But we can essentially expand the class of lower bounds T+,∞ by including constants only. But then the function 0 must be in F0 due to transitivity criterion. Therefore, a reducibility ≤m [F 1 F0 ] must be equal to the unbounded m-reducibility. So m∗-reducibility is a co-atom in L. Assume ≤m [A 1 A0 ] is another co-atom in L. Since ≤m [A 1 A0 ] and ≤m [T + T+,∞ ] are incomparable with respect to ⊆ relations A1 E1 T+ & T+,∞ 50 A0 or A1 51 T+ & T+,∞ E0 A0 must take place. The second case is impossible, obvious. In the first case T+,∞ 50 A0 means that A0 must contain the function 0 (see above.) To finish the proof we need the following auxiliary notions (see [7]): recursive function Φ(m,x) is universal for class S if ∀ϕ ∈ S ∃m : ϕ(·) = Φ(m, ·) and ∀m ∈ N Φ(m,x) ∈ S. Let S and S1 are classes of r.f. If for every fj ′ ∈ S1 there is fi ∈ S and infinite set A such that:(∀x ∈ A)[f ′j(x) 6 fi(x)], then S weakly majors S1. In paper [7] the following proposition was proved: Proposition 2. (1) If S has universal r.f. then there exists r.f. h such that S E1 {h} (2) If S weakly majors the class of all r.f. then S has no universal r.f. Let us return to the theorem proof. It follows from above that ≤m [F 1 F0 ] cannot be a co-atom in L if F1 is majorized by some class S with universal r.f. As has been stated above, if the reducibility ≤m [F 1 F0 ] is another co- atom then F0 must contain function 0. On the other hand it must exist r.f. h such that {h} 51 F1 and ˜F1 ∪ {h} D1 T+. But this means that class {h} weakly majors class F1. By the assumption ˜F1 ∪ {h} majors the class of all r.f. Now, define H {̃h}. It’s obvious, H has universal r.f. In additional ˜F1 ∪ {h} is weakly majored by H. It follows from this that H weakly majors the class of all r.f. This contradicts the assumption Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 11 that L has co-atoms not equal to ≤m∗ . This completes the proof of the theorem. The reducibility hierarchy is not trivial. In paper [2] the following theorem was proved: Theorem 6. Every countable partial ordering can be isomorphically em- bedded into L. In Fig.1 the structure of L is shown schematically. Three reducibilities of "special" type are picked out here. The other reducibilities may be named as reducibilities of "general" type. In the area between ≤m [ {I} {I}] and ≤m∗ the reducibilities with low restrictions from T+,∞ are placed. In the following sections we will focus on the special subclass of the latter reducibilities. They are reducibilities with enumerable classes of restrictions. 6. The structure of recursive degrees In this section we consider the structure of degrees of recursive sets for bounded m-reducibilities. For arbitrary bounded reducibility we are in- terested in the quantity of degrees, the density of their partial order and the possibility to embed other posets into the order. In fact, we almost don’t use the information of the oracles in re- ductions here. For the classical m-reducibility there are three recursive degrees only: {∅}, {N} and all other recursive sets (since ≤m does not suppose any restriction on the reducing function apart from its recursive- ness.) Clearly, the same is true when we set upper restrictions only, i.e. when we deal with reducibility ≤m [F T+ ] for some F. L : ≤m ≤m ∗ ≤m [ {I} {I}] t t t Figure 1: The structure of bounded � � � � � � � � � � � � ∅ N finite co-finite |A| = |A| = ∞ Figure 2: The structure of recursive ≤m∗ -degrees � � � m-reducibilities Jo u rn al A lg eb ra D is cr et e M at h .12 On bounded m-reducibilities The quantity of degrees can increase when we introduce non-trivial low restrictions on reducing function. Actually, if there are no upper bounds and low restrictions are represented by the subclass of T+,∞ then we have five degrees (see Fig.2): {∅}, {N}, all finite sets, all co-finite sets, other recursive sets (i.e. infinite recursive sets with infinite comple- ment.)Yet, if in addition we put upper restrictions, the fifth class can fall to other degrees. We call R as enumerable class if there is a r.f. s such that R = {ϕs(i)|i ∈ N}. Proposition 3. Let ≤m [F 1 F0 ] a reducibility such that F0 ⊆ T+,∞ and there are enumerable classes Φ0,Φ1 of recursive functions from T+,∞ which minors F0 and majors F1 respectively. Then there are recursive sets A and B such that |A| = |A| = |B| = |B| = ∞ and A 6≤m [F 1 F0 ]B. Proof. The case when for every r.f. f such that F0 E f E F1 ⇒ f = I almost everywhere is obvious (we can take then two disjoint infinite recursive sets.) Let γ be some recursive function of large oscillation and r.f. e0 and e1 enumerate Φ0 and Φ1 respectively. We construct recursive A and B in such a way that CA and CB are defined at step n on initial segment σn : S t e p 0: Define CA(0) = CB(0), σ0 = {0}; S t e p n + 1 : Define CB(‖σn‖) = 1, CA(‖σn‖) = 0, where ‖σn‖ is the length of σn. Next, let γ(n + 1) = 〈l, r〉. Let us find first x : x > ‖σn‖ such that ϕe0(l)(x) > ‖σn‖ (it is possible because Φ0,Φ1 ⊆ T+,∞) and define CA(x) = 1, CB(x) = 0, σn+1 = [0, ϕe1(r)(x)]. At last, let CA(t) = CB(t) = 0 for every t from σn+1 \ ([0, ‖σn‖] ∪ {x}). Since A and B are enumerating in increasing order, they are recur- sive.Let assume for some r.f. t A ≤t m [F 1 F0 ]B holds. This means that there are f0 ∈ F0, f1 ∈ F1 and numbers l∗, r∗ such that ϕe0(l∗) E f0 E t E f1 E ϕe1(r∗) On the other hand for l∗ and r∗ there is an infinite computable sequence {ni} : ∀i γ(ni) = 〈l∗, r∗〉. Let us consider an infinite recursive set A∗ A ∩ (∪i∈N(σni \ σni−1)) By construction for every x from A∗ there are no elements from B in the segment [ϕe0(l∗)(x), ϕe1(r∗)(x)]. The latter is true and for the segment [f0(x), f1(x)]. We come to a contradiction with the reduction. Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 13 Below by a non-trivial interval for reducibility ≤α we mean a pair (A,B) such that: 1) A <α B, i.e. A ≤α B and B 6≤α A; 2) A 6∈ {∅,N}. Theorem 7. Let ≤α ≤m [F 1 F0 ] a reducibility such that F0 ⊆ T+,∞ and there are enumerable classes Φ0,Φ1 of recursive functions from T+,∞ which minors F0 and majors F1 respectively. Then there is an isomor- phical embedding of an arbitrary finite poset into any non-trivial interval of the structure of recursive ≤α-degrees. Proof. Let A < f α B and r.f. e0 and e1 enumerates Φ0 and Φ1 respectively. Since B 6≤α A then for every pair (m,n) there is an infinite set Rm,n such that ∀x ∈ Rm,n CB(x) = σ & ∀y : y ∈ [ϕe0(m)(x), ϕe1(n)(x)] CA(y) = 1 − σ, where σ = 0, 1 (in the opposite case the functions ϕe0(m) and ϕe1(n) are bounds of reduction B ≤m [F 1 F0 ]A and the reducing function can be constructed by the choosing of appropriate numbers from segment [ϕe0(m)(x), ϕe1(n)(x)] for every x sufficiently large.) It is easy to see all Rm,n are recursive. Further, we construct recursive set X. Denote t-th element of X as X(t) and define it at step t : S t e p 0: X(0) = R0,0(0); S t e p t: if t = pk for some prime p, p > 2 then X(t) = min y{y ∈ Rm,n & y > X(t− 1)}, where k = 〈m,n, l〉; else X(t) = X(t− 1) + 1. Therefore, for every prime p, p > 2 we have ∀m,n |{X(pt)|t ∈ N} ∩Rm,n| = ∞, (∗) that is the set {X(pt)|t ∈ N} is "bad" for all r.f. which have a minorants in F0 and a majorants in F1. It is well known that every partial ordering (M,≤l) can be isomor- phically embedded into partial ordering ({Si|i ∈ M},⊆), where Si = {m ∈M |m ≤l i}. Let ψ is one-to-one map from given finite poset M into set {p|p - prime , p > 2}. Define S ψ i = ⋃ p∈ψ(Si) {pt|t > 1} and recursive Xi = X(Sψ i ) (we write X(S) as a shortening of {X(k)|k ∈ S}.) It is clear Jo u rn al A lg eb ra D is cr et e M at h .14 On bounded m-reducibilities that (M,≤l) can be isomorphically embedded into ({Xi|i ∈ M},⊂). At last, define the family of sets Ai, i ∈M : CAi(x) = (CA(x) + CXi(x)) mod 2. Let i, j ∈M and i <l j. Then Xi ⊂ Xj and |Xj \Xi| = ∞. It follows from this that Ai ≤ fij α Aj , where fij(x) = { f(x) if x ∈ Xj \Xi x otherwise On the other hand Aj 6≤α A i since construction of Xi and Xj . Indeed, in the opposite case Aj ≤h α A i and there are m?, n? such that ϕe0(m?) and ϕe1(n?) are low and upper bounds for h respectively. Since Xi ⊂ Xj there is prime p? such that {X(pt?)|t ∈ N} ⊆ Xj \ Xi. On the other hand |{X(pt?)|t ∈ N} ∩Rm?,n? | = ∞ since condition (*). Thus, h fails on infinitely many numbers. If i||lj in (M,≤l) then |Xi \ Xj | = |Xj \ Xi| = ∞. Thus Aj 6≤α A i and Ai 6≤α A j as above. At last, for all i ∈M 1) A ≤fi α Ai, where fi(x) = { f(x) if x ∈ Xi; x otherwise. 2) Ai 6≤α A because of property of Xi; 3) Ai ≤gi α B, where gi(x) = { x if x ∈ Xi; f(x) otherwise. 4) B 6≤α A i, because of property of X \Xi. That completes the proof. Corollary 3. For the reducibility obeying the conditions of the theorem the structure of degrees for simultaneously infinite and co-infinite recur- sive sets is dense. A more detailed analysis shows that it is possible to replace finite poset by countable poset of some "constructive" type. 7. m ∗-reducibility I this section we compare ≤m∗ with ≤1 and study consequences for m- reducibility enforced by the essential low bounds using. First trivial fact concerns to isolated sets [6]: A ≤1 B & B is isolated ⇒ A is isolated. Clearly, the same is true for m∗-reducibility. Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 15 Lemma 6. ≤1(≤m∗(≤m Proof. Let A ≤f 1 B. It is obvious that e0f ∈ T+,∞. That is A ≤m∗ B. Let C,D be finite sets and |C| < |D|. Then C <1 D and C ≡m∗ D. That is ≤1 6=≤m∗ . Thus, the first relation is proven. Let A be an infinite recursive set and B be an immune set, b1 ∈ B, b2 ∈ B̄. Then A ≤f m B where f(x) = b1 for x ∈ A and f(x) = b2 for x ∈ Ā. But the existence of an infinite enumerable subset of B holds by reduction A ≤m∗ B. That is ≤m∗ 6=≤m . Thus, the second relation is proven. The following theorem is an example of low bounds information using. Let us remind [6] that set A is T -complete iff B ≤T A for any r.e. B. It is well known that in contrast to m-reducibility T -complete set can be simple. It is convenient to describe classes of T -complete simple sets by notion of "weak effectivisation" [1]: recursively enumerable set A is weakly effectively simple if and only if there exists a total f such that f ≤T A and ∀z[Wz ⊂ A ⇒ |Wz| 6 f(x)]. Recursively enumerable set A is weakly 2-strictly recursively simple if and only if there exists a total f such that f ≤T A and ∀z[Wz ⊂ A⇒ max{Wz} 6 f(x)]. Lachlan showed that A is T -complete and simple ⇐⇒ A is weakly effectively simple. Arslanov in [1] showed that A is weakly effectively simple ⇐⇒ A is weakly 2-strictly recursively simple. Let us now introduce the following notations: f−↓(x) = min{y : f(y) > x}. It is clear that f−↓ is computable on f. Theorem 8. Let B be an r.e. set. If 1) A ≤m∗ B and h ∈ T+,∞ is low bound in reduction, 2) B is weakly 2-strictly recursively simple with function f, 3) h−↓ ◦ f ≤T A then A is T -complete. Proof. Let t be reducing function in 1). Every r.e. subset of B is finite since condition 2). Obviously, the same is for A. We need to estimate maximal elements of r.e. subsets of A. That is we need to estimate partial function m(z) max y{y ∈Wz, Wz ⊆ A}. There exists recursive function g such thatWg(z) = t(Wz). Since condition 1) the inequality h(m(z)) 6 t(m(z)) holds. Next, observe that t(m(z)) 6 Jo u rn al A lg eb ra D is cr et e M at h .16 On bounded m-reducibilities max{Wg(z)} 6 f(g(z)). That is h(m(z)) 6 f(g(z)) and inequalitym(z) 6 h−↓f(g(z)) take place. Hence ∀z[Wz ⊆ A⇒ max{Wz} 6 h−↓f(g(z))]. But h−↓ ◦ f ◦ g ≤T A since condition 3), thus A is weakly 2-strictly recursively simple with function h−↓ ◦ f ◦ g. Thus, A is T -complete. We note that analogous statements are true for h-simple and pseudo- simple sets. The first condition (h ∈ T+,∞) is essential in above theorem. Indeed, let B be Post’s simple set [6]. It is well known B is effectively simple (see [1]) with r.f. f(x) = 2x+ 1, that is B is T -complete. Define A = N ⊕ ∅. It is easy to see other conditions are true. But A is not complete, obviously. The following theorem characterizes cylinders in terms of m∗: Theorem 9. A is a cylinder iff (∀B)[B ≤m A⇒ B ≤m∗ A]. Proof. Necessity is obvious by Lemma 6 and the cylinder criterion [6] : A is a cylinder iff (∀B)[B ≤m A⇒ B ≤1 A]. Sufficiency. We will use another cylinder criterion: A is a cylinder iff (∃ r.f. g)(∀x)[g(x) > x & x ∈ A⇔ g(x) ∈ A]. By the conditions of the theorem A × N ≤f m∗ A holds, where f is some r.f. Since f has a minorant in T+,∞ the set Ix = {i|f(〈x, i〉) 6 x, i ∈ N} is finite. Define g(x) = f(〈x,mx〉), where mx = min{i|i 6∈ Ix}. Hence, g is total r.f. and g(x) > x for every x. By the theorem conditions and definition of A× N we have: (∀i)[x ∈ A ⇐⇒ 〈x, i〉 ∈ A× N ⇐⇒ f(〈x, i〉) ∈ A]. Thus x ∈ A iff g(x) ∈ A and A is a cylinder. Corollary 4. A is a cylinder iff A ≡m∗ A× N The degree structure created by a reducibility inside the degrees of another and weaker reducibility has been discussed in the literature. A.Degtev actually showed in [5] that the structure of 1-degrees inside the m∗-degree of any simple set neither is upper nor low semi-lattice. An m-degree is indecomposable if it consists of a single 1-degree [5]. We callm-degree asm∗-indecomposable if it consists of a singlem∗-degree. Corollary 5. m-degree of a set A is indecomposable iff it is m∗-indecomposable. Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 17 Proof. We note only that for every B such that B ≡m A the equivalence B ≡m∗ B × N holds. Thus A is a cylinder by Corollary 4. Now it’s naturally to ask about the structure of degrees of a stronger bounded reducibility inside the degrees of a weaker bounded reducibility. Let us consider m∗-reducibility as a weaker and ≤m [T + R ]-reducibility as a stronger bounded reducibility, where R is the subclass of T+,∞. We generalize the definition from [6] of the operator ⊕ . Let r.f. s enumerates indexes of some functions from T+,∞, i.e. {ϕs(i)|i ∈ N} ⊆ T+,∞. Now, define r.f. t and a map ψ : 2N → 2N in the following way: t(0) = 0, t(x) = µk[k > t(x− 1) & ϕs(i) i6x (k) > x], ψ({x}) = [t(x), t(x+ 1)) It is clear t ∈ T+,∞. For simplicity we write ψ(x) instead of ψ({x}) when x is a number. Finally, define ⊕ s as follows: ∀x, y y ∈ ψ(x) C� s A(y) = CA(x), therefore, x ∈ A ⇐⇒ ψ(x) ⊆ ⊕ s A. Lemma 7. If A is not a cylinder then ⊕ s A is not a cylinder too. Proof. In the opposite case there is a r.f. f such that ∀y f(y) > y & y ∈ B ⇐⇒ f(y) ∈ B where B ⊕ s A. Now we define g(x) for every x. Letm(x) is the maximal element of ψ(x). By construction of ψ we have: x ∈ A ⇐⇒ ψ(x) ⊆ B ⇐⇒ m(x) ∈ B ⇐⇒ f(m(x)) ∈ B. We set g(x) as ψ−1(f(m(x))). It is clear that g(x) > x and g is a r.f. Therefore, A is a cylinder, contrary to the assumption. Lemma 8. Let A be not a cylinder and the class M {ϕs(i)|i ∈ N} minors the class R of low bounds of ≤m [T + R ]-reducibility. Then ⊕ s A 6≤m [T + R ]A. Jo u rn al A lg eb ra D is cr et e M at h .18 On bounded m-reducibilities Proof. Assume ⊕ s A ≤f m [TR]A. By condition there is a number j such that ϕs(j) E f. Now, according to the definition of the operator ⊕ s we have x ∈ A ⇐⇒ ψ(x) ⊆ ⊕ s A. But by the assumption ψ(x) ⊆ ⊕ s A ⇐⇒ f(ψ(x)) ⊆ A The following inequalities are obvious: max{f(ψ(x))} > f(t(x)) > ϕs(j)(t(x)). In additional, if x > j then ϕs(j)(t(x)) > x holds according to the de- finition of t. Therefore, ∀x x > j max{f(ψ(x))} > x, and thus g(x) = max{f(ψ(x))} is a r.f. obeying x ∈ A ⇐⇒ g(x) ∈ A. Yet, then A is a cylinder, that contradicts to the condition of the lemma. On the other hand ⊕ s A ≤h m∗ A, where h(x) = max{k|t(k) 6 x}. Therefore, ⊕ s A ≡m∗ A. Let R is defined as in Lemma 8 above. Theorem 10. If m∗-degree includes more than one ≤m [T + R ]-degree then it includes infinite chain of ≤m [T + R ]-degrees. Proof. To finish the proof we note that a m∗-degree obeying the assump- tion must include non-cylinder A. Thus A <m [T + R ] ⊕ s A <m [T + R ] ⊕ s ⊕ s A < . . . . This is what the theorem states. 8. Conclusion and future research In the previous sections we discovered the system of reducibilities which arose from the classical many-to-one reducibility by imposing restrictions on reducing functions. The motivation is an attempt to refine (detail) some results of classical recursion theory. In section 6 we saw that the restriction on oracle access separated the family of recursive sets and in such way it formed some classification of the latter. The construction and analysis of nontrivial models for such classifications is future research direction. The further investigation of the relationship betweenm∗-reducibility and 1-reducibility are interesting Jo u rn al A lg eb ra D is cr et e M at h .V. N. Belyaev 19 too. Here we note the problem of describing of m∗-degrees consisting of a single 1-degree. We analyze also the relationship between the restrictions and the completeness for corresponding reducibilities. References [1] M. M. Arslanov. Local theory of unsolvability degrees and ∆ 0 2-sets. KGU press, Kazan,1987. (In Russian) [2] V. N. Belyaev, V. K. Bulitko. m-reducibility with upper and low limits// Mathema- tical Notes.— 2001.— Vol. 70, No 1.— pp. 12–21. [3] V. N. Belyaev. Reducibility ≤m with upper and low limits // Bull. Symbolic Logic.— 2002.— Vol. 8, No 1.— pp. 166–167. [4] V. K. Bulitko. About segment complexity of Turing reductions//Math. Log. Quart.—1999.— Vol. 45, No 4.— pp.561 - 571. [5] A. N. Degtev. Partial ordered sets of 1-degrees inside enumerable m- degrees//Algebra and Logic.— 1976.— Vol. 15, No 3.— pp. 248-266. (In Russian) [6] Rogers, H., Jr. Theory of recursive functions and effective computability McGrow- Hill, New York, 1967. [7] V. V. Shkira. On universal functions for some classes of recursive functions and sets //Mathematical logic, algorithms and set theory. Trudy MIAN. Nauka, Moscow.— 1973.—Vol. 133.— pp.243-250. (In Russian) Contact information V. N. Belyaev Department of Computer Algebra and Discrete Mathematics, Odessa National University, Dvoranskaja st. 2, Odessa, Ukraine, 65026 E-Mail: vbelyaev@paco.net Received by the editors: 11.04.2005 and final form in 04.07.2005.

Ähnliche Einträge