Valentina Harizanov
All publications (41)
Sergei S. Goncharov. Countable Boolean algebras and decidability. English translation of Schetnye bulevy algebry i razreshimost′. Siberian school of algebra and logic. Consultants Bureau, New York, London, and Moscow, 1997, xii + 318 pp (review)
Journal of Symbolic Logic 63 (3): 1188-1190. 1998.
Logic and Philosophy of LogicNonclassical LogicsNonclassical Logics
Computability-theoretic categoricity and Scott families
with Ekaterina Fokina and Daniel Turetsky
Annals of Pure and Applied Logic 170 (6): 699-717. 2019.
Induction, algorithmic learning theory, and philosophy (edited book)
with Michele Friend and Norma B. Goethe
Springer. 2007.
Downey, R., Fiiredi, Z., Jockusch Jr., CG and Ruhel, LA
with W. I. Gasarch, A. C. Y. Lee, M. Groszek, T. Hummel, H. Ishihara, B. Khoussainov, A. Nerode, I. Kalantari, and L. Welch
Annals of Pure and Applied Logic 93 263. 1998.
Σ 1 0 and Π 1 0 equivalence structures
with Douglas Cenzer and Jeffrey B. Remmel
We study computability theoretic properties of and equivalence structures and how they differ from computable equivalence structures or equivalence structures that belong to the Ershov difference hierarchy. Our investigation includes the complexity of isomorphisms between equivalence structures and between equivalence structures
Quantum MechanicsLogic and Philosophy of Logic
Partial automorphism semigroups
with Jennifer Chubb, Andrei S. Morozov, Sarah Pingrey, and Eric Ufferman
We study the relationship between algebraic structures and their inverse semigroups of partial automorphisms. We consider a variety of classes of natural structures including equivalence structures, orderings, Boolean algebras, and relatively complemented distributive lattices. For certain subsemigroups of these inverse semigroups, isomorphism of the subsemigroups yields isomorphism of the underlying structures. We also prove that for some classes of computable structures, we can reconstruct a c…Read more
We study the relationship between algebraic structures and their inverse semigroups of partial automorphisms. We consider a variety of classes of natural structures including equivalence structures, orderings, Boolean algebras, and relatively complemented distributive lattices. For certain subsemigroups of these inverse semigroups, isomorphism of the subsemigroups yields isomorphism of the underlying structures. We also prove that for some classes of computable structures, we can reconstruct a computable structure, up to computable isomorphism, from the isomorphism type of its inverse semigroup of computable partial automorphisms
Model TheoryScience, Logic, and MathematicsLogic and Philosophy of Logic, Miscellaneous
$\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations
with John Chisholm, Jennifer Chubb, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl, and Sarah Pingrey
Journal of Symbolic Logic 72 (3). 2007.
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
Model TheoryLogic and Philosophy of LogicLogic and Philosophy of Logic, Miscellaneous
Bounding Homogeneous Models
with Barbara F. Csima, Denis R. Hirschfeldt, and Robert I. Soare
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 single CD theory T such that every homogene…Read more
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 single CD theory T such that every homogeneous model of T has a PA degree
Model TheoryLogic and Philosophy of Logic
Some effects of Ash–Nerode and other decidability conditions on degree spectra
Annals of Pure and Applied Logic 55 (1): 51-65. 1991.
With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that R is intrinsically r.e. if and only if a natural recursive-syntacti…Read more
With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that R is intrinsically r.e. if and only if a natural recursive-syntactic condition is satisfied. We show that, while a recursive non-intrinsically r.e. relation may have a two element degree spectrum, a non-intrinsically r.e. relation which satisfies the Ash–Nerode decidability condition has an infinite degree spectrum. We also study several related decidability conditions and their effects on the degree spectra, including some conditions which are sufficient to obtain every r.e. degree in a spectrum
Chains and antichains in partial orderings
with Carl G. Jockusch and Julia F. Knight
Archive for Mathematical Logic 48 (1): 39-53. 2009.
We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is ${\Sigma _{1}^{1}}$ or ${\Pi _{1}^{1}}$ , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two ${\Pi _{1}^{1}}$ sets. Our main result is that there is a computa…Read more
We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is ${\Sigma _{1}^{1}}$ or ${\Pi _{1}^{1}}$ , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two ${\Pi _{1}^{1}}$ sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering ${\mathcal{A}}$ has the feature that for every ${\mathcal{B} \cong \mathcal{A}}$ , there is an infinite chain or antichain that is ${\Delta _{2}^{0}}$ relative to ${\mathcal{B}}$ , then we have uniform dichotomy: either for all copies ${\mathcal{B}}$ of ${\mathcal{A}}$ , there is an infinite chain that is ${\Delta _{2}^{0}}$ relative to ${\mathcal{B}}$ , or for all copies ${\mathcal{B}}$ of ${\mathcal{A}}$ , there is an infinite antichain that is ${\Delta _{2}^{0}}$ relative to ${\mathcal{B}}$
Areas of Mathematics
Isomorphism relations on computable structures
with Ekaterina B. Fokina, Sy-David Friedman, Julia F. Knight, Charles Mccoy, and Antonio Montalbán
Journal of Symbolic Logic 77 (1): 122-132. 2012.
We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω
Model TheoryLogic and Philosophy of Logic, MiscellaneousLogic and Philosophy of Logic
San Antonio Convention Center San Antonio, Texas January 14–15, 2006
with Douglas Cenzer, C. Ward Henson, Michael C. Laskowski, Alain Louveau, Russell Miller, Itay Neeman, and Sergei Starchenko
Bulletin of Symbolic Logic 12 (4). 2006.
Turing degrees of hypersimple relations on computable structures
Annals of Pure and Applied Logic 121 (2-3): 209-226. 2003.
Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose d…Read more
Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose domain the image of R is hypersimple and of arbitrary nonzero computably enumerable Turing degree
Of the association for symbolic logic
Logic and Philosophy of Logic, MiscScience, Logic, and Mathematics
Π11 Relations And Paths Through
with Sergey Goncharov, Julia Knight, and Richard Shore
Computability of fraïssé limits
with Barbara F. Csima, Russell Miller, and Antonio Montalbán
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 defi…Read more
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 a quantifier-free formula. We give some sufficient or necessary conditions for a Fraïssé limit to be spectrally universal. As an application, we prove that the computable atomless Boolean algebra is spectrally universal
Logic and Philosophy of LogicLogic and Philosophy of Logic, Miscellaneous
Regular relations and the quantifier "there exist uncountably many"
with Zarko Mijajlović
Mathematical Logic Quarterly 29 (3): 151-161. 1983.
Effective categoricity of Abelian p -groups
with Wesley Calvert, Douglas Cenzer, and Andrei Morozov
We investigate effective categoricity of computable Abelian p-groups . We prove that all computably categorical Abelian p-groups are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. We investigate which computable Abelian p-groups are categorical and relatively categorical
Model TheoryScience, Logic, and Mathematics
Sequences of n-diagrams
with Julia F. Knight and Andrei S. Morozov
Computability-theoretic complexity of countable structures
Bulletin of Symbolic Logic 8 (4): 457-477. 2002.
Model TheoryLogic and Philosophy of LogicComputability
New Orleans Marriott and Sheraton New Orleans New Orleans, Louisiana January 7–8, 2007
with Matthew Foreman, Su Gao, Ulrich Kohlenbach, Michael Rathjen, Reed Solomon, Carol Wood, and Marcia Groszek
Intrinsic bounds on complexity and definability at limit levels
with John Chisholm, Ekaterina B. Fokina, Sergey S. Goncharov, Julia F. Knight, and Sara Quinn
We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ on A (equivalently,…Read more
We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ on A (equivalently, it is not definable by a computable $\Sigma _\alpha $ formula with finitely many parameters). Earlier results in [7], [10], and [8] establish the same facts for computable successor ordinals α
The possible turing degree of the nonzero member in a two element degree spectrum
Annals of Pure and Applied Logic 60 (1): 1-30. 1993.
We construct a recursive model , a recursive subset R of its domain, and a Turing degree x 0 satisfying the following condition. The nonrecursive images of R under all isomorphisms from to other recursive models are of Turing degree x and cannot be recursively enumerable
Review: C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (review)
Simple and immune relations on countable structures
with Sergei S. Goncharov, Julia F. Knight, and Charles F. D. McCoy
Archive for Mathematical Logic 42 (3): 279-291. 2003.
Spaces of orders and their Turing degree spectra
with Malgorzata A. Dabkowska, Mieczyslaw K. Dabkowski, and Amir A. Togha
Annals of Pure and Applied Logic 161 (9): 1134-1143. 2010.
We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora's …Read more
We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora's [28] investigation of orders on groups in topology and Solomon's [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group Fn of rank n>1 has a bi-order in every Turing degree
Areas of MathematicsScience, Logic, and Mathematics
Π 1 1 relations and paths through
with Sergey S. Goncharov, Julia F. Knight, and Richard A. Shore
Effective categoricity of equivalence structures
Annals of Pure and Applied Logic 141 (1): 61-78. 2006.
We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Sin…Read more
We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence structures are relatively categorical, we further investigate when they are categorical. We also obtain results on the index sets of computable equivalence structures
Model TheoryScience, Logic, and MathematicsAreas of Mathematics
Sequences of $n$-diagrams
with Julia Knight and Andrei Morozov
Effectively and Noneffectively Nowhere Simple Sets
R. Shore proved that every recursively enumerable set can be split into two nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ϵ of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets.…Read more
R. Shore proved that every recursively enumerable set can be split into two nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ϵ of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* is effectively isomorphic to ϵ*, and that there is a nowhere simple set A such that L* is not effectively isomorphic to ϵ*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L* effectively isomorphic to ϵ*