17 found
Sort by:
  1. Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore (2013). Degrees of Categoricity and the Hyperarithmetic Hierarchy. Notre Dame Journal of Formal Logic 54 (2):215-231.
    We study arithmetic and hyperarithmetic degrees of categoricity. We extend a result of E. Fokina, I. Kalimullin, and R. Miller to show that for every computable ordinal $\alpha$, $\mathbf{0}^{}$ is the degree of categoricity of some computable structure $\mathcal{A}$. We show additionally that for $\alpha$ a computable successor ordinal, every degree $2$-c.e. in and above $\mathbf{0}^{}$ is a degree of categoricity. We further prove that every degree of categoricity is hyperarithmetic and show that the index set of structures with degrees (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Barbara F. Csima, Rod Downey & Keng Meng Ng (2011). Limits on Jump Inversion for Strong Reducibilities. Journal of Symbolic Logic 76 (4):1287-1296.
    We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a ${\mathrm{\Delta }}_{2}^{0}$ set B > tt ∅′ such that there is no c.e. set A with A′ ≡ wtt B. We also show that there is a ${\mathrm{\Sigma }}_{2}^{0}$ set C > tt ∅′ such that there is no ${\mathrm{\Delta }}_{2}^{0}$ set D with D′ ≡ wtt C.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  3. Barbara F. Csima, Valentina S. Harizanov, Russell Miller & Antonio Montalbán (2011). Computability of Fraïssé Limits. Journal of Symbolic Logic 76 (1):66 - 93.
    Fraïssé studied countable structures S through analysis of the age of S i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  4. Barbara F. Csima & Reed Solomon (2011). The Complexity of Central Series in Nilpotent Computable Groups. Annals of Pure and Applied Logic 162 (8):667-678.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  5. Barbara F. Csima & Iskander S. Kalimullin (2010). Degree Spectra and Immunity Properties. Mathematical Logic Quarterly 56 (1):67-77.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  6. Douglas Cenzer, Barbara F. Csima & Bakhadyr Khoussainov (2009). Linear Orders with Distinguished Function Symbol. Archive for Mathematical Logic 48 (1):63-76.
    We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Barbara F. Csima, Inessa Epstein, Rahim Moosa, Christian Rosendal, Jouko Väänänen & Ali Enayat (2009). Marriott Wardman Park Hotel, Washington, DC January 7–8, 2009. Bulletin of Symbolic Logic 15 (2).
    Direct download  
     
    My bibliography  
     
    Export citation  
  8. Barbara F. Csima & Joseph R. Mileti (2009). The Strength of the Rainbow Ramsey Theorem. Journal of Symbolic Logic 74 (4):1310 - 1324.
    The Rainbow Ramsey Theorem is essentially an "anti-Ramsey" theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA₀ of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA₀. The separation involves techniques (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  9. Ali Enayat & Barbara F. Csima (2009). 2008-2009 Winter Meeting of the Association for Symbolic Logic. Bulletin of Symbolic Logic 15 (2):237.
     
    My bibliography  
     
    Export citation  
  10. 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  
  11. Barbara F. Csima & Richard A. Shore (2007). The Settling-Time Reducibility Ordering. Journal of Symbolic Logic 72 (3):1055 - 1071.
    To each computable enumerable (c.e.) set A with a particular enumeration {As}s∈ω, there is associated a settling function mA(x), where mA(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >st A) if for every computable function f, for all but finitely many x, mB(x) > f(m₄(x)). This settling-time ordering, which is a natural extension to an ordering of the (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  12. 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  
  13. Barbara F. Csima, Antonio Montalbán & Richard A. Shore (2006). Boolean Algebras, Tarski Invariants, and Index Sets. Notre Dame Journal of Formal Logic 47 (1):1-23.
    Tarski defined a way of assigning to each Boolean algebra, B, an invariant inv(B) ∈ In, where In is a set of triples from ℕ, such that two Boolean algebras have the same invariant if and only if they are elementarily equivalent. Moreover, given the invariant of a Boolean algebra, there is a computable procedure that decides its elementary theory. If we restrict our attention to dense Boolean algebras, these invariants determine the algebra up to isomorphism. In this paper we (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  14. Barbara F. Csima & Robert I. Soare (2006). Computability Results Used in Differential Geometry. Journal of Symbolic Logic 71 (4):1394 - 1410.
    Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating properties. (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  15. Barbara F. Csima (2004). Degree Spectra of Prime Models. 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, (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  16. 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