April 12
Julia Knight, University of Notre Dame
Coding structures

A Turing computable embedding is a Turing operator that maps one class of structures to another so as to preserve isomorphism. The embedding codes the input structure in the output structure. It is interesting when there is an effective decoding. It is also interesting when the decoding is very difficult. Recently, Harrison-Trainor, Melnikov, R. Miller, and Montalbán have defined very general notions of interpretation, in which the interpreting formulas have no fixed arity. Uniformly defined interpretations give us decoding. I will discuss some known Turing computable embeddings, looking for uniform interpretations that yield effective, or Borel, decoding.

  1. Marker's embedding of directed graphs in undirected graphs,
  2. Mal'tsev's embedding of fields in groups,
  3. Friedman and Stanley's embedding of graphs in linear orderings.
The first two embeddings come with uniform 'effective' interpretations, which give uniform effective decoding. For the third, we do not even have uniform interpretation via $L_{\omega_1\omega}$ formulas.