Valentina Harizanov

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

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