Julia Knight

Friedman and Stanley [9] developed the notion of Borel reducibility and illustrated its use in comparing classification problems for some familiar classes of countable structures. For many embeddings, the fact that the embedding is 1–1 on isomorphism types is explained by the existence of simple formulas that, uniformly, interpret the input structure in the output structure. For the embeddings of graphs in trees, and in linear orderings, there is no uniform interpretation [16, 20]. We focus on a version of the Friedman–Stanley embedding from [16] that takes each structure A $\mathcal {A}$ script upper A for the language of graphs to a labeled tree T A $T_{\mathcal {A}}$ upper T Subscript script upper A. Gonzalez and Rossegger [13] showed that this embedding preserves Scott complexity. We refine this result, showing that for an X-computable ordinal, if one of A $\mathcal {A}$ script upper A, T A $T_{\mathcal {A}}$ upper T Subscript script upper A has a computable infinitary Scott sentence, then so does the other, and the complexities match. Let T $\mathbb {T}$ double struck upper T be the class of labeled trees isomorphic to those in the range of the embedding, and let T α $\mathbb {T}^\alpha $ double struck upper T Superscript alpha be the subclass consisting of structures of Scott rank at most α $\alpha $ alpha. It follows from results of Gao [10] that T $\mathbb {T}$ double struck upper T is not Borel. We show that for each α $\alpha $ alpha, T α $\mathbb {T}^\alpha $ double struck upper T Superscript alpha is Borel. In fact, if α $\alpha $ alpha is an X-computable ordinal, then T α $\mathbb {T}^\alpha $ double struck upper T Superscript alpha is complete X-effective Π 2 α + 2 $\Pi _{2\alpha +2}$ normal upper Pi Subscript 2 alpha plus 2.