Skip to main content
Log in

On the isomorphism problem for some classes of computable algebraic structures

  • Published:
Archive for Mathematical Logic Aims and scope Submit manuscript

Abstract

We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \(\Sigma _{1}^{1}\)-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Alvir, R., Calvert, W.C., Goodman, G., Harizanov, V.S., Knight, J.F., Morozov, A.S., Miller, R.G., Soskova, A.A., Weisshaar, R.: Interpreting a field in its Heisenberg group (preprint)

  2. Barwise, K.J.: Admissible sets and structures. Springer, Berlin (1975)

    Book  Google Scholar 

  3. Calvert, W.C.: The isomorphism problem for classes of computable fields. Arch. Math. Logic 43, 327–336 (2004)

    Article  MathSciNet  Google Scholar 

  4. Calvert, W.C., Cenzer, D.A., Harizanov, V.S., Morozov, A.S.: Effective categoricity of equivalence structures. Ann. Pure Appl. Logic 141, 61–78 (2006)

    Article  MathSciNet  Google Scholar 

  5. Downey, R.G., Montalbán, A.: The isomorphism problem for torsion-free abelian groups is analytic complete. J. Algebra 320, 2291–2300 (2008)

    Article  MathSciNet  Google Scholar 

  6. Friedman, H.M., Stanley, L.J.: A Borel reducibility theory for classes of countable structures. J. Symb. Log. 54, 894–914 (1989)

    Article  MathSciNet  Google Scholar 

  7. Goncharov, S.S., Knight, J.F.: Computable structure and non-structure theorems. Algebra Logic 41, 351–373 (2002)

    Article  MathSciNet  Google Scholar 

  8. Goncharov, S.S., Harizanov, V.S., Knight, J.F., Morozov, A.S., Romina, A.V.: On automorphic tuples of elements in computable models. Sib. Math. J. 46, 405–412 (2005)

    Article  MathSciNet  Google Scholar 

  9. Harrison, J.A.: Recursive pseudo well-orderings. Trans. Am. Math. Soc. 131, 526–543 (1968)

    Article  MathSciNet  Google Scholar 

  10. Hirschfeldt, D.R., Khoussainov, B.M., Shore, R.A., Slinko, A.M.: Degree spectra and computable dimension in algebraic structures. Ann. Pure Appl. Logic 115, 233–277 (2002)

    Article  MathSciNet  Google Scholar 

  11. Mal’cev, A.I.: On a correspondence between rings and groups. Am. Math. Soc. Trans (ser. 2) 45, 221–232 (1965)

  12. Morozov, A.S.: Groups of computable automorphisms. In: Ershov, Y.L., Goncharov, S.S., Nerode, A., Remmel, J.B. (eds.) Handbook of recursive mathematics, vol. 1, pp. 311–345. Elsevier, Amsterdam (1998)

    Google Scholar 

  13. Morozov, A.S.: Functional trees and automorphisms of models. Algebra Logic 32, 28–38 (1993)

    Article  MathSciNet  Google Scholar 

  14. Rabin, M.O., Scott, D.S.: The undecidability of some simple theories (unpublished manuscript)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Valentina S. Harizanov.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The authors thank the anonymous referee for numerous helpful suggestions that greatly improved this paper. The first four authors are grateful for support from NSF Grant DMS-1600025. The first author was partially supported by Simons Foundation Collaboration Grant 429466 and GW Dean’s Research Chair award. The second author was partially supported by AMS-Simons Foundation Collaboration Grant 626304.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Harizanov, V.S., Lempp, S., McCoy, C.F.D. et al. On the isomorphism problem for some classes of computable algebraic structures. Arch. Math. Logic 61, 813–825 (2022). https://doi.org/10.1007/s00153-021-00811-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00153-021-00811-5

Keywords

Mathematics Subject Classification

Navigation