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.