9
$\begingroup$

This question occurred to me while I was writing my most recent answer.

Recall that given an extended metric space $(X,d)$ the hyperspace of $X$, which I'll write as $\def\Hc{\mathcal{H}}\Hc(X)$, is the set of non-empty closed subsets of $X$ endowed with the Hausdorff metric. (Often in the literature there is an additional restriction that $\Hc(X)$ only consists of the compact or at least bounded sets, which in particular ensures that $\Hc(X)$ is a metric space (rather than just an extended metric space) when $X$ is a metric space, but I'd be surprised if that changed the answer of this question.) I'm going to be writing $\Hc^n(X)$ for the $n$-th iterated hyperspace of $X$ (e.g., $\Hc^3(X) = \Hc(\Hc(\Hc(X)))$).

As I mentioned in my linked answer, the Kuratowski pair map $\langle x, y\rangle \mapsto \{\{x\},\{x,y\}\}$ yields a $1$-Lipschitz embedding of $X^2$ (with the $\max$ metric) into $\Hc(\Hc(X))$ for any metric space $X$. This isn't an isometric embedding, however, as the inverse is only guaranteed to be $3$-Lipschitz (which is sharp in the specific case of $X= \mathbb{R}$ with the pairs $\langle 2,0\rangle$ and $\langle 1, 3\rangle$).

If you tweak the definition of hyperspace to allow $\varnothing$ as an element, then it is possible to get an isometric embedding. Specifically, let $\Hc_\varnothing(X)$ be the set of all closed subsets of $X$ endowed with the Hausdorff metric (with the understanding that $d_H(\varnothing,A) = \infty$ for any non-empty $A \subseteq X$). It's now relatively easy to show that the Wiener's older definition of ordered pair $\langle x, y \rangle := \{\{\{x\},\varnothing\},\{\{y\}\}\}$ gives an isometric embedding of $X^2$ into $\Hc^3_\varnothing(X)$.

It seems like this kind of embedding really needs the guaranteed separation of $d_H(\varnothing,A) = \infty$ to be isometric, which leads me to my questions.

Question 1. Is it true that for every extended metric space $X$, there is an $n$ such that $X^2$ (with the $\max$ metric) isometrically embeds into $\Hc^n(X)$?

It seems pretty likely that if this is possible, it will be because of a uniform construction, so it's natural to wonder how uniform it can be.

Note that in the category of extended metric spaces with $1$-Lipschitz maps, $X \mapsto \Hc(X)$ can be regarded as a covariant functor (specifically by taking $f : X \to Y$ to the map $\Hc(f) : \Hc(X) \to \Hc(Y)$ defined by $\Hc(f)(A) = \overline{f[A]}$, where $\overline{f[A]}$ is the closure of the image of $A$ under $f$). Likewise the Cartesian square construction is functorial (taking $f: A \to B$ to $g : A^2 \to B^2$ defined by $g(\langle x,y \rangle) = \langle f(x),f(y)\rangle$). Finally, it's fairly easy to see that the Kuratowski pair map is a natural transformation from $X \mapsto X^2$ to $X \mapsto \Hc^2(X)$ (and, for that matter, the Wiener pair map is a natural transformation from $X \mapsto X^2$ to $X \mapsto \Hc^3_\varnothing(X)$, which is also functorial).

Question 2. Is there an $n$ and a natural transformation $\eta$ from $X \mapsto X^2$ to $X \mapsto \Hc^n(X)$ such that for every extended metric space $X$, $\eta_X : X^2 \to \Hc^n(X)$ is an isometric embedding?

$\endgroup$
1
  • $\begingroup$ As an aside, I find it interesting that the same issue of needing to use the Wiener pair over the Kuratowski pair also occurs in the development of univalent material set theory. $\endgroup$ Commented Jun 12 at 20:24

1 Answer 1

5
$\begingroup$

Yes. Specifically, we use the map $\langle x,y \rangle \mapsto \{\{\{\{x\}\},\{\{x,y\}\}\},\{\{\{y\}\},\{\{x\},\{y\}\}\}\}$, with $n = 4$.

