Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 

 

Describing groups


Author: Meng-Che Ho
Journal: Proc. Amer. Math. Soc. 145 (2017), 2223-2239
MSC (2010): Primary 03D45, 03C57, 20F10
DOI: https://doi.org/10.1090/proc/13458
Published electronically: January 31, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D45, 03C57, 20F10

Retrieve articles in all journals with MSC (2010): 03D45, 03C57, 20F10


Additional Information

Meng-Che Ho
Affiliation: Department of Mathematics, University of Wisconsin-Madison, 480 Lincoln Drive, Madison, WI 53706
Email: turboho@gmail.com

DOI: https://doi.org/10.1090/proc/13458
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
Article copyright: © Copyright 2017 American Mathematical Society