Abstract: A Т-complete wtt-mitotic set is composed, which is not tt-mitotic. A relation is found out between
structure of computably enumerable sets and the density of their unsolvability degrees.
Let us adduce some definitions:
A computably enumerable (c.e.) set is tt - mitotic (wtt - mitotic) set if it is the disjoint union of two c.e.
sets both of the same tt -degree ( wtt -degree) of unsolvability.
Let A be an infinite set. f majorize A if ( ( ) ) n ∀n f n ≥ z , where z0 ,z1, are the members of A
in strictly increasing order.
A is hyperimmune (abbreviated h-immune) if A is infinite and (∀ recursive f ) f does not majorize A.
A is hypersimple if A is c.e. and A is hyperimmune.
A is hyperhyperimmune if A is infinite and ¬(∃ recursive f ) so that
[( ) &( )( ) ∀u Wf (u) is finite & Wf (u) A ≠ ∅ ∀u ∀v u ≠ v ⇒Wf (u) Wf (v) = ∅ ].
A is hyperhypersimple if A is computably enumerable and A is hyperhyperimmune.
We shall denote T-degrees by small bold Latin letters.
A degree a ≤ 0′ is low if a′ = 0′(i.e. if the jumpa′ has the lowest degree possible).
Theorem (Martin 6). a is the degree of a maximal set ⇔ a is the degree of a hypersimple set ⇔ a
is c.e. and a′ = 0′′ .
Theorem (R. Robinson 8). Let b and c be c.e. degrees such that c < b and c is low. Then there
exist incomparable low c.e. degrees 0 a and a1 , such that 0 1 b = a ∪ a and a > c i , for i < 2 .
Griffiths (3) proved that there is a low c.e. T-degree u such that if v is a c.e. T-degree and u ≤ v then
v is not completely mitotic.
In this article it is proved the following theorem:
Theorem. There exists a low c.e. T-degree u such that if v is a c.e. T-degree and u ≤ v then v contains
hypersimple wtt -mitotic set, which is not tt -mitotic.
From the abovementioned theorems of Martin and R. Robinson follows that it is impossible to replace
hypersimple by hyperhypersimple.
Keywords: computably enumerable (c.e.) set, mitotic, wtt -reducibility, tt -reducibility, hypersimple set, low
ACM Classification Keywords: F. Theory of Computation, F.1.3 Complexity Measures and Classes.
ON HYPERSIMPLE wtt -MITOTIC SETS, WHICH ARE NOT tt -MITOTIC
Arsen H. Mokatsian