Turing degrees of nonabelian groups

Dabkowska, M.; Dabkowski, M.; Harizanov, V.; Sikora, A.

doi:10.1090/S0002-9939-07-08845-4

Turing degrees of nonabelian groups
HTML articles powered by AMS MathViewer

by M. A. Dabkowska, M. K. Dabkowski, V. S. Harizanov and A. S. Sikora

Proc. Amer. Math. Soc. 135 (2007), 3383-3391

DOI: https://doi.org/10.1090/S0002-9939-07-08845-4

Published electronically: May 14, 2007

PDF | Request permission

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

S. I. Adian, The Burnside problem and identities in groups, Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], vol. 95, Springer-Verlag, Berlin-New York, 1979. Translated from the Russian by John Lennox and James Wiegold. MR 537580
C. J. Ash, C. G. Jockusch Jr., and J. F. Knight, Jumps of orderings, Trans. Amer. Math. Soc. 319 (1990), no. 2, 573–599. MR 955487, DOI 10.1090/S0002-9947-1990-0955487-0
C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
W. Burnside, On an unsettled question in the theory of discontinuous groups, Quarterly Journal of Pure and Applied Mathematics 33 (1902), pp. 230–238.
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.
Richard J. Coles, Rod G. Downey, and Theodore A. Slaman, Every set has a least jump enumeration, J. London Math. Soc. (2) 62 (2000), no. 3, 641–649. MR 1794274, DOI 10.1112/S0024610700001459
Rodney G. Downey, On presentations of algebraic structures, Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., vol. 187, Dekker, New York, 1997, pp. 157–205. MR 1455136
Rodney Downey and Julia F. Knight, Orderings with $\alpha$th jump degree ${\bf 0}^{(\alpha )}$, Proc. Amer. Math. Soc. 114 (1992), no. 2, 545–552. MR 1065942, DOI 10.1090/S0002-9939-1992-1065942-0
Marshall Hall Jr., Solution of the Burnside problem for exponent six, Illinois J. Math. 2 (1958), 764–786. MR 102554
Valentina S. Harizanov, Pure computable model theory, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114. MR 1673621, DOI 10.1016/S0049-237X(98)80002-5
Valentina S. Harizanov, Computability-theoretic complexity of countable structures, Bull. Symbolic Logic 8 (2002), no. 4, 457–477. MR 1956865, DOI 10.2307/797952
Valentina S. Harizanov, Julia F. Knight, and Andrei S. Morozov, Sequences of $n$-diagrams, J. Symbolic Logic 67 (2002), no. 3, 1227–1247. MR 1926609, DOI 10.2178/jsl/1190150160
V. Harizanov and R. Miller, Spectra of structures and relations, to appear in the Journal of Symbolic Logic.
Denis R. Hirschfeldt, Computable trees, prime models, and relative decidability, Proc. Amer. Math. Soc. 134 (2006), no. 5, 1495–1498. MR 2199197, DOI 10.1090/S0002-9939-05-08097-4
Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore, and Arkadii M. Slinko, Degree spectra and computable dimensions in algebraic structures, Ann. Pure Appl. Logic 115 (2002), no. 1-3, 71–113. MR 1897023, DOI 10.1016/S0168-0072(01)00087-2
Sergei V. Ivanov, On the Burnside problem on periodic groups, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 2, 257–260. MR 1149874, DOI 10.1090/S0273-0979-1992-00305-1
A. N. Khisamiev, On the Ershov upper semilattice $\mathfrak {L}_E$, Sibirsk. Mat. Zh. 45 (2004), no. 1, 211–228 (Russian, with Russian summary); English transl., Siberian Math. J. 45 (2004), no. 1, 173–187. MR 2048764, DOI 10.1023/B:SIMJ.0000013023.90154.bb
Julia F. Knight, Degrees coded in jumps of orderings, J. Symbolic Logic 51 (1986), no. 4, 1034–1042. MR 865929, DOI 10.2307/2273915
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.
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
P. S. Novikov and S. I. Adjan, Infinite periodic groups. I, Izv. Akad. Nauk SSSR Ser. Mat. 32 (1968), 212–244 (Russian). MR 0240178
P. S. Novikov and S. I. Adjan, Infinite periodic groups. I, Izv. Akad. Nauk SSSR Ser. Mat. 32 (1968), 212–244 (Russian). MR 0240178
P. S. Novikov and S. I. Adjan, Infinite periodic groups. I, Izv. Akad. Nauk SSSR Ser. Mat. 32 (1968), 212–244 (Russian). MR 0240178
S. Oates, Jump Degrees of Groups, Ph.D. dissertation, University of Notre Dame, 1989.
P. G. Odifreddi, Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland Publishing Co., Amsterdam, 1999. MR 1718169
Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723–731. MR 641486, DOI 10.2307/2273222
Joseph J. Rotman, The theory of groups. An introduction, 2nd ed., Allyn and Bacon Series in Advanced Mathematics, Allyn and Bacon, Inc., Boston, Mass., 1973. MR 0442063
I. N. Sanov, Solution of Burnside’s problem for exponent 4, Leningrad State Univ. Annals [Uchenye Zapiski] Math. Ser. 10 (1940), 166–170 (Russian). MR 0003397
Theodore A. Slaman, Relative to any nonrecursive set, Proc. Amer. Math. Soc. 126 (1998), no. 7, 2117–2122. MR 1443408, DOI 10.1090/S0002-9939-98-04307-X
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
Stephan Wehner, Enumerations, countable structures and Turing degrees, Proc. Amer. Math. Soc. 126 (1998), no. 7, 2131–2139. MR 1443415, DOI 10.1090/S0002-9939-98-04314-7