Switch to: References

Add citations

You must login to add citations.
  1. $\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations.John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl & Sarah Pingrey - 2007 - Journal of Symbolic Logic 72 (3):1003 - 1018.
    We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable $\Pi _{1}^{0}$ subsets of 2ω and Kolmogorov complexity play a major role in the proof.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • The Hypersimple-Free C.E. WTT Degrees Are Dense in the C.E. WTT Degrees.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (3):361-370.
    We show that in the c.e. weak truth table degrees if b < c then there is an a which contains no hypersimple set and b < a < c. We also show that for every w < c in the c.e. wtt degrees such that w is hypersimple, there is a hypersimple a such that w < a < c. On the other hand, we know that there are intervals which contain no hypersimple set.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  • A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
    We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations