|
The paper relates to questions
raised by A. A. Muchnik in a 1956 Doklady abstract, namely, whether a noncreative
r.e. set can be simple in a creative one, and whether a creative r.e. set can be simple
in a noncreative one. We furnish a negative answer to the second question, and give a
variety of partial results having to do with the first. Thus, we show that no
universal set can have immune relative complement inside a noncreative
r.e. set and that any r.e. set which is hyperhypersimple in a creative set must
itself be creative; whereas, there exist three sets α, β, γ, α ⊆ β ⊆ γ, such
that β is creative, α and γ are nonuniversal, and both β − α and γ − β are
hyperhyperimmune.
In addition, we answer two questions of J. P. Cleave regarding the comparison of
effectively inseparable (e.i.) and “almost effectively inseparable” (almost e.i.)
sequences of r.e. sets. Thus: a sequence can be almost e.i. without being e.i.;
and an almost e.i. sequence of disjoint r.e. sets may have a noncreative
union.
|
