Describing groups
HTML articles powered by AMS MathViewer
- by Meng-Che Ho PDF
- Proc. Amer. Math. Soc. 145 (2017), 2223-2239 Request permission
Abstract:
We study two complexity notions of groups – the syntactic complexity of a computable Scott sentence and the $m$-degree of the index set of a group. Finding the exact complexity of one of them usually involves finding the complexity of the other, but this is not always the case. Knight et al. determined the complexity of index sets of various structures.
In this paper, we focus on finding the complexity of computable Scott sentences and index sets of various groups. We give computable Scott sentences for various different groups, including nilpotent groups, polycyclic groups, certain solvable groups, and certain subgroups of $\mathbb {Q}$. In some of these cases, we also show that the sentences we give are optimal. In the last section, we also show that d-$\Sigma _2\subsetneq \Delta _3$ in the complexity hierarchy of pseudo-Scott sentences, contrasting the result saying d-$\boldsymbol {\Sigma }_2=\boldsymbol {\Delta }_3$ in the complexity hierarchy of Scott sentences, which is related to the boldface Borel hierarchy.
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
- Igor Belegradek, On co-Hopfian nilpotent groups, Bull. London Math. Soc. 35 (2003), no. 6, 805–811. MR 2000027, DOI 10.1112/S0024609303002480
- Gilbert Baumslag, Alexei Myasnikov, and Vladimir Remeslennikov, Algebraic geometry over groups. I. Algebraic sets and ideal theory, J. Algebra 219 (1999), no. 1, 16–79. MR 1707663, DOI 10.1006/jabr.1999.7881
- J. Carson, V. Harizanov, J. Knight, K. Lange, C. McCoy, A. Morozov, S. Quinn, C. Safranski, and J. Wallbaum, Describing free groups, Trans. Amer. Math. Soc. 364 (2012), no. 11, 5715–5728. MR 2946928, DOI 10.1090/S0002-9947-2012-05456-0
- 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
- O. G. Harlampovič, A finitely presented solvable group with unsolvable word problem, Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 4, 852–873, 928 (Russian). MR 631441
- J. F. Knight and C. McCoy, Index sets and Scott sentences, Arch. Math. Logic 53 (2014), no. 5-6, 519–524. MR 3237865, DOI 10.1007/s00153-014-0377-8
- Julia F. Knight and Vikram Saraph, Scott sentences for certain groups, preprint arXiv:1606.06353
- Douglas E. Miller, The invariant $\Pi ^{0}_{\alpha }$ separation principle, Trans. Amer. Math. Soc. 242 (1978), 185–204. MR 496802, DOI 10.1090/S0002-9947-1978-0496802-9
- Wilhelm Magnus, Abraham Karrass, and Donald Solitar, Combinatorial group theory, 2nd ed., Dover Publications, Inc., Mineola, NY, 2004. Presentations of groups in terms of generators and relations. MR 2109550
- Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
- 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
- Yves Stalder, Convergence of Baumslag-Solitar groups, Bull. Belg. Math. Soc. Simon Stevin 13 (2006), no. 2, 221–233. MR 2259902
- E. I. Timoshenko, On universally equivalent solvable groups, Algebra Log. 39 (2000), no. 2, 227–240, 245 (Russian, with Russian summary); English transl., Algebra and Logic 39 (2000), no. 2, 131–138. MR 1778319, DOI 10.1007/BF02681667
- Robert Vaught, Invariant sets in topology and logic, Fund. Math. 82 (1974/75), 269–294. MR 363912, DOI 10.4064/fm-82-3-269-294
- M. Vanden Boom, The effective Borel hierarchy, Fund. Math. 195 (2007), no. 3, 269–289. MR 2338544, DOI 10.4064/fm195-3-4
Additional Information
- Meng-Che Ho
- Affiliation: Department of Mathematics, University of Wisconsin-Madison, 480 Lincoln Drive, Madison, WI 53706
- MR Author ID: 1200055
- ORCID: setImmediate$0.7583630476368097$9
- Email: turboho@gmail.com
- Received by editor(s): April 6, 2016
- Received by editor(s) in revised form: June 2, 2016
- Published electronically: January 31, 2017
- Communicated by: Mirna Džamonja
- © Copyright 2017 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 145 (2017), 2223-2239
- MSC (2010): Primary 03D45, 03C57, 20F10
- DOI: https://doi.org/10.1090/proc/13458
- MathSciNet review: 3611333