On isometry and isometric embeddability between metric and ultrametric Polish spaces

We study the complexity with respect to Borel reducibility of the relations of isometry and isometric embeddability between ultrametric Polish spaces for which a set $D$ of possible distances is fixed in advance. These are, respectively, an analytic equivalence relation and an analytic quasi-order and we show that their complexity depends only on the order type of $D$. When $D$ contains a decreasing sequence, isometry is Borel bireducible with graph isomorphism and isometric embeddability has maximal complexity among analytic quasi-orders. If $D$ is well-ordered the situation is more complex: for isometry we have an increasing sequence of Borel equivalence relations of length $\omega_1$ which are cofinal among Borel equivalence relations classifiable by countable structures, while for isometric embeddability we have an increasing sequence of analytic quasi-orders of length at least $\omega+3$. We then apply our results to solve various open problems in the literature. For instance, we answer a long-standing question of Gao and Kechris by showing that the relation of isometry on locally compact ultrametric Polish spaces is Borel bireducible with graph isomorphism. Finally, we show how to apply our machinery to the study of isometry and isometric embeddability on arbitrary Polish metric spaces and we give a fairly complete description of the complexity of these relations restricted to spaces realizing any given set of distances.