Excursion: The Urysohn Space

Recall that a mapping $f: X \to Y$ between two metric spaces $(X,d_X)$ and $(Y,d_Y)$ is an isometry if

that is, an isometry is a mapping that preserves distances. The function $f$ is also called an isometric embedding of $X$ into $Y$. $X$ and $Y$ are isometric if there exists a bijective isometry between them.

Universal spaces¶

A concrete example of such a space is $\mathcal{C}[0,1]$.

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 Urysohn (1927).

The construction features an amalgamation principle that has surfaced in other areas like model theory or graph theory.

Extensions of finite isometries and Urysohn universality¶

Suppose $X$ is a Polish metric space. Let $D = \{x_1, x_2, \dots\}$ be a countable, dense subset. We first observe that, to isometrically embed $X$ into another Polish space, it is sufficient to embed $D$.

In order to embed $D$, we can now exploit the inductive structure of $\Nat$ and reduce the task to extending finite isometries.

Suppose we have constructed an isometry $e$ between $F_N = \{x_1, \dots, x_N \} \subset D$ and a space $Y$. We would like to extend the isometry to include $x_{N+1}$. For this we have to find an element $y \in Y$ such that for all $i \leq N$

This extension property gives rise to the following definition.

As outlined above, the extension property of Urysohn universal spaces implies the desired isometric embedding property.

But the extension property also implies a strong intrinsic extension property for the Urysohn space itself.

The proof applies the Back-and-forth method that you may know from the rationals: every order-isomorphism between finite subsets of $\Q$ extends to an automorphism of $(\Q,<)$.

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 Macpherson (2011) and in the topological dynamics of automorphism groups of countable structures Kechris et al. (2005).

We will prove the existence of this unique Polish space, which we denote by $\Ury$, in the following sections.

Constructing the Urysohn space -- a first approximation¶

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 $X$ is a metric space and $x \in X$, then the mapping $f_{x}: X \to \Real^{\geq 0}$ given by

is 1-Lipschitz. Recall that a function $g$ between metric spaces $X$ and $Y$ is $L$-Lipschitz, $L > 0$ if for every $x,y \in X$,

Let $\Lip_1(X)$ be the set of 1-Lipschitz mappings from $X$ to $\Real$. We endow $\Lip_1(X)$ with the supremum metric

If $\diam(X) \leq \mathrm{d}$ and $f,g$ are 1-Lipschitz, then $d(f,g)$ is indeed finite. However, we will later need that the resulting space is also bounded. Let $\Lip^{\mathrm{d}}_1(X)$ be the space of all 1-Lipschitz functions from $X$ to $[0,\mathrm{d}]$.

Clearly, $\diam(\Lip^{\mathrm{d}}_1(X)) \leq \mathrm{d}$.

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 $\leq d(x,z)$. On the other hand, setting $y=z$ yields $d(f_x,f_z) \geq d(x,z)$. This embedding of $X$ into $\Lip^{\mathrm{d}}_1(X)$ is called the Kuratowski embedding.

We use this fact as follows: If $X^* = X \sqcup \{x^*\}$ and $d^*$ is an extension of $d_X$, then $f_{x^*}$ is an element of $\Lip^{\mathrm{d}}_1(X)$, and as above, for any $x \in X$

Hence $\Lip^{\mathrm{d}}_1(X)$ has an extension property of the kind we are looking for.

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 $X_\infty$ has the extension property needed to be Urysohn universal. Let $F$ be a finite subset of $X_\infty$. There exists $N$ such that $F \subset X_N$. Suppose $F^* = F \sqcup \{x^*\}$ and $d^*$ is an extension of $d$ to $F^*$. Let $\mathrm{d}^* = \diam(F^*)$. Note that $\diam(X_n) = 2^n \mathrm{d}$. Choose $M$ so that $M \geq N$ and $\diam(X_M) \geq \mathrm{d}^*$. The next lemma ensures that we can find $f \in X_{M+1}$ such that $f(x) = d^*(x^*,x)$ for all $x \in F$.

Finishing the construction¶

The set $X_\infty$ we constructed has two deficiencies with respect to our goal of constructing a Urysohn universal space: $X_\infty$ is not necessarily separable, and $X_\infty$ is not necessarily complete.

To make $X_\infty$ separable, we observe that if $X$ is compact, then the set $\Lip^{\mathrm{d}}_1(X)$ is closed in $\mathcal{C}(X)$ (the set of all real-valued continuous functions on $X$), bounded, and equicontinuous. By the Arzelà-Ascoli Theorem, $\Lip^{\mathrm{d}}_1(X)$ is compact. Every compact metric space is separable: For every $\eps > 0$, there exists a finite covering of the space with sets of $\diam < \eps$. Letting $\eps$ traverse all positive rationals and picking a point from each set in an $\eps$-covering yields a countable dense subset. Hence if we start with $X_0$ compact, each $X_n$ will be compact, too. A countable union of separable spaces is separable, thus $X_\infty$ is separable.

To obtain a complete space, we can pass from $X_\infty$ to its completion $\Cl{X_\infty}$. First note that if a metric space $X$ is separable, so is its completion $\Cl{X}$. However, we also have to ensure that $\Cl{X_\infty}$ retains the universality property of $X_\infty$.