# Degree spectra of analytic complete equivalence relations

Dino Rossegger  Department of Pure Mathematics, University of Waterloo,
Waterloo, Ontario<EMAIL_ADDRESS>
###### Abstract.

We study the bi-embeddability and elementary bi-embeddability relation on
graphs under Borel reducibility and investigate the degree spectra realized by
this 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 to show that every bi-embeddability spectrum of a graph is
the jump spectrum of an elementary bi-embeddability spectrum of a graph.

###### Key words and phrases:

Borel reducibility, degree spectra, computable functors, bi-embeddability,
equivalence relation

###### 1991 Mathematics Subject Classification:

03C75, 03D45,03E15

The author thanks David Marker for providing crucial references on minimality.

##  1\. Introduction

Equivalence relations on countable structures are among the most heavily
studied objects in descriptive set theory and computability theory. In
descriptive set theory, starting with the work of Friedman and Stanley [FS89],
the complexity of equivalence relations on spaces of structures under Borel
reducibility has seen much interest by experts, culminating in results by
Louveau and Rosendal [LR05], who showed that, among others, the bi-
embeddability relation on graphs is $\boldsymbol{\Sigma}^{1}_{1}$-complete.
Since then there has been a constant stream of work on the complexity of the
bi-embeddability relation, both on other classes of structures, see for
instance [CT19], and refinements of completeness notions, e.g. in [CMM13].

Equivalence relations are also one of the main objects of study in
computability theory. Here, the equivalence relations are usually on the set
of natural numbers and their complexity is established using computable
reducibility. Identifying a computable structure with the index of the
algorithm computing it, one can obtain completeness results like the ones in
descriptive set theory for equivalence relations on computable structures
[FF09, Fok+10]. One object of study in computable structure theory which also
takes non-computable structures into account are degree spectra of structures,
introduced by Knight [Kni86]. The degree spectrum of a given structure is the
set of sets of natural numbers Turing equivalent to one of its isomorphic
copies. They provide a measure of the algorithmic complexity of countable
structures.

Recently, researchers initiated the study of degree spectra with respect to
other model theoretic equivalence relations such as bi-embeddability [FRS19],
elementary bi-embeddability [Ros18], elementary equivalence [AM15, And+17,
AK13], or $\Sigma_{n}$ equivalence [FRS17]. One of the main goals in this line
of research is to distinguish these equivalence relations with respect to the
degree spectra they realize. While for elementary equivalence and $\Sigma_{n}$
equivalence examples that separate them from each other and from isomorphism
and elementary bi-embeddability are known, so far all attempts to separate
isomorphism, bi-embeddability and elementary bi-embeddability have been
unsuccessful.

There seem to be various reasons for this. That we can separate elementary
equivalence and $\Sigma_{n}$ equivalence is the case because they have
different levels in the Borel hierarchy while isomorphism and bi-embeddability
are not even Borel. On the other hand bi-embeddability preserves very little
structural properties and it is thus difficult to construct interesting
examples. The aim of this article is to investigate the relationship between
the degree spectra realized by the bi-embeddability relation and by the
elementary bi-embeddability relation. First, we establish that elementary bi-
embeddability on graphs is $\boldsymbol{\Sigma}^{1}_{1}$ complete with respect
to Borel reducibility. We then proceed to establish a relationship between the
degree spectra realized by the bi-embeddability and elementary bi-
embeddability relation on graphs. Our main results are as follows.

######  Theorem 1.

The elementary embeddability relation on graphs
$\operatorname{\preccurlyeq}_{\mathfrak{G}}$ is a complete
$\boldsymbol{\Sigma}^{1}_{1}$ quasi-order. In particular, the elementary bi-
embeddability relation on graphs $\approxeq_{\mathfrak{G}}$ is a complete
$\boldsymbol{\Sigma}^{1}_{1}$ equivalence relation.

######  Theorem 2.

Let $\mathcal{G}$ be a graph, then there is a graph $\hat{\mathcal{G}}$ such
that

$DgSp_{\approxeq}(\hat{\mathcal{G}})=\\{X:X^{\prime}\in
DgSp_{\approx}({\mathcal{G}})\\}.$

As a corollary of Theorem 1 we obtain the corresponding result for elementary
bi-embeddability on computable structures.

######  Theorem 3.

The elementary embeddability relation on the class of graphs is a
$\Sigma^{1}_{1}$ complete quasi-order with respect to computable reducibility.
In particular, the elementary bi-embeddability relation on graphs is a
$\Sigma^{1}_{1}$ complete quasi-order with respect to computable reducibility.

The proofs of Theorems 1 and 3 are the topic of Section 3. In Section 4 we
build on these results to prove Theorem 2. In Section 2 we give the necessary
background and definitions.

##  2\. Background

Our definitions follow for the most part [Gao08] and [Mon18]. We assume that
all structures have universe $\omega$ and are relational. Let $\mathcal{L}$ be
a relational language $(R_{i})_{i\in\omega}$ where without loss of generality
$R_{i}$ has arity $i$. Then each element $\mathcal{A}$ of $Mod(\mathcal{L})$
can be viewed as an element of the product space

$X_{\mathcal{L}}=\prod_{i\in\omega}2^{\omega^{i}}$

and thus $Mod(\mathcal{L})$ becomes a compact Polish space on which we can
define the Borel and projective hierarchy in the usual way.

Let $\mathcal{A}$ be an $\mathcal{L}$-structure and
$(\varphi_{i}^{at})_{i\in\omega}$ be a computable enumeration of the atomic
$\mathcal{L}$-sentences with variables in $\\{x_{1},x_{2},\dots\\}$. The
_atomic diagram $D(\mathcal{A})$_ of $\mathcal{A}$ is the element of Cantor
space defined by

$D(\mathcal{A})(i)=\begin{cases}1&\text{ if
}\mathcal{A}\models\varphi_{i}^{at}[x_{j}\rightarrow j:j\in\omega]\\\ 0&\text{
otherwise.}\end{cases}$

The Turing degree of a structure $\mathcal{A}$ is the degree of
$D(\mathcal{A})$. We will in general not distinguish between a structure as an
element of $Mod(\mathcal{L})$ and its atomic diagram and assume that what is
meant is clear from the context.

Variations of the following definition were independently suggested in [Mon15,
FST19, Yu15].

######  Definition 1.

