The complexity of Scott sentences of scattered linear orders

Abstract

Given a countable scattered linear order $L$ of Hausdorff rank $\alpha <{\omega }_1$ we show that it has a $d\text{-}{\Sigma }_{2\alpha +1}$ Scott sentence. Ash calculated the back and forth relations for all countable well-orders. From this result we obtain that this upper bound is tight, i.e., for every $\alpha <{\omega }_1$ there is a linear order whose optimal Scott sentence has this complexity. We further show that for all countable $\alpha$ the class of Hausdorff rank $\alpha$ linear orders is ${\Sigma }_{2\alpha +2}$ complete.

25 pages

Cited by in corpus (3)

• Scott sentence complexities of linear orderings
• New jump operators on equivalence relations
• On bi-embeddable categoricity of algebraic structures