Article contents
THE COMPLEXITY OF SCOTT SENTENCES OF SCATTERED LINEAR ORDERS
Published online by Cambridge University Press: 23 October 2020
Abstract
We calculate the complexity of Scott sentences of scattered linear orders. Given a countable scattered linear order L of Hausdorff rank
$\alpha $
we show that it has a
${d\text {-}\Sigma _{2\alpha +1}}$
Scott sentence. It follows from results of Ash [2] that for every countable
$\alpha $
there is a linear order whose optimal Scott sentence has this complexity. Therefore, our bounds are tight. We furthermore show that every Hausdorff rank 1 linear order has an optimal
${\Pi ^{\mathrm {c}}_{3}}$
or
${d\text {-}\Sigma ^{\mathrm {c}}_{3}}$
Scott sentence and give a characterization of those linear orders of rank
$1$
with
${\Pi ^{\mathrm {c}}_{3}}$
optimal Scott sentences. At last we show that for all countable
$\alpha $
the class of Hausdorff rank
$\alpha $
linear orders is
$\boldsymbol {\Sigma }_{2\alpha +2}$
complete and obtain analogous results for index sets of computable linear orders.
MSC classification
- Type
- Articles
- Information
- Copyright
- © The Association for Symbolic Logic 2020
References
REFERENCES
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20210315143802656-0856:S0022481220000468:S0022481220000468_inline11.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20210315143802656-0856:S0022481220000468:S0022481220000468_inline12.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20210315143802656-0856:S0022481220000468:S0022481220000468_inline13.png?pub-status=live)
- 5
- Cited by