Elementary differences between the degrees of unsolvability and degrees of compressibility
type: Item
instance of: scholarly article
title: Elementary differences between the degrees of unsolvability and degrees of compressibility
zbMATH Open document ID: 1227.03054
author: George Barmpalias
published in: Annals of Pure and Applied Logic
publication date: 2011-08-26T00:00:00Z
review text: 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.
reviewed by: Roland Sh. Omanadze
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 5943631
zbMATH Keywords: degrees of unsolvability
zbMATH Keywords: degrees of compressibility
zbMATH Keywords: elementary equivalence
zbMATH Keywords: minimal pairs
MaRDI profile type: Publication
full work available at URL: j.apal.2009.11.004
OpenAlex ID: W2072474105
cites work: Tracing and domination in the Turing degrees
cites work: Relative randomness and cardinality
cites work: Randomness, lowness and degrees
cites work: \(\Pi_1^0 \) classes, LR degrees and Turing degrees
cites work: Non-cupping, measure and computably enumerable splittings
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Lowness notions, measure and domination
cites work: Low for random reals and positive-measure domination
cites work: Q3214803
cites work: Lower Bounds for Pairs of Recursively Enumerable Degrees
cites work: Lowness properties and randomness
cites work: Q3611832
cites work: A minimal degree less than 0’
cites work: Almost everywhere domination and superhighness
cites work: Q4040892
cites work: A formal theory of inductive inference. Part I
cites work: A minimal pair of recursively enumerable degrees
DOI: 10.1016/J.APAL.2009.11.004
description: scientific article; zbMATH DE number 5943631