Two More Characterizations of K-triviality

Daniel Turetsky, Noam Greenberg, Joe Miller, Benoit Monin

    Veröffentlichungen: Beitrag in FachzeitschriftArtikelPeer Reviewed

    Abstract

    We give two new characterizations of K-triviality. We show that
    if for all Y such that Ω is Y-random, Ω is (Y⊕A)-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, (Y⊕A) LR-equals Y .
    This answers a question of Merkle. 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 is LR-below B, then for every set X there is a B-random set Y such that X is computable from Y⊕A.
    OriginalspracheEnglisch
    Seiten (von - bis)189-195
    Seitenumfang7
    FachzeitschriftNotre Dame Journal of Formal Logic
    Jahrgang59
    Ausgabenummer2
    Frühes Online-Datum2016
    DOIs
    PublikationsstatusVeröffentlicht - 2018

    ÖFOS 2012

    • 101013 Mathematische Logik

    Zitationsweisen