Coding in graphs and linear orderings

Abstract

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 Montalbán have also shown this, by a quite different proof.

Accepted in JSL