There is a Turing computable embedding $Phi$ of directed graphs $A$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform interpretation; i.e., for all directed graphs $A$, these formulas interpret $A$ in $Phi(G)$. It follows that A is Medvedev reducible to $Phi(A)$ uniformly; i.e., there is a fixed Turing operator that serves for all $A$. We observe that there is a graph $G$ that is not Medvedev reducible to any linear ordering. Hence, $G$ is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $Sigma_2$ formulas. 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 is no fixed tuple of $L_{omega_1,omega}$ formulas that, for all $G$, interpret the input graph $G$ in the output linear ordering $L(G)$. Harrison-Trainor and Montalban have also shown this, by a quite different proof.
Download