Georgian Mathematical Journal Volume 9 (2002), Number 1, 161–166

ON SOME PROPERTIES OF r-MAXIMAL SETS AND Q_{1−N}-REDUCIBILITY

R. OMANADZE

Abstract. It is shown that if M_{1}, M_{2} are r-maximal sets and M_{1} ≡ _{Q_{1−N}} M_{2}, then M_{1} ≡ _{m}M_{2}. In addition, we prove that there exists a simultaneously Q_{1−N}- and W -complete recursively enumerable set which is not sQ-complete.

2000 Mathematics Subject Classification: 03D25, 03D30.

Key words and phrases: Recursively enumerable set, maximal set, r-maximal set, Q_{1−N}-reducibility, m-reducibility.

A set A is Q-reducible to a set B, written A ≤ _{Q}B (see [1, p. 207]), if there exists a general recursive function (GRF) f such that (∀x) (x ∈ A ⟺ W_{f(x)} ⊆ B). If, in addition, there exists a GRF g such that (∀x)(∀y) (y ∈ W_{f(x)} ⟹ y < g(x)), then a set A is sQ-reducible to a set B, written A ≤ _{sQ}B.

A set A is Q_{1−N}-reducible to a set B, written A ≤ _{Q_{1−N}} B, if there exists a GRF f such that the following relations hold:

1. (∀x) (x ∈ A ⟺ W_{f(x)} ⊆ B),

2. (∀x)(∀y) (x ≠ y ⟹ W_{f(x)} ∩ W_{f(y)} = ∅),

3. ∪_{x∈N}W_{f(x)} is recursive.

The notion of Q_{1−N}-reducibility was introduced by Bulitko in [2]. In this work some properties of Q_{1−N}-reducibility are investigated. In par-

ticular, it is proved that if M_{1}, M_{2} are r-maximal sets and M_{1} ≡ _{Q_{1−N}} M_{2}, then M_{1} ≡ _{m}M_{2}. It is shown that there exists a simultaneously Q_{1−N}- and W -complete set which is not sQ-complete. All the notions and notation used without definition can be found in [1].

An infinite set A is cohesive if there is no recursively enumerable (RE) set W such that W ∩ A and \overline{W} ∩ A are both infinite.

An infinite set A is r-cohesive if there is no recursive set R such that R ∩ A and \overline{R} ∩ A are both infinite.

An RE set A is maximal (r-maximal) if M is cohesive (r-cohesive). In [3] it is proved that if M is a maximal set and A is an arbitrary set, then

M ≡ _{Q}A ⟹ M ≤ _{m}A.

The following statement shows that a maximal set in this theorem cannot be replaced by an r-maximal one.

ISSN 1072-947X / $8.00 / \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag www.heldermann.de

Proposition 1. There are r-maximal Q-complete sets M_{1} and M_{2} such that M_{1}|_{m}M_{2}.

Proof. Let M_{1} be an r-maximal Q-complete set. Then M_{1} is not a hyperhypersimple set. Therefore there is a GRF f such that

(∀x) (W_{f(x)} ∩ \overline{M}_{1} ≠ ∅), (∀x)(∀y) (x ≠ y ⟹ W_{f(x)} ∩ W_{f(y)} = ∅).

Consider the set

M_{2} = M_{1} ⋃ ( ⋃_{x∈K} W_{f(x)}),

where K is a creative set. Then M_{2} is an r-maximal Q-complete set and |M_{2}\M_{1}| = ∞. (Note that the sets M_{1} and M_{2} could be built using Theorem 1 from [4] and Proposition X.4.3 from [5], too.) In [6] it is shown that if M_{1}, M_{2} are r-maximal sets, M_{1} ⊂ M_{2} and |M_{2}\M_{1}| = ∞, then M_{1}|_{m}M_{2}.

Lemma 1. Let M be an r-maximal set. Then

(∀f GRF) ((|f(\overline{M})| = ∞ & f(\overline{M}) ⊆ \overline{M})
⟹ |\{x : x ∈ \overline{M} & f(x) ≠ x\}| < ∞).  (1)

Proof. Kobzev [7] showed that if M is an r-maximal set, then

(∀f GRF) (|\{f(x) : x ∈ \overline{M} & f(x) ∈ \overline{M} & x ≠ f(x)\}| < ∞).  (2)

