Switch to: References

Add citations

You must login to add citations.
  1. Superhighness.Bjørn Kjos-Hanssen & Andrée Nies - 2009 - Notre Dame Journal of Formal Logic 50 (4):445-452.
    We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the class $superhigh^\diamond$ and show that it contains some, but not all, of the noncomputable K-trivial sets.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • A Survey of Mučnik and Medvedev Degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.
    We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Denjoy, Demuth and Density.Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies - 2014 - Journal of Mathematical Logic 14 (1):1450004.
    We consider effective versions of two classical theorems, the Lebesgue density theorem and the Denjoy–Young–Saks theorem. For the first, we show that a Martin-Löf random real z ∈ [0, 1] is Turing incomplete if and only if every effectively closed class.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Mass Problems and Measure-Theoretic Regularity.Stephen G. Simpson - 2009 - Bulletin of Symbolic Logic 15 (4):385-409.
    A well known fact is that every Lebesgue measurable set is regular, i.e., it includes an F$_{\sigma}$ set of the same measure. We analyze this fact from a metamathematical or foundational standpoint. We study a family of Muchnik degrees corresponding to measure-theoretic regularity at all levels of the effective Borel hierarchy. We prove some new results concerning Nies's notion of LR-reducibility. We build some $\omega$-models of RCA$_0$which are relevant for the reverse mathematics of measure-theoretic regularity.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Tracing and Domination in the Turing Degrees.George Barmpalias - 2012 - Annals of Pure and Applied Logic 163 (5):500-505.
  • A Reducibility Related To Being Hyperimmune-Free.Frank Stephan & Liang Yu - 2014 - Annals of Pure and Applied Logic 165 (7-8):1291-1300.
    The main topic of the present work is the relation that a set X is strongly hyperimmune-free relative to Y . Here X is strongly hyperimmune-free relative to Y if and only if for every partial X -recursive function p there is a partial Y -recursive function q such that every a in the domain of p is also in the domain of q and satisfies p (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Degree Spectra and Immunity Properties.Barbara F. Csima & Iskander S. Kalimullin - 2010 - Mathematical Logic Quarterly 56 (1):67-77.
    We analyze the degree spectra of structures in which different types of immunity conditions are encoded. In particular, we give an example of a structure whose degree spectrum coincides with the hyperimmune degrees. As a corollary, this shows the existence of an almost computable structure of which the complement of the degree spectrum is uncountable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations