Logic Seminar

Please note that the time is PST

In this talk, we will show that elementary bi-embeddability is an analytic complete equivalence relation under Borel reducibility by giving a reduction from the bi-embeddability relation on graphs. We will then discuss the degree spectra realized by these relations. The degree spectrum of a countable structure with respect to an equivalence relation E, a central notion in computable structure theory, is the set of Turing degrees of structures E-equivalent to it. By analyzing the computability theoretic properties of our reduction from bi-embeddability to elementary bi-embeddability we show that the degree spectra of these two relations are related. Suppose a set of Turing degrees X is the bi-embeddability spectrum of a graph. Then the set of degrees whose Turing jump is in X is the elementary bi-embeddability spectrum of a graph. Combining results of Harrison-Trainor and the coauthor one sees that this is sharp: There is a bi-embedddability spectrum that is not an elementary bi-embeddability spectrum.