DEGREE SPECTRA OF ANALYTIC COMPLETE EQUIVALENCE RELATIONS
Published Web Location
https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/degree-spectra-of-analytic-complete-equivalence-relations/1640DA39A8F523D43791FAFAC1775AD4Abstract
AbstractWe 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.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.