## Works by Barbara Csima

26 found
Order:
Disambiguations
 Barbara F. Csima [26] Barbara Csima [2]
1. Degrees of Categoricity and the Hyperarithmetic Hierarchy.Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore - 2013 - 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 (...)

Export citation

Bookmark   14 citations
2. Degrees That Are Not Degrees of Categoricity.Bernard Anderson & Barbara Csima - 2016 - Notre Dame Journal of Formal Logic 57 (3):389-398.
A computable structure $\mathcal {A}$ is $\mathbf {x}$-computably categorical for some Turing degree $\mathbf {x}$ if for every computable structure $\mathcal {B}\cong\mathcal {A}$ there is an isomorphism $f:\mathcal {B}\to\mathcal {A}$ with $f\leq_{T}\mathbf {x}$. A degree $\mathbf {x}$ is a degree of categoricity if there is a computable structure $\mathcal {A}$ such that $\mathcal {A}$ is $\mathbf {x}$-computably categorical, and for all $\mathbf {y}$, if $\mathcal {A}$ is $\mathbf {y}$-computably categorical, then $\mathbf {x}\leq_{T}\mathbf {y}$. We construct a $\Sigma^{0}_{2}$ set whose degree (...)

Export citation

Bookmark   9 citations
3. Finite computable dimension and degrees of categoricity.Barbara F. Csima & Jonathan Stephenson - 2019 - Annals of Pure and Applied Logic 170 (1):58-94.

Export citation

Bookmark   3 citations
4. The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - 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 (...)

Export citation

Bookmark   9 citations
5. Degrees of categoricity on a Cone via η-systems.Barbara F. Csima & Matthew Harrison-Trainor - 2017 - Journal of Symbolic Logic 82 (1):325-346.
We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is${\rm{\Delta }}_\alpha ^0$-complete for someα. To prove this, we extend Montalbán’sη-system framework to deal with limit ordinals in a more general way. We also show that, for any fixed computable structure, there is an ordinalαand a cone in the Turing degrees such that the exact complexity (...)

Export citation

Bookmark   3 citations
6. Limits on jump inversion for strong reducibilities.Barbara F. Csima, Rod Downey & Keng Meng Ng - 2011 - 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.

Export citation