Let $E$ be an equivalence relation on $Mod(\mathcal{L})$ and $\mathcal{A}\in
Mod(\mathcal{L})$. Then the _degree spectrum of $\mathcal{A}$ with respect to
$E$_, or, short $E$-spectrum of $\mathcal{A}$, is the set

$DgSp_{E}(\mathcal{A})=\\{X:\exists\mathcal{B}\mathop{E}\mathcal{A}\
D(\mathcal{B})\equiv_{T}X\\}$

We write $\mathcal{A}\operatorname{\hookrightarrow}\mathcal{B}$ to say that
$\mathcal{A}$ is _embeddable_ in $\mathcal{B}$, and
$\mathcal{A}\approx\mathcal{B}$ to say that $\mathcal{A}$ is _bi-embeddable_
with $\mathcal{B}$, i.e.,
$\mathcal{A}\operatorname{\hookrightarrow}\mathcal{B}$ and
$\mathcal{B}\operatorname{\hookrightarrow}\mathcal{A}$. Further, we write
$\mathcal{A}\operatorname{\preccurlyeq}\mathcal{B}$ to say that $\mathcal{A}$
is _elementary embeddable_ in $\mathcal{B}$ and
$\mathcal{A}\approxeq\mathcal{B}$ to say that $\mathcal{A}$ is _elementary bi-
embeddable_ with $\mathcal{B}$, i.e.,
$\mathcal{A}\operatorname{\preccurlyeq}\mathcal{B}$ and
$\mathcal{B}\operatorname{\preccurlyeq}\mathcal{A}$.

######  Definition 2.

Let $R,S$ be binary relations on a set $X$. The relation $R$ is _reducible_ to
$S$ if there is a function $f:X\rightarrow X$ such that for all $x,y\in X$

$xRy\Leftrightarrow f(x)Sf(y).$

Assume $X=Mod(\mathcal{L})$. Then

  1. (1)

$R$ is _Borel reducible_ to $S$ if $f$ is Borel on $Mod(\mathcal{L})\times
Mod(\mathcal{L})$,

  2. (2)

$R$ is _computably reducible_ to $S$ if there is a computable operator $\Phi$
such that for all $\mathcal{A}\in Mod(\mathcal{L})$,
$\Phi^{D(\mathcal{A})}=D(f(\mathcal{A}))$.

Assume $X$ is $\omega$ and that $(\mathcal{A}_{i})_{i\in\omega}$ is a
computable enumeration of all partial computable $\mathcal{L}$ structures.
Then $R$ is _computably reducible_ to $S$ if $f$ is a computable function.

We say that a equivalence relation (quasi-order) $R\in\Gamma$ is a $\Gamma$
complete equivalence relation (quasi-order) for a complexity class $\Gamma$
with respect to $x$-reducibility if all equivalence relations (quasi-orders)
in $\Gamma$ are $x$-reducible to $R$.

A standard reference on Borel reducibility is [Gao08]. The study of computable
reducibility for sets of natural numbers has a long history in computable
structure theory starting with work of Ershov TODO. Fokina and Friedman [FF09]
showed that bi-embeddability on trees and thus also graphs is $\Sigma^{1}_{1}$
complete with respect to computable reducibility, and in [Fok+10] it is shown
that isomorphism on graphs is $\Sigma^{1}_{1}$ complete with respect to
computable reducibility. This contrasts with Borel reducibility; it is well
known that isomorphism on graphs is not $\boldsymbol{\Sigma}^{1}_{1}$
complete.

##  3\. Elementary bi-embeddability is analytic complete

###  3.1. The reduction from $\operatorname{\hookrightarrow}_{\mathfrak{G}}$
to $\operatorname{\preccurlyeq}_{\mathfrak{C}}$

The main idea of the construction is that for any given graph $\mathcal{G}$ we
replace the edge relation with structures having the property that they are
minimal under elementary embeddability.

######  Definition 3.

A structure $\mathcal{A}$ is _minimal_ if it does not have proper elementary
substructures.

Minimal structures were investigated by Fuhrken [Fuh66] who showed that there
is a theory with $2^{\aleph_{0}}$ minimal models, and Shelah [She78] who
showed that for every $n\leq\aleph_{0}$, there is a theory with $n$ minimal
models. Later, Ikeda [Ike93] investigated minimal models of minimal theories.
Notice that a prime model is not necessarily minimal, as it might contain
elementary substructures isomorphic to itself.

Given a graph $\mathcal{G}$, if $x,y\in G$ and $xEy$, then we associate a copy
of a structure $\mathcal{A}$ with the pair $(x,y)$ and otherwise we associate
a copy $\mathcal{B}$ with $(x,y)$. The structures $\mathcal{A}$ and
$\mathcal{B}$ will be elementary equivalent and minimal.

Before we formally state the reduction let us describe $\mathcal{A}$ and
$\mathcal{B}$. They will be models of the theory of the following structure
studied by Shelah [She78]. The language of the theory contains countably many
unary functions $F_{\nu}$ and unary relation symbols $R_{\nu}$, one for each
$\nu\in 2^{<\omega}$. Consider the structure

$\mathcal{S}=(2^{\omega},\langle F_{\nu}\rangle_{\nu\in 2^{<\omega}},\langle
R_{\nu}\rangle_{\nu\in 2^{<\omega}})$

where $F_{\nu}$ is defined by $F_{\nu}(\sigma)(x)=\sigma(x)+\nu(x)\mod 2$
where we assume that $\nu(x)=0$ for $x\geq|\nu|$ and $R_{\nu}(\sigma)$ if and
only if $\nu\prec\sigma$. To prove his result, Shelah showed that the theory
of this structure has quantifier eliminiation. Let $\hat{\mathcal{S}_{0}}$ be
the substructure of $\mathcal{S}$ generated by $\bar{0}$, the constant string
of $0$’s and $\hat{\mathcal{S}_{1}}$ be the substructure generated by
$\bar{1}$, the constant string of $1$’s.

Using Shelah’s argument one can show that the theories of
$\hat{\mathcal{S}}_{0}$ and $\hat{\mathcal{S}}_{1}$ both have quantifier
elimination and are therefore equivalent. Furthermore, $\hat{\mathcal{S}}_{0}$
and $\hat{\mathcal{S}}_{1}$ are minimal models of $Th(\mathcal{S})$. To see
this, let $x\in\hat{S}_{0}$, then $x=F_{\nu}(\bar{0})$ and in particular,
$\bar{0}=F_{\nu}(x)$ for some $\nu\in 2^{<\omega}$. So, the substructure of
$\hat{\mathcal{S}}_{0}$ generated by $x$ is already $\hat{\mathcal{S}}_{0}$.

