The complexity of Scott sentences of scattered linear orders

Journal of Symbolic Logic 85 (3):1079-1101 (2020)
  Copy   BIBTEX

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,479

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Π⁰₁ classes with complex elements.Stephen Binns - 2008 - Journal of Symbolic Logic 73 (4):1341-1353.
Posets of copies of countable scattered linear orders.Miloš S. Kurilić - 2014 - Annals of Pure and Applied Logic 165 (3):895-912.
Coloring linear orders with Rado's partial order.Riccardo Camerlo & Alberto Marcone - 2007 - Mathematical Logic Quarterly 53 (3):301-305.
Scott sentences for equivalence structures.Sara B. Quinn - 2020 - Archive for Mathematical Logic 59 (3-4):453-460.
$\Pi _{1}^{0}$ Classes with Complex Elements.Stephen Binns - 2008 - Journal of Symbolic Logic 73 (4):1341 - 1353.
The metamathematics of scattered linear orderings.P. Clote - 1989 - Archive for Mathematical Logic 29 (1):9-20.
Complexity Ranks of Countable Models.Su Gao - 2007 - Notre Dame Journal of Formal Logic 48 (1):33-48.
A decision algorithm for linear sentences on a PFM.Lian Li, Huilin Li & Yixun Liu - 1993 - Annals of Pure and Applied Logic 59 (3):273-286.

Analytics

Added to PP
2020-10-24

Downloads
11 (#846,983)

6 months
4 (#185,765)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

New jump operators on equivalence relations.John D. Clemens & Samuel Coskey - 2022 - Journal of Mathematical Logic 22 (3).

Add more citations

References found in this work

Pairs of recursive structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
Pairs of computable structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
Δ20-categoricity in Boolean algebras and linear orderings.Charles F. D. McCoy - 2003 - Annals of Pure and Applied Logic 119 (1-3):85-120.
Index sets and Scott sentences.J. F. Knight & C. McCoy - 2014 - Archive for Mathematical Logic 53 (5-6):519-524.
Computable structures of rank.J. F. Knight & J. Millar - 2010 - Journal of Mathematical Logic 10 (1):31-43.

View all 9 references / Add more references