To make it easier to keep track of the alternating $\text{min}$s and $\text{max}$s (well, technically $\text{inf}$s and $\text{sup}$s, but here we're dealing with finite sets so it doesn't make a difference) that arise from iterating the Hausdorff metric, I'm going to be viewing the computation of Hausdorff distance as a game between two players, Maximiser and Minimiser. When computing the distance between two sets $A$ and $B$, Maximiser picks an element of one set, Minimiser picks an element of the other set, and then the game continues from their choices, ending once they have both chosen elements of the underlying space $X$, at which point the result is the distance between the elements. Maximiser aims to maximise this distance, and Minimiser aims to minimise it. The distance between two sets is the result when both players play this game optimally.

(If you would prefer to skip reading the next several paragraphs of rather messy exposition, I also made this page where you can play this game against a program that executes the strategies I'm about to describe).

First we will prove that $d(f(\langle x,y \rangle), f(\langle z,w \rangle)) \leq \text{max}(d(x, z), d(y, w))$, where $f$ is the map I defined above (because I don't want to type the whole thing out again), by giving a strategy for Minimiser. The strategy is actually surprisingly simple: just copy Maximiser's moves, and the game ends at either $d(x, z)$ or $d(y, w)$.

Now the converse: $\text{max}(d(x, z), d(y, w)) \leq d(f(\langle x,y \rangle), f(\langle z,w \rangle))$, by giving a strategy for Maximiser. Our opening move will be in whichever index we want to check, i.e. if we want to show the distance is at least $d(x, z)$ then move to $\{\{\{x\}\}, \{\{x, y\}\}\}$, and if we want $d(y, w)$ then move to $\{\{\{y\}\}, \{\{x\}, \{y\}\}\}$.

If Minimiser moves to the same component, then we move to $\{\{x\}\}$ or $\{\{y\}\}$; if they move to $\{\{z\}\}$ or $\{\{w\}\}$, then we've succeeded, because we got whichever of $d(x, z)$ or $d(y, w)$ we wanted. If they move to $\{\{z, w\}\}$, then after one move we move in $\{z, w\}$ to $z$, and get $d(x, z)$; if they move to $\{\{z\}, \{w\}\}$, then we move to $\{w\}$, and after one move we have $d(y, w)$.

If Minimiser moves to the opposite component, then we move to $\{\{z, w\}\}$ or $\{\{z\}, \{w\}\}$. If they then move to $\{\{x\}\}$, we move to $\{z\}$; if they move to $\{\{y\}\}$, we move to $w$; if they move to $\{\{x, y\}\}$ or $\{\{x\}, \{y\}\}$, then because we're dealing with opposite components, we get to choose whichever of $x$ and $y$ we want and whichever of $z$ and $w$ we want, by always moving in whichever component currently allows a choice.

This completes the proof: $d(f(\langle x,y \rangle), f(\langle z,w \rangle)) = d(\langle x,y \rangle, \langle z,w \rangle)$, so $f$ is an isometric embedding. It is also fairly clear that it is natural, for roughly the same reason that the Kuratowski pair is.

This construction of ordered pairs feels somewhat similar in spirit to the Hausdorff pair, but solves the problem of the tags not being canonical by using $\{\{x,y\}\}$ and $\{\{x\},\{y\}\}$ as tag elements. In terms of the metric, these fill the same role as $\varnothing$ in Wiener's pair; they don't have distance $\infty$ from the other sets we're dealing with, but they have large enough distances that it all ends up working if we're careful.

$\endgroup$
3
  • $\begingroup$ It sort of feels like this proof (and the proof for Wiener's pair) should have some framing as "we can prove in [weak logic] that [appropriate phrasing of 'this construction of ordered pairs actually works'], and [something involving metric spaces] is a model of this logic, therefore it's an isometric embedding", but I'm not really sure what the details would look like. $\endgroup$ Commented Jun 24 at 19:05
  • $\begingroup$ Very nice answer, thanks. $\endgroup$ Commented Jun 24 at 20:37
  • $\begingroup$ I suspect it has to do with substructural logic, actually, since the proof is so straightforward and part of what's happening is that the pair provably works in some kind of system in $[0,1]$-valued Łukasiewicz logic. (This follows from completeness theorems for Łukasiewicz logic.) I don't know if there's a way of framing this in terms of the internal logic of the relevant categories though. $\endgroup$ Commented Jun 24 at 20:38

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.