Describing free groups
Authors:
J. Carson, V. Harizanov, J. Knight, K. Lange, C. McCoy, A. Morozov, S. Quinn, C. Safranski and J. Wallbaum
Journal:
Trans. Amer. Math. Soc. 364 (2012), 57155728
MSC (2010):
Primary 03C57
Published electronically:
June 21, 2012
MathSciNet review:
2946928
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We consider countable free groups of different ranks. For these groups, we investigate computability theoretic complexity of index sets within the class of free groups and within the class of all groups. For a computable free group of infinite rank, we consider the difficulty of finding a basis.
 1.
C.
J. Ash and J.
Knight, Computable structures and the hyperarithmetical
hierarchy, Studies in Logic and the Foundations of Mathematics,
vol. 144, NorthHolland Publishing Co., Amsterdam, 2000. MR 1767842
(2001k:03090)
 2.
M. Bestvina and M. Feighn, ``Definable and negligible subsets of free groups'', in process.
 3.
V.
Kalvert, V.
S. Kharizanova, D.
F. Naĭt, and S.
Miller, Index sets of computable models, Algebra Logika
45 (2006), no. 5, 538–574, 631–632
(Russian, with Russian summary); English transl., Algebra Logic
45 (2006), no. 5, 306–325. MR 2307694
(2008e:03056), 10.1007/s1046900600290
 4.
D. Grove and M. Culler, personal correspondence.
 5.
Olga
Kharlampovich and Alexei
Myasnikov, Elementary theory of free nonabelian groups, J.
Algebra 302 (2006), no. 2, 451–552. MR 2293770
(2008e:20033), 10.1016/j.jalgebra.2006.03.033
 6.
Roger
C. Lyndon and Paul
E. Schupp, Combinatorial group theory, Classics in
Mathematics, SpringerVerlag, Berlin, 2001. Reprint of the 1977 edition. MR 1812024
(2001i:20064)
 7.
