Complexity of Scott Sentences

Abstract

We give effective versions of some results on Scott sentences. We show that if $\mathcal{A}$ has a computable ${\Pi }_{\alpha }$ Scott sentence, then the orbits of all tuples are defined by formulas that are computable ${\Sigma }_{\beta }$ for some $\beta <\alpha$. (This is an effective version of a result of Montalbán.) We show that if a countable structure $\mathcal{A}$ has a computable ${\Sigma }_{\alpha }$ Scott sentence and one that is computable ${\Pi }_{\alpha }$, then it has one that is computable $d$-${\Sigma }_{\beta }$ for some $\beta <\alpha$. (This is an effective version of a result of A. Miller.) We also give an effective version of a result of D. Miller. Using the non-effective results of Montalbán and A. Miller, we show that a finitely generated group has a $d$-${\Sigma }_2$ Scott sentence iff the orbit of some (or every) generating tuple is defined by a ${\Pi }_1$ formula. Using our effective results, we show that for a computable finitely generated group, there is a computable $d$-${\Sigma }_2$ Scott sentence iff the orbit of some (every) generating tuple is defined by a computable ${\Pi }_1$ formula.

21 pages