Switch to: References

Add citations

You must login to add citations.
  1. Computability of Homogeneous Models.Karen Lange & Robert I. Soare - 2007 - Notre Dame Journal of Formal Logic 48 (1):143-170.
    In the last five years there have been a number of results about the computable content of the prime, saturated, or homogeneous models of a complete decidable theory T in the spirit of Vaught's "Denumerable models of complete theories" combined with computability methods for degrees d ≤ 0′. First we recast older results by Goncharov, Peretyat'kin, and Millar in a more modern framework which we then apply. Then we survey recent results by Lange, "The degree spectra of homogeneous models," which (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Η-representation of sets and degrees.Kenneth Harris - 2008 - Journal of Symbolic Logic 73 (4):1097-1121.
    We show that a set has an η-representation in a linear order if and only if it is the range of a 0'-computable limitwise monotonic function. We also construct a Δ₃ Turing degree for which no set in that degree has a strong η-representation, answering a question posed by Downey.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Bounding Homogeneous Models.Barbara F. Csima, Valentina S. Harizanov, Denis R. Hirschfeldt & Robert I. Soare - 2007 - Journal of Symbolic Logic 72 (1):305 - 323.
    A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Degree Spectra of Prime Models.Barbara F. Csima - 2004 - Journal of Symbolic Logic 69 (2):430 - 442.
    We consider the Turing degrees of prime models of complete decidable theories. In particular we show that every complete decidable atomic theory has a prime model whose elementary diagram is low. We combine the construction used in the proof with other constructions to show that complete decidable atomic theories have low prime models with added properties. If we have a complete decidable atomic theory with all types of the theory computable, we show that for every degree d with 0 0, (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Coarse computability, the density metric, Hausdorff distances between Turing degrees, perfect trees, and reverse mathematics.Denis R. Hirschfeldt, Carl G. Jockusch & Paul E. Schupp - 2023 - Journal of Mathematical Logic 24 (2).
    For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes (...)
    Download  
     
    Export citation  
     
    Bookmark