\(Q _{1}\)-degrees of c.e. sets (Q453193): Difference between revisions

\(A\leq_QB\) if there is a computable function \(f\) such that for every \(x\), \(x\in A\leftrightarrow W_{f(x)}\supsetneq B\). If \(f\) has the further property that \(W_{f(x)}\) and \(W_{f(y)}\) are disjoint whenever \(x\neq y\), then \(A\leq_{Q_1}B\). The \(Q\)-degrees and \(Q_1\)-degrees are generated in the natural way. \(A\leq_Q B\) assures \(A\leq_\tau B\) if \(A\) and \(B\) are c.e., but not generally. Exactly parallel to the classical result about simple \(m\)-degrees and \(1\)-degrees, it is established that any hyperhypersimple \(Q\)-degree includes a ``collection of \(Q_1\)-degrees linearly ordered under \(\leq_{Q_1}\), with order type of the integers and consisting entirely of hyperhypersimple sets.'' Like the c.e. \(1\)-degrees, the c.e. \(Q_1\)-degrees are shown not to be an uppersemilattice. A set is hemimaximal if it is one of a pair of disjoint noncomputable c.e. sets into which some maximal set can be split. If \(A\) is hemimaximal and \(B\) is a noncomputable c.e. set with \(B\leq_{Q_1}A\) then \(B\) is hemimaximal. Further, if \(A\) is hemimaximal then every c.e. set in the \(Q_1\)-degree of \(A\) is isomorphic to \(A\), i.e., the \(Q_1\)-degree of \(A\) contains only one c.e. \(1\)-degree. An open question is whether there is a c.e. \(Q\)-degree that contains only one \(m\)-degree.