Switch to: References

Add citations

You must login to add citations.
  1. Interpreting true arithmetic in the theory of the r.e. truth table degrees.André Nies & Richard A. Shore - 1995 - Annals of Pure and Applied Logic 75 (3):269-311.
    We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Effective embeddings into strong degree structures.Timothy H. McNicholl - 2003 - Mathematical Logic Quarterly 49 (3):219.
    We show that any partial order with a Σ3 enumeration can be effectively embedded into any partial order obtained by imposing a strong reducibility such as ≤tt on the c. e. sets. As a consequence, we obtain that the partial orders that result from imposing a strong reducibility on the sets in a level of the Ershov hiearchy below ω + 1 are co-embeddable.
    Download  
     
    Export citation  
     
    Bookmark