Scott sentence; Scott sentence complexity; Scott rank; linear orders; linear orderings; total orders; infinitary logic; computable structures
en
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 Πinα complexities. We then take a more direct approach and exhibit linear orderings of all Scott sentence complexities except Σin3 and Σinλ+1 for λ a limit ordinal. We show that the former cannot 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.
en
Project title:
Algorithmische Komplexität von Strukturen und deren Äquivalenzrelationen: 101026834 (European Commission)
