-
On Cohesive Products of Fields
Authors:
Rumen Dimitrov,
Valentina Harizanov,
Henry J. Klatt,
Keshav Srinivasan
Abstract:
We develop the foundations of effective ultraproducts of fields and their Galois groups using the methods of computability theory. These computability-theoretic analogs of ultraproducts are called cohesive products, since the role of an ultrafilter is played by a cohesive set. A set of natural numbers is cohesive if it is infinite and cannot be partitioned into two infinite subsets by any computab…
▽ More
We develop the foundations of effective ultraproducts of fields and their Galois groups using the methods of computability theory. These computability-theoretic analogs of ultraproducts are called cohesive products, since the role of an ultrafilter is played by a cohesive set. A set of natural numbers is cohesive if it is infinite and cannot be partitioned into two infinite subsets by any computably enumerable set. In particular, we investigate the way cohesive products interact with field extensions with emphasis on both finite and infinite Galois extensions, and the associated Galois groups. We study the first-order theories and definability of cohesive powers of number fields, and characterize the infinite Galois groups of cohesive powers for a large class of infinite Galois extensions. Finally, we introduce hyper-automorphisms, which are automorphisms of a cohesive power that respect non-standard field operations, and give a complete description of the hyper-automorphism groups of cohesive powers of a large class of computable Galois extensions, and use them to describe the classical infinite Galois groups of such fields.
△ Less
Submitted 10 April, 2026;
originally announced April 2026.
-
sp-Homogeneous Linear Orderings
Authors:
Wesley Calvert,
Douglas Cenzer,
David Gonzalez,
Valentina Harizanov,
Keng Meng Ng
Abstract:
We study linear orderings expanded by functions for successor and predecessor. The successor and predecessor on linear orderings capture the relatively intrinsically computably enumerable information about orderings in much the same way that dependence captures that for vector spaces. In particular, the sp-homogeneous and weakly sp-homogeneous linear orderings are those which are (ultra-)homogeneo…
▽ More
We study linear orderings expanded by functions for successor and predecessor. The successor and predecessor on linear orderings capture the relatively intrinsically computably enumerable information about orderings in much the same way that dependence captures that for vector spaces. In particular, the sp-homogeneous and weakly sp-homogeneous linear orderings are those which are (ultra-)homogeneous or weakly homogeneous with this additional structure.
We demonstrate that these orderings are always relatively $Δ_4$ categorical and determine exactly which ones are (uniformly) relatively $Δ_3$ categorical.
We also provide a classification for sp-homogeneity and weak sp-homogeneity.
We establish that this is the best possible classification by showing that the set of sp-homogeneous linear orderings is $Π_5^0$ complete, and that the set of weakly sp-homogeneous linear orderings is $Σ_6^0$ complete.
These results are obtained in two different ways, one using a hands-on computability theoretic approach and another using more abstract descriptive set theory.
△ Less
Submitted 13 April, 2026; v1 submitted 29 September, 2025;
originally announced September 2025.
-
Generically Computable Linear Orderings
Authors:
Wesley Calvert,
Douglas Cenzer,
David Gonzalez,
Valentina Harizanov
Abstract:
We study notions of generic and coarse computability in the context of computable structure theory. Our notions are stratified by the $Σ_β$ hierarchy. We focus on linear orderings. We show that at the $Σ_1$ level all linear orderings have both generically and coarsely computable copies. This behavior changes abruptly at higher levels; we show that at the $Σ_{α+2}$ level for any $α\inω_1^{ck}$ the…
▽ More
We study notions of generic and coarse computability in the context of computable structure theory. Our notions are stratified by the $Σ_β$ hierarchy. We focus on linear orderings. We show that at the $Σ_1$ level all linear orderings have both generically and coarsely computable copies. This behavior changes abruptly at higher levels; we show that at the $Σ_{α+2}$ level for any $α\inω_1^{ck}$ the set of linear orderings with generically or coarsely computable copies is $\mathbfΣ_1^1$-complete and therefore maximally complicated. This development is new even in the general analysis of generic and coarse computability of countable structures. In the process of proving these results we introduce new tools for understanding generically and coarsely computable structures. We are able to give a purely structural statement that is equivalent to having a generically computable copy and show that every relational structure with only finitely many relations has coarsely and generically computable copies at the lowest level of the hierarchy.
△ Less
Submitted 25 January, 2024;
originally announced January 2024.
-
In Memory of Martin Davis
Authors:
Wesley Calvert,
Valentina Harizanov,
Eugenio G. Omodeo,
Alberto Policriti,
Alexandra Shlapentokh
Abstract:
The present paper gives an account for the general mathematical reader of the life and work of Martin Davis. Since two rather comprehensive autobiographical accounts and two long biographical interviews already exist, the present work focusses on Davis's scientific achievements, including work on computably enumerable sets, universal Turing machines, the hyperarithmetical hierarchy, neural network…
▽ More
The present paper gives an account for the general mathematical reader of the life and work of Martin Davis. Since two rather comprehensive autobiographical accounts and two long biographical interviews already exist, the present work focusses on Davis's scientific achievements, including work on computably enumerable sets, universal Turing machines, the hyperarithmetical hierarchy, neural networks, Hilbert's Tenth Problem, and automated reasoning.
△ Less
Submitted 15 January, 2024;
originally announced January 2024.
-
Computability in infinite Galois theory and algorithmically random algebraic fields
Authors:
Wesley Calvert,
Valentina Harizanov,
Alexandra Shlapentokh
Abstract:
We introduce a notion of algorithmic randomness for algebraic fields. We prove the existence of a continuum of algebraic extensions of $\mathbb{Q}$ that are random according to our definition. We show that there are noncomputable algebraic fields which are not random. We also partially characterize the index set, relative to an oracle, of the set of random algebraic fields computable relative to t…
▽ More
We introduce a notion of algorithmic randomness for algebraic fields. We prove the existence of a continuum of algebraic extensions of $\mathbb{Q}$ that are random according to our definition. We show that there are noncomputable algebraic fields which are not random. We also partially characterize the index set, relative to an oracle, of the set of random algebraic fields computable relative to that oracle.
In order to carry out this investigation of randomness for fields, we develop computability in the context of infinite Galois theory (where the relevant Galois groups are uncountable), including definitions of computable and computably enumerable Galois groups and computability of Haar measure on the Galois groups.
△ Less
Submitted 3 July, 2024; v1 submitted 7 December, 2023;
originally announced December 2023.
-
Cohesive Powers of Structures
Authors:
Valentina Harizanov,
Keshav Srinivasan
Abstract:
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 countable ultrapower 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 cohesi…
▽ More
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 countable ultrapower 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. 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.
△ Less
Submitted 6 April, 2023;
originally announced April 2023.
-
On cohesive powers of linear orders
Authors:
Rumen Dimitrov,
Valentina Harizanov,
Andrey Morozov,
Paul Shafer,
Alexandra A. Soskova,
Stefan V. Vatev
Abstract:
Cohesive powers of computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let $ω$, $ζ$, and $η$ 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 $ω$. If…
▽ More
Cohesive powers of computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let $ω$, $ζ$, and $η$ 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 $ω$. If $\mathcal{L}$ is a computable copy of $ω$ that is computably isomorphic to the usual presentation of $ω$, then every cohesive power of $\mathcal{L}$ has order-type $ω+ ζη$. However, there are computable copies of $ω$, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to $ω+ ζη$. For example, we show that there is a computable copy of $ω$ with a cohesive power of order-type $ω+ η$. Our most general result is that if $X \subseteq \mathbb{N} \setminus \{0\}$ is a Boolean combination of $Σ_2$ sets, thought of as a set of finite order-types, then there is a computable copy of $ω$ with a cohesive power of order-type $ω+ σ(X \cup \{ω+ ζη+ ω^*\})$, where $σ(X \cup \{ω+ ζη+ ω^*\})$ denotes the shuffle of the order-types in $X$ and the order-type $ω+ ζη+ ω^*$. Furthermore, if $X$ is finite and non-empty, then there is a computable copy of $ω$ with a cohesive power of order-type $ω+ σ(X)$.
△ Less
Submitted 22 February, 2023; v1 submitted 1 September, 2020;
originally announced September 2020.
-
Interpreting a field in its Heisenberg group
Authors:
Rachael Alvir,
Wesley Calvert,
Grant Goodman,
Valentina Harizanov,
Julia Knight,
Andrey Morozov,
Russell Miller,
Alexandra Soskova,
Rose Weisshaar
Abstract:
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 $(u,v)$ as parameters. We show that $F$ is interpreted in $H(F)$ using computable $Σ_1$ formulas with no parameters. We give two proofs. The…
▽ More
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 $(u,v)$ as parameters. We show that $F$ is interpreted in $H(F)$ using computable $Σ_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.
△ Less
Submitted 5 April, 2022; v1 submitted 21 June, 2020;
originally announced June 2020.
-
Cohesive Powers of Linear Orders
Authors:
Rumen Dimitrov,
Valentina Harizanov,
Andrey Morozov,
Paul Shafer,
Alexandra Soskova,
Stefan Vatev
Abstract:
Cohesive powers of computable structures can be viewed as effective ultraproducts over effectively indecomposable sets called cohesive sets. We investigate the isomorphism types of cohesive powers $Π_{C}% \mathcal{L}$ for familiar computable linear orders $\mathcal{L}$. If $% \mathcal{L}$ is isomorphic to the ordered set of natural numbers $\mathbb{N}$ and has a computable successor function, then…
▽ More
Cohesive powers of computable structures can be viewed as effective ultraproducts over effectively indecomposable sets called cohesive sets. We investigate the isomorphism types of cohesive powers $Π_{C}% \mathcal{L}$ for familiar computable linear orders $\mathcal{L}$. If $% \mathcal{L}$ is isomorphic to the ordered set of natural numbers $\mathbb{N}$ and has a computable successor function, then $Π_{C}\mathcal{L}$ is isomorphic to $\mathbb{N}+\mathbb{Q}\times \mathbb{Z}.$ Here, $+$ stands for the sum and $\times $ for the lexicographical product of two orders. We construct computable linear orders $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ isomorphic to $\mathbb{N},$ both with noncomputable successor functions, such that $Π_{C}\mathcal{L}_{1}\mathbb{\ }$is isomorphic to $\mathbb{N}+% \mathbb{Q}\times \mathbb{Z}$, while $Π_{C}\mathcal{L}_{2}$ is not$.$ While cohesive powers preserve all $Π_{2}^{0}$ and $Σ_{2}^{0}$ sentences, we provide new examples of $Π_{3}^{0}$ sentences $Φ$ and computable structures $% \mathcal{M}$ such that $\mathcal{M}\vDash Φ$ while $Π_{C}\mathcal{M}% \vDash \urcorner Φ.$
△ Less
Submitted 15 January, 2019;
originally announced January 2019.
-
Turing Degrees and Automorphism Groups of Substructure Lattices
Authors:
Rumen Dimitrov,
Valentina Harizanov,
Andrey Morozov
Abstract:
The study of automorphisms of computable and other structures connects computability theory with classical group theory. Among the noncomputable countable structures, computably enumerable structures are one of the most important objects of investigation in computable model theory. In this paper, we focus on the lattice structure of computably enumerable substructures of a given canonical computab…
▽ More
The study of automorphisms of computable and other structures connects computability theory with classical group theory. Among the noncomputable countable structures, computably enumerable structures are one of the most important objects of investigation in computable model theory. In this paper, we focus on the lattice structure of computably enumerable substructures of a given canonical computable structure. In particular, for a Turing degree $\mathbf{d}$, we investigate the groups of $\mathbf{d}$ -computable automorphisms of the lattice of $\mathbf{d}$-computably enumerable vector spaces, of the interval Boolean algebra $\mathcal{B}_{η}$ of the ordered set of rationals, and of the lattice of $\mathbf{d}$ -computably enumerable subalgebras of $\mathcal{B}_{η}$. For these groups we show that Turing reducibility can be used to substitute the group-theoretic embedding. We also prove that the Turing degree of the isomorphism types for these groups is the second Turing jump of $\mathbf{d}$ , $\mathbf{d^{\prime \prime }}$.
△ Less
Submitted 3 November, 2018;
originally announced November 2018.
-
Strong Jump Inversion
Authors:
W. Calvert,
A. Frolov,
V. Harizanov,
J. Knight,
C. McCoy,
A. Soskova,
S. Vatev
Abstract:
We say that a structure $\mathcal{A}$ admits \emph{strong jump inversion} provided that for every oracle $X$, if $X'$ computes $D(\mathcal{C})'$ for some $\mathcal{C}\cong\mathcal{A}$, then $X$ computes $D(\mathcal{B})$ for some $\mathcal{B}\cong\mathcal{A}$. Jockusch and Soare \cite{JS} showed that there are low linear orderings without computable copies, but Downey and Jockusch \cite{DJ} showed…
▽ More
We say that a structure $\mathcal{A}$ admits \emph{strong jump inversion} provided that for every oracle $X$, if $X'$ computes $D(\mathcal{C})'$ for some $\mathcal{C}\cong\mathcal{A}$, then $X$ computes $D(\mathcal{B})$ for some $\mathcal{B}\cong\mathcal{A}$. Jockusch and Soare \cite{JS} showed that there are low linear orderings without computable copies, but Downey and Jockusch \cite{DJ} showed that every Boolean algebra admits strong jump inversion. More recently, D.\ Marker and R.\ Miller \cite{MM} have shown that all countable models of $DCF_0$ (the theory of differentially closed fields of characteristic $0$) admit strong jump inversion. We establish a general result with sufficient conditions for a structure $\mathcal{A}$ to admit strong jump inversion. Our conditions involve an enumeration of $B_1$-types, where these are made up of formulas that are Boolean combinations of existential formulas. Our general result applies to some familiar kinds of structures, including some classes of linear orderings and trees. We do not get the result of Downey and Jockusch for arbitrary Boolean algebras, but we do get a result for Boolean algebras with no $1$-atom, with some extra information on the complexity of the isomorphism. Our general result gives the result of Marker and Miller. In order to apply our general result, we produce a computable enumeration of the types realized in models of $DCF_0$. This also yields the fact that the saturated model of $DCF_0$ has a decidable copy.
△ Less
Submitted 21 August, 2018;
originally announced August 2018.
-
Generically Computable Equivalence Structures and Isomorphisms
Authors:
Wesley Calvert,
Douglas Cenzer,
Valentina Harizanov
Abstract:
We define notions of generically and coarsely computable relations and structures and functions between structures. We investigate the existence and uniqueness of equivalence structures in the context of these definitions
We define notions of generically and coarsely computable relations and structures and functions between structures. We investigate the existence and uniqueness of equivalence structures in the context of these definitions
△ Less
Submitted 8 August, 2018;
originally announced August 2018.
-
Turing degrees of isomorphism types of geometric objects
Authors:
Wesley Calvert,
Valentina Harizanov,
Alexandra Shlapentokh
Abstract:
We initiate the computability-theoretic study of ringed spaces and schemes. In particular, we show that any Turing degree may occur as the least degree of an isomorphic copy of a structure of these kinds. We also show that these structures may fail to have a least degree.
We initiate the computability-theoretic study of ringed spaces and schemes. In particular, we show that any Turing degree may occur as the least degree of an isomorphic copy of a structure of these kinds. We also show that these structures may fail to have a least degree.
△ Less
Submitted 9 November, 2011; v1 submitted 14 June, 2011;
originally announced June 2011.
-
Effective categoricity of Abelian p-groups
Authors:
W. Calvert,
D. Cenzer,
V. S. Harizanov,
A. Morozov
Abstract:
Let p be a fixed prime. An Abelian p-group is an Abelian group (not necessarily finitely generated) in which every element has for its order some power of p. The countable Abelian p-groups are classified by Ulm's theorem, and Khisamiev characterized the Abelian p-groups with computable copies. A computable structure A is said to be $Δ^0_α$ categorical if for any computable structure B isomorphic…
▽ More
Let p be a fixed prime. An Abelian p-group is an Abelian group (not necessarily finitely generated) in which every element has for its order some power of p. The countable Abelian p-groups are classified by Ulm's theorem, and Khisamiev characterized the Abelian p-groups with computable copies. A computable structure A is said to be $Δ^0_α$ categorical if for any computable structure B isomorphic to A there is a $Δ^0_α$ function witnessing that the two are isomorphic.
The present paper seeks to characterize $Δ^0_α$ categoricity for Abelian p-groups, and results of this kind are given for broad classes of Abelian p-groups and values of $α$. The remaining open cases are exhaustively described.
△ Less
Submitted 13 May, 2008;
originally announced May 2008.
-
Effective categoricity of equivalence Structures
Authors:
W. Calvert,
D. Cenzer,
V. S. Harizanov,
A. Morozov
Abstract:
An equivalence structure is a set with a single binary relation, satisfying sentences stating that the relation is an equivalence relation. A computable structure A is said to be $Δ^0_α$ categorical if for any computable structure B isomorphic to A there is a $Δ^0_α$ function witnessing that the two are isomorphic.
The present paper gives an exact characterization of $Δ^0_α$ equivalence struct…
▽ More
An equivalence structure is a set with a single binary relation, satisfying sentences stating that the relation is an equivalence relation. A computable structure A is said to be $Δ^0_α$ categorical if for any computable structure B isomorphic to A there is a $Δ^0_α$ function witnessing that the two are isomorphic.
The present paper gives an exact characterization of $Δ^0_α$ equivalence structures where $α= 1$ or $α\geq 3$. Extensive results for $α= 2$ are also given, and open cases are exhaustively described.
△ Less
Submitted 13 May, 2008;
originally announced May 2008.
-
Index Sets of Computable Structures
Authors:
Wesley Calvert,
Valentina S. Harizanov,
Julia F. Knight,
Sara Miller
Abstract:
The \emph{index set} of a computable structure $\mathcal{A}$ is the set of indices for computable copies of $\mathcal{A}$. We determine the complexity of the index sets of various mathematically interesting structures, including arbitrary finite structures, $\mathbb{Q}$-vector spaces, Archimedean real closed ordered fields, reduced Abelian $p$-groups of length less than $ω^{2}$, and models of th…
▽ More
The \emph{index set} of a computable structure $\mathcal{A}$ is the set of indices for computable copies of $\mathcal{A}$. We determine the complexity of the index sets of various mathematically interesting structures, including arbitrary finite structures, $\mathbb{Q}$-vector spaces, Archimedean real closed ordered fields, reduced Abelian $p$-groups of length less than $ω^{2}$, and models of the original Ehrenfeucht theory. The index sets for these structures all turn out to be $m$-complete $Π_{n}^{0}$, $d$-$Σ_{n}^{0}$, or $Σ_{n}^{0}$, for various $n$. In each case, the calculation involves finding an \textquotedblleft optimal\textquotedblright% \ sentence (i.e., one of simplest form) that describes the structure. The form of the sentence (computable $Π_{n}$, $d$-$Σ_{n}$, or $Σ_{n}$) yields a bound on the complexity of the index set. When we show $m$% -completeness of the index set, we know that the sentence is optimal. For some structures, the first sentence that comes to mind is not optimal, and another sentence of simpler form is shown to serve the purpose. For some of the groups, this involves Ramsey theory.
△ Less
Submitted 22 March, 2008;
originally announced March 2008.
-
Compactness of the space of left orders
Authors:
Malgorzata A. Dabkowska,
Mieczyslaw K. Dabkowski,
Valentina S. Harizanov,
Jozef H. Przytycki,
Michael A. Veve
Abstract:
A left order on a magma (e.g., semigroup) is a total order of its elements that is left invariant under the magma operation. A natural topology can be introduced on the set of all left orders of an arbitrary magma. We prove that this topological space is compact. Interesting examples of nonassociative magmas, whose spaces of right orders we analyze, come from knot theory and are called quandles.…
▽ More
A left order on a magma (e.g., semigroup) is a total order of its elements that is left invariant under the magma operation. A natural topology can be introduced on the set of all left orders of an arbitrary magma. We prove that this topological space is compact. Interesting examples of nonassociative magmas, whose spaces of right orders we analyze, come from knot theory and are called quandles. Our main result establishes an interesting connection between topological properties of the space of left orders on a group, and the classical algebraic result by Conrad and Los concerning the existence of left orders.
△ Less
Submitted 3 March, 2007; v1 submitted 11 June, 2006;
originally announced June 2006.
-
Turing Degrees of Isomorphism Types of Algebraic Objects
Authors:
Wesley Calvert,
Valentina Harizanov,
Alexandra Shlapentokh
Abstract:
The Turing degree spectrum of a countable structure $\mathcal{A}$ is the set of all Turing degrees of isomorphic copies of $\mathcal{A}$. The Turing degree of the isomorphism type of $\mathcal{A}$, if it exists, is the least Turing degree in its degree spectrum. We show there are countable fields, rings, and torsion-free abelian groups of arbitrary rank, whose isomorphism types have arbitrary Tu…
▽ More
The Turing degree spectrum of a countable structure $\mathcal{A}$ is the set of all Turing degrees of isomorphic copies of $\mathcal{A}$. The Turing degree of the isomorphism type of $\mathcal{A}$, if it exists, is the least Turing degree in its degree spectrum. We show there are countable fields, rings, and torsion-free abelian groups of arbitrary rank, whose isomorphism types have arbitrary Turing degrees. We also show that there are structures in each of these classes whose isomorphism types do not have Turing degrees.
△ Less
Submitted 6 July, 2005;
originally announced July 2005.