Logic Seminar
Meng-Che Ho
University of Wisconsin-Madison
Describing Groups
Abstract: In this talk, we will consider two complexity notions of computable 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.
Generalizing methods that was previously used by Knight et al., 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 sentence we give are optimal. We also give an example showing d-$\Sigma_2\subsetneq\Delta_3$ in the complexity hierarchy of pseudo-Scott sentences, contrasting the result by D. Miller saying d-$\boldsymbol{\Sigma}_2=\boldsymbol{\Delta}_3$ in the complexity hierarchy of Scott sentences, which is related to the boldface Borel hierarchy.
Tuesday January 26, 2016 at 4:00 PM in SEO 427