Valentina Harizanov

R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) 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 (non) 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* (A) is effectively isomorphic to ϵ*, and that there is a nowhere simple set A such that L*(A) 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*(A) effectively isomorphic to ϵ*. Mathematics Subject Classification: 03D25, 03D10.

We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$, using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, Melnikov, R. Miller, and Montalbán. This proof allows the possibility that the elements of F are represented by tuples in $H(F)$ of no fixed arity. The second proof is direct, giving explicit finitary existential formulas that define the interpretation, with elements of F represented by triples in $H(F)$. Looking at what was used to arrive at this parameter-free interpretation of F in $H(F)$, we give general conditions sufficient to eliminate parameters from interpretations.

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure is categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.An additional relation R on the domain of a computable structure is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.The dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees

Mathematical logic is the study of reasoning about mathematical objects and the degree to which mathematical and scientific reasoning can be formalized and mechanized. Logic provides the foundations of mathematics and of theoretical computer science. Classical logic defined truth, developed the theory of infinite numbers, resolved paradoxes of naive set theory, defined what an algorithm is, and established that certain mathematical principles are independent from the rest of mathematics. Modern logic contributes to current developments in mathematics and its foundations, and continues to closely interact with various areas of mathematics. Essential and surprising connections are often found in order to solve big problems. To bring various resources into a single argument, common methods, uniform terminology, and concisely stated theorems are needed. This interaction of disciplines has not only led to new approaches and results but also to new areas of mathematical research, such as computable structure theory, reverse mathematics, and the emerging quantum computing theory.

Computability theory is the mathematical theory of algorithms, which explores the power and limitations of computation. Classical computability theory formalized the intuitive notion of an algorithm and provided a theoretical basis for digital computers. It also demonstrated the limitations of algorithms and showed that most sets of natural numbers and the problems they encode are not decidable (Turing computable). Important results of modern computability theory include the classification of the computational difficulty of sets and problems. Arithmetical and hyperarithmetical hierarchies and the Turing degrees provide important measures of the level of such difficulty. There are uncountably many Turing degrees and they are partially ordered. These classifications are used in contemporary research to investigate the complexity of problems in modern computable mathematics, for example, regarding structures and their properties.

In 1934, Skolem gave a remarkable construction of a countable nonstandard model of arithmetic. His construction contains ideas of the ultrapower construction which was introduced in model theory 20 years later. However, typical ultrapower constructions produce uncountable models. Skolem’s construction can also be connected with ideas from computability theory, formalized by Turing and others in 1936. The proof of one of Skolem’s key statements can be interpreted using computability-theoretic notions of indecomposable sets developed in the late 1950s. We favor the computability-theoretic approach and describe the connections of Skolem’s ideas with our current study of cohesive powers of models in computable model theory.

A cohesive power of a structure is an effective analog of the classical ultrapower of a structure. We start with a computable structure, and consider its effective power over a cohesive set of natural numbers. A cohesive set is an infinite set of natural numbers that is indecomposable with respect to computably enumerable sets. It plays the role of an ultrafilter, and the elements of a cohesive power are the equivalence classes of certain partial computable functions determined by the cohesive set. Thus, unlike many classical ultrapowers, a cohesive power is a countable structure. In this paper we focus on cohesive powers of graphs, equivalence structures, and computable structures with a single unary function satisfying various properties, which can also be viewed as directed graphs. For these computable structures, we investigate the isomorphism types of their cohesive powers, as well as the properties of cohesive powers when they are not isomorphic to the original structure.

Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual presentation of$\omega $, then every cohesive power of$\mathcal {L}$has order-type$\omega + \zeta \eta $. However, there are computable copies of$\omega $, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to$\omega + \zeta \eta $. For example, we show that there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \eta $. Our most general result is that if$X \subseteq \mathbb {N} \setminus \{0\}$is a Boolean combination of$\Sigma _2$sets, thought of as a set of finite order-types, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$, where$\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$denotes the shuffle of the order-types inXand the order-type$\omega + \zeta \eta + \omega ^*$. Furthermore, ifXis finite and non-empty, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X)$.

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 α.

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 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.

We consider embeddings of structures which preserve spectra: if g: M → S with S computable, then M should have the same Turing degree spectrum (as a structure) that g(M) has (as a relation on S). We show that the computable dense linear order L is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph G. Such structures are said to be spectrally universal. We use our results to answer a question of Goncharov, and also to characterize the possible spectra of structures as precisely the spectra of unary relations on G. Finally, we consider the extent to which all spectra of unary relations on the structure L may be realized by such embeddings, offering partial results and building the first known example of a structure whose spectrum contains precisely those degrees c with c′ ≥T 0″

A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary for to contain every Turing degree. These conditions imply that if every Turing degree 0″ can be realized in via an isomorphism of the same Turing degree as its image of R, then contains every Turing degree. We also discuss an example of and R whose coincides with the Turing degrees which are 0′