Describing free groups

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

Review text

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}\).NEWLINENEWLINE 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\).NEWLINENEWLINE 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.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: Describing free groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2844726)