[proofplan] We prove the equivalence by comparing the three numerical defects: Gromov-Hausdorff distance, approximation error, and correspondence distortion. A small Hausdorff realisation of $X_j$ and $Y$ in one [metric space](/page/Metric%20Space) gives nearest-point maps with small distortion and dense image. Conversely, an $\varepsilon$-approximation defines a glued metric on the disjoint union $X\sqcup Y$ for which the two copies have Hausdorff distance at most $\varepsilon$. Finally, $\varepsilon$-approximations and correspondences convert into one another with distortion tending to zero. [/proofplan]

[step:Extract small approximations from a small Hausdorff realisation] Let $(X,d_X)$ and $(Y,d_Y)$ be compact metric spaces, and suppose $d_{GH}(X,Y)<\delta$ for some $\delta>0$. By the definition of the [Gromov-Hausdorff distance](/page/Gromov-Hausdorff%20Distance) $d_{GH}$, there is a metric $\rho$ on the disjoint union $X\sqcup Y$ such that $\rho|_{X\times X}=d_X$, $\rho|_{Y\times Y}=d_Y$, and \begin{align*} d_H^\rho(X,Y)<\delta. \end{align*} Here $d_H^\rho$ denotes the Hausdorff distance between subsets of the metric space $(X\sqcup Y,\rho)$, defined for non-empty subsets $A,B\subset X\sqcup Y$ by \begin{align*} d_H^\rho(A,B) := \max\left\{ \sup_{a\in A}\inf_{b\in B}\rho(a,b), \sup_{b\in B}\inf_{a\in A}\rho(a,b) \right\}. \end{align*} For each $x\in X$, choose $f(x)\in Y$ such that $\rho(x,f(x))<\delta$. This defines a map \begin{align*} f:X&\to Y. \end{align*} For $x,x'\in X$, the triangle inequality in $(X\sqcup Y,\rho)$ gives \begin{align*} d_Y(f(x),f(x')) &=\rho(f(x),f(x')) \\ &\leq \rho(f(x),x)+\rho(x,x')+\rho(x',f(x')) \\ &< d_X(x,x')+2\delta, \end{align*} and also \begin{align*} d_X(x,x') &=\rho(x,x') \\ &\leq \rho(x,f(x))+\rho(f(x),f(x'))+\rho(f(x'),x') \\ &< d_Y(f(x),f(x'))+2\delta. \end{align*} Hence $\operatorname{dis}(f)\leq 2\delta$. If $y\in Y$, choose $x\in X$ with $\rho(y,x)<\delta$. Then \begin{align*} d_Y(y,f(x)) =\rho(y,f(x)) \leq \rho(y,x)+\rho(x,f(x)) <2\delta. \end{align*} Thus $f$ is a $2\delta$-approximation. Applying this with $\delta_j>d_{GH}(X_j,Y)$ and $\delta_j\to 0$ proves that $d_{GH}(X_j,Y)\to 0$ implies the existence of $\varepsilon_j$-approximations $f_j:X_j\to Y$ with $\varepsilon_j\to 0$. [/step]

[step:Glue an approximation into a common metric space]Assume that $f:X\to Y$ is an $\varepsilon$-approximation between compact metric spaces $(X,d_X)$ and $(Y,d_Y)$, where $\varepsilon>0$. Define a function \begin{align*} \rho:(X\sqcup Y)\times (X\sqcup Y)&\to [0,\infty) \end{align*} as follows: \begin{align*} \rho(x,x')&:=d_X(x,x') &&\text{for }x,x'\in X,\\ \rho(y,y')&:=d_Y(y,y') &&\text{for }y,y'\in Y,\\ \rho(x,y)&:=\inf_{a\in X}\left\{d_X(x,a)+\varepsilon+d_Y(f(a),y)\right\} &&\text{for }x\in X,\ y\in Y,\\ \rho(y,x)&:=\rho(x,y) &&\text{for }x\in X,\ y\in Y. \end{align*} The function $\rho$ is symmetric, non-negative, restricts to the original metrics, and separates points because every mixed distance is at least $\varepsilon$. It remains to check the triangle inequality for mixed triples. Let $x,x'\in X$ and $y\in Y$. For arbitrary $a,b\in X$, the distortion bound for $f$ gives \begin{align*} d_X(a,b) \leq d_Y(f(a),f(b))+\varepsilon. \end{align*} Therefore \begin{align*} d_X(x,x') &\leq d_X(x,a)+d_X(a,b)+d_X(b,x')\\ &\leq d_X(x,a)+d_Y(f(a),f(b))+\varepsilon+d_X(b,x')\\ &\leq d_X(x,a)+d_Y(f(a),y)+d_Y(y,f(b))+\varepsilon+d_X(b,x')\\ &\leq \left[d_X(x,a)+\varepsilon+d_Y(f(a),y)\right] +\left[d_X(x',b)+\varepsilon+d_Y(f(b),y)\right]. \end{align*} Taking the infimum over $a,b\in X$ yields \begin{align*} \rho(x,x')\leq \rho(x,y)+\rho(y,x'). \end{align*} The inequalities \begin{align*} \rho(x,y)\leq d_X(x,x')+\rho(x',y) \end{align*} and \begin{align*} \rho(x,y)\leq \rho(x,y')+d_Y(y',y) \end{align*} follow directly from the defining infimum and the triangle inequalities in $X$ and $Y$. Thus $\rho$ is a metric on $X\sqcup Y$. For each $x\in X$, \begin{align*} \rho(x,f(x))\leq d_X(x,x)+\varepsilon+d_Y(f(x),f(x))=\varepsilon. \end{align*} Since $f(X)$ is $\varepsilon$-dense in $Y$, for every $y\in Y$ there exists $x\in X$ with $d_Y(f(x),y)<\varepsilon$, and hence \begin{align*} \rho(x,y)\leq \varepsilon+d_Y(f(x),y)<2\varepsilon. \end{align*} Therefore \begin{align*} d_H^\rho(X,Y)\leq 2\varepsilon. \end{align*} By the definition of the [Gromov-Hausdorff distance](/page/Gromov-Hausdorff%20Distance) $d_{GH}$, \begin{align*} d_{GH}(X,Y)\leq 2\varepsilon. \end{align*}[/step]

[guided]The goal is to turn the approximate map $f:X\to Y$ into an actual ambient metric in which the two spaces are close. The cross-distance from $x\in X$ to $y\in Y$ is defined by allowing travel inside $X$ to some point $a$, paying the bridge cost $\varepsilon$, and then travelling inside $Y$ from $f(a)$ to $y$: \begin{align*} \rho(x,y) := \inf_{a\in X} \left\{ d_X(x,a)+\varepsilon+d_Y(f(a),y) \right\}. \end{align*} The restrictions $\rho|_{X\times X}=d_X$ and $\rho|_{Y\times Y}=d_Y$ are imposed by definition, and symmetry is imposed by setting $\rho(y,x)=\rho(x,y)$. The only non-formal point is the triangle inequality. Triangles entirely inside $X$ or entirely inside $Y$ are exactly the triangle inequalities for $d_X$ and $d_Y$. For a triangle with two points $x,x'\in X$ and one point $y\in Y$, we must prove \begin{align*} d_X(x,x')\leq \rho(x,y)+\rho(y,x'). \end{align*} Choose arbitrary comparison points $a,b\in X$. Since $f$ has distortion at most $\varepsilon$, we have \begin{align*} d_X(a,b) \leq d_Y(f(a),f(b))+\varepsilon. \end{align*} Using the triangle inequality first in $X$, then the distortion bound, and then the triangle inequality in $Y$, we obtain \begin{align*} d_X(x,x') &\leq d_X(x,a)+d_X(a,b)+d_X(b,x')\\ &\leq d_X(x,a)+d_Y(f(a),f(b))+\varepsilon+d_X(b,x')\\ &\leq d_X(x,a)+d_Y(f(a),y)+d_Y(y,f(b))+\varepsilon+d_X(b,x')\\ &\leq \left[d_X(x,a)+\varepsilon+d_Y(f(a),y)\right] + \left[d_X(x',b)+\varepsilon+d_Y(f(b),y)\right]. \end{align*} Because this holds for every $a,b\in X$, taking the infimum over both variables gives the desired mixed triangle inequality. The other mixed triangle inequalities are built into the infimum formula. For example, if $x,x'\in X$ and $y\in Y$, then for every $a\in X$, \begin{align*} \rho(x,y) &\leq d_X(x,a)+\varepsilon+d_Y(f(a),y)\\ &\leq d_X(x,x')+d_X(x',a)+\varepsilon+d_Y(f(a),y). \end{align*} Taking the infimum over $a\in X$ gives \begin{align*} \rho(x,y)\leq d_X(x,x')+\rho(x',y). \end{align*} Similarly, if $x\in X$ and $y,y'\in Y$, then for every $a\in X$, \begin{align*} \rho(x,y) &\leq d_X(x,a)+\varepsilon+d_Y(f(a),y)\\ &\leq d_X(x,a)+\varepsilon+d_Y(f(a),y')+d_Y(y',y), \end{align*} and taking the infimum over $a\in X$ gives \begin{align*} \rho(x,y)\leq \rho(x,y')+d_Y(y',y). \end{align*} Thus $\rho$ is a metric on the disjoint union. Finally, this metric places $X$ close to $Y$. For each $x\in X$, \begin{align*} \rho(x,f(x))\leq \varepsilon. \end{align*} For each $y\in Y$, the $\varepsilon$-density of $f(X)$ gives some $x\in X$ with $d_Y(f(x),y)<\varepsilon$, and therefore \begin{align*} \rho(x,y)\leq \varepsilon+d_Y(f(x),y)<2\varepsilon. \end{align*} Hence \begin{align*} d_H^\rho(X,Y)\leq 2\varepsilon, \end{align*} so \begin{align*} d_{GH}(X,Y)\leq 2\varepsilon. \end{align*}[/guided]

[step:Convert approximations into correspondences] We use the standard definition that a [correspondence](/page/Correspondence) between sets $X$ and $Y$ is a subset $R\subset X\times Y$ whose coordinate projections onto $X$ and onto $Y$ are both surjective. Assume that $f:X\to Y$ is an $\varepsilon$-approximation. Define \begin{align*} R_f:=\{(x,y)\in X\times Y: d_Y(f(x),y)<\varepsilon\}. \end{align*} For every $x\in X$, the pair $(x,f(x))$ belongs to $R_f$. For every $y\in Y$, the $\varepsilon$-density of $f(X)$ gives $x\in X$ with $(x,y)\in R_f$. Hence $R_f$ is a correspondence. Let $(x,y),(x',y')\in R_f$. Then \begin{align*} d_Y(y,y') &\leq d_Y(y,f(x))+d_Y(f(x),f(x'))+d_Y(f(x'),y')\\ &<\varepsilon+\left(d_X(x,x')+\varepsilon\right)+\varepsilon\\ &=d_X(x,x')+3\varepsilon, \end{align*} and also \begin{align*} d_X(x,x') &\leq d_Y(f(x),f(x'))+\varepsilon\\ &\leq d_Y(f(x),y)+d_Y(y,y')+d_Y(y',f(x'))+\varepsilon\\ &<d_Y(y,y')+3\varepsilon. \end{align*} Thus \begin{align*} \operatorname{dis}(R_f)\leq 3\varepsilon. \end{align*} Consequently, if $\varepsilon_j$-approximations $f_j:X_j\to Y$ exist with $\varepsilon_j\to 0$, then the correspondences $R_{f_j}\subset X_j\times Y$ satisfy $\operatorname{dis}(R_{f_j})\to 0$. [/step]

[step:Convert correspondences into approximations] Let $R\subset X\times Y$ be a correspondence with $\operatorname{dis}(R)=\eta$, and let $\alpha>0$ be arbitrary. For each $x\in X$, choose one point $f(x)\in Y$ such that $(x,f(x))\in R$. This defines a map \begin{align*} f:X&\to Y. \end{align*} For $x,x'\in X$, the pairs $(x,f(x))$ and $(x',f(x'))$ lie in $R$, so \begin{align*} \left|d_X(x,x')-d_Y(f(x),f(x'))\right|\leq \eta<\eta+\alpha. \end{align*} Thus $\operatorname{dis}(f)\leq \eta<\eta+\alpha$. Since $R$ projects onto $Y$, for every $y\in Y$ there exists $x\in X$ such that $(x,y)\in R$. Comparing $(x,y)$ and $(x,f(x))$ in $R$ gives \begin{align*} d_Y(y,f(x)) = \left|d_Y(y,f(x))-d_X(x,x)\right| \leq \eta<\eta+\alpha. \end{align*} Therefore every point of $Y$ lies in an open $d_Y$-ball of radius $\eta+\alpha$ centred at a point of $f(X)$, and $f$ is an $(\eta+\alpha)$-approximation. Hence, if correspondences $R_j\subset X_j\times Y$ satisfy $\operatorname{dis}(R_j)\to 0$, then taking $\alpha_j:=1/j$ and $\varepsilon_j:=\operatorname{dis}(R_j)+\alpha_j$ yields $\varepsilon_j$-approximations $f_j:X_j\to Y$ with $\varepsilon_j\to 0$. [/step]

[step:Assemble the three equivalences] The first step proves \begin{align*} d_{GH}(X_j,Y)\to 0 \implies \text{there exist }\varepsilon_j\text{-approximations }f_j:X_j\to Y\text{ with }\varepsilon_j\to 0. \end{align*} The second step proves the reverse implication from such approximations to $d_{GH}(X_j,Y)\to 0$. The third step proves that approximations with error tending to zero produce correspondences with distortion tending to zero, and the fourth step proves that correspondences with distortion tending to zero produce approximations with error tending to zero. Therefore all three stated conditions are equivalent. [/step]