Search for: All records

Abstract We introduce a notion of algorithmic randomness for algebraic fields. We prove the existence of a continuum of algebraic extensions of 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 the 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. 

Abstract 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 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 α ∈ ωCK 1 the set of linear orderings with generically or coarsely computable copies is Σ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. 

We give a systematic account of the current state of knowledge of an e↵ective analogue of the ultraproduct construction. We start with a product of a uniformly computable sequence of computable structures indexed by the set of natural numbers. The equality of elements and sat- isfaction of formulas are defined modulo a subset of the index set, which is cohesive, i.e., indecomposable with respect to computably enumerable sets. We present an analogue of Lo ́s’s theorem for e↵ective ultraprod- ucts and a number of results on definability and isomorphism types of the e↵ective ultrapowers of the field of rational numbers, when the com- plements of cohesive sets are computably enumerable. These e↵ective ultraproducts arose naturally in the study of the automorphisms of the lattice of computably enumerable vector spaces. Previously, a number of authors considered related constructions in the context of nonstandard models of fragments of arithmetic. 

Generically computable sets, as introduced by Jockusch and Schupp, have been of great interest in recent years. This idea of approximate computability was motivated by asymptotic density problems studied by Gromov in combinatorial group theory. More recently, we have defined notions of generically computable structures, and studied in particular equivalence structures and injection structures. A structure is said to be generically computable if there is a c.e. substructure defined on an asymptotically dense set, where the functions are computable and the relations are computably enumerable. It turned out that every equivalence structure has a generically computable copy, whereas there is a non-trivial characterization of the injection structures with generically computable copies. In this paper, we return to group theory, as we explore the generic computability of Abelian groups. We show that any Abelian p-group has a generically computable copy and that such a group has a Σ2-generically computably enumerable copy if and only it has a computable copy. We also give a partial characterization of the Σ1-generically computably enumerable Abelian p-groups. We also give a non-trivial characterization of the generically computable Abelian groups that are not p-groups. 

Inspired by the study of generic and coarse computability in computability theory, we extend such investigation to the context of computable model theory. In this paper, we continue our study initiated in the previous paper (Journal of Logic and Computation 32 (2022) 581–607) , where we introduced and studied the notions of generically and coarsely computable structures and their generalizations. In this paper, we introduce the notions of generically and coarsely computable isomorphisms, and their weaker variants. We sometimes also require that the isomorphisms preserve the density structure. For example, for any coarsely computable structure A, there is a density preserving coarsely computable isomorphism from A to a computable structure. We demonstrate that each notion of generically and coarsely computable isomorphisms, density preserving or not, gives interesting insights into the structures we consider, focusing on various equivalence structures and injection structures.