{'fraction_non_alphanumeric': 0.05058000281782746, 'fraction_numerical': 0.010050251256281407, 'mean_word_length': 3.756310029037302, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Degree spectra of analytic complete equivalence relations

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 analytic 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.


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 Σ Σ Σ 1 1 -complete. Since then there has been a constant stream of work on the complexity of the biembeddability 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 Σ 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 Σ 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 biembeddability have been unsuccessful.
There seem to be various reasons for this. That we can separate elementary equivalence and Σ 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 Σ Σ Σ 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 G is a complete Σ Σ Σ 1 1 quasi-order. In particular, the elementary bi-embeddability relation on graphs ≅ G is a complete Σ Σ Σ 1 1 equivalence relation.
Theorem 2. Let G be a graph, then there is a graphĜ such that 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 Σ 1 1 complete quasi-order with respect to computable reducibility. In particular, the elementary bi-embeddability relation on graphs is a Σ 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.

Background
Our definitions follow for the most part [Gao08] and [Mon18]. We assume that all structures have universe ω and are relational. Let L be a relational language (R i ) i∈ω where without loss of generality R i has arity i. Then each element A of M od(L) can be viewed as an element of the product space The Turing degree of a structure A is the degree of D(A). We will in general not distinguish between a structure as an element of M od(L) and its atomic diagram  Assume X is ω and that (A i ) i∈ω is a computable enumeration of all partial computable L structures. Then R is computably reducible to S if f is a computable function.
We say that a equivalence relation (quasi-order) R ∈ Γ is a Γ complete equivalence relation (quasi-order) for a complexity class Γ with respect to x-reducibility if all equivalence relations (quasi-orders) in Γ 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 Σ 1 1 complete with respect to computable reducibility, and in [Fok+10] it is shown that isomorphism on graphs is Σ 1 1 complete with respect to computable reducibility. This contrasts with Borel reducibility; it is well known that isomorphism on graphs is not Σ Σ Σ 1 1 complete.

Elementary bi-embeddability is analytic complete
3.1. The reduction from ֒→ G to C . The main idea of the construction is that for any given graph G we replace the edge relation with structures having the property that they are minimal under elementary embeddability. Minimal structures were investigated by Fuhrken [Fuh66] who showed that there is a theory with 2 ℵ0 minimal models, and Shelah [She78] who showed that for every n ≤ ℵ 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 G, if x, y ∈ G and xEy, then we associate a copy of a structure A with the pair (x, y) and otherwise we associate a copy B with (x, y). The structures A and B will be elementary equivalent and minimal.
Before we formally state the reduction let us describe A and 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 ν and unary relation symbols R ν , one for each ν ∈ 2 <ω . Consider the structure where F ν is defined by F ν (σ)(x) = σ(x) + ν(x) mod 2 where we assume that ν(x) = 0 for x ≥ |ν| and R ν (σ) if and only if ν ≺ σ. To prove his result, Shelah showed that the theory of this structure has quantifier eliminiation. LetŜ 0 be the substructure of S generated by0, the constant string of 0's andŜ 1 be the substructure generated by1, the constant string of 1's.
Using Shelah's argument one can show that the theories ofŜ 0 andŜ 1 both have quantifier elimination and are therefore equivalent. Furthermore,Ŝ 0 andŜ 1 are minimal models of T h(S). To see this, let x ∈Ŝ 0 , then x = F ν (0) and in particular,0 = F ν (x) for some ν ∈ 2 <ω . So, the substructure ofŜ 0 generated by x is alreadyŜ 0 .
As we require our structures in C to be of relational syntax we will let S 0 and S 1 be the structures corresponding toŜ 0 , respectivelyŜ 1 , after we replace each F ν by its graph graph Fν . We may of course assume without loss of generality that the universes of S 0 and S 1 are ω and let A = S 0 and B = S 1 .
Let us describe the structures in the class C more formally. The class of structures C consists of all countable structures with universe ω in the language consisting of a unary relation W , binary relations R ν and graph Fν for all ν ∈ 2 <ω , a binary relation N and a ternary relation O. We are now ready to give the function f : G → C witnessing the reduction.
We formally describe how to obtain a structure in C given a graph. Let G be a graph and partition ω into countably many infinite, coinfinite subsets (A i ) i∈ω .

Then
• for every a i ∈ A 0 , W f (G) (a i ) (we will call elements of A 0 the vertices of This finishes the construction of f (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 ֒→ G to C it remains to prove the following.
follows trivially from the construction. Say G ֒→ H by g. We get an induced embeddingĝ defined such that if g : i → j, then g : a i → 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ĝ is elementary. We use Ehrenfeucht-Fraïssé games to verify this claim. Say we are playing on the structures (f (G), g 1 , . . . , g n ) and (f (H), f (g 1 ), . . . , f (g n )). We will call the O-closure of the substructures induced by g 1 , . . . , g n , respectively, f (g 1 ), . . . , 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 y 1 , z 1 , x 1 ) for some y 1 , z 1 ∈ f (H), never mentioned in the play before. Then player II can choose y 2 , z 2 ∈ f (G) never mentioned in the play before and as S 0 ≡ 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 , . . . , g n were arbitrary, the lemma follows.
3.2. Graphs are complete for elementary embeddability. We will show that for every class of structures K, there is a computable reduction K → 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 K is a class of structures in relational language L = R 0 , R 1 , . . . where each R i has arity i. Given A ∈ K, the graph g(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 ∈ A we add a vertex v x and an edge a v x . For every i tuple x 1 , . . . , x i ∈ A we add chains of length i + k for every k, 1 ≤ k ≤ i with common last elements y. We add an edge v x k y 1 only if y 1 is the first element of the chain of length of i + k.
If A |= R i (x 1 , . . . , x i ) we add an edge y b and otherwise add an edge y c. This finishes the construction. See Fig. 1 for an example.

Proof. (⇒). Assume that A B and that A is an elementary substructure of B.
We may also assume without loss of generality that g(A) ⊆ g(B). We will show that for all n ∈ ω and any a ∈ g(A) <ω player II has a winning strategy for the n turn Ehrenfeucht Fraïssé game G n ((g(A), a), (g(B), a)). Assume that n is the least such that player II has no winning strategy for G n ((g(A), a), (g(B), a)). Then either there is v ∈ g(A) n such that for all u ∈ g(B) n a, v g(A) ∼ = a, u g(B) or there is u ∈ g(B) n such that for all v ∈ g(B) n a, u g(B) ∼ = a, v g(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 au is in a substructure of g(B) coding a finite substructure of B in a finite part L 1 of the language of B. Extend a, u g(B) so that it codes such a substructure B 1 of B. Now consider the conjunction ϕ of atomic formulas or negations thereof true of B 1 in L 1 . Let a ′ be the elements in B 1 ∩ A and u ′ the elements in B 1 \ A. Then B |= ϕ(a ′ , u ′ ) and Tarski-Vaught gives us elements v ′ in A such that A |= ϕ(a ′ , v ′ ). It follows that we have a partial isomorphism between a ′ , u ′ B and a ′ , v ′ A in L 1 . This induces an isomorphism between the subgraph coding B 1 and the subgraph coding a ′ , v ′ A . But a, u g(B) is a subgraph of the graph coding B 1 and thus it is isomorphic to a substructure a, v g(A) of the structure coding a ′ , v ′ A , a contradiction.
(⇐). An easy induction on the quantifier depth of formulas in L shows that for every A ∈ K and L-formula ϕ with n-free variables the set , a 1 , . . . , a n ) |= ϕ(a 1 , . . . , a n )} is definable in g(A). Now, assume that g(A) g(B) and without loss of generality that g(A) is an elementary substructure of g(B). Let g B : B → g(B) be defined by To see that this embedding is elementary assume that (A, a) |= ϕ, thenvā ∈ D A ϕ and by elementarityvā ∈ D B ϕ . So, (B, g −1 B (vā)) |= ϕ(g −1 B (vā)).
Concatenating the reductions f and g and from the fact that ֒→ G , ≈ G are complete Σ Σ Σ 1 1 quasi-orders, respectively equivalence relations we obtain Theorem 1.

Degree spectra
In this section we finish the proof of Theorem 2. It is easy to see that the two reductions f : G → C and g : C → G are computable. To relate the family of degree spectra realized by ≈ G and ≅ G we need a few more definitions.
Definition 4 (cf. [Har+17;Mil+18]). Let C and D be categories. A computable functor between C and D is a pair of computable operators (Φ, Φ * ) such that Computable functors preserve many computability theoretic properties. Recall We have in particular that if F : (C, 1 ) → (D, 2 ) is a computable functor and ∼ 1 , ∼ 2 are the symmetric closure of 1 , and 2 , respectively, then for all A ∈ C It is an easy exercise to see that g •f induces a computable functor H : (G, ֒→) → (G, ) and thus for all G ∈ G, DgSp ≈ (H(G)) ≤ s DgSp ≅ (G).
To get that every degree spectrum realized in C is also realized in D we need a stronger notion of reducibility. The following notion is central to it.

Definition 5 ([Har+17]
). A functor F : C → D is effectively isomorphic to G : C → D if there is a Turing operator Λ such that for every A ∈ C Λ A is an isomorphism from F (A) to G(A), and the following diagram commutes for all A, B ∈ C and every morphism γ : A → B.
there is a computable functor F : C → D and a computable functor G : D ⊇D → C whereD is the symmetric closure of F (C), F • G is effectively isomorphic to IdD, and G • F is effectively isomorphic to Id C .
Proposition 6. If (C, 1 ) ≤ CBF (D, 1 ), then every set realized as a ∼ 1 -spectrum in C is realized as a ∼ 2 -spectrum in D.
Definition 7. A class of structures C is CBF-complete with respect to an equivalence relation if for every class K, (K, ∼) ≤ CBF (C, ∼).
For any class K equipped with the elementary embeddability relation by Section 3.2 there is a computable reduction g from (K, ) to (G, ). 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 K. It is clear from the construction that g induces a computable functor F : (K, ≅) → (G, ≅). We have to show that F (K) is closed under elementary bi-embeddability and that there is a functor G : We may assume without loss of generality that G is an elementary substructure of F (A). For everyā ∈ G <ω , tp G (ā) = tp A (ā). Thus G must contain the elements a, b, c of F (A) with unique 3, respectively, 5 and 7 cycles connected to them. Furthermore, sayā ∈ G codes elements of A in F (A) such that A |= R i (ā), then this information must also be coded in G as it is preserved in the type ofā. We can compute a structure G(G) as follows. Fix a G computable enumeration f of the set {x : a x}. Notice that this can be done uniformly since the set {x : a x} is uniformly computable in all structures in F (K). Then for all To finish the construction of G and showing that GF and F G are effectively isomorphic to the identities on K and G, respectively, first note that G(F (A)) ∼ = A. There is a canonic isomorphism given by the composition of the maps a → v a and the enumeration f of the set {x : a x}, i.e., the isomorphism is defined by a → f −1 (v a ). It is clearly uniformly computable, say by Λ K . On the other hand let GinF (K), then we can compute an isomorphism between F (G(G)) and G by doing the following.
Every v ∈ 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(G)). In the first case, we have to find the tuple w such that v is involved in the coding of the relation R i onw. We then map v to the corresponding element in the coding of R i on the tuple v f − 1(w) . It is easy to see that one can define a Turing operator Λ F(K) computing this isomorphism. The Turing operators Λ F(K) and Λ K will witness the effective isomorphism between F G and the identity on F (K), respectively, the effective isomorphism between GF and the identity on G.
It remains to show that G(G) ≅ A, how to compute embeddings and that the diagram in Definition 5 commutes. To see the former just notice that F (G(G)) ∼ = G and since G ≅ F (A) we get that F (G(G)) ≅ F (A). That G(G) ≅ A now follows directly from Lemma 5. Given an elementary embedding ν : G 1 → G 2 G(ν) can be computed in exactly the same fashion as Λ 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 C given in Section 3.1 we can not deduce that (G, ≈) ≤ UCT (C, ≅). However, we can still establish a relationship between the degree spectra in these classes.
Proof. As X is ∆ 0 2 there is an X-computable two valued function f such that Define a structure C as follows. Fix an enumeration g of 2 <ω . At stage 0 define 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 C s . At stage s + 1 we look at f (i, j) for j < s and define C s+1 as if a was the finite string with a(j) = f (j) for j < s. To be more precise: (1) For all k, if k ≤ s and |g(k)| ≤ s then let R g(k) (a) if and only if g(k) a, and if F g(k) (a) has not been defined yet add a new element and set F g(k) (a).
(2) We may assume by induction that for all elements b in C s+1 there is k ≤ s such that b = F g(k) (a). We set R g(l) (b) respecting this equation for all l ≤ s.
It is easy to see that this procedure yields a computable sequence of structures C s with C s ⊆ C s+1 and a computable structure as its limit. We let C be this structure. Lemma 9. For every structure G ∈ G there is A ∈ C such that Proof. Recall the reduction from embeddability on graphs to elementary embeddability on C given in Section 3.1. It is easy to see that it induces a computable functor F : (G, ≈) → (C, ≅). We show that the functor has a pseudo-inverse G on the ≅-saturation of F (G) and then use Lemma 8 to obtain the lemma. The minimality of the submodels S used in the construction of F will play a crucial role in the proof. 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 biembeddability on graphs and elementary bi-embeddability on graphs. We thus ask.

Question 1. Is every bi-embeddability spectrum of a graph the elementary biembeddability 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 ′ = {x ′ : x ∈ 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 ′ the elementary bi-embeddability spectrum of a graph?
Question 3. Let X be the theory spectrum of a graph. Is X ′ the theory spectrum of a graph?