Logic Seminar
Dino Rossegger
University of Waterloo
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.
Tuesday February 16, 2021 at 4:00 PM in Zoom