Makkai [10] produced an arithmetical structure of Scott rank ω1CK. In [9], Makkai’s example is made computable. Here we show that there are computable trees of Scott rank ω1CK. We introduce a notion of “rank homogeneity”. In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated “group trees” of [10] and [9]. Using the same kind of trees, we obtain one of rank ω1CK that (...) is “strongly computably approximable”. We also develop some technology that may yield further results of this kind. (shrink)

Let L be a countable language, let I be an isomorphism-type of countable L-structures, and let a∈2ω. We say that I is a-strange if it contains a computable-from-a structure and its Scott rank is exactly ω1a. For all a, a-strange structures exist. Theorem : If C is a collection of ℵ1 isomorphism-types of countable structures, then for a Turing cone of a’s, no member of C is a-strange.

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. (shrink)

We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$, $\Pi _{\alpha }$, or $\mathrm {d-}\Sigma _{\alpha }$. We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit (...) ordinal. This answers a question left open by A. Miller.We also construct examples of computable structures of high Scott rank with Scott complexities $\Sigma _{\omega _1^{CK}+1}$ and $\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$. There are three other possible Scott complexities for a computable structure of high Scott rank: $\Pi _{\omega _1^{CK}}$, $\Pi _{\omega _1^{CK}+1}$, $\Sigma _{\omega _1^{CK}+1}$. Examples of these were already known. Our examples are computable structures of Scott rank $\omega _1^{CK}+1$ which, after naming finitely many constants, have Scott rank $\omega _1^{CK}$. The existence of such structures was an open question. (shrink)