Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Turing degrees of nonabelian groups


Authors: M. A. Dabkowska, M. K. Dabkowski, V. S. Harizanov and A. S. Sikora
Journal: Proc. Amer. Math. Soc. 135 (2007), 3383-3391
MSC (2000): Primary 03C57, 03D45
DOI: https://doi.org/10.1090/S0002-9939-07-08845-4
Published electronically: May 14, 2007
MathSciNet review: 2322771
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For a countable structure $ \mathcal{A}$, the (Turing) degree spectrum of $ \mathcal{A}$ is the set of all Turing degrees of its isomorphic copies. If the degree spectrum of $ \mathcal{A}$ has the least degree $ \mathbf{d}$, then we say that $ \mathbf{d}$ is the (Turing) degree of the isomorphism type of $ \mathcal{A}$. So far, degrees of the isomorphism types have been studied for abelian and metabelian groups. Here, we focus on highly nonabelian groups. We show that there are various centerless groups whose isomorphism types have arbitrary Turing degrees. We also show that there are various centerless groups whose isomorphism types do not have Turing degrees.


References [Enhancements On Off] (What's this?)

  • 1. S. I. Adjan, The Burnside Problem and Identities in Groups, Nauka, Moscow, 1975 (in Russian). (Translated by J. Lennox and J. Wiegold, Ergebnisse der Mathematik und ihrer Grenzgebiete 95, Springer-Verlag, Berlin, 1979.)MR 0537580 (80d:20035)
  • 2. C. J. Ash, C. G. Jockusch, Jr. and J. F. Knight, Jumps of orderings, Transactions of the American Mathematical Society 319 (1990), pp. 573-599.MR 0955487 (90j:03081)
  • 3. C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, Amsterdam, 2000. MR 1767842 (2001k:03090)
  • 4. W. Burnside, On an unsettled question in the theory of discontinuous groups, Quarterly Journal of Pure and Applied Mathematics 33 (1902), pp. 230-238.
  • 5. W. Calvert, V. Harizanov and A. Shlapentokh, Turing degrees of the isomorphism types of algebraic objects, to appear in the Journal of the London Mathematical Society.
  • 6. R. J. Coles, R. G. Downey and T. A. Slaman, Every set has a least jump enumeration, Journal of the London Mathematical Society 62 (2000), pp. 641-649.MR 1794274 (2002a:03081)
  • 7. R. Downey, On presentations of algebraic structures, in: A. Sorbi, editor, Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics 197 (Marcel Dekker, New York), 1997, pp. 157-205.MR 1455136 (98k:03099)
  • 8. R. Downey and J. F. Knight, Orderings with $ \alpha$th jump degree $ \mathbf{0}^{(\alpha )}$, Proceedings of the American Mathematical Society 114 (1992), pp. 545-552.MR 1065942 (92e:03063)
  • 9. M. Hall, Jr., Solution of the Burnside problem for exponent six, Illinois Journal of Mathematics 2 (1958), pp. 764-786. MR 0102554 (21:1345)
  • 10. V. S. Harizanov, Pure computable model theory, Chapter 1, in: Yu. L. Ershov, S. S. Goncharov, A. Nerode and J. B. Remmel, editors, Handbook of Recursive Mathematics, vol. 1 (Elsevier, Amsterdam, 1998), pp. 3-114.MR 1673621 (2000f:03108)
  • 11. V. S. Harizanov, Computability-theoretic complexity of countable structures,Bulletin of Symbolic Logic 8 (2002), pp. 457-477.MR 1956865 (2004h:03076)
  • 12. V. S. Harizanov, J. F. Knight and A. S. Morozov, Sequences of $ n$-diagrams, Journal of Symbolic Logic 67 (2002), pp. 1227-1247. MR 1926609 (2003f:03046)
  • 13. V. Harizanov and R. Miller, Spectra of structures and relations, to appear in the Journal of Symbolic Logic.
  • 14. D. R. Hirschfeldt, Prime models and relative decidability, Proceedings of the American Mathematical Society 134 (2006), pp. 1495-1498.MR 2199197
  • 15. D. R. Hirschfeldt, B. Khoussainov, R. A. Shore and A. M. Slinko, Degree spectra and computable dimension in algebraic structures, Annals of Pure and Applied Logic 115 (2002), pp. 71-113. MR 1897023 (2003d:03060)
  • 16. S. V. Ivanov, On the Burnside problem on periodic groups, Bulletin of the American Mathematical Society 27 (1992), pp. 257-260. MR 1149874 (93a:20061)
  • 17. A. N. Khisamiev, On the upper semilattice $ \mathcal{L} _{E}$, Siberian Mathematical Journal 45 (2004), pp. 173-187. MR 2048764 (2005f:03061)
  • 18. J. F. Knight, Degrees coded in jumps of orderings, Journal of Symbolic Logic 51 (1986), pp. 1034-1042. MR 0865929 (88j:03030)
  • 19. F. Levi and B. L. van der Waerden, Über eine besondere Klasse von Gruppen, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 9 (1933), pp. 154-158.
  • 20. R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory , Springer-Verlag, Berlin, 1977.MR 0577064 (58:28182)
  • 21. P. S. Novikov and S. I. Adjan, Infinite periodic groups I, Izvestia Akademii Nauk SSSR, Ser. Math. 32 (1968), pp. 212-244 (in Russian).MR 0240178 (39:1532a)
  • 22. P. S. Novikov and S. I. Adjan, Infinite periodic groups II, Izvestia Akademii Nauk SSSR, Ser. Math. 32 (1968), pp. 251-524 (in Russian).MR 0240179 (39:1532b)
  • 23. P. S. Novikov and S. I. Adjan, Infinite periodic groups III, Izvestia Akademii Nauk SSSR, Ser. Math. 32 (1968), pp. 709-731 (in Russian).MR 0240180 (39:1532c)
  • 24. S. Oates, Jump Degrees of Groups, Ph.D. dissertation, University of Notre Dame, 1989.
  • 25. P. G. Odifreddi, Classical Recursion Theory, vol. II, Elsevier, Amsterdam, 1999.MR 1718169 (2001b:03040)
  • 26. M. O. Rabin, Computable algebra, general theory and theory of computable fields, Transactions of the American Mathematical Society 95 (1960), pp. 341-360.MR 0113807 (22:4639)
  • 27. L. J. Richter, Degrees of structures, Journal of Symbolic Logic 46 (1981), pp. 723-731.MR 0641486 (83d:03048)
  • 28. J. J. Rotman, The Theory of Groups, second edition, Allyn and Bacon, Boston, 1973.MR 0442063 (56:451)
  • 29. I. N. Sanov, Solution of Burnside's problem for exponent four, Leningrad State University Annals,Ser. 10 (1940), pp. 166-170 (in Russian).MR 0003397 (2:212c)
  • 30. T. A. Slaman, Relative to any nonrecursive set, Proceedings of the American Mathematical Society 126 (1998), pp. 2117-2122. MR 1443408 (98h:03047)
  • 31. R. I. Soare, Recursively Enumerable Sets and Degrees , Springer-Verlag, Berlin, 1987.MR 0882921 (88m:03003)
  • 32. S. Wehner, Enumerations, countable structures, and Turing degrees, Proceedings of the American Mathematical Society 126 (1998), pp. 2131-2139.MR 1443415 (98h:03059)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03C57, 03D45

Retrieve articles in all journals with MSC (2000): 03C57, 03D45


Additional Information

M. A. Dabkowska
Affiliation: Department of Mathematics, George Washington University, Washington, D.C. 20052
Email: gdab@gwu.edu

M. K. Dabkowski
Affiliation: Department of Mathematical Sciences, University of Texas at Dallas, Richardson, Texas 75083
Email: mdab@utdallas.edu

V. S. Harizanov
Affiliation: Department of Mathematics, George Washington University, Washington, D.C. 20052
Email: harizanv@gwu.edu

A. S. Sikora
Affiliation: Department of Mathematics, State University of New York at Buffalo, Buffalo, New York 14260
Email: asikora@buffalo.edu

DOI: https://doi.org/10.1090/S0002-9939-07-08845-4
Keywords: Computable structure, Turing degree, degree spectrum, isomorphism, group
Received by editor(s): March 21, 2006
Received by editor(s) in revised form: July 1, 2006
Published electronically: May 14, 2007
Communicated by: Julia Knight
Article copyright: © Copyright 2007 American Mathematical Society

American Mathematical Society