Switch to: References

Add citations

You must login to add citations.
  1. Classes bounded by incomplete sets.Kejia Ho & Frank Stephan - 2002 - Annals of Pure and Applied Logic 116 (1-3):273-295.
    We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We say that a class of computably enumerable sets bounded iff there is an m-incomplete computably enumerable set A such that every set in is m-reducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Bounded Immunity and Btt‐Reductions.Stephen Fenner & Marcus Schaefer - 1999 - Mathematical Logic Quarterly 45 (1):3-21.
    We define and study a new notion called k-immunity that lies between immunity and hyperimmunity in strength. Our interest in k-immunity is justified by the result that θ does not k-tt reduce to a k-immune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not btt-reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Cuppability of Simple and Hypersimple Sets.Martin Kummer & Marcus Schaefer - 2007 - Notre Dame Journal of Formal Logic 48 (3):349-369.
    An incomplete degree is cuppable if it can be joined by an incomplete degree to a complete degree. For sets fulfilling some type of simplicity property one can now ask whether these sets are cuppable with respect to a certain type of reducibilities. Several such results are known. In this paper we settle all the remaining cases for the standard notions of simplicity and all the main strong reducibilities.
    Download  
     
    Export citation  
     
    Bookmark