The dense simple sets are orbit complete with respect to the simple sets (Q1295401): Difference between revisions

A collection \(\mathcal C\) of computably enumerable sets is orbit complete w.r.t. a class of computable enumerable sets \({\mathcal D}\) if for every set \(A\in {\mathcal D}\) there is a computably enumerable set \(B\in{\mathcal C}\) and an automorphism \(\Phi\) of the computably enumerable sets such that \(\Phi(A) = B\). A set \(B\) is dense simple iff \(B\) is computably enumerable and the principal function \(p_{\overline{B}}\) of \(\overline{B}\) dominates every computable total function. The paper under review shows that the dense simple sets are orbit complete w.r.t. the simple sets. This implies a positive answer to the conjectures of Herrmann, that the collection of hypersimple sets is orbit complete for simple sets, and of Stob, that the collection of dense simple sets is orbit complete [see \textit{T. Slaman} ``Open questions in recursion theory'', Continually updated since 1993 (URL: http://math.berkeley.edu/slaman)].