We prove that every quasi-Hopfian finitely presented structure _A_ has a _d_- \(\Sigma _2\) Scott sentence, and that if in addition _A_ is computable and _Aut_(_A_) satisfies a natural computable condition, then _A_ has a computable _d_- \(\Sigma _2\) Scott sentence. This unifies several known results on Scott sentences of finitely presented structures and it is used to prove that other not previously considered algebraic structures of interest have computable _d_- \(\Sigma _2\) Scott sentences. In particular, we show that every (...) right-angled Coxeter group of finite rank has a computable _d_- \(\Sigma _2\) Scott sentence, as well as any strongly rigid Coxeter group of finite rank. Finally, we show that the free projective plane of rank 4 has a computable _d_- \(\Sigma _2\) Scott sentence, thus exhibiting a natural example where the assumption of quasi-Hopfianity is used (since this structure is not Hopfian). (shrink)

Universality has been an important concept in computable structure theory. A class C of structures is universal if, informally, for any structure of any kind there is a structure in C with the same computability-theoretic properties as the given structure. Many classes such as graphs, groups, and fields are known to be universal. This paper is about the class of finitely generated groups. Because finitely generated structures are relatively simple, the class of finitely generated groups has no hope of being (...) universal. We show that finitely generated groups are as universal as possible, given that they are finitely generated: for every finitely generated structure, there is a finitely generated group which has the same computability-theoretic properties. The same is not true for finitely generated fields. We apply the results of this investigation to quasi Scott sentences, and also answer a question of Alvir, Knight, and McCoy. (shrink)

Every countable structure has a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ which characterizes that structure up to isomorphism among countable structures. Such a sentence is called a Scott sentence, and can be thought of as a description of the structure. The least complexity of a Scott sentence for a structure can be thought of as a measurement of the complexity of describing the structure. We begin with an introduction to the area, with short and simple proofs (...) where possible, followed by a survey of recent advances. (shrink)

We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$, $\Pi _{\alpha }$, or $\mathrm {d-}\Sigma _{\alpha }$. We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit (...) ordinal. This answers a question left open by A. Miller.We also construct examples of computable structures of high Scott rank with Scott complexities $\Sigma _{\omega _1^{CK}+1}$ and $\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$. There are three other possible Scott complexities for a computable structure of high Scott rank: $\Pi _{\omega _1^{CK}}$, $\Pi _{\omega _1^{CK}+1}$, $\Sigma _{\omega _1^{CK}+1}$. Examples of these were already known. Our examples are computable structures of Scott rank $\omega _1^{CK}+1$ which, after naming finitely many constants, have Scott rank $\omega _1^{CK}$. The existence of such structures was an open question. (shrink)