Omanadze, R. On some properties of \(r\)-maximal sets and \(Q_{1-N}\)-reducibility. (English) Zbl 1021.03036 Georgian Math. J. 9, No. 1, 161-166 (2002). In the paper, some properties of \(Q_{1-N}\)-reducibility are studied. By definition, a set \(A\) is \(Q_{1-N}\)-reducible to a set \(B\) if there exists a computable function \(f\) such that: \[ x\in A \leftrightarrow {W_{f(x)}}\subseteq B,\quad x\neq y \rightarrow W_{f(x)}\cap W_{f(y)}=\emptyset, \quad \bigcup_x W_{f(x)}\text{ is computable}. \] The author proves that if \(M_1\), \(M_2\) are \(r\)-maximal \(Q_{N-1}\)-equivalent sets, then they are \(m\)-equivalent. Besides, there exists a \(Q_{N-1}\)- and \(W\)-complete computably enumerable set which is not \(sQ\)-complete. Reviewer: Shamil Ishmukhametov (Ul’yanovsk) Cited in 1 Document MSC: 03D25 Recursively (computably) enumerable sets and degrees 03D30 Other degrees and reducibilities in computability and recursion theory Keywords:recursively enumerable set; maximal set; \(r\)-maximal; \(m\)-reducibility; computably enumerable set PDFBibTeX XMLCite \textit{R. Omanadze}, Georgian Math. J. 9, No. 1, 161--166 (2002; Zbl 1021.03036) Full Text: EuDML