Sets without subsets of higher many-one degree (Q2565991): Difference between revisions

For a reducibility \(r\), a set \(A\) is called \(r\)-introimmune iff there is no set \(B \subseteq A\) such that \(A-B\) is infinite and \(A\) is \(r\)-reducible to \(B\). \textit{R. I. Soare} [``Sets with no subset of higher degree'', J. Symb. Log. 34, 53--56 (1969; Zbl 0182.01602)] showed that there are Turing-introreducible sets. This result translates of course directly to all stronger reducibilities like many-one reducibility or polynomial-time Turing reducibility. Therefore, the author asks more for the complexity of such sets than for their existence. He investigates this question in the context of the many-one reducibility. In the present paper, he shows that many-one introimmune sets are immune. Furthermore, cohesive sets are many-one introimmune and hence there are \(\Pi^0_1\)-sets with this property. Also, the author constructs a \(\Delta^0_2\)-set \(A\) such that whenever \(A \leq_m B\) and \(B\) is a subset of \(A\) or its complement then \(B\) is a finite variant of \(A\) or its complement, respectively. Such a set \(A\) is called bi-many-one-introimmune. Bi-many-one-introimmune sets cannot be \(\Pi^0_1\)-sets or \(\Sigma^0_1\)-sets, so the example given fits into the lowest possible level of Kleene's hierarchy. The author's example \(A\) has some further properties: if \(A \leq_m B\) then the many-one reduction witnessing this is one-one on a cofinite domain, what is called strongly bi-many-one-introimmune; furthermore, the set \(A\) has large gaps, that is, for a fixed \(K\)-recursive function \(f\) dominating all recursive functions, there are infinitely many numbers \(x\) such that \(x+1,x+2,\ldots,f(x) \notin A\); the same type of gaps occur in the complement of \(A\). It could be noted, that one can obtain (strongly) bi-many-one-introimmune sets also from the theory of randomness as every Martin-Löf random set has this property and Chaitin's \(\Omega\) is a \(\Delta^0_2\)-set of this type. Furthermore, every \(1\)-generic set Turing reducible to the halting-problem \(K\) admits all types of recursive gaps although only some \(1\)-generic sets below \(K\) admit the types of gaps desired by the author. In the last section, the construction of this set \(A\) is transferred into the complexity-theoretic setting. \textit{K. Ambos-Spies} [``Problems which cannot be reduced to any proper subproblems'', Lect. Notes Comput. Sci. 2747, 162--168 (2003)] constructed already an exponential-time computable set that is Turing-introimmune. The author constructs a strongly bi-polynomial-time many-one-introimmune set \(A\) such that both \(A\) and its complement have gaps with respect to a given recursive function \(f\). In the paper, some concrete function \(f\) is given, but indeed, any recursive function \(f\) could be used.