Logo

Mathematical Sciences Research Institute

Home » DDC - Computability Theory: Degree spectra of analytic complete equivalence relations

Seminar

DDC - Computability Theory: Degree spectra of analytic complete equivalence relations December 03, 2020 (09:00 AM PST - 10:00 AM PST)
Parent Program:
Location: MSRI: Online/Virtual
Speaker(s) Dino Rossegger (University of Waterloo)
Description

Hilbert’s Tenth Problem was the only decision problem among his twenty-three problems. Precise mathematical theory of (in)computability and its interaction with number theory led to the negative solution of the problem. The seminar will focus on modern topics on computability-theoretic phenomena in number-theoretic and other algebraic and model-theoretic structures.

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

 

Video

Degree Spectra Of Analytic Complete Equivalence Relations

Abstract/Media

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

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.

Asset no preview Slides 165 KB application/pdf

Degree Spectra Of Analytic Complete Equivalence Relations

H.264 Video 25197_28695_8670_Degree_Spectra_of_Analytic_Complete_Equivalence_Relations.mp4