A.
I. Mal′cev, On the equation
𝑧𝑥𝑦𝑥⁻¹𝑦⁻¹𝑧⁻¹=𝑎𝑏𝑎⁻¹𝑏⁻¹
in a free group, Algebra i Logika Sem. 1 (1962),
no. 5, 45–50 (Russian). MR 0153726
(27 #3687)
 8.
C. McCoy and J. Wallbaum, ``Describing free groups, Part II: hardness and no basis'', Tran. Amer. Math. Soc., this issue.
 9.
G.
Metakides and A.
Nerode, Effective content of field theory, Ann. Math. Logic
17 (1979), no. 3, 289–320. MR 556895
(82b:03082), 10.1016/00034843(79)900111
 10.
Anand
Pillay, On genericity and weight in the free
group, Proc. Amer. Math. Soc.
137 (2009), no. 11, 3911–3917. MR 2529900
(2010k:03031), 10.1090/S0002993909099560
 11.
Bruno
Poizat, Groupes stables, avec types génériques
réguliers, J. Symbolic Logic 48 (1983),
no. 2, 339–355 (French). MR 704088
(85e:03082), 10.2307/2273551
 12.
Dana
Scott, Logic with denumerably long formulas and finite strings of
quantifiers, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley),
NorthHolland, Amsterdam, 1965, pp. 329–341. MR 0200133
(34 #32)
 13.
Z. Sela, series of papers, ``Diophantine geometry over groups I: MakaninRazborov diagrams'', Publications Mathématiques, Institute des Hautes Études Scientifiques, vol. 93 (2001), pp. 31105; Diophantine geometry over groups II: Completions, closures, and formal solutions'', Israel J. of Math., vol. 134 (2003), pp. 173254; Z. Sela, ``Diophantine geometry over groups III: Rigid and solid solutions'', Israel J. of Math. , vol.147 (2005), pp. 173; ``Diophantine geometry over groups IV: An iterative procedure for validation of a sentence'', Israel J. of Math., vol. 143 (2004), pp. 1130; ``Diophantine geometry over groups V: Quantifier elimination I'', Israel J. of Math. , vol. 150 (2005), pp. 1197; ``Diophantine geometry over groups V: Quantifier elimination II'', Geometric and Functional Analysis, vol. 16 (2006), pp. 537706; ``Diophantine geometry over groups VI: The elementary theory of a free group'', Geometric and Functional Analysis, vol. 16 (2006), pp.707730.
 14.
R. Sklinos, ``On the generic type of the free group'', to appear in the Journal of Symbolic Logic.
 1.
 C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, 2000. MR 1767842 (2001k:03090)
 2.
 M. Bestvina and M. Feighn, ``Definable and negligible subsets of free groups'', in process.
 3.
 W. Calvert, V. S. Harizanov, J. F. Knight, and S.Miller, ``Index sets for computable structures'', Algebra and Logic, vol. 45 (2006), pp. 306325. MR 2307694 (2008e:03056)
 4.
 D. Grove and M. Culler, personal correspondence.
 5.
 O. Kharlampovich and A. Myasnikov, ``Elementary theory of free nonabelian groups'', Journal of Algebra, vol. 302 (2006), pp. 451552. MR 2293770 (2008e:20033)
 6.
 R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Springer, 2001. MR 1812024 (2001i:20064)
 7.
 A. I. Mal'tsev, ``On the equation in a free group'', (Russian) Algebra i Logika Sem. 1, no. 5 (1962), pp.4550. MR 0153726 (27:3687)
 8.
 C. McCoy and J. Wallbaum, ``Describing free groups, Part II: hardness and no basis'', Tran. Amer. Math. Soc., this issue.
 9.
 G. Metakides and A. Nerode, ``Effective content of field theory'', Annals of Math. Logic, vol. 17 (1979), pp. 289320. MR 556895 (82b:03082)
 10.
 A. Pillay, ``On genericity and weight in the free group'', Proc. Amer. Math. Soc.. 137 (2009), no. 11, 39113917. MR 2529900 (2010k:03031)
 11.
 B. Poizat, ``Groupes stables, avec types génriques réguliers'', Journal of Symbolic Logic, vol. 48(1983), pp. 339355. MR 704088 (85e:03082)
 12.
 D. Scott, ``Logic with denumerably long formulas and finite strings of quantifiers'', in The Theory of Models, J. Addison, L. Henkin, and A. Tarski, eds., NorthHolland, 1965, pp. 329341. MR 0200133 (34:32)
 13.
 Z. Sela, series of papers, ``Diophantine geometry over groups I: MakaninRazborov diagrams'', Publications Mathématiques, Institute des Hautes Études Scientifiques, vol. 93 (2001), pp. 31105; Diophantine geometry over groups II: Completions, closures, and formal solutions'', Israel J. of Math., vol. 134 (2003), pp. 173254; Z. Sela, ``Diophantine geometry over groups III: Rigid and solid solutions'', Israel J. of Math. , vol.147 (2005), pp. 173; ``Diophantine geometry over groups IV: An iterative procedure for validation of a sentence'', Israel J. of Math., vol. 143 (2004), pp. 1130; ``Diophantine geometry over groups V: Quantifier elimination I'', Israel J. of Math. , vol. 150 (2005), pp. 1197; ``Diophantine geometry over groups V: Quantifier elimination II'', Geometric and Functional Analysis, vol. 16 (2006), pp. 537706; ``Diophantine geometry over groups VI: The elementary theory of a free group'', Geometric and Functional Analysis, vol. 16 (2006), pp.707730.
 14.
 R. Sklinos, ``On the generic type of the free group'', to appear in the Journal of Symbolic Logic.
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2010):
03C57
Retrieve articles in all journals
with MSC (2010):
03C57
Additional Information
J. Carson
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556
V. Harizanov
Affiliation:
Department of Mathematics, George Washington University, Washington, DC 20052
J. Knight
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556
K. Lange
Affiliation:
Department of Mathematics, Wellesley College, Wellesley, Massachusetts 02482
C. McCoy
Affiliation:
Department of Mathematics, University of Portland, Portland, Oregon 97203
A. Morozov
Affiliation:
Sobolev Mathematical Institute, Russian Academy of Sciences, Novosibirsk 630090 Russia
S. Quinn
Affiliation:
Department of Mathematics, Dominican University, River Forest, Illinois 60305
C. Safranski
Affiliation:
Department of Mathematics, Saint Vincent College, Latrobe, Pennsylvania 15650
J. Wallbaum
Affiliation:
Department of Mathematical Sciences, Eastern Mennonite University, Harrisonburg, Virginia 22802
DOI:
http://dx.doi.org/10.1090/S000299472012054560
Received by editor(s):
July 1, 2009
Received by editor(s) in revised form:
August 25, 2010
Published electronically:
June 21, 2012
Additional Notes:
The authors acknowledge partial support under NSF Grant # DMS0554841. The second author also received partial support under NSF Grant # DMS0904101
Article copyright:
© Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
