Isomorphism relations on classes of c.e. algebras
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911384757862400 |
|---|---|
| author | Ho, Meng-Che "Turbo" Ritter, Martin Mauro, Luca San |
| author_facet | Ho, Meng-Che "Turbo" Ritter, Martin Mauro, Luca San |
| contents | We investigate the complexity of isomorphism relations for classes of finitely generated and n-generated computably enumerable (c.e.) algebras, presented via c.e. presentations -- that is, as quotients of term algebras over decidable sets of generators by c.e. congruences. Our goal is to develop a systematic framework for analyzing such isomorphism problems from a computability-theoretic perspective. To compare their complexity, we employ the notion of computable reducibility, measuring these relations against canonical benchmarks on c.e. sets, such as =^{ce}, E_0^{ce}, and the ordinal-indexed family E_min(α). A central insight of our work is the interplay between the algebraic structure and the algorithmic complexity: we show that if every algebra in a class satisfies the ascending chain condition on its congruence lattice, then the corresponding isomorphism relation is computably reducible to =^{ce}. We also apply this framework to a range of concrete cases. In particular, we analyze the isomorphism relations for finitely generated commutative semigroups, monoids, and groups, positioning them within the broader landscape of classification problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_13005 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Isomorphism relations on classes of c.e. algebras Ho, Meng-Che "Turbo" Ritter, Martin Mauro, Luca San Logic 03C57, 20F10 We investigate the complexity of isomorphism relations for classes of finitely generated and n-generated computably enumerable (c.e.) algebras, presented via c.e. presentations -- that is, as quotients of term algebras over decidable sets of generators by c.e. congruences. Our goal is to develop a systematic framework for analyzing such isomorphism problems from a computability-theoretic perspective. To compare their complexity, we employ the notion of computable reducibility, measuring these relations against canonical benchmarks on c.e. sets, such as =^{ce}, E_0^{ce}, and the ordinal-indexed family E_min(α). A central insight of our work is the interplay between the algebraic structure and the algorithmic complexity: we show that if every algebra in a class satisfies the ascending chain condition on its congruence lattice, then the corresponding isomorphism relation is computably reducible to =^{ce}. We also apply this framework to a range of concrete cases. In particular, we analyze the isomorphism relations for finitely generated commutative semigroups, monoids, and groups, positioning them within the broader landscape of classification problems. |
| title | Isomorphism relations on classes of c.e. algebras |
| topic | Logic 03C57, 20F10 |
| url | https://arxiv.org/abs/2601.13005 |