×

Describing free groups. (English) Zbl 1302.03045

It is known that all free groups \(F_n\) of different finite ranks \(n>1\) are elementarily equivalent. Thus, it is of interest to describe specific free groups in a more expressive language. The authors use the infinitary language \(L_{\omega_1\omega}\) with computably enumerable disjunctions and conjunctions, but only finite strings of quantifiers. The groups \(F_n\) and the group \(F_\infty\) of rank \(\aleph_0\) all have computable copies. A computable index for a structure \(\mathcal A\) is a number \(e\) such that \(\varphi_e\) is the characteristic function of the atomic diagram of \(\mathcal A\). The index set \(I({\mathcal A})\) for a structure \(\mathcal A\) is the set of computable indices for structures isomorphic to \(\mathcal A\). The index set \(I(K)\) for a class \(K\) of structures is the set of computable indices for elements of \(K\). There is a connection between the computability-theoretic complexity of the index set and the complexity of the simplest description of a structure or a class of structures in the language \(L_{\omega_1\omega}\).
Let \(\Gamma\) be a complexity class. A set \(A\) is in \(\Gamma\) within a larger set \(B\) if there is a set \(C\in\Gamma\) such that \(A=C\cap B\). A set \(A\) is \(\Gamma\)-hard within \(B\) if for any set \(S\in\Gamma\) there is a computable function \(f:\omega\to B\) such that \(f(n)\in A\) iff \(n\in S\). A set \(A\) is \(m\)-complete \(\Gamma\) within \(B\) if \(A\) is in \(\Gamma\) within \(B\) and \(A\) is \(\Gamma\)-hard within \(B\).
The following results are proved in the paper: \(I(F_1)\) is \(m\)-complete \(\Pi^0_1\) within the class \(\mathrm{FrGr}\) of free groups (i.e., within \(I(\mathrm{FrGr}))\). The set \(I(F_2)\) is \(m\)-complete \(\Pi^0_2\) within \(\mathrm{FrGr}\). For \(n>2\), the set \(I(F_n)\) is \(m\)-complete \(d\)-\(\Sigma^0_2\) within \(\mathrm{FrGr}\). The set \(I(F_\infty)\) is \(m\)-complete \(\Pi^0_3\) within \(\mathrm{FrGr}\). For finite \(n\), the set \(I(F_n)\) is \(m\)-complete \(d\)-\(\Sigma^0_2\) (within the class \(\mathrm{Gr}\) of all groups). \(I(F_\infty)\) is \(\Pi^0_4\). The index set of the class \(\mathrm{FinGen}\) of all finitely generated groups is \(m\)-complete \(\Sigma^0_3\) within \(\mathrm{FrGr}\). The index set of the class of all locally free groups is \(m\)-complete \(\Pi^0_2\) within \(\mathrm{Gr}\). Every computable copy of \(F_\infty\) has a \(\Pi^0_2\) basis, and a \(\Pi^0_2\) index for the basis can be computed uniformly from a computable index for \(F_\infty\). For every \(n\geq2\), the statement that \(\{x_1,\dots,x_n\}\) is a basis for \(F_n\) is expressed by an infinitary formula \(\theta(x_1,\dots,x_n)\), which is a computably enumerable conjunction of formulas \(\forall\bar u\,\psi(x_1,\dots,x_n,\bar u)\), where \(\psi\) is finitary quantifier-free.

MSC:

03C57 Computable structure theory, computable model theory
03C75 Other infinitary logic
03D15 Complexity of computation (including implicit computational complexity)
20K20 Torsion-free groups, infinite rank
20E05 Free nonabelian groups
PDFBibTeX XMLCite
Full Text: DOI

References:

[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. · Zbl 0960.03001
[2] M. Bestvina and M. Feighn, “Definable and negligible subsets of free groups”, in process. · Zbl 1348.20028
[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. · Zbl 1164.03325 · doi: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. · Zbl 1110.03020 · doi: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. · Zbl 0997.20037
[8] 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. · Zbl 1325.03037
[9] G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289 – 320. · Zbl 0469.03028 · doi: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. · Zbl 1184.03023
[11] Bruno Poizat, Groupes stables, avec types génériques réguliers, J. Symbolic Logic 48 (1983), no. 2, 339 – 355 (French). · Zbl 0525.03024 · doi: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.
[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\( _{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.
[14] R. Sklinos, “On the generic type of the free group”, to appear in the Journal of Symbolic Logic. · Zbl 1213.03047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.