View in EDS

Generically computable Abelian groups and isomorphisms.

Saved in:
Bibliographic Details
Title: Generically computable Abelian groups and isomorphisms.
Authors: Calvert, Wesley1 (AUTHOR), Cenzer, Douglas2 (AUTHOR), Harizanov, Valentina3 (AUTHOR)
Source: Journal of Logic & Computation. Sep2025, Vol. 35 Issue 6, p1-21. 21p.
Subjects: Abelian groups, Isomorphism (Mathematics), Recursion theory, Computable analysis, Cyclic groups, Equivalence classes (Set theory)
Abstract: Approximate computability, in the form of generically computable sets introduced by Jockusch and Schupp, 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. We also introduced a graded family of elementarity conditions for substructures, in which the dense substructures more strongly resemble the original structure by being |$\varSigma _{n}$| elementary substructures for a given |$n$|⁠. We now return to group theory, as we explore the generic computability of torsion Abelian groups. We show that any Abelian |$p$| -group has a generically computable copy, and that, for an important family of Abelian |$p$| -groups, a group |$\mathcal{G}$| has a |$\varSigma _{2}$| -generically c.e. copy if and only if it has a computable copy. We also give a partial characterization of the |$\varSigma _{1}$| -generically c.e. Abelian |$p$| -groups, and give a non-trivial characterization of the generically computable torsion Abelian groups. Coarsely computable and |$\varSigma _{n}$| -coarsely c.e. groups are also studied. It is well known that there are computable Abelian groups that are countable sums of cyclic groups of order |$p$| and |$p^{2}$| that are not computably isomorphic. We present a notion of generically computable isomorphism and give conditions under which two such groups will be generically computably isomorphic. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Approximate computability, in the form of generically computable sets introduced by Jockusch and Schupp, 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. We also introduced a graded family of elementarity conditions for substructures, in which the dense substructures more strongly resemble the original structure by being |$\varSigma _{n}$| elementary substructures for a given |$n$|⁠. We now return to group theory, as we explore the generic computability of torsion Abelian groups. We show that any Abelian |$p$| -group has a generically computable copy, and that, for an important family of Abelian |$p$| -groups, a group |$\mathcal{G}$| has a |$\varSigma _{2}$| -generically c.e. copy if and only if it has a computable copy. We also give a partial characterization of the |$\varSigma _{1}$| -generically c.e. Abelian |$p$| -groups, and give a non-trivial characterization of the generically computable torsion Abelian groups. Coarsely computable and |$\varSigma _{n}$| -coarsely c.e. groups are also studied. It is well known that there are computable Abelian groups that are countable sums of cyclic groups of order |$p$| and |$p^{2}$| that are not computably isomorphic. We present a notion of generically computable isomorphism and give conditions under which two such groups will be generically computably isomorphic. [ABSTRACT FROM AUTHOR]
ISSN:0955792X
DOI:10.1093/logcom/exaf044