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 study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, \ bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of \ bi-embeddable categoricity and relative \ bi-embeddable categoricity coincide for equivalence structures for \. We also prove that computable equivalence structures have degree of bi-embeddable categoricity \, or \. We furthermore obtain results (...) on the index set complexity of computable equivalence structure with respect to bi-embeddability. (shrink)

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 $\Pi ^{\mathrm {in}}_{\alpha }$ complexities. We then take a more direct approach and exhibit linear orderings of all Scott sentence complexities except $\Sigma ^{\mathrm {in}}_{3}$ and $\Sigma ^{\mathrm {in}}_{\lambda +1}$ for $\lambda $ 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. (shrink)

We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure A as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of A; the degree of bi-embeddable categoricity of A is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and (...) we show that every degree d.c.e above 0(α) for α a computable successor ordinal and 0(λ) for λ a computable limit ordinal is a degree of bi-embeddable categoricity. We also give examples of families of degrees that are not bi-embeddable categoricity spectra. (shrink)

We study the algorithmic complexity of isomorphic embeddings between computable structures.

We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega $ in vocabulary $\tau $ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is $\Pi ^0_\alpha $ in the Borel hierarchy of this topology if and only if it is definable by a $\Pi ^p_\alpha $ -formula, a positive $\Pi ^0_\alpha $ formula in the infinitary logic $L_{\omega _1\omega }$. As (...) a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let $\mathcal {K}$ be positively computably embeddable in $\mathcal {K}'$ by $\Phi $, then for every $\Pi ^p_\alpha $ formula $\xi $ in the vocabulary of $\mathcal {K}'$ there is a $\Pi ^p_\alpha $ formula $\xi ^{*}$ in the vocabulary of $\mathcal {K}$ such that for all $\mathcal {A}\in \mathcal {K}$, $\mathcal {A}\models \xi ^{*}$ if and only if $\Phi (\mathcal {A})\models \xi $. We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings. (shrink)

We calculate the possible Scott ranks of countable models of Peano arithmetic. We show that no non-standard model can have Scott rank less than $\omega $ and that non-standard models of true arithmetic must have Scott rank greater than $\omega $. Other than that there are no restrictions. By giving a reduction via $\Delta ^{\mathrm {in}}_{1}$ bi-interpretability from the class of linear orderings to the canonical structural $\omega $ -jump of models of an arbitrary completion T of $\mathrm {PA}$ we (...) show that every countable ordinal $\alpha>\omega $ is realized as the Scott rank of a model of T. (shrink)

In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to [Formula: see text]. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute [Formula: see text]. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree [Formula: see text] with [Formula: see text] for [Formula: see text] a computable ordinal greater than 2 is (...) the strong degree of categoricity of a rigid structure. Using quite different techniques we show that every degree [Formula: see text] with [Formula: see text] is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree [Formula: see text] with [Formula: see text] that is not the degree of categoricity of a rigid structure. (shrink)

Journal of Mathematical Logic, Volume 24, Issue 03, December 2024. In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to [math]. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute [math]. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree [math] with [math] for [math] a computable ordinal greater than 2 is (...) the strong degree of categoricity of a rigid structure. Using quite different techniques we show that every degree [math] with [math] is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree [math] with [math] that is not the degree of categoricity of a rigid structure. (shrink)

Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibility. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility (...) spectrum of computably enumerable equivalence relations with no countable basis and a reducibility spectrum of computably enumerable equivalence relations which is downward dense, thus has no basis. (shrink)

We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by these relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a $\boldsymbol {\Sigma }^1_1$ complete equivalence relation. We then investigate the algorithmic properties of this reduction. We obtain that elementary bi-embeddability on the class of computable graphs is $\Sigma ^1_1$ complete with respect (...) to computable reducibility and show that the elementary bi-embeddability and bi-embeddability spectra realized by graphs are related. (shrink)