As we require our structures in $\mathfrak{C}$ to be of relational syntax we
will let $\mathcal{S}_{0}$ and $\mathcal{S}_{1}$ be the structures
corresponding to $\hat{\mathcal{S}}_{0}$, respectively
$\hat{\mathcal{S}}_{1}$, after we replace each $F_{\nu}$ by its graph
$graph_{F_{\nu}}$. We may of course assume without loss of generality that the
universes of $\mathcal{S}_{0}$ and $\mathcal{S}_{1}$ are $\omega$ and let
$\mathcal{A}=\mathcal{S}_{0}$ and $\mathcal{B}=\mathcal{S}_{1}$.

Let us describe the structures in the class $\mathfrak{C}$ more formally. The
class of structures $\mathfrak{C}$ consists of all countable structures with
universe $\omega$ in the language consisting of a unary relation $W$, binary
relations $R_{\nu}$ and $graph_{F_{\nu}}$ for all $\nu\in 2^{<\omega}$, a
binary relation $N$ and a ternary relation $O$. We are now ready to give the
function $f:\mathfrak{G}\rightarrow\mathfrak{C}$ witnessing the reduction.

We formally describe how to obtain a structure in $\mathfrak{C}$ given a
graph. Let $\mathcal{G}$ be a graph and partition $\omega$ into countably many
infinite, coinfinite subsets $(A_{i})_{i\in\omega}$. Then

  * •

for every $a_{i}\in A_{0}$, $W^{f(\mathcal{G})}(a_{i})$ (we will call elements
of $A_{0}$ the vertices of $f(\mathcal{G})$),

  * •

for every $m,n\in\omega$, if $mEn$, then for all $\nu\in 2^{<\omega}$ define
$R_{\nu}^{f(\mathcal{G})}$ and ${graph_{F_{\nu}}}^{f(\mathcal{G})}$ on
$A_{\langle m,n\rangle+1}$ such that $(A_{\langle
m,n\rangle+1},\langle{graph_{F_{\nu}}}^{f(\mathcal{G})}\rangle_{\nu\in
2^{<\omega}},R_{\nu}^{f(\mathcal{G})})\cong\mathcal{S}_{0}$,

  * •

for every $m,n\in\omega$, if $\neg mEn$, then for all $\nu\in 2^{<\omega}$
define the $R_{\nu}^{f(\mathcal{G})}$ and ${graph_{F_{\nu}}}^{f(\mathcal{G})}$
on $A_{\langle m,n\rangle+1}$ such that $(A_{\langle
m,n\rangle+1},\langle{graph_{F_{\nu}}}^{f(\mathcal{G})}\rangle_{\nu\in
2^{<\omega}},R_{\nu}^{f(\mathcal{G})})\cong\mathcal{S}_{1}$,

  * •

for every $m,n\in\omega$, let $O^{f(\mathcal{G})}(a_{m},a_{n},j)$ for all
$j\in A_{\langle m,n\rangle+1}$.

  * •

and for every $i\in\omega$ let $N(a_{i},-)=\bigcup_{j\in\omega}A_{\langle
i,j\rangle+1}$.

This finishes the construction of $f(\mathcal{G})$. It is easy to see that the
function $f$ so defined is Borel, indeed it is even computable. To see that
$f$ is indeed a reduction from $\operatorname{\hookrightarrow}_{G}$ to
$\operatorname{\preccurlyeq}_{\mathfrak{C}}$ it remains to prove the
following.

######  Lemma 4.

For $\mathcal{G},\mathcal{H}\in G$,
$\mathcal{G}\operatorname{\hookrightarrow}\mathcal{H}$ if and only if
$f(\mathcal{G})\operatorname{\preccurlyeq}f(\mathcal{H})$.

###### Proof.

That $\mathcal{G}\operatorname{\hookrightarrow}\mathcal{H}$ if
$f(\mathcal{G})\operatorname{\preccurlyeq}f(\mathcal{H})$ follows trivially
from the construction. Say
$\mathcal{G}\operatorname{\hookrightarrow}\mathcal{H}$ by $g$. We get an
induced embedding $\hat{g}$ defined such that if $g:i\mapsto j$, then
$\hat{g}:a_{i}\mapsto a_{j}$ and so that it is the canonical isomorphism on
the structures associated to $(a_{i},a_{j})$ and $(a_{j},a_{i})$. We claim
that $\hat{g}$ is elementary. We use Ehrenfeucht-Fraïssé games to verify this
claim. Say we are playing on the structures
$(f(\mathcal{G}),g_{1},\dots,g_{n})$ and
$(f(\mathcal{H}),f(g_{1}),\dots,f(g_{n}))$. We will call the $O$-closure of
the substructures induced by $g_{1},\dots,g_{n}$, respectively,
$f(g_{1}),\dots,f(g_{n})$, the fixed substructures. Notice that for player $I$
to have a win in the game of length $m$ they need to play elements not covered
by the fixed substructures as these are isomorphic. So say that $I$ plays
$x_{1}\in f(H)$ such that $O^{f(\mathcal{H})}(y_{1},z_{1},x_{1})$ for some
$y_{1},z_{1}\in f(H)$, never mentioned in the play before. Then player $II$
can choose $y_{2},z_{2}\in f(G)$ never mentioned in the play before and as
$\mathcal{S}_{0}\equiv\mathcal{S}_{1}$ they can choose an element $x_{2}$ so
that they have a winning strategy for games of length $m$ played inside these
structures. The cases when player $I$ plays elements from $f(G)$ or when
player $I$ plays elements from vertices which already appeared in the play
before are similar. Thus player $II$ has a winning strategy for the game of
length $m$. As $m$, $n$, and $g_{1},\dots,g_{n}$ were arbitrary, the lemma
follows. ∎

###  3.2. Graphs are complete for elementary embeddability

We will show that for every class of structures $\mathfrak{K}$, there is a
computable reduction
$\operatorname{\preccurlyeq}_{\mathfrak{K}}\rightarrow\operatorname{\preccurlyeq}_{\mathfrak{G}}$.

