Elementary differences between the degrees of unsolvability and degrees of compressibility (Q636334): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 09:20, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Elementary differences between the degrees of unsolvability and degrees of compressibility |
scientific article |
Statements
Elementary differences between the degrees of unsolvability and degrees of compressibility (English)
0 references
26 August 2011
0 references
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.
0 references
degrees of unsolvability
0 references
degrees of compressibility
0 references
elementary equivalence
0 references
minimal pairs
0 references