Dino Rossegger, Pure Math Department, University of Waterloo
"Analytic complete equivalence relations and their degree spectra"
A well known result in descriptive set theory by Louveau and Rosendal shows that the bi-embeddability relation on the class of graphs is an analytic complete equivalence relation with respect to Borel reducibility. We give a Borel reduction from bi-embeddability on graphs to elementary bi-embeddability on graphs and thus obtain that elementary bi-embeddability on graphs is also analytic complete. An analysis of this reduction shows that it is computable, i.e., can be realized by a Turing operator, and that it is faithful on equivalence classes. These facts let us obtain results on the relationship between the degree spectra under these equivalence relations, i.e., the sets of Turing degrees of the bi-embeddable, respectively, elementary bi-embeddable copies of a given structure. They also motivate the study of a new type of reduction which allows us to study the relationship between degree spectra relative to different equivalence relations and in different classes of structures.
MC 5413