Caltech Logo

Logic Seminar

Wednesday, November 2, 2022
11:00am to 12:00pm
Add to Cal
Online Event
Analytic complete equivalence relations and their degree spectra
Dino Rossegger, Department of Mathematics, UC Berkeley,

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.

For more information, please contact Math Dept. by phone at 626-395-4335 or by email at A. Kechris at [email protected].