Relative Randomness and Cardinality

Notre Dame Journal of Formal Logic 51 (2):195-205 (2010)
  Copy   BIBTEX

Abstract

A set $B\subseteq\mathbb{N}$ is called low for Martin-Löf random if every Martin-Löf random set is also Martin-Löf random relative to B . We show that a $\Delta^0_2$ set B is low for Martin-Löf random if and only if the class of oracles which compress less efficiently than B , namely, the class $\mathcal{C}^B=\{A\ |\ \forall n\ K^B(n)\leq^+ K^A(n)\}$ is countable (where K denotes the prefix-free complexity and $\leq^+$ denotes inequality modulo a constant. It follows that $\Delta^0_2$ is the largest arithmetical class with this property and if $\mathcal{C}^B$ is uncountable, it contains a perfect $\Pi^0_1$ set of reals. The proof introduces a new method for constructing nontrivial reals below a $\Delta^0_2$ set which is not low for Martin-Löf random

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

Relative Randomness and Real Closed Fields.Alexander Raichev - 2005 - Journal of Symbolic Logic 70 (1):319 - 330.
On the construction of effectively random sets.Wolfgang Merkle & Nenad Mihailović - 2004 - Journal of Symbolic Logic 69 (3):862-878.
Computational randomness and lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Lowness and $\Pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.

Analytics

Added to PP
2010-08-13

Downloads
38 (#365,484)

6 months
6 (#202,901)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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.
Algorithmic Randomness and Measures of Complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
Algorithmic randomness and measures of complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
Kolmogorov complexity and computably enumerable sets.George Barmpalias & Angsheng Li - 2013 - Annals of Pure and Applied Logic 164 (12):1187-1200.

Add more citations

References found in this work

On the Concept of a Random Sequence.Alonzo Church - 1940 - Journal of Symbolic Logic 5 (2):71-72.
On the Concept of a Random Sequence.Alonzo Church - 1940 - Bulletin of the American Mathematical Society 46 (2):130--135.
Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.

View all 9 references / Add more references