Given \(n\)-ary analytic relations \(R\) and \(R'\) on Polish spaces \(X\) and \(X'\), say that \(R\) is Borel reducible to \(R'\) if there is a Borel measurable function \(f: X \to X'\) such that \(R(x_1,\dots, x_n)\) and \(R' (f(x_1), \dots,f(x_n))\) are equivalent for all \(x_1,\dots, x_n\) in \(X\). They are Borel equivalent if each is Borel reducible to the other. \(R\) is complete if any \(n\)-ary analytic relation is Borel reducible to \(R\). Borel reducibility measures complexity of analytic relations. A. Louveau and C. Rosendal [Trans. Am. Math. Soc. 357, No. 12, 4839–4866 (2005; Zbl 1118.03043)] have proved that embeddability of countable graphs is a complete analytic quasi-order.
The authors strengthen the result of Louveau and Rosendal by proving that in fact every analytic quasi-order \(R\) is Borel equivalent to embeddability of countable graphs restricted to a class of graphs satisfying a certain sentence in the language \({\mathcal L}_{\omega_1 \omega}\) corresponding to \(R\). As a consequence, an analogous result holds for analytic equivalence relations and bi-embeddability of countable graphs. This result (and the techniques introduced to prove it) shed new light on the relationship between bi-embeddability and isomorphism on the class of countable models of \({\mathcal L}_{\omega_1 \omega}\)-sentences. The authors also prove that every analytic quasi-order is Borel equivalent to isometric embeddability of a Borel class of discrete Polish spaces or ultrametric Polish spaces, and, similarly, to continuous embeddability of a Borel class of compact metrizable spaces, as well as to linear isometric embeddability of a Borel class of separable Banach spaces isomorphic to \(c_0\).