The result we are going to prove appeared in [Ros18]. There, a proof sketch
was given that shows that it preserves elementary bi-embeddability spectra. We
will give a full proof here. We note that the coding used in the reduction is
not new but was already used in [AM15] to show that graphs are universal for
theory spectra. Let us first describe the coding.

We may assume without loss of generality that $\mathfrak{K}$ is a class of
structures in relational language $\mathcal{L}=R_{0},R_{1},\dots$ where each
$R_{i}$ has arity $i$. Given $\mathcal{A}\in\mathfrak{K}$, the graph
$g(\mathcal{A})$ has three vertices $a$, $b$, $c$ where to $a$ we connect the
unique $3$-cycle in the graph, to $b$ the unique $5$-cycle, and to $c$ the
unique $7$-cycle. For each element $x\in A$ we add a vertex $v_{x}$ and an
edge $a\rightarrowtail v_{x}$. For every $i$ tuple $x_{1},\dots,x_{i}\in A$ we
add chains of length $i+k$ for every $k$, $1\leq k\leq i$ with common last
elements $y$. We add an edge $v_{x_{k}}\rightarrowtail y_{1}$ only if $y_{1}$
is the first element of the chain of length of $i+k$. If $\mathcal{A}\models
R_{i}(x_{1},\dots,x_{i})$ we add an edge $y\rightarrowtail b$ and otherwise
add an edge $y\rightarrowtail c$. This finishes the construction. See Fig. 1
for an example.

$3$$5$$7$$v_{3}$$v_{2}$$v_{1}$ Figure 1.  Part of the graph $F(\mathcal{A})$
coding that $\mathcal{A}\not\models R_{3}(3,2,1)$ and $\mathcal{A}\models
R_{3}(1,2,3)$.

######  Lemma 5.

For $\mathcal{A},\mathcal{B}\in\mathfrak{K}$,
$\mathcal{A}\operatorname{\preccurlyeq}\mathcal{B}$ if and only if
$g(\mathcal{A})\operatorname{\preccurlyeq}g(\mathcal{B})$.

###### Proof.

$(\Rightarrow)$. Assume that
$\mathcal{A}\operatorname{\preccurlyeq}\mathcal{B}$ and that $\mathcal{A}$ is
an elementary substructure of $\mathcal{B}$. We may also assume without loss
of generality that $g(\mathcal{A})\subseteq g(\mathcal{B})$. We will show that
for all $n\in\omega$ and any $\overline{a}\in g(\mathcal{A})^{<\omega}$ player
II has a winning strategy for the $n$ turn Ehrenfeucht Fraïssé game
$G_{n}((g({\mathcal{A}}),\overline{a}),(g({\mathcal{B}}),\overline{a}))$.
Assume that $n$ is the least such that player II has no winning strategy for
$G_{n}((g({\mathcal{A}}),\overline{a}),(g(\mathcal{B}),\overline{a}))$. Then
either there is $\overline{v}\in g(\mathcal{A})^{n}$ such that for all
$\overline{u}\in g(\mathcal{B})^{n}$
$\langle\overline{a},\overline{v}\rangle^{g({\mathcal{A}})}\not\cong\langle\overline{a},\overline{u}\rangle^{g({\mathcal{B}})}$
or there is $\overline{u}\in g(\mathcal{B})^{n}$ such that for all
$\overline{v}\in g(\mathcal{B})^{n}$
$\langle\overline{a},\overline{u}\rangle^{g(\mathcal{B})}\not\cong\langle\overline{a},\overline{v}\rangle^{g({\mathcal{A}})}$.
We will derive a contradiction assuming the second case. Deriving one from the
first case can be done in a similar fashion.

Notice that $\overline{a}\overline{u}$ is in a substructure of
$g({\mathcal{B}})$ coding a finite substructure of $\mathcal{B}$ in a finite
part $\mathcal{L}_{1}$ of the language of $\mathcal{B}$. Extend
$\langle\overline{a},\overline{u}\rangle^{g({\mathcal{B}})}$ so that it codes
such a substructure $\mathcal{B}_{1}$ of $\mathcal{B}$. Now consider the
conjunction $\varphi$ of atomic formulas or negations thereof true of
$\mathcal{B}_{1}$ in $\mathcal{L}_{1}$. Let $\overline{a}^{\prime}$ be the
elements in $B_{1}\cap A$ and $\overline{u}^{\prime}$ the elements in
$B_{1}\setminus A$. Then
$\mathcal{B}\models\varphi(\overline{a}^{\prime},\overline{u}^{\prime})$ and
Tarski-Vaught gives us elements $\overline{v}^{\prime}$ in $\mathcal{A}$ such
that $\mathcal{A}\models\varphi(\overline{a}^{\prime},\overline{v}^{\prime})$.
It follows that we have a partial isomorphism between
$\langle\overline{a}^{\prime},\overline{u}^{\prime}\rangle^{\mathcal{B}}$ and
$\langle\overline{a}^{\prime},\overline{v}^{\prime}\rangle^{\mathcal{A}}$ in
$\mathcal{L}_{1}$. This induces an isomorphism between the subgraph coding
$\mathcal{B}_{1}$ and the subgraph coding
$\langle\overline{a}^{\prime},\overline{v}^{\prime}\rangle^{\mathcal{A}}$. But
$\langle\overline{a},\overline{u}\rangle^{g(\mathcal{B})}$ is a subgraph of
the graph coding $\mathcal{B}_{1}$ and thus it is isomorphic to a substructure
$\langle\overline{a},\overline{v}\rangle^{g(\mathcal{A})}$ of the structure
coding
$\langle\overline{a}^{\prime},\overline{v}^{\prime}\rangle^{\mathcal{A}}$, a
contradiction.

$(\Leftarrow)$. An easy induction on the quantifier depth of formulas in
$\mathcal{L}$ shows that for every $\mathcal{A}\in\mathfrak{K}$ and
$\mathcal{L}$-formula $\varphi$ with $n$-free variables the set

$D_{\varphi}^{\mathcal{A}}=\\{(v_{a_{1}},\dots,v_{a_{n}}):(\mathcal{A},a_{1},\dots,a_{n})\models\varphi(a_{1},\dots,a_{n})\\}$

