# New preprint on arXiv!

My newest preprint Degree spectra of analytic complete equivalence relations just appeared on arXiv.

This article investigates the bi-embeddability and elementary bi-embeddability relation on countable structures both from the viewpoint of descriptive set theory and computable structure theory. Two structures are *bi-embeddable* if either is isomorphic to an substructure of the other. They are *elementary bi-embeddable* if either is isomorphic to a elementary substructure of the other.

Our main results are the following.

**Theorem 1.** *The elementary bi-embeddability relation on graphs is a \(\pmb \Sigma^1_1\) complete equivalence relation under Borel reducibility.*

The proof of this result uses Marker extensions with so called minimal models. A structure \(\mathcal A\) is *minimal* if it does not contain an elementary substructure.

Let \(\sim\) be an equivalence relation on a class of structures. Then given a structure \(\mathcal A\) we define the \(\sim\) spectrum of \(\mathcal A\) as the set of all sets Turing equivalent to a structure \(\sim\) equivalent to \(\mathcal A\), i.e., \[ DgSp_\sim(\mathcal A)=\{ X\subseteq \omega: \exists \mathcal B \sim \mathcal A \ X\equiv_T \mathcal A\}.\]

**Theorem 2.** *Every bi-embeddability spectrum of a graph is the jump spectrum of an elementary bi-embeddability spectrum of a graph, i.e., for every \(\mathcal G\), there is a graph \(\mathcal G'\) such that*
\[ DgSp_\approx(\mathcal G’)=\{ X: X’\in DgSp_\approxeq(\mathcal G)\}.\]

This result is proven by analyzing the reduction given to prove Theorem 1. We show that this reduction induces a computable bi-transformation with a suitable class of structures.