Let

(∃f_{1} GRF) (|f_{1}(\overline{M})| = ∞ & f_{1}(\overline{M}) ⊆ \overline{M}
& |\{x : x ∈ \overline{M} & f(x) ≠ x\}| = ∞).  (3)

By (2) and (3), we have |\{f_{1}(x) : x ∈ \overline{M} & f_{1}(x) = x\}| = ∞. From this it follows that

|\{x : x ∈ \overline{M} & f_{1}(x) = x\}| = ∞.  (4)

If the statement of Lemma 1 is false, then from (4) we have that the recursive sets R_{1} = \{x : f_{1}(x) ≠ x\} and R_{2} = \{x : f_{1}(x) = x\} give a splitting of \overline{M} into two infinite sets, which is impossible.

By using the construction of Theorem 1 [3], we shall prove the following statement.

Theorem 1. Let M_{1} and M_{2} be r-maximal sets. Then

M_{1} ≡ _{Q_{1−N}} M_{2} ⟹ M_{1} ≡ _{m}M_{2}.

r-MAXIMAL SETS AND Q_{1−N}-REDUCIBILITY 163

Proof. Let M_{1} and M_{2} be r-maximal sets, M_{1} ≤ _{Q_{1−N}} M_{2} via a GRF f and M_{2} ≤ _{Q_{1−N}} M_{1} via a GRF g. Using the recursively enumerability of the sets M_{1} and M_{2}, we can assume that

(∃f_{1} GRF)(∀x) (W_{f_{1}(x)} = M_{2} ∪ W_{f(x)}),
(∃g_{1} GRF)(∀x) (W_{g_{1}(x)} = M_{1} ∪ W_{g(x)}).

By r-maximality of the sets M_{1} and M_{2}, from the relations above, in particular, it follows that

⋃_{x∈N} W_{f_{1}(x)} = ^{∗}N and ⋃_{x∈N} W_{g_{1}(x)} = ^{∗}N,  (5)

where X = ^{∗}Y stands for |(X\Y) ∪ (Y \X)| < ∞.

Let us define a partial recursive function (PRF) φ as follows. We compute simultaneously {W_{g_{1}(i)}}_{i∈N} and {W_{f_{1}(j)}}_{j∈N} and, for given z, seek for first integers x, y (if they exist) such that z ∈ W_{g_{1}(y)} & y ∈ W_{f_{1}(x)}. If we can find such x and y, then we let φ(z) = x. It is clear that if z ∈ \overline{M}_{1}, and φ(z) is defined, then φ(z) ∈ \overline{M}_{1}.

From the definition of the function φ and from (5) it is clear, that φ is defined for almost all points of the set N.

Lemma 2. |φ(\overline{M}_{1})| = ∞.

Proof. From the recursiveness of the set ∪_{i∈N}W_{g(i)} and from the condition that (∀x)(∀y) (x ≠ y ⟹ W_{g(x)} ∩ W_{g(y)} = ∅) it follows that (∀i) (W_{g(i)} is recursive).

Let us show that (∀x) (|W_{g(x)} ∩ \overline{M}_{1}| < ∞) and, hence,

(∀x) (|W_{g_{1}(x)} ∩ \overline{M}_{1}| < ∞).  (6)

Let us assume the contrary and let

(∃x_{1}) (|W_{g(x_{1})} ∩ \overline{M}_{1}| = ∞).  (7)

Then by the nonrecursiveness of the set \overline{M}_{2},

|\overline{M}_{1}\(W_{g(x_{1})} ∩ \overline{M}_{1})| = ∞.  (8)

Conditions (7) and (8) yield a contradiction to the r-maximality of the set M_{1} since the set W_{g(x_{1})} is recursive.

Thus, condition (6) holds. Now from the definition of the function φ it is clear that |φ(\overline{M}_{1})| = ∞.

Hence the function φ is defined for almost all points of the set N, φ(\overline{M}_{1}) ⊆ \overline{M}_{1} and |φ(\overline{M}_{1})| = ∞.

It is easy to show that Lemma 1 is valid for every PRF φ̃ which is defined for almost all points of the set N. Therefore it is possible apply Lemma 1 for φ and, consequently, we have

|\{x : x ∈ \overline{M}_{1} & φ(x) defined & φ(x) ≠ x\}| < ∞.