is definable in $g(\mathcal{A})$. Now, assume that
$g(\mathcal{A})\operatorname{\preccurlyeq}g(\mathcal{B})$ and without loss of
generality that $g(\mathcal{A})$ is an elementary substructure of
$g(\mathcal{B})$. Let $g_{\mathcal{B}}:\mathcal{B}\rightarrow g(\mathcal{B})$
be defined by $g_{\mathcal{B}}:b\mapsto v_{b}$. Notice that the map $a\mapsto
g_{\mathcal{B}}^{-1}(v_{a})$ is an embedding of $\mathcal{A}$ in
$\mathcal{B}$. To see that this embedding is elementary assume that
$(\mathcal{A},\overline{a})\models\varphi$, then $\bar{v}_{\bar{a}}\in
D_{\varphi}^{\mathcal{A}}$ and by elementarity $\bar{v}_{\bar{a}}\in
D_{\varphi}^{\mathcal{B}}$. So,
$(\mathcal{B},g_{\mathcal{B}}^{-1}(\bar{v}_{\bar{a}}))\models\varphi(g_{\mathcal{B}}^{-1}(\bar{v}_{\bar{a}}))$.

∎

Concatenating the reductions $f$ and $g$ and from the fact that
$\operatorname{\hookrightarrow}_{\mathfrak{G}}$, $\approx_{\mathfrak{G}}$ are
complete $\boldsymbol{\Sigma}^{1}_{1}$ quasi-orders, respectively equivalence
relations we obtain Theorem 1.

##  4\. Degree spectra

In this section we finish the proof of Theorem 2. It is easy to see that the
two reductions $f:\mathfrak{G}\rightarrow\mathfrak{C}$ and
$g:\mathfrak{C}\rightarrow\mathfrak{G}$ are computable. To relate the family
of degree spectra realized by $\approx_{\mathfrak{G}}$ and
$\approxeq_{\mathfrak{G}}$ we need a few more definitions.

######  Definition 4 (cf. [Har+17, Mil+18]).

Let $\mathfrak{C}$ and $\mathfrak{D}$ be categories. A _computable functor_
between $\mathfrak{C}$ and $\mathfrak{D}$ is a pair of computable operators
$(\Phi,\Phi_{*})$ such that

  1. (1)

for all $\mathcal{A}\in\mathfrak{C}_{1}$, $F(\mathcal{A})=\Phi^{\mathcal{A}}$,

  2. (2)

for all $f:\mathcal{A}\rightarrow\mathcal{B}\in\mathfrak{C}_{2}$,
$F(f)=\Phi^{\mathcal{A}\oplus f\oplus\mathcal{B}}$.

Computable functors preserve many computability theoretic properties. Recall
that for $X,Y\subseteq\mathcal{P}(\omega)$, $X$ is _Medwedev reducible_ to
$Y$, $X\leq_{s}Y$, if there is a Turing operator $\Phi$ such that for all
$y\in Y$, there is $x\in X$ such that $\Phi^{y}=x$. We have in particular that
if
$F:(\mathfrak{C},\operatorname{\leadsto}_{1})\rightarrow(\mathfrak{D},\operatorname{\leadsto}_{2})$
is a computable functor and $\sim_{1}$, $\sim_{2}$ are the symmetric closure
of $\operatorname{\leadsto}_{1}$, and $\operatorname{\leadsto}_{2}$,
respectively, then for all $\mathcal{A}\in\mathfrak{C}$

$DgSp_{\sim_{1}}(F(\mathcal{A}))\leq_{s}DgSp_{\sim_{2}}(\mathcal{A}).$

It is an easy exercise to see that $g\circ f$ induces a computable functor
$H:(\mathfrak{G},\operatorname{\hookrightarrow})\rightarrow(\mathfrak{G},\operatorname{\preccurlyeq})$
and thus for all $\mathcal{G}\in\mathfrak{G}$,
$DgSp_{\approx}(H(\mathcal{G}))\leq_{s}DgSp_{\approxeq}(\mathcal{G})$.

To get that every degree spectrum realized in $\mathfrak{C}$ is also realized
in $\mathfrak{D}$ we need a stronger notion of reducibility. The following
notion is central to it.

######  Definition 5 ([Har+17]).

A functor $F:\mathfrak{C}\rightarrow\mathfrak{D}$ is _effectively isomorphic_
to $G:\mathfrak{C}\rightarrow\mathfrak{D}$ if there is a Turing operator
$\Lambda$ such that for every $\mathcal{A}\in\mathfrak{C}$
$\Lambda^{\mathcal{A}}$ is an isomorphism from $F(\mathcal{A})$ to
$G(\mathcal{A})$, and the following diagram commutes for all
$\mathcal{A},\mathcal{B}\in\mathfrak{C}$ and every morphism
$\gamma:\mathcal{A}\rightarrow\mathcal{B}$.

${F(\mathcal{A})}$${G(\mathcal{A})}$${F(\mathcal{B})}$${G(\mathcal{B})}$$\scriptstyle{\Lambda^{\mathcal{A}}}$$\scriptstyle{F(\gamma)}$$\scriptstyle{G(\gamma)}$$\scriptstyle{\Lambda^{\mathcal{B}}}$

######  Definition 6 ([Har+17]).

A category $\mathfrak{C}$ is _CBF_ -reducible to $\mathfrak{D}$,
$\mathfrak{C}\leq_{CBF}\mathfrak{D}$ if there is a computable functor
$F:\mathfrak{C}\rightarrow\mathfrak{D}$ and a computable functor
$G:\mathfrak{D}\supseteq\hat{\mathfrak{D}}\rightarrow\mathfrak{C}$ where
$\hat{\mathfrak{D}}$ is the symmetric closure of $F(\mathfrak{C})$, $F\circ G$
is effectively isomorphic to $Id_{\hat{\mathfrak{D}}}$, and $G\circ F$ is
effectively isomorphic to $Id_{\mathfrak{C}}$.

######  Proposition 6.

If
$(\mathfrak{C},\operatorname{\leadsto}_{1})\leq_{CBF}(\mathfrak{D},\operatorname{\leadsto}_{1})$,
then every set realized as a $\sim_{1}$-spectrum in $\mathfrak{C}$ is realized
as a $\sim_{2}$-spectrum in $\mathfrak{D}$.

######  Definition 7.

A class of structures $\mathfrak{C}$ is _CBF-complete_ with respect to an
equivalence relation if for every class $\mathfrak{K}$,
$(\mathfrak{K},\sim)\leq_{CBF}(\mathfrak{C},\sim)$.

