19 found
Sort by:
  1. Michael Benedikt, Andreas Blass, Natasha Dobrinen, Noam Greenberg, Denis R. Hirschfeldt, Salma Kuhlmann, Hannes Leitgeb, William J. Mitchell & Thomas Wilke (2007). Gainesville, Florida March 10–13, 2007. Bulletin of Symbolic Logic 13 (3).
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl & Sarah Pingrey (2007). $\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Barbara F. Csima, Valentina S. Harizanov, Denis R. Hirschfeldt & Robert I. Soare (2007). Bounding Homogeneous Models. 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 (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Denis R. Hirschfeldt & Richard A. Shore (2007). Combinatorial Principles Weaker Than Ramsey's Theorem for Pairs. Journal of Symbolic Logic 72 (1):171-206.
    We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for pairs (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  5. Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt & Joseph S. Miller (2006). Every 1-Generic Computes a Properly 1-Generic. Journal of Symbolic Logic 71 (4):1385 - 1393.
    A real is called properly n-generic if it is n-generic but not n+1-generic. We show that every 1-generic real computes a properly 1-generic real. On the other hand, if m > n ≥ 2 then an m-generic real cannot compute a properly n-generic real.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn (2006). Calibrating Randomness. Bulletin of Symbolic Logic 12 (3):411-491.
    Direct download (10 more)  
     
    My bibliography  
     
    Export citation  
  7. Denis R. Hirschfeldt, Bakhadyr Khoussainov & Pavel Semukhin (2006). An Uncountably Categorical Theory Whose Only Computably Presentable Model Is Saturated. Notre Dame Journal of Formal Logic 47 (1):63-71.
    We build an א₁-categorical but not א₀-categorical theory whose only computably presentable model is the saturated one. As a tool, we introduce a notion related to limitwise monotonic functions.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  8. Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies (2005). Relativizing Chaitin's Halting Probability. Journal of Mathematical Logic 5 (02):167-192.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  9. Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare (2004). Bounding Prime Models. Journal of Symbolic Logic 69 (4):1117 - 1142.
    A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model U of T decidable in X. It is easy to see that $X = 0\prime$ is prime bounding. Denisov claimed that every $X <_{T} 0\prime$ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets $X \leq_{T} 0\prime$ are exactly the sets which are not $low_2$ . Recall that (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Denis R. Hirschfeldt, Bakhadyr Khoussainov & Richard A. Shore (2003). A Computably Categorical Structure Whose Expansion by a Constant has Infinite Computable Dimension. Journal of Symbolic Logic 68 (4):1199-1241.
    Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  11. Denis R. Hirschfeldt (2002). Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms. Journal of Symbolic Logic 67 (2):697 - 720.
    We give some new examples of possible degree spectra of invariant relations on Δ 0 2 -categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ 0 2 (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. Denis R. Hirschfeldt (2002). Degree Spectra of Relations on Structures of Finite Computable Dimension. Annals of Pure and Applied Logic 115 (1-3):233-277.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  13. Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko (2002). Degree Spectra and Computable Dimensions in Algebraic Structures. Annals of Pure and Applied Logic 115 (1-3):71-113.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  14. Walker M. White & Denis R. Hirschfeldt (2002). Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures. Notre Dame Journal of Formal Logic 43 (1):51-64.
    We construct a class of relations on computable structures whose degree spectra form natural classes of degrees. Given any computable ordinal and reducibility r stronger than or equal to m-reducibility, we show how to construct a structure with an intrinsically invariant relation whose degree spectrum consists of all nontrivial r-degrees. We extend this construction to show that can be replaced by either or.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  15. Rod Downey, Denis R. Hirschfeldt, Steffen Lempp & Reed Solomon (2001). A Δ02 Set with No Infinite Low Subset in Either It or its Complement. Journal of Symbolic Logic 66 (3):1371 - 1381.
    We construct the set of the title, answering a question of Cholak, Jockusch, and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every ω-model of RCA 0 + SRT 2 2 must contain a nonlow set.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Denis R. Hirschfeldt (2001). Degree Spectra of Intrinsically C.E. Relations. Journal of Symbolic Logic 66 (2):441-469.
    We show that for every c.e. degree a > 0 there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of sets S there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements of S. Then we show that if α ∈ (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  17. Klaus Ambos-Spies, Denis R. Hirschfeldt & Richard A. Shore (2000). Undecidability and 1-Types in Intervals of the Computably Enumerable Degrees. Annals of Pure and Applied Logic 106 (1-3):1-47.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. Denis R. Hirschfeldt (2000). Degree Spectra of Relations on Computable Structures. Bulletin of Symbolic Logic 6 (2):197-212.
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation