×

On some properties of \(r\)-maximal sets and \(Q_{1-N}\)-reducibility. (English) Zbl 1021.03036

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.

MSC:

03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
PDFBibTeX XMLCite
Full Text: EuDML