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), 5715-5728

MSC (2010):
Primary 03C57

DOI:
https://doi.org/10.1090/S0002-9947-2012-05456-0

Published electronically:
June 21, 2012

MathSciNet review:
2946928

Full-text 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, North-Holland Publishing Co., Amsterdam, 2000. MR**1767842****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**, https://doi.org/10.1007/s10469-006-0029-0**4.**D. Grove and M. Culler, personal correspondence.**5.**Olga Kharlampovich and Alexei Myasnikov,*Elementary theory of free non-abelian groups*, J. Algebra**302**(2006), no. 2, 451–552. MR**2293770**, https://doi.org/10.1016/j.jalgebra.2006.03.033**6.**Roger C. Lyndon and Paul E. Schupp,*Combinatorial group theory*, Classics in Mathematics, Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition. MR**1812024****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****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**, https://doi.org/10.1016/0003-4843(79)90011-1**10.**Anand Pillay,*On genericity and weight in the free group*, Proc. Amer. Math. Soc.**137**(2009), no. 11, 3911–3917. MR**2529900**, https://doi.org/10.1090/S0002-9939-09-09956-0**11.**Bruno Poizat,*Groupes stables, avec types génériques réguliers*, J. Symbolic Logic**48**(1983), no. 2, 339–355 (French). MR**704088**, https://doi.org/10.2307/2273551**12.**Dana Scott,*Logic with denumerably long formulas and finite strings of quantifiers*, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 329–341. MR**0200133****13.**Z. Sela, series of papers, ``Diophantine geometry over groups I: Makanin-Razborov diagrams'',*Publications Mathématiques*, Institute des Hautes Études Scientifiques, vol. 93 (2001), pp. 31-105; Diophantine geometry over groups II: Completions, closures, and formal solutions'',*Israel J. of Math.*, vol. 134 (2003), pp. 173-254; Z. Sela, ``Diophantine geometry over groups III: Rigid and solid solutions'',*Israel J. of Math.*, vol.147 (2005), pp. 1-73; ``Diophantine geometry over groups IV: An iterative procedure for validation of a sentence'',*Israel J. of Math.*, vol. 143 (2004), pp. 1-130; ``Diophantine geometry over groups V: Quantifier elimination I'',*Israel J. of Math.*, vol. 150 (2005), pp. 1-197; ``Diophantine geometry over groups V: Quantifier elimination II'',*Geometric and Functional Analysis*, vol. 16 (2006), pp. 537-706; ``Diophantine geometry over groups VI: The elementary theory of a free group'',*Geometric and Functional Analysis*, vol. 16 (2006), pp.707-730.**14.**R. Sklinos, ``On the generic type of the free group'', to appear in the*Journal of Symbolic Logic*.

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:
https://doi.org/10.1090/S0002-9947-2012-05456-0

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 # DMS-0554841. The second author also received partial support under NSF Grant # DMS-0904101

Article copyright:
© Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.