Therefore for almost all x we get

x ∈ \overline{M}_{1} ⟹ |\{y : y ∈ W_{f_{1}(x)} & x ∈ W_{g_{1}(y)}\}| = 1.

Then, for almost all x, we have:

x ∈ \overline{M}_{1} ⟹ x ∈ W_{g_{1}(y)} & y ∈ W_{f_{1}(x)} ⟹ y ∈ \overline{M}_{2},
x ∈ M_{1} ⟹ x ∈ W_{g_{1}(y)} & y ∈ W_{f_{1}(x)} ⟹ y ∈ M_{2}.

Let, for all x, f̃(x) be the first element which appears in the computation of the set {y : y ∈ W_{f_{1}(x)} & x ∈ W_{g_{1}(y)}}. Then with the help of f̃ it is possible to construct a GRF which m-reduces the set M_{1} to the set M_{2}.

By symmetry the conditions of the theorem for the sets M_{1} and M_{2} yield M_{2} ≤ _{m}M_{1}.

Theorem 2. Let A be a maximal set and B be an r-maximal set. Then

A ≤ _{Q_{1−N}} B ≤ _{Q}A ⟹ A ≡ _{m}B.

Proof. Let the conditions of the theorem be satisfied. Then by Theorem 1 [3] A ≤ _{m}B. Note here that it is possible to prove Theorem 2 without appealing to Theorem 1 [3]. If it is shown that B ≤ _{m}A, then by the well-known Young theorem (see [1, Theorem XV]) we will have B ≡ _{m}A. Thus, for the proof of Theorem 2 it is sufficient to show that B ≤ _{m}A.

Let A ≤ _{Q_{1−N}} B via a GRF f and B ≤ _{Q}A via a GRF g. Using the recursive enumerability of the sets A and B, we can assume that

(∃f_{1} GRF)(∀x) (W_{f_{1}(x)} = B ∪ W_{f(x)}),
(∃g_{1} GRF)(∀x) ((x ∈ B ⟺ W_{g_{1}(x)} ⊆ A)
& (x ∈ \overline{B} ⟹ |W_{g_{1}(x)} ∩ \overline{A}| < ∞) & A ⊆ W_{g_{1}(x)}).

From the last relations, in particular, we obtain

⋃_{x∈N} W_{f_{1}(x)} = ^{∗}N and ⋃_{x∈N} W_{g_{1}(x)} = ^{∗}N.

Let us define a PRF φ as follows. We compute simultaneously {W_{f(i)}}_{i∈N} and {W_{g_{1}(j)}}_{j∈N} and, for given z, we seek (if they exist)for first integers x, y such that

z ∈ W_{f(y)} & y ∈ W_{g_{1}(x)}.

If we can find such x and y, then we let φ(z) = x. It is clear that if z ∈ \overline{B} and φ(z) is defined, then φ(z) ∈ \overline{B}.

Similarly to the proof of Lemma 2 we can prove

Lemma 3. |φ(\overline{B})| = ∞.

Now the proof of Theorem 2 can be completed in exactly the same way as that of Theorem 1.

Remark. Kobzev [7] proved that if M_{1} and M_{2} are r-maximal sets and M_{1} ≡ bttM_{2}, then M_{1} ≡ _{m}M_{2}.

An RE set A is finitely strongly hypersimple if it is coinfinite and if there is no GRF f such that:

(1) (∀x) (W_{f(x)} ∩ \overline{A} ≠ ∅),

(2) (∀x)(∀y) (x ≠ y ⟹ W_{f(x)} ∩ W_{f(y)} = ∅),

(3) (∀x) (|W_{f(x)}| < ∞),

(4) ∪_{x∈N}W_{f(x)} = N.

It is easy to show that condition (4) can be replaced by the condition (4′) ∪_{x∈N}W_{f(x)} is recursive.

Proposition 2. A coinfinite RE set A is finitely strongly hypersimple if and only if it has no Q_{1−N}-complete superset.

Proof. Let a coinfinite RE set A be not finitely strongly hypersimple. Then there is a GRF f such that conditions (1)–(3) and (4′) are valid. Consider the set

B = A ⋃ ( ⋃_{x∈K} W_{f(x)}),

