Computability Seminar MSRI program on DDC-Degree spectra of analytic complete equivalence relations

Organizer: V. Harizanov

For link contact [email protected]

Thursday, December 3, 12:00-1:00 ET on Zoom

Speaker: Dino Rossegger, University of Waterloo, Canada

Title: Degree spectra of analytic complete equivalence relations

Abstract: We present new results on the complexity of the classification problem of countable structures and their computational complexity. We show that the elementary bi-embeddability relation on the class of graphs is analytic complete under Borel reducibility by giving a reduction from the bi-embeddability relation on graphs. We then compare the degree spectra with respect to these equivalence relations. The degree spectrum of a countable structure with respect to an equivalence relation E is the set of Turing degrees of structures E-equivalent to it. We show that the degree spectra of structures with respect to bi-embeddability and elementary bi-embeddability are related: Every bi-embeddability spectrum of a graph is the set of jumps of Turing degrees in the elementary bi-embeddability spectrum of a graph.