Describing free groups

Carson, J.; Harizanov, V.; Knight, J.; Lange, K.; McCoy, C.; Morozov, A.; Quinn, S.; Safranski, C.; Wallbaum, J.

doi:10.1090/S0002-9947-2012-05456-0

Describing free groups
HTML articles powered by AMS MathViewer

by J. Carson, V. Harizanov, J. Knight, K. Lange, C. McCoy, A. Morozov, S. Quinn, C. Safranski and J. Wallbaum PDF

Trans. Amer. Math. Soc. 364 (2012), 5715-5728 Request permission

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.

References

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
M. Bestvina and M. Feighn, “Definable and negligible subsets of free groups”, in process.
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, DOI 10.1007/s10469-006-0029-0
D. Grove and M. Culler, personal correspondence.
Olga Kharlampovich and Alexei Myasnikov, Elementary theory of free non-abelian groups, J. Algebra 302 (2006), no. 2, 451–552. MR 2293770, DOI 10.1016/j.jalgebra.2006.03.033
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Classics in Mathematics, Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition. MR 1812024, DOI 10.1007/978-3-642-61896-3
A. I. Mal′cev, On the equation $zxyx^{-1}y^{-1}z^{-1}= aba^{-1}b^{-1}$ in a free group, Algebra i Logika Sem. 1 (1962), no. 5, 45–50 (Russian). MR 0153726
C. McCoy and J. Wallbaum, “Describing free groups, Part II: $\Pi ^0_4$ hardness and no $\Sigma ^0_2$ basis”, Tran. Amer. Math. Soc., this issue.
G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289–320. MR 556895, DOI 10.1016/0003-4843(79)90011-1
Anand Pillay, On genericity and weight in the free group, Proc. Amer. Math. Soc. 137 (2009), no. 11, 3911–3917. MR 2529900, DOI 10.1090/S0002-9939-09-09956-0
Bruno Poizat, Groupes stables, avec types génériques réguliers, J. Symbolic Logic 48 (1983), no. 2, 339–355 (French). MR 704088, DOI 10.2307/2273551
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
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$_{1}$: Quantifier elimination I”, Israel J. of Math. , vol. 150 (2005), pp. 1–197; “Diophantine geometry over groups V$_{2}$: 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.
R. Sklinos, “On the generic type of the free group”, to appear in the Journal of Symbolic Logic.