Relative Randomness and Cardinality

Notre Dame Journal of Formal Logic 51 (2):195-205 (2010)
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
Keywords randomness   cardinality   relative randomness
Categories (categorize this paper)
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 9,351
External links
  •   Try with proxy.
  •   Try with proxy.
  •   Try with proxy.
  • Through your library Configure
    References found in this work BETA

    No references found.

    Citations of this work BETA
    Similar books and articles

    Monthly downloads

    Added to index


    Total downloads

    6 ( #162,810 of 1,088,388 )

    Recent downloads (6 months)

    1 ( #69,601 of 1,088,388 )

    How can I increase my downloads?

    My notes
    Sign in to use this feature

    Start a new thread
    There  are no threads in this forum
    Nothing in this forum yet.