Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility (Q892147): Difference between revisions

If there is a computable function \(f\) such that, for all \(x\in\omega\), \[ \text{(a) }x\in A\Longleftrightarrow W_{f(x)}\nsubseteq B\text{, (b) }x\neq y\Longrightarrow W_{f(x)}\cap W_{f(y)}=\varnothing\text{, and (c) }\bigcup_{x\in\omega} W_{f(x)} \] is computable, we say that \(A\) is \(Q_{1,N}\)-reducible to \(B\). This relation, due to Bulitko, generates the \(Q_{1,N}\)-degrees. Condition (a) characterizes \(Q\)-reducibility, which yields the \(Q\) degrees; (a) and (b) together define \(Q_1\)-reducibility, generating the \(Q_1\) degrees. \(Q_1\)-reducibility was studied by the author and \textit{I. O. Chitaia} [Arch. Math. Logic 51, No. 5--6, 503--515 (2012; Zbl 1257.03065)]. The present paper gives comparable results about the \(Q_{1,N}\)-degrees. Among them: There is a pair of c.e. sets that has no least c.e. upper bound in the \(Q_{1,N}\) ordering, so that the c.e. \(Q_{1,N}\)-degrees are not an upper semilatice. If a set \(A\) belongs to the same \(Q_{1,N}\)-degree as an \(r\)-maximal set \(M\), then \(M\leq_{m}A\). If \(A\) and \(B\) are a Friedberg splitting of an \(r\)-maximal set, every c.e. set in the \(Q_{1,N}\)-degree of \(A\) is isomorphic to \(A\).