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 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.