where K is a creative set and, hence, Q_{1−N}-complete. Then the set B is Q_{1−N}- complete.

Let A be a finitely strongly hypersimple set, B be a Q_{1−N}-complete set and A ⊆ B, C be a RE set such that there is an infinite recursive set R ⊆ \overline{C}, C ≤ _{Q_{1−N}} B via a GRF g, h is a one-to-one GRF, Val h = R. Let us define a GRF f as follows:

(∀x) (W_{f(x)} = W_{gh(x)}).

Then the function f satisfies the conditions (1)–(3) and (4′), hence, the set A is not a finitely strongly hypersimple set, which is a contradiction.

Corollary. There is a Q-complete, but not a Q_{1−N}-complete RE set.

Proof. It is known [4] that there is a Q-complete finitely strongly hypersimple set.

Theorem 1 from [8] asserts that there is a simultaneously Q- and W -complete RE set, which is not sQ-complete. Since there is a Q-complete, but not Q_{1−N}- complete RE set, the following theorem is a stronger statement than Theorem 1 [8].

Theorem 3. There is a simultaneously Q_{1−N}- and W -complete RE set which is not sQ-complete.

Proof. First, let us show that there is a Q_{1−N}-complete, but not a W -complete RE set. Let A be a hypersimple, but not finitely strongly hypersimple set. Then there is a GRF f such that conditions (1)–(3) and (4′) are valid. Consider the set

B = A ⋃ ( ⋃_{x∈K} W_{f(x)}),

where K is a creative set. Then the set B is a Q_{1−N}-complete hypersimple set. It is known [1], that a hypersimple set is not W -complete. Thus there is a Q_{1−N}-complete, but not a W -complete RE set.

It is known [9] that every RE W -degree contains a nowhere simple set. Let A_{1} be a Q_{1−N}-complete but not a W -complete RE set, B_{1} be a W -

complete nowhere simple set. The set A_{1} ⊕ B_{1} = {2x : x ∈ A_{1}} ∪ {2x + 1 : x ∈ B_{1}} is simultaneously Q_{1−N}- and W -complete. Let us assume that the set A_{1}⊕B_{1} is sQ-complete and S is a simple sQ-complete set. Then S ≤ _{sQ}A_{1}⊕B_{1}. From this, by Theorem 2 [8], we have S ≤ _{sQ}A_{1}, i.e., the set A_{1} is sQ-complete, which is a contradiction.

References

1. H. Rogers, Jr. Theory of recursive functions and effective computability. McGraw-Hill, New York, 1967.

2. V. K. Bulitko, On ways for characterizing complete sets. (Russian) Izv. Akad. Nauk SSSR, Ser. Math. 55(1991), No. 2, 227–253; English transl.: Math. USSR, Izv. 38(1992), No. 2, 225–249.

3. R. Sh. Omanadze, Upper semilattice of recursively enumerable Q-degrees. (Russian) Algebra i Logika 23(1984), No. 2, 175–184; English transl.: Algebra and Logic 23(1984), 124–130.

4. R. Sh. Omanadze, Major sets, classes of simple sets, and Q-complete sets. (Russian) Mat. Zametki 71(2002), No. 1, 100-108; English transl.: Math. Notes 71(2002), No. 1, 90–97.

5. R. I. Soare, Recursively enumerable sets and degrees. Springer-Verlag, Berlin, 1987.

6. A. N. Degtev, m-degrees of simple sets. (Russian) Algebra i Logika 11(1972), No. 2, 130–139; English transl.: Algebra and Logic 11(1972), 74–80.

7. G. N. Kobzev, On btt-reducibilities. (Russian) Algebra i Logika 12(1973), No. 4, 433–444; English transl.: Algebra and Logic 12(1973), 242–248.

8. R. Sh. Omanadze, Relations between some reducibilities. (Russian) Algebra i Logika 33(1994), No. 6, 681–688; English transl.: Algebra and Logic 33(1994), 381–385.

9. R. A. Shore, Nowhere simple sets and the lattice of recursively enumerable sets. J. Symb. Logic 43(1978), No. 2, 322–330.

(Received 1.05.2001)

Author’s Address: I. Vekua Institute of Applied Mathematics I. Javakhishvili Tbilisi State University 2, University St., Tbilisi 380043 Georgia E-mail: omanr@viam.hepi.edu.ge