For any class $\mathfrak{K}$ equipped with the elementary embeddability
relation by Section 3.2 there is a computable reduction $g$ from
$(\mathfrak{K},\operatorname{\preccurlyeq})$ to
$(\mathfrak{G},\operatorname{\preccurlyeq})$. We show that these reductions
induce $CBF$-reductions and that thus graphs are CBF-complete for bi-
embeddability.

######  Theorem 7.

The class of graphs is CBF-complete for bi-embeddability.

###### Proof.

Fix a class $\mathfrak{K}$. It is clear from the construction that $g$ induces
a computable functor
$F:(\mathfrak{K},\approxeq)\rightarrow(\mathfrak{G},\approxeq)$. We have to
show that $F(\mathfrak{K})$ is closed under elementary bi-embeddability and
that there is a functor $G:F(\mathfrak{K})\rightarrow\mathfrak{K}$ such that
$F\circ G$ and $G\circ F$ are effectively isomorphic.

Let $\mathcal{G}\approxeq F(\mathcal{A})$ for some
$\mathcal{A}\in\mathfrak{K}$. We may assume without loss of generality that
$\mathcal{G}$ is an elementary substructure of $F(\mathcal{A})$. For every
$\bar{a}\in\mathcal{G}^{<\omega}$,
$tp_{\mathcal{G}}(\bar{a})=tp_{\mathcal{A}}(\bar{a})$. Thus $\mathcal{G}$ must
contain the elements $a,b,c$ of $F(\mathcal{A})$ with unique $3$,
respectively, $5$ and $7$ cycles connected to them. Furthermore, say
$\bar{a}\in\mathcal{G}$ codes elements of $A$ in $F(\mathcal{A})$ such that
$\mathcal{A}\models R_{i}(\bar{a})$, then this information must also be coded
in $\mathcal{G}$ as it is preserved in the type of $\bar{a}$. We can compute a
structure $G(\mathcal{G})$ as follows. Fix a $\mathcal{G}$ computable
enumeration $f$ of the set $\\{x:a\rightarrowtail x\\}$. Notice that this can
be done uniformly since the set $\\{x:a\rightarrowtail x\\}$ is uniformly
computable in all structures in $F(\mathfrak{K})$. Then for all
$a_{1},\dots,a_{i}=\bar{a}\in\omega^{i}$, $G(\mathcal{G})\models
R_{i}(\bar{a})$ if for every $a_{j}$, $j<i$, there is a chain of $i+j$
connected elements $y_{1},\dots y_{i+j}$ with $f(a_{j})\rightarrowtail y_{1}$,
all $j$ chains share the same last element $y$ and $y\rightarrowtail b$.
Likewise, $G(\mathcal{G})\models\neg R_{i}(\bar{a})$ if there are chains
satisfying the above conditions with $y\rightarrowtail c$. This finishes the
construction of $G(\mathcal{A})$. To finish the construction of $G$ and
showing that $GF$ and $FG$ are effectively isomorphic to the identities on
$\mathfrak{K}$ and $\mathfrak{G}$, respectively, first note that
$G(F(\mathcal{A}))\cong\mathcal{A}$. There is a canonic isomorphism given by
the composition of the maps $a\mapsto v_{a}$ and the enumeration $f$ of the
set $\\{x:a\rightarrowtail x\\}$, i.e., the isomorphism is defined by
$a\mapsto f^{-1}(v_{a})$. It is clearly uniformly computable, say by
$\Lambda_{\mathfrak{K}}$. On the other hand let
$\mathcal{G}inF(\mathfrak{K})$, then we can compute an isomorphism between
$F(G(\mathcal{G}))$ and $\mathcal{G}$ by doing the following. Every $v\in G$
either defines a relation $R_{i}$ on some tuple or codes an element, or is
used to define $a,b,c$. One can computably determine which of the three cases
holds. In the second case simply map $v$ to $v_{f^{-}1(v)}$, in the third case
one can computably determine whether $v$ is used to define $a,b,c$ and using
$F$ and $G$ computably find the corresponding element in $F(G(\mathcal{G}))$.
In the first case, we have to find the tuple $\overline{w}$ such that $v$ is
involved in the coding of the relation $R_{i}$ on $\bar{w}$. We then map $v$
to the corresponding element in the coding of $R_{i}$ on the tuple
$v_{f^{-}1(\overline{w})}$. It is easy to see that one can define a Turing
operator $\Lambda_{\mathfrak{F(\mathfrak{K})}}$ computing this isomorphism.
The Turing operators $\Lambda_{\mathfrak{F(\mathfrak{K})}}$ and
$\Lambda_{\mathfrak{K}}$ will witness the effective isomorphism between $FG$
and the identity on $F(\mathfrak{K})$, respectively, the effective isomorphism
between $GF$ and the identity on $\mathfrak{G}$.

It remains to show that $G(\mathcal{G})\approxeq\mathcal{A}$, how to compute
embeddings and that the diagram in Definition 5 commutes. To see the former
just notice that $F(G(\mathcal{G}))\cong\mathcal{G}$ and since
$\mathcal{G}\approxeq F(\mathcal{A})$ we get that $F(G(\mathcal{G}))\approxeq
F(\mathcal{A})$. That $G(\mathcal{G})\approxeq\mathcal{A}$ now follows
directly from Lemma 5. Given an elementary embedding
$\nu:\mathcal{G}_{1}\rightarrow\mathcal{G}_{2}$ $G(\nu)$ can be computed in
exactly the same fashion as $\Lambda^{\mathfrak{K}}$ computes the isomorphisms
and that the diagram in Definition 5 commutes follows easily by the uniformity
of the constructions. ∎

Unfortunately, for the reduction from bi-embeddability on graphs to elementary
bi-embeddability on $\mathfrak{C}$ given in Section 3.1 we can not deduce that
$(\mathfrak{G},\approx)\leq_{UCT}(\mathfrak{C},\approxeq)$. However, we can
still establish a relationship between the degree spectra in these classes.

######  Lemma 8.

Let $X$ be $\Delta^{0}_{2}(Y)$ for some set $Y$. Then there exist a sequence
of structures $(\mathcal{C}_{i})_{i\in\omega}$, uniformly computable in $Y$,
such that for all $i\in\omega$

$\mathcal{C}_{i}\cong\begin{cases}\mathcal{S}_{0}&\text{if }i\in X\\\
\mathcal{S}_{1}&\text{if }i\not\in X\end{cases}.$

###### Proof.

