Two More Characterizations of K-Triviality

Notre Dame Journal of Formal Logic 59 (2):189-195 (2018)
  Copy   BIBTEX

Abstract

We give two new characterizations of K-triviality. We show that if for all Y such that Ω is Y-random, Ω is -random, then A is K-trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of K-triviality and answering a question of Yu. We also prove that if A is K-trivial, then for all Y such that Ω is Y-random, ≡LRY. This answers a question of Merkle and Yu. The other direction is immediate, so we have the second characterization of K-triviality.The proof of the first characterization uses a new cupping result. We prove that if A≰LRB, then for every set X there is a B-random set Y such that X is computable from Y⊕A.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 97,319

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Computing from projections of random points.Noam Greenberg, Joseph S. Miller & André Nies - 2019 - Journal of Mathematical Logic 20 (1):1950014.
The K -Degrees, Low for K Degrees,and Weakly Low for K Sets.Joseph S. Miller - 2009 - Notre Dame Journal of Formal Logic 50 (4):381-391.
The Kolmogorov complexity of random reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
Schnorr trivial reals: a construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Relative Randomness and Cardinality.George Barmpalias - 2010 - Notre Dame Journal of Formal Logic 51 (2):195-205.

Analytics

Added to PP
2018-02-02

Downloads
83 (#210,662)

6 months
21 (#178,916)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

The axiomatization of randomness.Michiel van Lambalgen - 1990 - Journal of Symbolic Logic 55 (3):1143-1167.
Cone avoidance and randomness preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
Characterizing strong randomness via Martin-Löf randomness.Liang Yu - 2012 - Annals of Pure and Applied Logic 163 (3):214-224.
Degrees joining to 0'. [REVIEW]David B. Posner & Robert W. Robinson - 1981 - Journal of Symbolic Logic 46 (4):714 - 722.

Add more references