Elementary differences between the degrees of unsolvability and degrees of compressibility (Q636334): Difference between revisions

In this paper the following is proved: Let \(X\) be a \(\Delta^0_2\)-set which is not \(K\)-trivial. Then there exists a c.e. set \(A\) which is not \(K\)-trivial such that \(A \leq_{LR} X\). It follows from this result that the \(\Delta^0_2\)-structures of \(LR/LK\)-degrees and the Turing degrees are not elementarily equivalent. Let \(X ,Y\) be \(\Delta^0_2\)-sets which are not \(K\)-trivial. Then there exists a c.e. set \(A\) which is not \(K\)-trivial such that \(A\leq_{LR} X\) and \(A\leq_{LR} Y\). It follows from this result that the \(\Sigma^0_1\)-structures of \(LR/LK\)-degrees and the Turing degrees are not elementarily equivalent. Also, the structure of the \(LR/LK\)-degrees below the \(LR/LK\)-degree of the halting problem is not elementarily equivalent to the \(\Sigma^0_1\)- and \(\Delta^0_2\)-structures of \(LR/LK\)-degrees.