As $X$ is $\Delta^{0}_{2}$ there is an $X$-computable two valued function $f$
such that

$\lim_{s\rightarrow\infty}f(i,s)=\begin{cases}0&\text{if }i\in X\\\ 1&\text{if
}i\not\in X\end{cases}.$

Define a structure $\mathcal{C}$ as follows. Fix an enumeration $g$ of
$2^{<\omega}$. At stage $0$ define $\mathcal{C}_{0}$ to be the partial
structure containing one element $a$ on which no relation holds and leave all
function symbols undefined. Say we have defined the structure
$\mathcal{C}_{s}$. At stage $s+1$ we look at $f(i,j)$ for $j<s$ and define
$\mathcal{C}_{s+1}$ as if $a$ was the finite string with $a(j)=f(j)$ for
$j<s$. To be more precise:

  1. (1)

For all $k$, if $k\leq s$ and $|g(k)|\leq s$ then let $R_{g(k)}(a)$ if and
only if $g(k)\preceq a$, and if $F_{g(k)}(a)$ has not been defined yet add a
new element and set $F_{g(k)}(a)$.

  2. (2)

We may assume by induction that for all elements $b$ in $\mathcal{C}_{s+1}$
there is $k\leq s$ such that $b=F_{g(k)}(a)$. We set $R_{g(l)}(b)$ respecting
this equation for all $l\leq s$.

It is easy to see that this procedure yields a computable sequence of
structures $\mathcal{C}_{s}$ with $\mathcal{C}_{s}\subseteq\mathcal{C}_{s+1}$
and a computable structure as its limit. We let $\mathcal{C}$ be this
structure. $\mathcal{C}$ contains an element $a$ such that $\mathcal{A}\models
R_{\sigma}(a)$ if and only if $a\preceq f(i,-)$ and all other elements are
equal to $F_{\tau}(a)$ for some $\tau\in 2^{<\omega}$. Thus, in particular if
$\lim f(i,s)=0$, then there is an element representing the constant string of
$0$’s in $\mathcal{A}$ and otherwise there is an element representing the
constant string of $1$’s in $\mathcal{A}$. Let $\mathcal{C}_{i}=\mathcal{C}$,
then $\mathcal{C}_{i}\cong\mathcal{S}_{0}$ if and only if $i\in X$ and
$\mathcal{C}_{i}\cong\mathcal{S}_{1}$ if and only if $i\not\in X$ as required.
∎

######  Lemma 9.

For every structure $\mathcal{G}\in\mathfrak{G}$ there is
$\mathcal{A}\in\mathfrak{C}$ such that

$DgSp_{\approxeq}(\mathcal{A})=\\{X:X^{\prime}\in
DgSp_{\approx}(\mathcal{G})\\}.$

###### Proof.

Recall the reduction from embeddability on graphs to elementary embeddability
on $\mathfrak{C}$ given in Section 3.1. It is easy to see that it induces a
computable functor
$F:(\mathfrak{G},\approx)\rightarrow(\mathfrak{C},\approxeq)$. We show that
the functor has a pseudo-inverse $G$ on the $\approxeq$-saturation of
$F(\mathfrak{G})$ and then use Lemma 8 to obtain the lemma. The minimality of
the submodels $\mathcal{S}$ used in the construction of $F$ will play a
crucial role in the proof.

Say $\mathcal{B}\approxeq F(\mathcal{G})$ for $\mathcal{G}\in\mathfrak{G}$.
Then, in particular, if $x,y$ are vertices in $\mathcal{B}$ and
$\mathcal{S}_{x,y}$ is the substructure on the elements satisfying $O(x,y,-)$
we have that $\mathcal{S}_{x,y}$ must be isomorphic to either the substructure
of $\mathcal{S}$ generated by the constant string of $0$’s or the constant
string of $1$’s since it elementary embeds into $\mathcal{S}_{u,v}$ for some
$u,v\in F(\mathcal{G})$, $\mathcal{S}_{u,v}$ is isomorphic to one of the two
and thus, by minimality, does not admit other elementary substructures than
itself. Thus, we get a graph $G(\mathcal{B})$ from $\mathcal{B}$ by defining
an edge between two vertex variables $x,y$ from $\mathcal{B}$ if and only if
$S_{u,v}\cong S_{0}$. Clearly every elementary embedding of $\mathcal{B}$ in
$F(\mathcal{G})$ yields an embedding of $G(\mathcal{B})$ in $\mathcal{G}\cong
G(F(\mathcal{G}))$ and the analogous fact is true for every elementary
embedding of $F(\mathcal{G})$ in $\mathcal{B}$. Likewise, we can argue that
$F(G(\mathcal{A}))\cong\mathcal{A}$ for every $\mathcal{A}\in
F(\mathfrak{G})$. Thus $G$ and $F$ are pseudo-inverses.

However, notice that $G$ is not effective. It is not hard to see that it takes
$1$ jump over the diagram of any $\mathcal{A}\in F(\mathfrak{G})$ to compute
$G(F(\mathcal{A}))$ as the isomorphism types of $\mathcal{S}_{1}$ and
$\mathcal{S}_{0}$ are definable by $\Sigma^{c}_{2}$ formulas in
$\mathfrak{C}$. This, in particular implies, that for all $\mathcal{A}\in
F(\mathfrak{G})$,

$DgSp_{\approxeq}(\mathcal{A})\leq_{s}\\{X:X^{\prime}\in
DgSp_{\approx}(G(\mathcal{A}))\\}.$

From the fact that $F$ and $G$ are pseudo-inverses and Lemma 8 we then obtain
that

$DgSp_{\approxeq}(\mathcal{A})=\\{X:X^{\prime}\in
DgSp_{\approx}(G(\mathcal{A}))\\}.$

∎

Combining the fact that graphs are universal for elementary bi-embeddability
shown in Theorem 7 and Lemma 9 we obtain Theorem 2.

We note that Theorem 2 may not be optimal. Using a different proof one might
be able to get an even stronger relationship between the spectra realized by
bi-embeddability on graphs and elementary bi-embeddability on graphs. We thus
ask.

######  Question 1.

Is every bi-embeddability spectrum of a graph the elementary bi-embeddability
spectrum of a graph and vice versa?

One way to answer this question positively is by showing that if $X$ is an
elementary bi-embeddability spectrum then so is $X^{\prime}=\\{x^{\prime}:x\in
X\\}$. This is true for isomorphism spectra and usually shown by considering
an appropriate definition for the jump of a structure. However, all known such
definitions do not preserve elementary embeddability (and not even elementary
equivalence). We thus ask.

