|
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
Posted:
May 14, 2007
MathSciNet review:
2322771
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: For a countable structure , the (Turing) degree spectrum of is the set of all Turing degrees of its isomorphic copies. If the degree spectrum of has the least degree , then we say that is the (Turing) degree of the isomorphism type of . 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.
- 1.
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, 1979. Translated
from the Russian by John Lennox and James Wiegold. MR 537580
(80d:20035)
- 2.
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
(90j:03081), http://dx.doi.org/10.1090/S0002-9947-1990-0955487-0
- 3.
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
(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.
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
(2002a:03081), http://dx.doi.org/10.1112/S0024610700001459
- 7.
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
(98k:03099)
- 8.
Rodney
Downey and Julia
F. Knight, Orderings with 𝛼th jump degree
0^{(𝛼)}, Proc. Amer. Math. Soc.
114 (1992), no. 2,
545–552. MR 1065942
(92e:03063), http://dx.doi.org/10.1090/S0002-9939-1992-1065942-0
- 9.
Marshall
Hall Jr., Solution of the Burnside problem for exponent six,
Illinois J. Math. 2 (1958), 764–786. MR 0102554
(21 #1345)
- 10.
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
(2000f:03108), http://dx.doi.org/10.1016/S0049-237X(98)80002-5
- 11.
Valentina
S. Harizanov, Computability-theoretic complexity of countable
structures, Bull. Symbolic Logic 8 (2002),
no. 4, 457–477. MR 1956865
(2004h:03076), http://dx.doi.org/10.2307/797952
- 12.
Valentina
S. Harizanov, Julia
F. Knight, and Andrei
S. Morozov, Sequences of 𝑛-diagrams, J. Symbolic Logic
67 (2002), no. 3, 1227–1247. MR 1926609
(2003f:03046), http://dx.doi.org/10.2178/jsl/1190150160
- 13.
V. Harizanov and R. Miller, Spectra of structures and relations, to appear in the Journal of Symbolic Logic.
- 14.
Denis
R. Hirschfeldt, Computable trees, prime models, and
relative decidability, Proc. Amer. Math.
Soc. 134 (2006), no. 5, 1495–1498 (electronic). MR 2199197
(2007b:03055), http://dx.doi.org/10.1090/S0002-9939-05-08097-4
- 15.
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
(2003d:03060), http://dx.doi.org/10.1016/S0168-0072(01)00087-2
- 16.
Sergei
V. Ivanov, On the Burnside problem on periodic
groups, Bull. Amer. Math. Soc. (N.S.)
27 (1992), no. 2,
257–260. MR 1149874
(93a:20061), http://dx.doi.org/10.1090/S0273-0979-1992-00305-1
- 17.
A.
N. Khisamiev, On the Ershov upper semilattice
𝔏_{𝔈}, 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 (2005f:03061), http://dx.doi.org/10.1023/B:SIMJ.0000013023.90154.bb
- 18.
Julia
F. Knight, Degrees coded in jumps of orderings, J. Symbolic
Logic 51 (1986), no. 4, 1034–1042. MR 865929
(88j:03030), http://dx.doi.org/10.2307/2273915
- 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.
Roger
C. Lyndon and Paul
E. Schupp, Combinatorial group theory, Springer-Verlag,
Berlin, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. MR 0577064
(58 #28182)
- 21.
P.
S. Novikov and S.
I. Adjan, Infinite periodic groups. I, Izv. Akad. Nauk SSSR
Ser. Mat. 32 (1968), 212–244 (Russian). MR 0240178
(39 #1532a)
- 22.
P.
S. Novikov and S.
I. Adjan, Infinite periodic groups. II, Izv. Akad. Nauk SSSR
Ser. Mat. 32 (1968), 251–524 (Russian). MR 0240179
(39 #1532b)
- 23.
P.
S. Novikov and S.
I. Adjan, Infinite periodic groups. III, Izv. Akad. Nauk SSSR
Ser. Mat. 32 (1968), 709–731 (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, Studies in
Logic and the Foundations of Mathematics, vol. 143, North-Holland
Publishing Co., Amsterdam, 1999. MR 1718169
(2001b:03040)
- 26.
Michael
O. Rabin, Computable algebra, general theory and
theory of computable fields., Trans. Amer.
Math. Soc. 95
(1960), 341–360. MR 0113807
(22 #4639), http://dx.doi.org/10.1090/S0002-9947-1960-0113807-4
- 27.
Linda
Jean Richter, Degrees of structures, J. Symbolic Logic
46 (1981), no. 4, 723–731. MR 641486
(83d:03048), http://dx.doi.org/10.2307/2273222
- 28.
Joseph
J. Rotman, The theory of groups. An introduction, 2nd ed.,
Allyn and Bacon Inc., Boston, Mass., 1973. Allyn and Bacon Series in
Advanced Mathematics. MR 0442063
(56 #451)
- 29.
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
(2,212c)
- 30.
Theodore
A. Slaman, Relative to any nonrecursive
set, Proc. Amer. Math. Soc.
126 (1998), no. 7,
2117–2122. MR 1443408
(98h:03047), http://dx.doi.org/10.1090/S0002-9939-98-04307-X
- 31.
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
(88m:03003)
- 32.
Stephan
Wehner, Enumerations, countable structures and
Turing degrees, Proc. Amer. Math. Soc.
126 (1998), no. 7,
2131–2139. MR 1443415
(98h:03059), http://dx.doi.org/10.1090/S0002-9939-98-04314-7
- 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
th jump degree , 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
-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
, 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:
http://dx.doi.org/10.1090/S0002-9939-07-08845-4
PII:
S 0002-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
Posted:
May 14, 2007
Communicated by:
Julia Knight
Article copyright:
© Copyright 2007 American Mathematical Society
|