Bookmark   4 citations
7. A Bounded Jump for the Bounded Turing Degrees.Bernard Anderson & Barbara Csima - 2014 - Notre Dame Journal of Formal Logic 55 (2):245-264.
We define the bounded jump of $A$ by $A^{b}=\{x\in \omega \mid \exists i\leq x[\varphi_{i}\downarrow \wedge\Phi_{x}^{A\upharpoonright \!\!\!\upharpoonright \varphi_{i}}\downarrow ]\}$ and let $A^{nb}$ denote the $n$th bounded jump. We demonstrate several properties of the bounded jump, including the fact that it is strictly increasing and order-preserving on the bounded Turing degrees. We show that the bounded jump is related to the Ershov hierarchy. Indeed, for $n\geq2$ we have $X\leq_{bT}\emptyset ^{nb}\iff X$ is $\omega^{n}$-c.e. $\iff X\leq_{1}\emptyset ^{nb}$, extending the classical result that $X\leq_{bT}\emptyset '\iff (...) Direct download (5 more) Export citation Bookmark 4 citations 8. Bounded low and high sets.Bernard A. Anderson, Barbara F. Csima & Karen M. Lange - 2017 - Archive for Mathematical Logic 56 (5-6):507-521. Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider whether the analogue of the Jump (...) No categories Direct download (2 more) Export citation Bookmark 2 citations 9. Degree spectra and immunity properties.Barbara F. Csima & Iskander S. Kalimullin - 2010 - Mathematical Logic Quarterly 56 (1):67-77. We analyze the degree spectra of structures in which different types of immunity conditions are encoded. In particular, we give an example of a structure whose degree spectrum coincides with the hyperimmune degrees. As a corollary, this shows the existence of an almost computable structure of which the complement of the degree spectrum is uncountable. Direct download (2 more) Export citation Bookmark 4 citations 10. Bounding Prime Models.Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare - 2004 - 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 (6 more) Export citation Bookmark 4 citations 11. Measuring complexities of classes of structures.Barbara F. Csima & Carolyn Knoll - 2015 - Annals of Pure and Applied Logic 166 (12):1365-1381. Direct download (3 more) Export citation Bookmark 2 citations 12. 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, (...) Direct download (6 more) Export citation Bookmark 4 citations 13. Boolean Algebras, Tarski Invariants, and Index Sets.Barbara F. Csima, Antonio Montalbán & Richard A. Shore - 2006 - 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 (5 more) Export citation Bookmark 3 citations 14. Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - 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 (6 more) Export citation Bookmark 2 citations 15. 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 (...) Direct download (4 more) Export citation Bookmark 2 citations 16. Degrees of categoricity and treeable degrees.Barbara F. Csima & Dino Rossegger - forthcoming - Journal of Mathematical Logic. In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to [Formula: see text]. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute [Formula: see text]. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree [Formula: see text] with [Formula: see text] for [Formula: see text] a computable ordinal greater than [Formula: see (...) Direct download (3 more) Export citation Bookmark 17. Linear orders with distinguished function symbol.Douglas Cenzer, Barbara F. Csima & Bakhadyr Khoussainov - 2009 - 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. Direct download (4 more) Export citation Bookmark 18. Computability of fraïssé limits.Barbara F. Csima, Valentina S. Harizanov, Russell Miller & Antonio Montalbán - 2011 - 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 (7 more) Export citation Bookmark 1 citation 19. Every 1-Generic Computes a Properly 1-Generic.Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt & Joseph S. Miller - 2006 - 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 (6 more) Export citation Bookmark 20. The complexity of central series in nilpotent computable groups.Barbara F. Csima & Reed Solomon - 2011 - Annals of Pure and Applied Logic 162 (8):667-678. The terms of the upper and lower central series of a nilpotent computable group have computably enumerable Turing degree. We show that the Turing degrees of these terms are independent even when restricted to groups which admit computable orders. Direct download (6 more) Export citation Bookmark 1 citation 21. Marriott Wardman Park Hotel, Washington, DC January 7–8, 2009.Barbara F. Csima, Inessa Epstein, Rahim Moosa, Christian Rosendal, Jouko Väänänen & Ali Enayat - 2009 - Bulletin of Symbolic Logic 15 (2). Export citation Bookmark 22. Which Classes of Structures Are Both Pseudo-Elementary and Definable by an Infinitary Sentence?Will Boney, Barbara F. Csima, D. A. Y. Nancy A. & Matthew Harrison-Trainor - 2023 - Bulletin of Symbolic Logic 29 (1):1-18. When classes of structures are not first-order definable, we might still try to find a nice description. There are two common ways for doing this. One is to expand the language, leading to notions of pseudo-elementary classes, and the other is to allow infinite conjuncts and disjuncts. In this paper we examine the intersection. Namely, we address the question: Which classes of structures are both pseudo-elementary and${\mathcal {L}}_{\omega _1, \omega }$-elementary? We find that these are exactly the classes (...) Direct download (2 more) Export citation Bookmark 23. 2008–2009 Winter Meeting of the Association for Symbolic Logic.Ali Enayat & Barbara F. Csima - 2009 - Bulletin of Symbolic Logic 15 (2):237. Direct download (2 more) Export citation Bookmark 24. Some questions of uniformity in algorithmic randomness.Laurent Bienvenu, Barbara F. Csima & Matthew Harrison-Trainor - 2021 - Journal of Symbolic Logic 86 (4):1612-1631. The$\Omega $numbers—the halting probabilities of universal prefix-free machines—are known to be exactly the Martin-Löf random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-Löf random left-c.e. real$\alpha $, a universal prefix-free machine U whose halting probability is$\alpha $. We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real$\alpha $, one cannot uniformly produce a left-c.e. real$\beta $such that$\alpha - \beta \$ is neither left-c.e. (...)

Export citation

Bookmark
25. Every Δ20 degree is a strong degree of categoricity.Barbara F. Csima & Keng Meng Ng - 2022 - Journal of Mathematical Logic 22 (3).
A strong degree of categoricity is a Turing degree [Formula: see text] such that there is a computable structure [Formula: see text] that is [Formula: see text]-computably categorical (there is a [Formula: see text]-computable isomorphism between any two computable copies of [Formula: see text]), and such that there exist two computable copies of [Formula: see text] between which every isomorphism computes [Formula: see text]. The question of whether every [Formula: see text] degree is a strong degree of categoricity has been (...)