\newcommand{\N}{\mathbb{N}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Real}{\mathbb{R}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\eps}{\varepsilon}
\newcommand{\Cant}{2^{\Nat}}
\newcommand{\Baire}{\Nat^{\Nat}}
\newcommand{\Ury}{\mathbb{U}}
\newcommand{\Cl}[1]{\overline{#1}}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Lip}{Lip}
Recall that a mapping
that is, an isometry is a mapping that preserves distances. The function
There exists a Polish metric space $\Ury$ such that every Polish metric space isometrically embeds into $\Ury$.
A concrete example of such a space is
:class: tip
Show that the set $\mathcal{C}[0,1]$ of all continuous, real-valued functions on $[0,1]$ with the metric
$$
d(f,g) = \sup\{|f(x) - g(x)| \colon x \in [0,1] \}
$$
contains an isomorphic copy of any Polish metric space.
But this example is not quite what we have in mind here. There exists another space with a stronger, more "intrinsic" universality property. This space was first constructed by Pavel Urysohn in 1927 {cite}Urysohn:1927a.
The construction features an amalgamation principle that has surfaced in other areas like model theory or graph theory.
Suppose
If $Y$ is Polish, then any isometric embedding $e$ of $D$ into $Y$ extends to an isometric embedding $e^*$ of $X$ into $Y$.
Given $z \in X$, let $(x_{i_n})$ be a sequence in $D$ converging to $z$. Since $(x_{i_n})$ converges, it is Cauchy.
$e$ is an isometry, and thus $y_n := e(x_{i_n})$ is Cauchy, and since $Y$ is Polish, $(y_n)$ converges to some $y \in Y$. Put $e^*(z) = y$.
To see that this mapping is well-defined, let $(x_{j_n})$ be another sequence with $x_{j_n} \to z$. Then $d(x_{i_n}, x_{j_n}) \to 0$, and hence $d(e(x_{i_n}),e(x_{j_n}) = d(y_n, e(x_{j_n}))\to 0$, implying $e(x_{j_n}) \to y$.
Furthermore, suppose $w = \lim x_{k_n}$ is another point in $X$. Then (since a metric is a continuous mapping from $Y\times Y \to \Real$)
$$
d(e^*(z), e^*(w)) = \lim d( e(x_{i_n}), e(x_{k_n})) = \lim d( x_{i_n}, x_{k_n}) = d(z,w).
$$
Thus $e^*$ is an isometry.
In order to embed
Suppose we have constructed an isometry
This extension property gives rise to the following definition.
A Polish metric space $(Y,d_Y)$ is **Urysohn universal** if for every finite subspace $F \subset Y$ and any extension $F^* = F \cup \{x^*\}$ with metric a $d^*$ such that
$$
d^*|_{F\times F} = d_Y|_{F\times F},
$$
there exists a point $u \in Y$ such that
$$
d_{Y}(u,x) = d^*(x^*,x) \quad \text{ for all $x \in F$}.
$$
As outlined above, the extension property of Urysohn universal spaces implies the desired isometric embedding property.
:label: prop-Urysohn-embedding
Let $U$ be a Urysohn universal Polish metric space. For any Polish metric space $(X,d)$ there exists an isometric embedding from $X$ into $U$.
But the extension property also implies a strong intrinsic extension property for the Urysohn space itself.
:label: prop-Urysohn-extension
Let $U$ be a Urysohn universal Polish metric space. Every isometry between finite subsets of $\Ury$ extends to an isometry of $U$ onto itself.
The proof applies the Back-and-forth method that you may know from the rationals: every order-isomorphism between finite subsets of
This property (which can be formulated for structures in general) is also known as homogeneity. It plays an important role, for example, in
model theory {cite}Macpherson:2011a and in the topological dynamics of automorphism groups of countable structures {cite}Kechris-Pestov-Todorcevic:2005a.
:class: tip
Show that any two Urysohn universal spaces are isometric.
We will prove the existence of this unique Polish space, which we denote by
We first give a construction of a space that has the extension property, but is not Polish. After that we will take additional steps to turn it into a Polish space.
The crucial idea is to observe that if
is
Let
If
Clearly,
With this metric, the mapping $x \mapsto f_{x}(y) = d(x,y) $ becomes an isometry: We have
By the reverse triangle inequality, this is always
We use this fact as follows: If $X^* = X \sqcup {x^}$ and $d^$ is an extension of
$$ d(f_{x^}, f_x) = d^(x^*,x). $$
Hence
Iterative construction: Let
$X_0$ be any non-empty Polish space with finite diameter$\mathrm{d} > 0$ . Given$X_n$ , let$\mathrm{d}(n) = \diam(X_n)$ and set $X_{n+1} = \Lip^{2\mathrm{d}(n)}1(X_n)$. Finally, put $X\infty = \bigcup_n X_n$. Note that$X_\infty$ inherits a well-defined metric$d$ from the$X_n$ , which embed isometrically into it.
We wan to verify that
Let $X$ be a metric space with $\diam(X) \leq \mathrm d$, $A \subseteq X$, and $f \in \Lip^{\mathrm{d}}_1(A)$, then $f$ can be extended to a $1$-Lipschitz function $f^*$ on all of $X$ such that
$$
f^*|_A = f \quad \text{ and } \quad f^* \in \Lip^{2\mathrm{d}}_1(X).
$$
For each $a \in A$ define $f_a: X \to \Real$ as
$$
f_a(x) = f(a) + d(a,x).
$$
Then $f_a$ is $1$-Lipschitz, by the reverse triangle inequality. Let
$$
f^*(x) = \inf \{f_a(x) \colon a \in A\}.
$$
Then $f^*(a) = f(a)$ for all $a \in A$. Let $x,y \in X$ and $\eps > 0$. Wlog assume $f^*(y) \geq f^*(x)$. Pick $a \in A$ so that $f_a(x) \leq f^*(x) + \eps$. Then
\begin{align*}
|f^*(x) - f^*(y)| = f^*(y) - f^*(x) & \leq f^*(y) - f_a(x) + \eps \\
& \leq f_a(y) - f_a(x) + \eps \leq d(x,y) + \eps.
\end{align*}
Since $\eps > 0$ was arbitrary, we have $|f^*(x) - f^*(y)| \leq d(x,y)$.
Finally, we have $f(a) \leq f_a(x) \leq f(a) + \mathrm{d}$ and thus $0 \leq f^*(x) \leq f_a(x) \leq 2\mathrm{d}$.
(ury-finishing-construction)=
The set
To make
To obtain a complete space, we can pass from
If a complete metric space $(Y,d)$ admits a dense Urysohn universal subspace $\mathcal{U}$, then $Y$ is Urysohn universal.
We follow {cite}`Gromov:1999a`. Let $F = \{x_1, \dots, x_n\} \subset Y$ and assume $F^* = F \sqcup \{x^*\}$ is an extension with metric $d^*$.
We first note that $Y$ is **approximately universal**. This means that for any $\eps > 0$, there exists a point $y^* \in Y$ such that
\begin{equation*} \tag{$*$}
|d(y*,x) - d^*(x^*,x)| < \eps \quad \text{ for all $x \in F$}.
\end{equation*}
This can be seen as follows. Since $\mathcal{U}$ is dense in $Y$, we can find a finite set $F_\eps = \{z_1, \dots, z_n\} \subset \mathcal{U}$ such that
$$
d(x_i, z_i) < \eps \quad \text{ for $1 \leq i \leq n$}.
$$
Now use the Urysohn universality of $\mathcal{U}$ for the set $G^* = \{z_1, \dots , z_n\} \sqcup \{x^*\}$ with the metric
$$
d^{**}(x^*, z_i) = d^*(x^*, x_i) \qquad (i = 1, \dots, n)
$$
to find $z \in \mathcal{U}$ with
$$
d(z,z_i) = d^{**}(x^*,z_i) = d^*(x^*,x_i) \qquad (i = 1, \dots, n)
$$
Then, by the reverse triangle inequality,
$$
\left | d(z,x_i) - d^*(x^*,z_i) \right | = \left | d(z,x_i) - d(z,z_i) \right | \leq d(z_i, x_i) = \eps,
$$
as required.
<!--
To keep the proof technically simple, wlog we assume $\eps$ is much smaller than the individual distances between the $x_i$. Consider the extension $F^*_\eps = F_\eps \sqcup \{x^*\}$ with metric
$$
e^*(x^*, z_i) = d^*(x^*,x_i) + d(x_i,z_i).
$$
Since $\mathcal{U}$ has the finite extension property, we can find $y^* \in \mathcal{U}$ such that
$$
d(y^*,z_i) = e^*(x^*,z_i)
$$
Hence
\begin{align*}
|d(y^*,x_i) - d^*(x^*,x_i)| & = | e^*(x^*,z_i) - d^*(x^*,x_i)| \\
& = | d^*(x^*,x_i) + d(x_i,z_i) - d^*(x^*,x_i) | < \eps.
\end{align*} -->
We use this approximate universality to construct a Cauchy sequence $(y_k)$ in $Y$ of 'approximate' extension points that satisfy $(*)$ for smaller and smaller $\eps$.
Let $0 < \delta = \max \{d^*(x^*,x_i) \colon 1 \leq i \leq n \}$.
The formal requirements for the sequence $(y_i)$ are as follows.
1. $|d(y_k,x_i) - d^*(x^*,x_i)| \leq 2^{-k} \delta$.
2. $d(y_{k+1},y_k) \leq 2^{-k}\delta$.
The sequence necessarily converges in $Y$ and the limit point must be a true extension point, due to (1.)
Suppose we have already constructed $y_1, \dots, y_k$ satisfying (1.), (2.). Add an (abstract) point $y^*_{k+1}$ to $F_k = F \cup \{y_1, \dots, y_k\}$. Let $F^*_{k+1} = F_k \sqcup \{y^*_{k+1}\}$.
We want to use approximate universality on $F^*_{k+1}$. To this end we have to define a metric $e^*$ on $F^*_{k+1}$ that has the following properties
\begin{align*}
(i) \qquad & e^*|_{F_k} = d|_{F_k} \\
(ii) \qquad & e^*(y^*_{k+1},x_i) = d^*(x^*,x_i) \quad (1 \leq i \leq n) \\
(iii) \qquad & e^*(y^*_{k+1}, y_k) = 2^{-k-1}\delta
\end{align*}
Indeed such a metric exists: The condition $(i)$ already defines a metric on the set $F_k$. The conditions $(i)$-$(iii)$ also define a metric on $F \cup \{y_k,y^*_{k+1}\}$ -- the only thing to check for this is the triangle inequality for $y_k, y^*_{k+1}$:
$$
|e^*(x_i,y_k) - e^*(y^*_{k+1},x_i)| = |d(x_i,y_k) - d^*(x^*,x_i) | \leq 2^{-k}\delta = e^*(y_k, y^*_{k+1}),
$$
by (1.). These metrics agree on the set
$$
F_k \cap (F \cup \{y_k,y^*_{k+1}\}) = F \cup \{y_k\}.
$$
Therefore, we can "merge" them to a metric on all of $F^*_{k+1}$ by letting
$$
e^*(y^*_{k+1}, y_j) = \inf \{e^*(y^*_{k+1}, z) + e^*(z,y_j) \colon z \in \{y_1, \dots, y_{k-1}\} \}.
$$
Now choose $\eps < 2^{-k-1}\delta$ and apply approximate universality to $F^*_{k+1}$. This yields a point $y_{k+1} \in Y$ such that
$$
|d(y_{k+1}, z) - e^*(y^*_{k+1}, z) | < 2^{-k-1}\delta
$$
for all $z \in F_k$. By definition of $e^*$, we have
$$
|d(y_{k+1}, x_i) - d^*(y^*_{k+1}, z) | < 2^{-k-1}\delta
$$
for $1 \leq i \leq n$, and $(iii)$ yields
$$
d(y_{k+1}, y_k) < e^*(y^*_{k+1},y_k) + \eps \leq 2^{-k-1}\delta + 2^{-k-1}\delta = 2^{-k}\delta
$$
as required.