2024/06/03 by David Gonzalez, Gonzalez, David, Matthew Harrison-Trainor +3 · 1 citation
Computer Science · Physics and Astronomy · #Matrix Theory and Algorithms #Quantum chaos and dynamical systems
paper · pdf · doi:10.48550/arxiv.2406.01836
For any limit ordinal λ, we construct a linear order Lλ whose Scott complexity is Σλ+1. This completes the classification of the possible Scott sentence complexities of linear orderings. Previously, there was only one known construction of any structure (of any signature) with Scott complexity Σλ+1, and our construction gives new examples, e.g., rigid structures, of this complexity. Moreover, we can construct the linear orders Lλ so that not only does Lλ have Scott complexity Σλ+1, but there are continuum-many structures M ≡λLλ and all such structures also have Scott complexity Σλ+1. In contrast, we demonstrate that there is no structure (of any signature) with Scott complexity Πλ+1 that is only λ-equivalent to structures with Scott complexity Πλ+1. Our construction is based on functions f \colon ℤ→ ℕ∪ \∞\ which are almost periodic but not periodic, such as those arising from shifts of the p-adic valuations.