######  Question 2.

Let $X$ be the elementary bi-embeddability spectrum of a graph. Is
$X^{\prime}$ the elementary bi-embeddability spectrum of a graph?

######  Question 3.

Let $X$ be the theory spectrum of a graph. Is $X^{\prime}$ the theory spectrum
of a graph?

Also, while Theorem 7 shows that graphs are complete for elementary bi-
embeddability spectra, it is unknown whether the same is true for bi-
embeddability. We therefore ask.

######  Question 4.

Is every bi-embeddability spectrum of a structure realized as the bi-
embeddability spectrum of a graph?

## References

  * [AK13] Uri Andrews and Julia Knight  “Spectra of Atomic Theories”  In _The Journal of Symbolic Logic_ 78.04, 2013, pp. 1189–1198  URL: http://journals.cambridge.org/abstract_S0022481200126507
  * [AM15] Uri Andrews and Joseph Miller  “Spectra of Theories and Structures”  In _Proceedings of the American Mathematical Society_ 143.3, 2015, pp. 1283–1298  DOI: 10.1090/S0002-9939-2014-12283-0
  * [And+17] Uri Andrews et al.  “Theory Spectra and Classes of Theories”  In _Transactions of the American Mathematical Society_ 369.9, 2017, pp. 6493–6510
  * [CMM13] Riccardo Camerlo, Alberto Marcone and Luca Motto Ros  “Invariantly Universal Analytic Quasi-Orders”  In _Transactions of the American Mathematical Society_ 365.4, 2013, pp. 1901–1931  DOI: 10.1090/S0002-9947-2012-05618-2
  * [CT19] Filippo Calderoni and Simon Thomas  “The Bi-Embeddability Relation for Countable Abelian Groups”  In _Transactions of the American Mathematical Society_ 371.3, 2019, pp. 2237–2254
  * [FF09] Ekaterina Fokina and Sy-David Friedman  “Equivalence Relations on Classes of Computable Structures”  In _Mathematical Theory and Computational Practice_ , Lecture Notes in Computer Science 5635  Springer Berlin Heidelberg, 2009, pp. 198–207  URL: http://link.springer.com/chapter/10.1007/978-3-642-03073-4_21
  * [Fok+10] Ekaterina B. Fokina et al.  “Isomorphism and Bi-Embeddability Relations on Computable Structures”  In _Preprint_ , 2010
  * [FRS17] Ekaterina Fokina, Dino Rossegger and Luca San Mauro  “Degree Spectra of Structures with Respect to the Bi-Embeddability Relation”  In _Proc. of the 11th Panhellenic Logic Symposium_ , 2017, pp. 32–38
  * [FRS19] Ekaterina Fokina, Dino Rossegger and Luca San Mauro  “Bi-Embeddability Spectra and Bases of Spectra”  In _Mathematical Logic Quarterly_ 65.2 Wiley Online Library, 2019, pp. 228–236  arXiv:1808.05451
  * [FS89] Harvey Friedman and Lee Stanley  “A Borel Reducibility Theory for Classes of Countable Structures”  In _The Journal of Symbolic Logic_ 54.03, 1989, pp. 894–914  DOI: 10.2307/2274750
  * [FST19] Ekaterina Fokina, Pavel Semukhin and Daniel Turetsky  “Degree Spectra with Respect to Equivalence Relations”  In _Algebra and Logic_ 58.2, 2019, pp. 158–172
  * [Fuh66] Gebhard Fuhrken  “Minimal-Und Primmodelle”  In _Archiv für mathematische Logik und Grundlagenforschung_ 9.1-2 Springer, 1966, pp. 3–11
  * [Gao08] Su Gao  “Invariant Descriptive Set Theory”  CRC Press, 2008  URL: https://books.google.at/books?hl=en&lr=&id=VfiOZWY282QC&oi=fnd&pg=PR1&dq=su+gao+descriptive+invariant+set+theory&ots=hBbOkAIp13&sig=dyra5awG-oFwywX_Z7pRaId6xdQ
  * [Har+17] Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller and Antonio Montalbán  “Computable Functors and Effective Interpretability”  In _The Journal of Symbolic Logic_ 82.1, 2017, pp. 77–97  URL: https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/div-classtitlecomputable-functors-and-effective-interpretabilitydiv/F346DA46B42BF1B989049E6DA8942E12
  * [Ike93] Koichiro Ikeda  “Minimal Models of Minimal Theories”  In _Tsukuba Journal of Mathematics_ 17.2 JSTOR, 1993, pp. 491–496
  * [Kni86] Julia F. Knight  “Degrees Coded in Jumps of Orderings”  In _The Journal of Symbolic Logic_ 51.04, 1986, pp. 1034–1042  DOI: 10.2307/2273915
  * [LR05] Alain Louveau and Christian Rosendal  “Complete Analytic Equivalence Relations”  In _Transactions of the American Mathematical Society_ 357.12, 2005, pp. 4839–4866  URL: http://www.ams.org/tran/2005-357-12/S0002-9947-05-04005-5/
  * [Mil+18] Russell Miller, Bjorn Poonen, Hans Schoutens and Alexandra Shlapentokh  “A Computable Functor from Graphs to Fields”  In _The Journal of Symbolic Logic_ 83.1, 2018, pp. 326–348
  * [Mon15] Antonio Montalbán  “Analytic Equivalence Relations Satisfying Hyperarithmetic-Is-Recursive”  In _Forum of Mathematics, Sigma_ 3 Cambridge University Press, 2015
  * [Mon18] Antonio Montalbán  “Computable Structure Theory”, 2018  URL: https://math.berkeley.edu/~antonio/
  * [Ros18] Dino Rossegger  “Elementary Bi-Embeddability Spectra of Structures”  In _Conference on Computability in Europe_ , Lecture Notes in Computer Science  Springer, 2018, pp. 349–358
  * [She78] Saharon Shelah  “On the Number of Minimal Models”  In _The Journal of Symbolic Logic_ 43.3 Cambridge University Press, 1978, pp. 475–480
  * [Yu15] Liang Yu  “Degree Spectra of Equivalence Relations”  In _Proceedings Of The 13th Asian Logic Conference_ World Scientific, 2015, pp. 237–242