Scott sentence complexities of linear orderings

Abstract

We study possible Scott sentence complexities of linear orderings using two approaches. First, we investigate the effect of the Friedman-Stanley embedding on Scott sentence complexity and show that it only preserves ${\Pi }_{\alpha }^{\mathrm{in}}$ complexities. We then take a more direct approach and exhibit linear orderings of all Scott complexities except ${\Sigma }_3^{\mathrm{in}}$ and ${\Sigma }_{\lambda +1}^{\mathrm{in}}$ for $\lambda$ a limit ordinal. We show that the former can not be the Scott sentence complexity of a linear ordering. In the process we develop new techniques which appear to be helpful to calculate the Scott sentence complexities of structures.

References in corpus (2)

• The complexity of Scott sentences of scattered linear orders
• Coding in graphs and linear orderings