Effective embeddings and interpretations

Abstract: Friedman and Stanley introduced Borel embeddings as a way of comparing classification problems for different classes of structures. Many Borel embeddings are actually Turing computable. The effective decoding is given by a uniform effective interpretation. Part of the effective interpretation is actually Medvedev reduction. The class of undirected graphs and the class of linear orderings both lie on top under Turing computable embeddings. We give examples of graphs that are not Medvedev reducible to any linear ordering, or to the jump of any linear ordering. For any graph, there is a linear ordering, that the graph is Medvedev reducible to the second jump of the linear ordering. Friedman and Stanley gave a Turing computable embedding $L$ of directed graphs in linear orderings. We show that there do not exist $L_{\omega_1\omega}$-formulas that uniformly interpret the input graph $G$ in the output linear ordering $L(G)$. This is joint work with Knight, and Vatev.

We have also one positive result --- we prove that the class of fields is uniformly effectively interpreted without parameters in the class of Heisenberg groups. The second part is joint work with Alvir, Calvert, Goodman, Harizanov, Knight, Miller, Morozov, and Weisshaar.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.