Valentina Harizanov

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}}$

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

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

Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fröhlich and Shepherdson realized that the concept of a computable function can make van der Waerden's intuitive notion of an explicit field precise. This led to the notion of a computable structure. In 1960, Rabin proved that every computable field has a computable algebraic closure. However, not every classical result “effectivizes”. Unlike Vaught's theorem that no complete theory has exactly two nonisomorphic countable models, Millar's and Kudaibergenov's result establishes that there is a complete decidable theory that has exactly two nonisomorphic countable models with computable elementary diagrams. In the 1970's, Metakides and Nerode [58], [59] and Remmel [71], [72], [73] used more advanced methods of computability theory to investigate algorithmic properties of fields, vector spaces, and other mathematical structures.

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 α

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

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

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 ϵ*