Complexity of Scott sentences
Volume 251 / 2020
Abstract
We give effective versions of some results on Scott sentences. Effectivizing a result of Montalbán (2015), we show that if $\mathcal {A}$ has a computable $\Pi _\alpha $ Scott sentence, then the automorphism orbits of all tuples are defined by formulas that are computable $\Sigma _\beta $ for some $\beta \lt \alpha $. Effectivizing a result of A. Miller (1983), 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 _{ \lt \alpha }$. We also give an effective version of a result of D. Miller (1978) on which the result of A. Miller was based. 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 if{f} the orbit of some (or every) generating tuple is defined by a $\Pi _1$ formula. Using our effective results, we show that a computable finitely generated group has a computable $d$-$\Sigma _2$ Scott sentence if{f} the orbit of some (or every) generating tuple is defined by a computable $\Pi _1$ formula.
