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.

Categories:

Updated: