Computable Scott sentences and the weak Whitehead problem for finitely presented groups. (English) Zbl 07848925
Summary: We prove that if \(A\) is a computable Hopfian finitely presented structure, then \(A\) has a computable \(d\)-\(\Sigma_{2}\) Scott sentence if and only if the weak Whitehead problem for \(A\) is decidable. We use this to infer that every hyperbolic group as well as any polycyclic-by-finite group has a computable \(d\)-\(\Sigma_{2}\) Scott sentence, thus covering two main classes of finitely presented groups. Our proof also implies that every weakly Hopfian finitely presented group is strongly defined by its \(\exists^{+}\)-types, a question which arose in a different context.
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 03D80 | Applications of computability and recursion theory |
| 03D40 | Word problems, etc. in computability and recursion theory |
References:
| [1] | André, Simon, Elementary subgroups of virtually free groups, Groups Geom. Dyn., 15, 1523-1552, 2021 · Zbl 07476326 |
| [2] | R. Alvir, J.F. Knight, C.F.D. McCoy, Complexity of Scott sentences, Preprint, available on the ArXiv. |
| [3] | Ash, C. J.; Knight, J. F., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, 2000, North Holland · Zbl 0960.03001 |
| [4] | Bogopolski, O.; Martino, A.; Ventura, E., Orbit decidability and the conjugacy problem for some extensions of groups, Trans. Am. Math. Soc., 362, 2003-2036, 2007 · Zbl 1234.20043 |
| [5] | Bridson, M. R.; Haefliger, A., Metric Spaces of Non-Positive Curvature, Grundlehren der mathematischen Wissenschaften (GL), vol. 319, 1999 · Zbl 0988.53001 |
| [6] | Carson, J.; Harizanov, V.; Knight, J. F.; Lange, K.; McCoy, C.; Morozov, A.; Quinn, S.; Safranski, C.; Wallbaum, J., Describing free groups, Trans. Am. Math. Soc., 364, 5715-5728, 2012 · Zbl 1302.03045 |
| [7] | Harrison-Trainor, M., An introduction to the Scott complexity of countable structures and a survey of recent results, Bull. Symb. Log., 28, 01, 71-103, 2022 · Zbl 1501.03002 |
| [8] | M. Harrison-Trainor, Describing finitely presented algebraic structures, Preprint, available on the ArXiv. |
| [9] | Harrison-Trainor, M.; Ho, Meng-Che, On optimal Scott sentences of finitely generated algebraic structures, Proc. Am. Math. Soc., 146, 10, 4473-4485, 2018 · Zbl 1522.03126 |
| [10] | Ho, Meng-Che, Describing groups, Proc. Am. Math. Soc., 145, 2223-2239, 2017 · Zbl 1423.03150 |
| [11] | Hodges, W., Model Theory, 1993, Cambridge University Press · Zbl 0789.03031 |
| [12] | Dahmani, F.; Guirardel, V., The isomorphism problem for all hyperbolic groups, Geom. Funct. Anal., 21, 02, 223-300, 2011 · Zbl 1258.20034 |
| [13] | Johnson, D. L., Presentations of Groups, 1997, Cambridge University Press: Cambridge University Press Cambridge · Zbl 0906.20019 |
| [14] | Knight, J. F.; Saraph, V., Scott sentences for certain groups, Arch. Math. Log., 57, 03-04, 453-472, 2018 · Zbl 1522.03173 |
| [15] | Miller, C. F., Decision problems for groups — survey and reflections, (Baumslag, G.; Miller, C. F., Algorithms and Classification in Combinatorial Group Theory. Algorithms and Classification in Combinatorial Group Theory, Mathematical Sciences Research Institute Publications, vol. 23, 1992, Springer: Springer New York, NY) · Zbl 0752.20014 |
| [16] | Myasnikov, A. G.; Romanovskii, N. S., Characterization of finitely generated groups by types, Int. J. Algebra Comput., 28, 08, 1613-1632, 2018 · Zbl 1483.20055 |
| [17] | Neumann, P. M., Endomorphisms of infinite soluble groups, Bull. Lond. Math. Soc., 12, 01, 13-16, 1980 · Zbl 0431.20032 |
| [18] | Nies, A., Aspects of free groups, J. Algebra, 263, 01, 119-125, 2003 · Zbl 1068.20027 |
| [19] | Paolini, G., Computable Scott sentences for quasi-Hopfian finitely presented structures, Arch. Math. Log., 62, 55-65, 2023 · Zbl 07680015 |
| [20] | Scott, D., Logic with denumerably long formulas and finite strings of quantifiers, (Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), 1965, North-Holland: North-Holland Amsterdam), 329-341 · Zbl 0166.26003 |
| [21] | Segal, D., Polycyclic Groups, 1983, Cambridge University Press · Zbl 0516.20001 |
| [22] | Segal, D., Decidable properties of polycyclic groups, Proc. Lond. Math. Soc. (3), 61, 03, 497-528, 1990 · Zbl 0674.20020 |
| [23] | Sela, Z., Endomorphisms of hyperbolic groups I: the Hopf property, Topology, 38, 02, 301-321, 1999 · Zbl 0929.20033 |
| [24] | Ventura, E., Group-theoretic orbit decidability, Groups Complex. Cryptol., 06, 02, 133-148, 2014 · Zbl 1322.20026 |
| [25] | Whitehead, J. H.C., On equivalent sets of elements in free groups, Ann. Math., 37, 782-800, 1936 · Zbl 0015.24804 |
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.
