Seminar

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

There are several ways to code the information of one structure into another. Friedman and Stanley introduced Borel embeddings as a way of comparing classification problems for different classes of structures. A Borel embedding of a class K in a class K’ represents a uniform procedure for coding structures from K in structures from K’. Many Borel embeddings are actually Turing computable. When a structure A is coded in a structure B, effective decoding is represented by a Medvedev reduction of A to B. Harrison-Trainor, Melnikov, Miller, and Montalba’n defined a notion of an effective interpretation of A in B and proved that this is equivalent with the existence of a computable functor, i.e., a pair of Turing operators, one taking copies of B to copies of A, and the other taking isomorphisms between copies of B to isomorphisms between the corresponding copies of A. The first operator gives a Medvedev reduction.

The class of undirected graphs and the class of linear orderings both lie “on top” under Turing computable embeddings. The standard Turing computable embeddings of directed graphs (or structures for an arbitrary computable relational language) in undirected graphs come with uniform effective interpretations. We give examples of graphs that are not Medvedev reducible to any linear ordering, or to the jump of any linear ordering. Any graph can be interpreted in a linear ordering using computable Sigma_3 formulas. 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 J. Knight and S. Vatev.

Notes 249 KB application/pdf

Effective Coding And Decoding In Classes Of Structures