Abstract 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.

Abstract 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.

In several classes of countable structures it is known that every hyperarithmetic structure has a computable presentation up to bi-embeddability. In this article we investigate the complexity of embeddings between bi-embeddable structures in two such classes, the classes of linear orders and Boolean algebras. We show that if L is a computable linear order of Hausdorff rank n, then for every bi-embeddable copy of it there is an embedding computable in 2n−1 jumps from the atomic diagrams. We furthermore show that this is the best one can do: Let L be a computable linear order of Hausdorff rank n≥1, then 0(2n−2) does not compute embeddings between it and all its computable bi-embeddable copies. We obtain that for Boolean algebras which are not superatomic, there is no hyperarithmetic degree computing embeddings between all its computable bi-embeddable copies. On the other hand, if a computable Boolean algebra is superatomic, then there is a least computable ordinal α such that 0(α) computes embeddings between all its computable bi-embeddable copies. The main technique used in this proof is a new variation of Ash and Knight's pairs of structures theorem.

Abstract 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.

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.