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

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

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,864
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

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

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.

Analytics

Added to PP index
2018-02-02

Total views
56 ( #184,055 of 2,433,155 )

Recent downloads (6 months)
1 ( #463,180 of 2,433,155 )

How can I increase my downloads?

Downloads

My notes