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 countable 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 ω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 ω + 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 countable graph isomorphism
On isometry and isometric embeddability between ultrametric Polish spaces
Riccardo Camerlo;
2018-01-01
Abstract
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 countable 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 ω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 ω + 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 countable graph isomorphismFile | Dimensione | Formato | |
---|---|---|---|
1412.6659.pdf
accesso aperto
Tipologia:
Documento in Pre-print
Dimensione
623.83 kB
Formato
Adobe PDF
|
623.83 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.