Two More Characterizations of K-Triviality

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

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.
Keywords Kolmogorov complexity   Martin-Löf randomness  K-triviality
Categories (categorize this paper)
DOI 10.1215/00294527-2017-0021
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 48,784
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Hyperimmune-Free Degrees and Schnorr Triviality.Johanna N. Y. Franklin - 2008 - Journal of Symbolic Logic 73 (3):999-1008.
Schnorr Trivial Reals: A Construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533-554.
Almost Everywhere Domination and Superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
Continuous Higher Randomness.Laurent Bienvenu, Noam Greenberg & Benoit Monin - 2017 - Journal of Mathematical Logic 17 (1):1750004.
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.


Added to PP index

Total views
46 ( #198,931 of 2,309,235 )

Recent downloads (6 months)
11 ( #66,658 of 2,309,235 )

How can I increase my downloads?


My notes

Sign in to use this feature