%\documentclass[10pt,oneside]{article}
%\documentclass[10pt]{report}
\documentclass[10pt]{amsart}
\usepackage{amscd}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
%\usepackage{verbatim}

%\usepackage[all]{xy}

\title{Universality and Randomness for the Graphs and Metric
Spaces}

\author{A.\;M.~Vershik}
\address{St.Petersburg Mathematical Institute of Russian
Academy of Science\\ Fontanka 27\\ St.Petersburg, 191011\\ Russia}
\email{vershik@pdmi.ras.ru}
\thanks{Supported by the RF President's Grant ``Podderzhka
Veduschikh Nauchnykh
Shkol RF'' No. 2251.2003.1}


% MISCANELLOUS -----------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\sloppy


% THEOREM Environments ---------------------------------------------------
\newtheorem{thm}{Theorem}[section]
%\newtheorem{thm}{Theorem}[subsection]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{question}[]{Open Question}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}

%\newenvironment{com}{\begin{verbatim}}{\end{verbatim}}
% \newtheorem{rem}[\]{Remark}
%\numberwithin{equation}{subsection}
\numberwithin{equation}{section}


% MATH ---------------------------------------------------
\DeclareMathOperator{\Adm}{Adm} \DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\supp}{supp}

\begin{document}
\maketitle
\tableofcontents \pagebreak

%\input{graphs}
\section{Universal and Random Graphs}
\label{s:UNIVERSAL AND RANDOM GRAPHS}

In this section we will show the existence of a denumerable,
non-directed graph
which is universal in the category of all countable, non-directed
graphs and homogeneous (with respect to its finite subgraphs).
Moreover, we will see that such a graph is determined unique
up to isomorphism. This definition was done by R.~Rado.
We will give the criteria of universality using
incidence matrix. Then we consider the random graphs or probability
measures on the set of graphs. We generalize the theorem
by P.~Erd\"os and A.~R\'enyi that the random graph is
universal graph with probability 1.


We will describe a non-directed countable graph by a pair $\Gamma =
(\Gamma,\Gamma^{(1)})$, where $\Gamma$ is the (countable)
set of vertices, and
$\Gamma^{(1)}\subseteq\Gamma\times\Gamma$ the set of edges.
Any subset
$S\subseteq\Gamma$ determines a subgraph
$(S,\Gamma^{(1)}|_{S \times S})$ of
$\Gamma$, which we will again denote by $S$.

Given two graphs $\Gamma_i$, $i=1,2$.
A mapping $\iota: \Gamma_1 \rightarrow
\Gamma_2$ is called a mono-(iso)morphism, if it is one-to-one (bijective,
resp.) and preserves the structure of the graph $\Gamma_1$:
\[
(x,y)\in \Gamma_1^{(1)} \text{  if and only if } (\iota x, \iota y)\in
\Gamma_2^{(1)}.
\]
In other words, $\Gamma_1$ is isomorphic to the subgraph $\iota(\Gamma_1)$ of
$\Gamma_2$. Every isomorphism of $\Gamma_1$ onto itself is called automorphism.


\begin{defn}
A (countable, non-directed) graph $\Gamma$ is said to be
\begin{itemize}
\item[(1)]
{\it universal}, if to any finite (non-directed) graph $F$ there exists a
monomorphism $\iota: F \rightarrow \Gamma$. In other words, any finite
non-directed graph is isomorphic to a subgraph of $\Gamma$.
\item[(2)]
{\it homogeneous}, if to any finite subgraphs $F_1$, $F_2$ of $\Gamma$, and
isomorphism $\iota: F_1 \rightarrow F_2$, there exists an automorphism
$\iota':\Gamma \rightarrow \Gamma$ which extends $\iota$.
\end{itemize}
\end{defn}


\subsection{Construction of the universal graph}

In the sequel, we will show that universality and homogeneity is equivalent to
the following extension property:

\begin{defn}
A graph $\Gamma$ is said to have the \emph{extension property}, if the
following holds: Given any finite graph $F$, and a one-point extension $F'$ of
$F$. If there is a monomorphism $\iota: F \rightarrow \Gamma$, then $\iota$ can
be extended to an monomorphism $\iota': F' \rightarrow \Gamma$, i.e. the
following diagram commutes:
\begin{equation*}
\begin{CD}
F     @>{\iota \:\text{(monomorphism)}}>>   \Gamma \\
@V{id}VV            @V{id}VV \\
F'    @>{\iota'\:\text{(monomorphism)}}>>  \Gamma
\end{CD}.
\end{equation*}
\end{defn}

In other words, the graph $\Gamma$ satisfies the extension property if and only
if to any finite subgraph $F$ of $\Gamma$, and any (exterior) one-point
extension $F'=F \cup \{ a \}$ of $F$, there exists a point $\alpha \in \Gamma$
such that for $x\in F$
\[
(\alpha,x)\in \Gamma^{(1)} \text{ if and only if } (a,x)\in F'{^{(1)}}.
\]

The extension property allows us to extend locally defined isomorphisms to
global isomorphisms via a so-called \emph{back and forth} argument:

\begin{lem}\label{l:gr:BACK AND FORTH}
Suppose $\Gamma$, $\tilde \Gamma$ are countable, non-directed graphs which have
the extension property, and $F \subseteq \Gamma$ finite. Then any monomorphism
$\iota: F\rightarrow \tilde{\Gamma}$ can be extended to an isomorphism $\iota':
\Gamma \rightarrow \tilde{\Gamma}$.
\end{lem}

\begin{proof}
Write $\Gamma = \{x_1, x_2, \ldots\}$ and $\tilde \Gamma =\{y_1, y_2, \ldots
\}$. Denote $F_1 = F$, $G_1 = \iota (F_1)$, and $\iota_1 = \iota : F_1
\rightarrow G_1$. Define $G_2 = G_1 \cup \{ y_1 \}$. By the extension property,
$\iota_1^{-1}: G_1 \rightarrow F_1$ extends to a monomorphism $\iota_2^{-1}:
G_2 \rightarrow F_2$ onto a subset $F_2 \supseteq F_1$. Now define $F_3 = F_2
\cup \{ x_1 \}$. Again there is a monomorphism $\iota_3: F_3 \rightarrow G_3$
onto a subset $G_3 \supseteq G_2$. Take $G_4 = G_3 \cup \{ y_2 \}$. Continuing
in the same manner as above, we can construct inductively subgraphs
\[
F_1 \subseteq F_2 \subseteq \cdots \subseteq F_n \subseteq \cdots \subseteq
\Gamma
\]
with
\[
F_n \supseteq \{x_k : 1 \leq k \leq \frac{n-1}{2}\},
\]
subgraphs
\[
G_1 \subseteq G_2 \subseteq \cdots \subseteq G_n \subseteq \cdots \subseteq
\tilde{\Gamma}
\]
satisfying
\[
G_n \supseteq \{y_k: 1 \leq k \leq \frac{n}{2}\},
\]
and isomorphisms $\iota_n: F_n\rightarrow G_n$,
\[
\iota=\iota_1 \subseteq \iota_2 \subseteq \cdots \subseteq \iota_n \subseteq
\cdots
\]
The mapping $\iota_\infty = \bigcup_{n=1}^\infty \iota_n$ maps
$\bigcup_{n=1}^\infty F_n = \Gamma$ isomorphically onto $\bigcup_{n=1}^\infty
G_n = \tilde \Gamma$.
\end{proof}


\begin{thm}\label{t:gr:U GRAPH UNIQUE}
A countable, non-directed graph is universal and homogeneous if and only if it
has the extension property. Two such graphs are isomorphic.
\end{thm}

\begin{proof}
Any universal and homogeneous graph $\Gamma$ has the extension property: By
universality there is an embedding $\kappa: F_2\rightarrow M$. Define
$i:\kappa(F_1)\rightarrow\iota(M_1)$, $i = \iota\circ\kappa^{-1}$. Now, choose
an automorphism $J:M\rightarrow M$ which extends $i$. The mapping
$J\circ\kappa: F_2\rightarrow M$ is an extension of $\iota$.

Conversely, if $\Gamma$ has the extension property, then it is obviously
universal. Moreover, if $\iota: F \rightarrow F'$ is an isomorphism between
finite subgraphs of $\Gamma$, then Lemma \ref{l:gr:BACK AND FORTH} (setting
$\Gamma=\tilde \Gamma$) shows that $\iota$ can be extended to a global
automorphism $\iota': \Gamma \rightarrow \Gamma$. Hence $\Gamma$ is
homogeneous.

Suppose $\tilde\Gamma$ is another countable graph which satisfies the extension
property. To show that $\Gamma$ and $\tilde\Gamma$ are isomorphic, choose any
$a\in\Gamma$, $\tilde a\in\tilde\Gamma$, and apply Lemma \ref{l:gr:BACK AND
FORTH} to the monomorphism $\iota: \{a\} \rightarrow \tilde \Gamma$, which maps
$a$ to $\tilde a$.
\end{proof}

\begin{rem}
\emph{A non-directed countable graph $\Gamma$ which has the extension property
is universal in the category of all countable non-directed graphs, i.e. every
countable, non-directed graph $\Gamma'$ can be embedded into $\Gamma$.}
\end{rem}


Consider a countable, non-directed graph $(\Gamma, \Gamma^{(1)})$,
$\Gamma=\{x_1,x_2,x_2,\ldots\}$. We define its incidence matrix
$m_\Gamma=(\varepsilon_{ij})_{i,j=1}^\infty\in \{0,1\}^{\mathbb  N\times\mathbb
N}$ by
\begin{equation}\label{e:gr:INCIDENCE MATRIX}
\varepsilon_{ij} =
\begin{cases}
  1 & \text{ if } (x_i,x_j)\in\Gamma^{(1)} \\
  0 & \text{ otherwise}
\end{cases}.
\end{equation}
Of course the definition of $m_\Gamma$ depends on the order of the $x_i$.

\begin{defn}\label{d:gr:UNIVERSAL INC MAT}
An incidence matrix $(\varepsilon_{ij})_{i,j=1}^\infty$ is said to be \emph{
universal}, if for every $n\in\mathbb  N$
  \begin{equation}\label{e:gr:UNIV INCID MAT1}
    \{ (\varepsilon_{1k},\varepsilon_{2k},\ldots,\varepsilon_{nk})
    : k > n
    \} = \{0,1\}^n.
  \end{equation}
In other words, every finite binary word
$(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n)$ occurs infinitely often:
\begin{equation}\label{e:gr:UNIV INCID MAT2}
(\varepsilon_{1k},\varepsilon_{2k},\ldots,\varepsilon_{nk}) =
(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n) \text{ for infinitely many }
k > n.
\end{equation}
The set of all universal matrices is denoted by $\mathcal U$.
\end{defn}

Universal matrices are connected with universal graphs as follows:

\begin{thm}
A countable non-directed graph $\Gamma$ is universal and homogeneous, if its
incidence matrix $m_\Gamma$ is universal.
\end{thm}
\begin{proof}
Write $\Gamma=\{x_1,x_2,x_3,\ldots\}$, and let $m_\Gamma$ be its incidence
matrix defined by \ref{e:gr:INCIDENCE MATRIX}. By Theorem \ref{t:gr:U GRAPH
UNIQUE}, we have to show that $\Gamma$ satisfies the extension property if and
only if $m_\Gamma$ is universal. But this is obvious, since Definition
\ref{e:gr:UNIV INCID MAT1} is only a reformulation of the extension property.
\end{proof}

To show the existence of a universal and homogeneous graph, we construct a
universal incidence matrix $(\varepsilon_{ij})_{i,j=1}^\infty$ as follows:
Choose an enumeration $\{w^{(1)},w^{(2)},w^{(3)},\ldots\}$ of all finite words
with alphabet $\{0,1\}$, such that every finite word occurs infinitely often.
Extend these finite words $w^{(i)}$ arbitrarily to infinite words
$\tilde{w}^{(i)}\in \{0,1\}^{\mathbb  N}$. Now define $\varepsilon_{ij}$,
$i<j$, as
\[
(\varepsilon_{1,n+1},\varepsilon_{2,n+1},\ldots,\varepsilon_{n,n+1})= \pi_n
\tilde{w}^{(n)}, \qquad n\in\mathbb  N
\]
where $\pi_n$ is the projection onto the first $n$ coordinates. Further define
$\varepsilon_{ii} = 0$, and $\varepsilon_{ij}=\varepsilon_{ji}$ for $i>j$. This
already defines an incidence matrix, such that (\ref{e:gr:UNIV INCID MAT2}) is
satisfied.

We thus have proved

\begin{thm}\label{t:gr:U GRAPH EXISTS}
There exists a countable, non-directed graph which is universal and
homogeneous. By Theorem \ref{t:gr:U GRAPH UNIQUE} this graph is determined
uniquely up to isomorphism.
\end{thm}

Since such a universal and homogeneous graph is unique (up to isometry), we
simply speak of \emph{the} universal graph $\Gamma_U$.

Suppose $x,y\in\Gamma_U$ are such that $(x,y)\notin \Gamma_U^{(1)}$. By the
extension property, there is a point $z\in \Gamma_U$ such that both
$(x,z),(z,y) \in \Gamma_U^{(1)}$. Thus the graph metric
\[
d(x,y)= \min \# \text{ edges in }\gamma,
\]
where the min is taken over all paths which join $x$ and $y$, can only attain
the values
\[
d(x,y) =
\begin{cases}
0 & \text{ if }x=y \\
1 & \text{ for }(x,y)\in \Gamma^{(1)} \\
2 & \text{ otherwise }
\end{cases}.
\]


\subsection{Action of the group $S^\infty$ and the set of universal
matrices}

We denote by $\mathcal M\subseteq\{0,1\}^{\mathbb N\times\mathbb N}$ the set of
all incidence matrices, equipped with the topology that inherits from the
product topology on $\{0,1\}^{\mathbb N\times\mathbb  N}$, and by $\mathcal U$
the subset of all universal incidence matrices. The space $\mathcal M$ is
compact and metrizable, and $\mathcal U$ is a closed subset of $\mathcal M$.

Let denote by $S^\infty$ the group of all permutations on the naturals $\mathbb
N$. Equipped with the topology of point-wise convergence, and choosing a proper
metric, for example the usual metric for point-wise convergence
\[
d(g_1,g_2)= \sum 1/2^n \frac{|g_1(n)-g_2(n)|}{1+|g_1(n)-g_2(n)|},
\]
$S^\infty$ is a complete separable metric space (=polish space), which is not
locally compact. Moreover, \emph{this topology makes $S^\infty$ to a
non-locally compact, polish group}. All finite permutations form a dense
subgroup $S_\infty$ of $S^\infty$.

For any $g\in S^\infty$ and infinite matrix $(a_{ij})_{i,j=1}^\infty$ we define
\begin{equation}\label{e:gr:PERMUTATION OF MATRIX}
T_g (a_{ij}) = g \, (a_{ij}) \, g^{-1} = (a_{g(i),g^{-1}(j)})_{i,j=1}^\infty.
\end{equation}
Clearly $T_g$ leaves the set $\mathcal M$ of incidence matrices invariant. Via
$g\mapsto T_g$, the group $S^\infty$ (or $S_\infty$) acts on $\mathcal M$. Note
that for any finite permutation $g\in S_\infty$, $T_g: \mathcal M \rightarrow
\mathcal M$ is a homeomorphism, whereas for any infinite permutation it is only
a Borel-automorphism.


Consider a graph $\Gamma$ with incidence matrix $m_\Gamma$: Another (countable,
non-directed) graph $\tilde \Gamma$ is isomorphic to $\Gamma$ if and only if
\[
m_{\tilde \Gamma} = g m_{\Gamma} g^{-1}
\]
for some $g\in S^\infty$, or equivalently if the orbits $S^\infty m_{\Gamma}$
and $ S^\infty m_{\tilde\Gamma}$ coincide. In this sense we may regard the
group $\Aut \Gamma$ of all automorphisms of $\Gamma$ as a (closed) subgroup of
$S^\infty$.

{\bf PROBLEM}

How does the group $\Aut(\Gamma_U)$ of automorphisms of the universal graph
$\Gamma_U$ look like?


It is known that this group is simple  (see \cite{CAM01})
Very interesting question whether this (uncountable) group has
unitary representations which do not extend to the whole group $S^\infty$

As we saw $\mathcal U$ is $S^\infty$-invariant subset of $\mathcal
M$. Moreover, since any two universal graphs are isomorphic, \emph{$S^\infty$
acts transitively on the set $\mathcal U$ of universal matrices}, i.e. if $m_1,
m_2\in\mathcal U$, then there is a $g\in S^\infty$ such that
\[
m_2= g \, m_1 \, g^{-1}.
\]
By the universality condition, it is clear that \emph{for any universal matrix
$m$, its orbit $S^\infty m$ is dense in $\mathcal M$}.

\begin{thm}\label{t:gr:UNIV MAT ARE GDELTA}
The set $\mathcal U$ of all universal incidence matrices is a dense
$G_\delta$-subset of $\mathcal M$.
\end{thm}

\begin{proof}
For any finite binary word $w = (\varepsilon_1, \varepsilon_2, \ldots,
\varepsilon_n)$, the set $ M_w = \{ (\varepsilon_{ij})_{i,j=1}^\infty \in
\mathcal M : (\ref{e:gr:UNIV INCID MAT2})\text{ holds } \} $ equals
\[
\bigcap_{m>n}\bigcup_{k\geq m} \{ (\varepsilon_{ij})_{i,j=1}^\infty \in
\mathcal M : (\varepsilon_{1k}, \varepsilon_{2k}, \ldots, \varepsilon_{nk}) =
(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n) \}
\]
is a $G_\delta$ set in $\mathcal M$. Therefore, as the intersection of
countably many $M_w$, the set $\mathcal U$ is also $G_\delta$.

For any universal incidence matrix $m$, the orbit $S_\infty M$ is dense in
$\mathcal M$. Since $\mathcal U$ is $S_{\infty}$-invariant, this completes the
proof of the theorem.
\end{proof}

\subsection{Random graphs}
Now we will define the probability measures on the set of all countable
graphs and in particular give a probabilistic proof of the existence
of the universal graph $\Gamma_U$. That fact that the simplest such probability
measures (independent entries) gives with probability one the universal graph
is due to P. Erd\"os and A. R\'enyi (\cite {ERD01} see also \cite{CAM01}).

This proof will also imply the existence $S^{\infty}$-invariant
measures which are concentrated on the set $\mathcal U$ of universal incidence
matrices.

We first give an intuitive description. Starting with a single point (one-point
graph), we successively define random graphs $\Gamma_n$, $n=1,2,3, \ldots$ in
the following manner: To a given $n$-point graph
$\Gamma_n=\{x_1,x_2,\ldots,x_n\}$ we add a $n+1$-th point $x_{n+1}$ and
independently set edges in $\Gamma_{n+1}=\Gamma_n\cup \{x_{n+1}\}$ between the
new point $x_n$ and the old points $x\in \Gamma_n$ according to
\begin{align*}
\text{Prob}[(x_{n+1},x_m)\in \Gamma_{n+1}] & = p \\
\text{Prob}[(x_{n+1}, x_m)\notin \Gamma_{n+1}] &= 1-p,
\end{align*}
where $0<p<1$ is a fixed number. Then, with probability one, the so obtained
graph is the universal graph $\Gamma_U$:

\begin{thm}[P.~Erdos, A.~Renyi]\label{t:gr:ERDOS}
Suppose $\{\xi_{ij}: i<j\}$ is an array of independent identically distributed
random variables with
\[
\begin{aligned}
P[\xi_{ij} = 1] & = p, \\
P[\xi_{ij} = 0] & = 1-p,
\end{aligned}
\]
where $0<p<1$. Set $\xi_{ii}=0$ and $\xi_{ij}=\xi_{ji}$ for $i>j$. Then, with
probability one, $(\xi_{ij})_{i,j=1}^\infty$ is a universal incidence matrix.
\end{thm}

\begin{proof}
We only have to show that, with probability one, every binary word
$(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n)\in\{0,1\}^n$ occurs
infinitely often:
\[
P[(\xi_{11},\xi_{2k},\ldots,\xi_{nk})=
(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n) \text{ for infinitely many }
k>n] = 1.
\]
But this is evident since all the $\xi_{ij}$, $i<j$, are independent, and since
for $k>n$
\[
0< P[(\xi_{1k},\xi_{2k},\ldots,\xi_{nk})=
(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n)]<1,
\]
which follows from $0<p<1$.
\end{proof}

\begin{rem}
The measures which were defined are invariant and ergodic with
respect to the $NW$-shift
$\sigma_{NW}:\mathcal M \rightarrow \mathcal M$ defined by
\begin{equation}\label{e:gr:NW SHIFT}
\sigma_{NW}(a_{i,j})_{i,j=1}^\infty = (a_{i+1,j+1})_{i,j=1}^\infty.
\end{equation}
\end{rem}

  There are lot of measures (besides those above) which
are invariant and ergodic with respect to the group $S_{\infty}$
which acts on the set of symmetric $0-1$ matrices and concentrated
on the subset of the universal matrices (see \cite{VERSH02}).
So we have a strong version of so called Kolmogorov's effect:
there are uncountable many invariant ergodic measures for
the transitive action of nonlocally compact group $S_{\infty}$ .

Moreover we can say that the set of the probability measures
on the space of symmetric $0-1$ matrices which have as support
the set of universal matrices is everywhere dense $G_{\delta}$-set
in the weak topology of the space of measures.

  In another words for the generic probability measure
on the set of countable graphs a universal graph has probability 1.

%
%
%
%
%


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "vershik"
%%% End:
\pagebreak
%\input{urysohn}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "vershik"
%%% End:

\section{The Urysohn Metric Space and Random Metric Spaces}
\label{s:URYSOHN}

In his last works \cite{URY01}, Paul S. Urysohn (1898--1924) gave
a concrete construction of a universal separable metric space
which is now known as ``Urysohn Space''. Different to other
universal separable metric spaces (for
example $C([0,1])$ with the sup-norm, as was proven by Banach and Mazur), the
Urysohn space is more special, since it is homogeneous in the sense of
Definition \ref{d:U SPACE} and the space $C([0,1])$ is not homogeneous.
Moreover it turns out that, up to isometric
equivalence, there is only one universal and homogeneous space --
Urysohn space $\mathfrak U$.

In this section we give an explicit construction of the Urysohn space
$\mathfrak U$ which is in the spirit of our construction of the universal graph
in Section \ref{s:UNIVERSAL AND RANDOM GRAPHS}, i.e. it is based on the property that
isometries from finite metric spaces $F$ into $\mathfrak U$ can be extended to
arbitrary one-point extensions of $F$ (see also \cite{VERSH01}). Beside
universality, this extension property also implies homogeneity and the
uniqueness of the Urysohn space. Another analogue to the case
(Gurarij spaces (see \cite{LUSK01}), or the Poulsen Simplex
(see \cite{LIND01}) will be considered elsewhere. For different
constructions of the Urysohn space, see \cite{KATE01} or \cite{URY01}.

\begin{defn} \label{d:U SPACE}
A  polish space $(U,d)$ is said to be
\begin{itemize}
\item[(1)] {\it universal}, if to any finite metric space $(F,d_F)$ there
exists an isometry $\iota:(F,d_F)\rightarrow (U,d)$.
\item[(2)] {\it homogeneous}   , if to any finite subsets $F_1$, $F_2$ of $U$,
and bijective isometry $\iota: F_1\rightarrow F_2$, there exists an
automorphism (=bijective isometry) $\iota':U \rightarrow U$ which extends
$\iota$.
\item[(3)] a {\it Urysohn space}, if it is universal and homogeneous.
\end{itemize}
\end{defn}

Note that any separable metric space $(M,d)$ can be embedded isometrically into
a separable Banach space $(B,\|\,.\,\|)$: For example, choose any point $x_0\in
M$ and consider the mapping
\[
\iota: M \rightarrow C_b(M), \qquad x\mapsto \iota(x)=d(x,\,.\,)-d(x_0,\,.\,),
\]
where $C_b(M)$ is the space of all bounded continuous functions on $M$,
equipped with the sup-norm $\|\,.\,\|_\infty$. The triangular inequality
\[
|d(x,z)-d(y,z)| \leq d(x,y), \qquad x,y,z\in K,
\]
implies that $\|\iota(x)-\iota(y)\|_\infty= d(x,y)$, and setting $z=y$ in the
formula above shows that $\|\iota(x)-\iota(y)\|_\infty =d(x,y)$. Thus $\iota$
is an isometric embedding of $M$ into $C_b(M)$. Set $B= \text{ closed linear
span of }\iota M$, $\|\,.\,\|=\|\,.\,\|_\infty$. This is a Banach space and by
the separability of $M$, $B$ is also separable.

This shows that any universal (separable) Banach space (for example $C[0,1]$
with the sup-norm, see \cite{DUG} or other textbooks on topology) is also a
universal separable metric space. But every known model of a universal Banach
space is not homogeneous in the sense of Definition \ref{d:U SPACE}.






\subsection{Extending Isometries}

In the sequel we will show that the Urysohn property can be characterized by
certain extension properties of isometries. This enables us to see that Urysohn
spaces are uniquely determined up to isomorphism.

\begin{defn}
Let $(M_1,d_1)$, $(M_2,d_2)$ be metric spaces and $\varepsilon>0$. A mapping
$\iota: M_1\rightarrow M_2$ is said to be an {\it $\varepsilon$-isometry}, if
\[
\| d_1(x,y)-d_2(x,y)\| \leq \varepsilon, \qquad x,y \in M_1.
\]
\end{defn}

\begin{defn}
Suppose $\varepsilon \geq 0$. A metric space $(M,d)$ is said to have the {\it
$\varepsilon$-extension property}, if the following holds: Given any finite
metric space $(F,d_F)$, and a one-point extension $(F', d_{F'})$ of $(F,d_F)$.
If there is an isometric mapping $\iota: F \rightarrow M$, then $\iota$ can be
extended to an $\varepsilon$-isometry $\iota': F'\rightarrow M$, i.e. the
following diagram commutes:
\begin{equation*}
\begin{CD}
F     @>{\iota \quad \text{(isometry)}}>>   M \\
@V{id}VV            @V{id}VV \\
F'     @>{\iota' \quad (\varepsilon-\text{isometry})}>>    M
\end{CD}.
\end{equation*}
If $\varepsilon=0$, we simply speak of the {\it extension property}.
\end{defn}

In other words, $(M,d)$ satisfies the $\varepsilon$-extension property if and
only if to any finite subspace $F\subseteq M$, and any (exterior) one-point
metric extension $(F'=F\cup\{a\},d_{F'})$ of $F$, there exists a point
$a_\varepsilon \in M$ such that
\[
|d(a_\varepsilon,x)-d_{F'}(a,x)| \leq \varepsilon, \qquad x\in F.
\]

The extension property allows us to extend locally defined isometries to global
isometries via a so-called \emph{back and forth} argument:

\begin{lem}\label{l:BACK AND FORTH}
Suppose $(M,d)$, $(\tilde{M},\tilde{d})$ are polish spaces which have the
extension property, $F\subseteq M$ finite. Then any isometric mapping $\iota:
F\rightarrow \tilde{M}$ can be extended to a bijective isometry $\iota':
M\rightarrow \tilde{M}$.
\end{lem}

\begin{proof}
Choose countable dense subsets $\{x_1,x_2,\ldots\}\subseteq M$ and
$\{y_1,y_2,\ldots\}\subseteq \tilde{M}$.

Denote $F_1=F$, $G_1=\iota (F_1)$, and $\iota_1 = \iota : F_1 \rightarrow G_1$.
Define $G_2=G_1\cup \{y_1\}$. By the extension property,
$\iota_1^{-1}:G_1\rightarrow F_1$ extends to an isometry $\iota_2^{-1}:
G_2\rightarrow F_2$ onto a subset $F_2\supseteq F_1$. Now define $F_3=
F_2\cup\{x_1\}$. Again there is an isometry $\iota_3:F_3\rightarrow G_3$ onto a
subset $G_3\supseteq G_2$. Take $G_4=G_3\cup \{y_2\}$. Continuing in the same
manner as above, we can construct inductively subsets
\[
F_1\subseteq F_2 \subseteq \cdots \subseteq F_n \subseteq \cdots \subseteq M
\]
with
\[
F_n\supseteq \{x_k : 1\leq k \leq \frac{n-1}{2}\},
\]
subsets
\[
G_1\subseteq G_2 \subseteq \cdots \subseteq G_n \subseteq \cdots \subseteq
\tilde{M}
\]
satisfying
\[
G_n\supseteq \{y_k: 1\leq k \leq \frac{n}{2}\},
\]
and isometric bijections $\iota_n: F_n\rightarrow G_n$,
\[
\iota=\iota_1\subseteq \iota_2 \subseteq \cdots \subseteq \iota_n \subseteq
\cdots
\]
The mapping $\iota_\infty=\bigcup_{n=1}^\infty \iota_n$ maps $F_\infty=
\bigcup_{n=1}^\infty F_n $ isometrically onto $G_\infty= \bigcup_{n=1}^\infty
G_n$. Since $F_\infty$ and $G_\infty$ are dense, and since the metrics on $M$
and $\tilde{M}$ are complete we may extend $\iota_\infty$ to an bijective
isometry $\iota':M\rightarrow \tilde{M}$.
\end{proof}



\begin{thm}\label{t:U SPACE IS UNIQUE}
A polish space is a Urysohn space if and only if it has the extension property.
Two Urysohn spaces are isometrically isomorphic.
\end{thm}
\begin{proof}
A Urysohn space $(M,d)$ has the finite extension property: By universality
there is an isometry $\kappa: F_2\rightarrow M$. Define
$i:\kappa(F_1)\rightarrow\iota(M_1)$, $i = \iota\circ\kappa^{-1}$. Now, choose
an automorphism $J:M\rightarrow M$ which extends $i$. The mapping
$J\circ\kappa: F_2\rightarrow M$ is an extension of $\iota$.

On the other hand, if $(M,d)$ has the extension property, then $(M,d)$ is
obviously universal. Moreover, if $\iota: F_1\rightarrow F_2$ is an isometry
between finite subspaces of $M$, then Lemma \ref{l:BACK AND FORTH} (setting
$M=\tilde{M}$) shows the existence of an automorphism $\iota':M\rightarrow M$
which extends $\iota$.

The uniqueness of two Urysohn spaces $(M,d)$,$(\tilde M,\tilde d)$ is now
obvious: Choose any two points $x_1\in M$, $x_2 \in \tilde M$ and consider the
isometry $\iota: x_1\mapsto x_2$. Since both spaces posses the extension
property, Lemma \ref{l:BACK AND FORTH} allows us to extend $\iota$ to an
isomorphism $\iota':M\rightarrow \tilde M$.
\end{proof}

\begin{rem}
The existence of a polish space which is Urysohn is shown in Section \ref{s:U
SPACE EXISTENCE}. Since such a space is unique up to isometry, we will simply
speak of \emph{the} Urysohn space $(\mathfrak U,d)$.
\end{rem}

Note that if a polish space $(M,d)$ satisfies the extension property, then it
is also universal in the category of polish spaces, i.e. every polish space
$(P,d)$ can be embedded isometrically into $M$: Choose a countable dense subset
$\{x_1,x_2,\ldots\}\subseteq M'$, and denote $F_n = \{x_1,\ldots, x_n\}$. There
exist exists isometric mappings $\iota_n: F_n\rightarrow M$,
\[
\iota_1\subseteq \iota_2 \subseteq \cdots \subseteq \iota_n \subseteq \cdots
\]
The mapping $\iota_\infty=\bigcup_{n=1}^\infty \iota_n$ maps $F_\infty=
\bigcup_{n=1}^\infty F_n $ isometrically into $M$. Since $F_\infty$ is dense in
$P$, and since the metric on $M$ is are complete, we may extend $\iota_\infty$
to an isometry $\iota:P\rightarrow M$.

\begin{lem}\label{l:EPSILON EXTENSION}
Suppose a complete metric space $(M,d)$ satisfies the $\varepsilon$-extension
property for all $\varepsilon>0$. Then $(M,d)$ has the extension property for
compact metric spaces: Given any compact metric space $(C,d_C)$, and any
one-point (or polish) extension $(C',d_{C'})$ of $(C,d_C)$. If there is an
isometric mapping $\iota: C \rightarrow M$, then $\iota$ can be extended to an
isometry $\iota': C' \rightarrow M$, i.e. the following diagram commutes:
\begin{equation*}
\begin{CD}
C     @>{\iota \quad \text{(isometry)}}>>   M \\
@V{id}VV            @V{id}VV \\
C'     @>{\iota' \quad (\varepsilon-\text{isometry})}>>    M
\end{CD}
\end{equation*}
\end{lem}

\begin{proof}
First of all, note that for arbitrary $\varepsilon>0$ the
$\varepsilon$-extension property holds also for compact metric spaces: Given
any compact metric space $(C,d_C)$, one-point extension
$(C'=C\cup\{a\},d_{C'})$, and isometry $\iota: C\rightarrow M$. Because
$C$ is compact, we may choose a finite set $F\subseteq C$ such that
\[
\min_{y\in F} d(\iota x,\iota y) \leq \varepsilon/2, \qquad x\in C.
\]
By the assumption on $M$, there exists an $\varepsilon/2$-extension of the
restriction of $\iota$ to $F$, which maps $a$ to $x_a\in M$, say. Now the
function
\[
\iota': C\cup\{a\}\rightarrow M,
\begin{cases}
\iota'=\iota & \text{on } C \\
a\mapsto x_a &
\end{cases}
\]
is an $\varepsilon$-extension of $\iota:C\rightarrow M$, as one easily can
verify.

To show the extension property, we have to find a point $\alpha\in M$ such that
\begin{equation}\label{e:LOC01}
d(\alpha,\iota(x))=d_{C'}(a,x), \qquad x\in C.
\end{equation}
Choose $\varepsilon_n$, such that $\sum_{n=0}^\infty \varepsilon_n < \infty$.
We will define inductively a sequence of points $x_n\in M$, $n=0,1,2,\ldots$,
such that
\begin{equation}\label{e:LOC02}
|d(x_n,\iota(x))-d_{C'}(a,x)|\leq \varepsilon_n, \qquad x\in C,
\end{equation}
and such that the sequence $(x_n)$ is Cauchy in $M$. Then, since $M$ is
complete, there exists a limit $\alpha$ which certainly satisfies
(\ref{e:LOC01}).

Since $M$ satisfies the $\varepsilon$-extension property for $\varepsilon =
\varepsilon_0$, we can find a point $x_0\in M$ which satisfies (\ref{e:LOC02})
with $n=0$. Define the other $x_n$, $n\geq 1$, by applying the following
induction step:

Given a point $x_n$ which satisfies (\ref{e:LOC02}). Define an (exterior)
one-point extension $(C\cup\{x_n,b\},d')$ of $(C\cup\{x_0\},d)$ by:
\begin{align*}
d'(x,y) &= d(x,y) \qquad x,y\in C\cup\{x_n\} \\
d'(x,b) &= d_{C'}(x,a) \qquad x\in C \\
d'(x_n,b) &= \varepsilon_n
\end{align*}
In fact, by (\ref{e:LOC02}), $d'$ satisfies the triangular inequality (if in
addition $\varepsilon_n \leq \inf_{x\in C} d_{C'}(x,a)$, which we certainly may
assume) as one can easily verify. Since $M$ satisfies the
$\varepsilon$-extension property for $\varepsilon = \varepsilon_{n+1}$, we can
find a point $x_{n+1}\in M$ such that
\[
|d(x_{n+1},\iota(x))-d_{C'}(a,x)|\leq \varepsilon_{n+1}, \qquad x\in C,
\]
and
\[
d(x_n,x_{n+1}) \leq d'(x_n,b) + \varepsilon_{n+1} = \varepsilon_n +
\varepsilon_{n+1}.
\]

By construction, \ref{e:LOC02} is satisfied, and since $\sum \varepsilon_n
<\infty$, the latter inequality shows that $(x_n)$ is a Cauchy sequence, which
completes the proof.
\end{proof}


As an immediate consequence of Lemma \ref{l:EPSILON EXTENSION}, any polish
space $(M,d)$ which satisfies the extension property (for finite metric spaces
) also satisfies the extension property for compact metric spaces. Repeating
the proof of Lemma \ref{l:BACK AND FORTH} verbatim we may conclude:

\begin{lem}\label{l:u:BACK AND FORTH COMP}
Suppose $(M,d)$, $(\tilde{M},\tilde{d})$ are polish spaces which have the
extension property, $C\subseteq M$ compact. Then any isometric mapping $\iota:
C\rightarrow \tilde{M}$ can be extended to a bijective isometry $\iota':
M\rightarrow \tilde{M}$.
\end{lem}

In particular, this shows that the Urysohn space is homogeneous with respect to
its compact subspaces. Hence the Urysohn space $\mathcal U$ is a ``good''
universal object in the category of all compact metric spaces: every compact
metric space $(C,d_C)$ can be embedded isometrically into $\mathcal U$, and
this embedding is unique up to isometry, i.e. if $\iota_1:C \rightarrow U$,
$\iota_2: C \rightarrow U$ are two such isometries, then there exists an
automorphism $J:\mathcal U\rightarrow \mathcal U$ such that
\[
\iota_1 = J \circ \iota_2.
\]
Lemma \ref{l:u:BACK AND FORTH COMP} is not true assuming $C$ to be closed, even
countable (see \cite{BOG01}, \cite{HUHU01}).

The following Theorem which will be important for our construction of the
Urysohn space (See subsection \ref{s:U SPACE EXISTENCE}):

\begin{thm}
A polish space is Urysohn if and only if it satisfies the
$\varepsilon$-extension property for every $\varepsilon>0$.
\end{thm}

\begin{proof}
Combine Lemma \ref{l:EPSILON EXTENSION} and Theorem \ref{t:U SPACE IS UNIQUE}.
\end{proof}




\subsection{Construction, Universal Matrices}
\label{s:U SPACE EXISTENCE}

Before show the existence of a Urysohn space, we need some preparations.

Suppose $(M,d)$ is an infinite polish space. Choose a countable dense subset
$D=\{x_1, x_2, x_3, \ldots\}$ and define a matrix $r=(r_{ij})_{i,j=1}^\infty$
by
\begin{equation} \label{e:DIST MATRIX}
r_{i,j}= d(x_i,x_j).
\end{equation}
Any matrix obtained in such a way is called a {\it (infinite) distance matrix}.
The set of all infinite distance matrices is denoted by $\mathcal{R}$. We will
consider $\mathcal{R}$ as topological space equipped with the topology that
inherits from the product topology on $\mathbb R^{\mathbb N \times \mathbb N}$.
$\mathcal R$ is a closed convex cone in $\mathbb R^{\mathbb N\times\mathbb N}$,
in particular it is a polish space.

Similarly we say that a finite matrix $(r_{i,j})_{i,j=1}^n$ is a {\it (finite)
distance matrix}, if there exists a finite metric space $(\{x_1, x_2,\ldots,
x_n\}, d)$ such that (\ref{e:DIST MATRIX}) holds. The set of all
$n$-dimensional distance matrices, equipped with the product topology, is
denoted by $\mathcal{R}_n$. If we define a (continuous) projection
$\pi_n:\mathcal R_{n+1}\rightarrow \mathcal R_n$ by
\[
\pi_n (r_{ij})_{i,j=1}^{n+1}=(r_{ij})_{i,j=1}^n,
\]
then we can regard $\mathcal R$ as the inverse limit of the cones $\mathcal
R_n$:
\[
\mathbb R^+ \stackrel{\pi_1}\leftarrow \mathcal R_2 \stackrel{\pi_2}\leftarrow
\cdots
 \stackrel{\pi_{n-1}}\leftarrow \mathcal R_n \stackrel{\pi_{n}}\leftarrow \mathcal R_{n+1}
 \stackrel{\pi_{n+1}}\leftarrow \cdots
\]

Given a $n$-dimensional distance matrix $r_n=(r_{ij})_{i,j=1}^n$, which
corresponds to $F=(\{x_1,\ldots,x_n\},d)$. A vector $b=(b_1,\ldots,b_n)$ is
called {\it admissible}, if the matrix
\[
r_n^b =
\begin{pmatrix}
r_{11} & r_{12} & \cdots & r_{1n} & b_1 \\
r_{21} & r_{22} & \cdots & r_{2n} & b_2 \\
\vdots & \vdots & \ddots  & \vdots & \vdots \\
r_{n1} & r_{n2} & \cdots & r_{nn} & b_n \\
b_1  & b_2 & \cdots & b_n & 0
\end{pmatrix}
\]
is also a distance matrix. In other words, $b$ is admissible if there exists a
one-point extension $(F\cup\{x\},d')$ of $(F,d)$, such that
\[
d'(x,x_i)=b_i, \qquad i=1,\ldots,n.
\]
The set of all admissible vectors is then denoted by $\Adm(r_n)$. It determines
all one-point extensions of $(F,d)$ up to isomorphism. Note that
\begin{equation}\label{e:ADMISSIBLE CONE}
\Adm(r_n)= \{ (b_i)_{i=1}^n\in\mathbb R^n : b_i-b_j \leq r_{ij} \leq b_i+b_j
\},
\end{equation}
hence $\Adm(r_n)$ is a closed convex cone $\subseteq \mathbb{R}^n$.


\begin{lem}\label{l:ADMISSIBLE CONES}
Suppose $M=(\{x_1,x_2,x_3,\ldots\},d)$ is countable metric space, and consider
the subspaces $F_n=(\{x_1,\ldots,x_n\},d)$, with $r_n=(d(x_i,x_j))_{i,j=1}^n$
as their corresponding distance matrices. Then
\[
\mathbb R^+ \stackrel{\pi_1}\leftarrow \Adm(r_2) \stackrel{\pi_2}\leftarrow
\cdots
 \stackrel{\pi_{n-1}}\leftarrow \Adm(r_n) \stackrel{\pi_{n}}\leftarrow \Adm(r_{n+1})
 \stackrel{\pi_{n+1}}\leftarrow \cdots,
\]
where $\pi_n:\mathbb R^{n+1}\rightarrow \mathbb R^n$ is the projection onto the
first $n$ coordinates.
\end{lem}

\begin{proof}
It is clear that $\pi_{n+1}\Adm(r_{n+1}) \subseteq \Adm(r_n)$. To prove the
opposite inclusion, it suffices to show that to any two vectors
$a,b\in\Adm(r_n)$ we can construct a two-point extension
$M=(F_n\cup\{y_a,y_b\},d)$ of $F_n$ with $d(x_i,y_a)= a_i$ and $d(x_i,y_b)=
b_i$, $i=1,\ldots, n$. The only distance left to choose is $\alpha=d(y_a,y_b)$.
The validity of the triangular inequality for $d$ is equivalent to
\[
|a_i-b_i|\leq \alpha \leq a_i+b_i,  \qquad 1\leq i \leq n,
\]
which is only possible if
\[
\max_{1\leq i \leq n} |a_i-b_i| \leq \min_{1\leq i \leq n} a_i + b_i.
\]
But the latter inequality is true since both vectors $a$ and $b$ are
admissible: There exists a one-point extension $(F_n \cup\{z_a\},d_a)$ of $F_n$
with
\[
d_a(z_a,x_i)= a_i, \qquad 1\leq i \leq n,
\]
and a one-point extension $(F_n \cup\{z_b\},d_b)$ of $F_n$ with
\[
d_b(z_b,x_i)= b_i, \qquad 1\leq i \leq n.
\]
Now, using the triangular inequality for both metrics, we have
\[
\begin{split}
a_i-b_i & = d_a(z_a,x_i) - d_b(z_b,x_i) \leq d_a(z_a,x_j) + d(x_i,x_j) -
d_b(z_b,x_i) \leq\\
&\leq d_a(z_a,x_j) + d_b(z_b,x_j) = a_j + b_j.
\end{split}
\]
Since $i$ and $j$ where arbitrary, this implies the desired inequality.
\end{proof}

\emph{Remark.} The above lemma shows that the cones $\Adm(r_n)$ are consistent
under projections. \emph{They are also consistent under permutations:} If $g$
is any permutation on the set $\{1,2,\ldots n\}$ then we have
\[
g\Adm(r_n) = \Adm(g r_n g^{-1}),
\]
where for vectors $x=(x_1,x_2,\ldots,x_n)$, its permutation $gx$ is defined by
$gx=(x_{g(1)}, x_{g(2)}, \ldots, x_{g(n)})$.

\begin{defn}\label{d:U MATRIX}
A distance matrix $r=(r_{ij})_{i,j=1}^\infty$ is said to be
%\begin{itemize}
\emph{universal}, if for every $n\in\mathbb N$
  \begin{equation}\label{e:U MATRIX}
    \text{closure } \{ (r_{1k},r_{2k},\ldots,r_{nk})
    : k= n, n+1, \ldots
    \} =  \Adm((r_{ij})_{i,j=1}^n).
  \end{equation}
It is called \emph{weakly universal}, if $S_\infty r$ is dense in $\mathcal R$.
%\end{itemize}
The set of all universal matrices is denoted by $\mathcal M$.
\end{defn}

Universal matrices are connected with Urysohn spaces:

\begin{thm}\label{t:U MATRIX U PROPERTY}
Suppose $(M,d)$ is a polish space, $(x_n)_{n=1}^\infty$ a dense sequence. The
matrix $r=(d(x_i,x_j))_{i,j=1}^\infty$ is universal if and only if $M$ is
Urysohn.
\end{thm}

\begin{proof}
Suppose $M$ is an Urysohn space. Fix $n\in\mathbb N$, $r_n =
(d(x_i,x_j))_{i,j=1}^n$ and choose an admissible vector $(a_1,a_2,\ldots,a_n)
\in \Adm(r_n)$. By the extension property, there is an $x\in M$ such that
\[
d(x,x_i)= a_i, \qquad i=1,2,\ldots ,n.
\]
Since the $x_k$ are dense in $M$, the property (\ref{e:U MATRIX}) is evident.

Conversely, suppose the distance matrix $(d(x_i,x_j))$ is universal. Choose a
finite subset $F=\{y_1, y_2, \ldots, y_n\}\subseteq  M$, and an admissible
vector $(a_1,a_2,\ldots, a_n) \in \Adm(r_n)$, where $r_n=
(d(y_i,y_j))_{i,j=1}^n$. Fix $\varepsilon>0$. Since the $x_k$ are dense, and
since (\ref{e:U MATRIX}) holds, there are points $x_{k_1},\ldots, x_{k_n}$ and
$x=x_{k_{n+1}}$ such that
\[
|x_{k_i}-y_i|<\varepsilon/2, \qquad i=1,2,\ldots,n
\]
and
\[
|d(x,x_{k_i})-a_i|<\varepsilon/2, \qquad i=1,2, \ldots, n.
\]
Therefore $|d(x,y_i)-a_i|<\varepsilon$, $i = 1,\ldots, n$, which proves the
$\varepsilon$-extension property of $M$. Since $\varepsilon>0$ was chosen
arbitrarily, we can conclude by Lemma \ref{l:EPSILON EXTENSION} that $M$ has
the extension property, hence it is a universal and homogeneous space.
\end{proof}


It is not difficult to show that \emph{the distance matrix
$r=(d(x_i,x_j))_{i,j=1}^\infty$ is weakly universal, if and only if $(M,d)$ is
weakly universal in the following sense: To any finite metric space $(F,d_F)$,
and any $\varepsilon>0$, there exists an $\varepsilon$-isometry $\iota$ which
maps $F$ into $M$.} Thus every universal matrix is also weakly universal. The
converse is not true: there exists weakly universal matrices (spaces), which
are not universal matrices (spaces, resp.). For example consider a sequence of
metric spaces
\[
(F_1,d_1),(F_2,d_2), (F_3,d_3), \ldots,
\]
such that their corresponding distance matrices
\[
r_1, r_2, r_3, \ldots
\]
enumerate all rational distance matrices of all dimensions. Now consider the
disjoint sum $(M,d)$ of the spaces $(F_i, d_i)$, i.e. $M=\bigcup_i F_i$ and
\[
d(x,y)=
\begin{cases}
  d_i(x,y) & \text{for }x,y\in F_i \\
  \frac{\diam(F_i)+\diam(F_j)}{2} & \text{for } x\in F_i, y\in F_j
\end{cases},
\]
where $\diam(F_i) = \max_{x,y\in F_i} d_i(x,y)$. The space $(M,d)$ is complete,
since it consists of isolated points only, separable, by construction weakly
universal but not every finite metric space can be embedded into $M$.

Before we can start with the construction of the Urysohn space, we need another
auxiliary lemma, which proof we leave to the reader.


\begin{lem}\label{l:LIFT DENSE SEQU CONES}
Suppose $A_n$,$A_m$ are convex cones in $\mathbb R^n$, $\mathbb R^m$
respectively ($n>m$), such that $\pi A_n= A_m$, where $\pi:\mathbb
R^n\rightarrow \mathbb R^m$ is the projection onto the first $m$ coordinates.
If $(a_i)_{i=1}^\infty$ is a sequence dense in $A_m$, then we can find vectors
$(a_i')_{i=1}^\infty$ dense in $A_n$ such that
\[
\pi a_i' = a_i, \qquad i\in\mathbb N.
\]
\end{lem}

\emph{Now we are able to construct a Urysohn space, or equivalently a universal
matrix}: To do so, we define a metric $d$ on the set of naturals $\mathbb N$ as
follows. Choose a sequence $(a_n^{(1)})_{n=2}^\infty$ dense in $\mathbb R_+$
and define
\[
d(1,n) = a_n^{(1)}, \qquad i=2,3,\ldots
\]
Note that $d$ already defines a metric on the two-point set $\{1,2\}$. Set
$r_1=(0)$, and let $r_2$ be the distance matrix which corresponds to the
two-point space $(\{1,2\},d)$. Since the projection $\pi:\mathbb R^2\rightarrow
\mathbb R$, $(x_1,x_2)\rightarrow x_1$ maps $\Adm(r_2)$ onto $\Adm(r_1)=\mathbb
R_+$, Lemma \ref{l:LIFT DENSE SEQU CONES} shows that there is a sequence of
numbers $(a_n^{(2)})_{n=3}^\infty$ such that
\[
\Adm(r_2)= \text{closure }\{\begin{pmatrix}a_n^{(1)}
\\a_n^{(2)}\end{pmatrix}: n\ge 3\}.
\]
Define
\[
d(2,n)= a_n^{(2)}, \qquad n=3,4,\ldots
\]
This defines already a metric on the three-point set $\{1,2,3\}$. Now let $r_3$
be the distance matrix corresponding to $(\{1,2,3\},d)$. Again, we can find a
sequence of non-negative numbers $(a_n^{(3)})_{n=4}^\infty$ such that
\[
\Adm(r_3)= \text{closure }\{\begin{pmatrix}a_n^{(1)} \\a_n^{(2)} \\
a_n^{(3)}\end{pmatrix}: i\ge 4\}.
\]
Define
\[
d(3,n)= a_n^{(2)}, \qquad n \ge 4.
\]
Continuing in this manner, we obtain a metric $d$ on $\mathbb N$ such that by
construction the matrix $(d(i,j))_{i,j=1}^\infty$ is universal. Therefore the
completion of $(\mathbb N, d)$ is a Urysohn space. We have proved the main
theorem of this section:

\begin{thm}[Urysohn]\label{t:U SPACE EXISTENCE}
There exists a polish space $(\mathfrak  U,d)$ which is universal and
homogeneous. By Theorem \ref{t:U SPACE IS UNIQUE} this space is determined
uniquely up to isomorphism.
\end{thm}

{\it Remark.} For $\alpha>0$, restricting ourselves to bounded distance
matrices $r\in [0,\alpha]^{\mathbb N\times \mathbb N}$, one similarly can
construct a homogeneous polish space $\mathfrak U_\alpha$ of diameter $\alpha$
which is universal in the following sense: {\it Every polish space of diameter
$\leq \alpha$ can be embedded isometrically into $\mathfrak U_\alpha$.} Such a
space is also unique up to isometric equivalence.




\subsection{Some Properties of the Urysohn space}
\label{s:PROPERTIES URYSOHN}

We now consider topological properties of the Urysohn space.

\begin{thm}\label{t:u:COMPACTA CONTRACTIBLE}
Any continuous map $f:C\rightarrow \mathfrak U$ from a compact metric space
$(C,d_C)$ into the Urysohn space $(\mathfrak U,d)$ is contractible (=homotopic
to the constant map).
\end{thm}
\begin{proof}
Consider the image $f(C)$ as a subspace of $\mathfrak U$. This is a compact
metric space and we therefore can find a isometric embedding
$\iota:f(C)\rightarrow B$ into a separable Banach space $(B,\|\,.\,\|)$ (as was
shown at the beginning of this section). By the extension property, the
isometry $\iota^{-1}:\iota(f(C))\rightarrow C$ can be extended to an isometry
$J: B\rightarrow \mathfrak U$:
\begin{equation*}
\begin{CD}
(C,d_C)    @>{f}>> (\mathfrak U,d) \\
@V{g=\iota\circ f}VV            @V{id}VV \\
(B,\|\,.\,\|)     @>{J}>>    (\mathfrak U,d)
\end{CD}
\end{equation*}
Since the mapping $g:C\rightarrow B$ is contractible, $f$ is also contractible.
\end{proof}

\begin{thm}\label{t:U SPACE HOMOTOPY TRIVIAL}
The Urysohn space $(\mathfrak U,d)$ is path-wise connected. Moreover all
homotopy groups $\pi_n$ (and therefore all homology groups) are trivial.
\end{thm}
\begin{proof}
That $\mathfrak U$ is path-wise connected is an immediate consequence of the
extension property: The mapping which maps two different numbers $a,b\in\mathbb
R$ to two different points $x,y\in \mathfrak U$ is an isometry, provided we
have chosen the proper norm on $\mathbb R$, and can therefore be extended to an
isometric embedding of the whole interval $[a,b]$ into $\mathfrak U$.

By Theorem \ref{t:u:COMPACTA CONTRACTIBLE}, any continuous mapping
$f:S^{n}\rightarrow \mathfrak U$ from the $n$-dimensional sphere into
$\mathfrak U$ is contractible, hence all homotopy groups of $U$ are trivial.
\end{proof}

{\bf PROBLEM}

Is Urysohn space $\mathfrak U$ contractible or not?


Consider the group $\Aut(\mathfrak U)$ of isometries of the Urysohn space,
equipped with the topology of pointwise convergence. In \cite{USP01}, the
author shows that $\Aut(\mathfrak U)$ is a universal topological group with a
countable base, i.e. every Hausdorff topological group with a countable base is
isomorphic to a subgroup of $\Aut(\mathfrak U)$. Apart from that, not very much
is known about this group.

{\bf PROBLEM}

To describe algebraic or topological properties of the Isometry
Group $\Aut(\mathfrak U)$ of the Urysohn space $\mathfrak U$.


We continue with miscellaneous considerations about the Urysohn space.

\begin{thm}\label{t:u:UTIMESU}
Consider the product $\mathfrak U^2= \mathfrak U\times \mathfrak U$ equipped
with the maximum metric $d_\infty((x,y),(x',y'))= \max \{ d(x,x'), d(y,y')\}$.
The product $\mathfrak U^2$ is separable and universal, but not isometrically
isomorphic to $\mathfrak U$
\end{thm}

\begin{proof}
We show that $(\mathfrak U^2,d_\infty)$ does not satisfy the extension
property: Choose a subspace $F_1=\{x_1,x_2,x_3\}\subseteq \mathfrak U$ with
distance matrix
\[
r_{F_1}=
\begin{pmatrix}
 0 & 1 & 1/4 \\
 1 & 0 & 1 \\
 1/4 & 1 & 0
\end{pmatrix}.
\]
and a subspace $F_2=\{y_1,y_2,y_3\}\subseteq \mathfrak U$ with distance matrix
\[
r_{F_2}=
\begin{pmatrix}
 0 & 1/4 & 1 \\
 1/4 & 0 & 1 \\
 1 & 1 & 0
\end{pmatrix}.
\]
Let $F\subseteq \mathfrak U^2$ be the subspace which consists of the points
$(x_i,y_i)$, $i=1,2,3$. All edges of this triangle have length one, i.e. the
distance matrix of $F$ is
\[
r_F=
\begin{pmatrix}
 0 & 1 & 1 \\
 1 & 0 & 1 \\
 1 & 1 & 0
\end{pmatrix}.
\]
The vector $(1/2,1/2,1)\in\Adm(r_F)$, but, by equation (\ref{e:ADMISSIBLE
CONE}), any vector $(b_1,b_2,b_3)\in \Adm(r_{F_j})$, $j=1,2$, with $b_j\leq
1/2$ must have $b_3 < 1$. Thus there is no point $(a,b)\in \mathfrak U^2$ such
that
\[
(d((a,b),(x_i,y_i)))_{i=1}^3 = (1/2,1/2,1).
\]
\end{proof}

\begin{rem}
The same argument as in the proof of Theorem \ref{t:u:UTIMESU} also works out
for the product $\mathfrak U\times [0,1]^2$ (equipped with the maximum metric).
Hence $\mathfrak U\times [0,1]^2$ and therefore $\mathfrak U\times [0,1]$ (also
equipped with the maximum metric) is not isometrically isomorphic to $\mathfrak
U$.
\end{rem}

\emph{For any $\alpha >0$, $(\mathfrak U,\alpha d)$ also has the extension
property and is therefore isometrically isomorphic to $(\mathfrak U,d)$}:
Suppose $\iota: C\rightarrow \mathfrak U$ is an isometric embedding of a
compact space $(C,d_C)$ into $(\mathfrak U,\alpha d)$, and suppose $(C',d_C')$
is a one-point extension of $(C,d_C)$. By
\[
\alpha d(\iota x,\iota y) = d_C(x,y), \qquad x,y\in C
\]
the same $\iota$ embeds $(C, \alpha^{-1}d_C)$ isometrically into $(\mathfrak
U,d)$. We thus can find an isometry $\iota':(C',\alpha^{-1}d_{C'}) \rightarrow
(\mathfrak U,d)$ which extends $\iota$. By the same argument as before,
$\iota'$ is also an isometric embedding of $(C',d_{C'})$ into $(\mathfrak
U,\alpha d)$.




\subsection{The set $\mathcal U$ of universal matrices}

As for incidence matrices in Section \ref{s:UNIVERSAL AND RANDOM GRAPHS}, the group
$S^\infty$ of permutations on $\mathbb N$ acts via formula
(\ref{e:gr:PERMUTATION OF MATRIX}) also on the cone of all distance matrices.
Unlike to the case of graphs may not regard $\Aut(\mathfrak U)$ as a
subgroup of $S^\infty$.

\begin{thm}\label{t:U MATR DENSE GDELTA}
The set $\mathcal U$ of all universal distance matrices is
$S_\infty$-invariant, i.e. $ g\mathcal M g^{-1} = \mathcal M$ for every $g\in
S_\infty$. Moreover, it is a dense $G_\delta$-subset of $\mathcal R$.
\end{thm}
\begin{proof}
>From the remark which follows Lemma \ref{l:ADMISSIBLE CONES} it is obvious that
a distance matrix $r=(r_{ij})_{i,j=1}^\infty$ is universal if and only if for
every finite subset $\{k_1, k_2, \ldots, k_n\}\subseteq \mathbb N$,
\[
\Adm((r_{k_i k_j})_{i,j=1}^n)= \text{closure } \{ (r_{k_1k}, r_{k_2k}, \ldots,
r_{k_nk}) : k= n, n+1, \ldots \}.
\]
Thus $\mathcal M$ is $S_\infty$-invariant.

By the above construction, there is at least one universal matrix $r\in\mathcal
R$. Its orbit $S_\infty r$ dense in $\mathcal R$, and consists of universal
matrices only. Hence $\mathcal U$ is dense in $\mathcal R$. For fixed $n,m\in
\mathbb N$ and $\alpha>0$, the function
$$
\varepsilon_{n,m,\alpha}: r=(r_{ij})\mapsto \sup_{a\in\Adm(\pi_n r),
\|a\|\leq\alpha} \min_{n<k\leq m} \|a-(r_{ik})_{i=1}^n\|,
$$
where $\|\:\cdot\:\|$ is the maximum norm on $\mathbb R^n$, is a continuous map
$\mathcal R \rightarrow \mathbb R$. By definition,
$$
\mathcal U= \bigcap_{k\in N}\bigcap_{n\in\mathbb N}\bigcap_{\alpha\in \mathbb
N}\bigcup_{m>n}[\varepsilon_{n,m,\alpha}<\frac{1}{k}]
$$
is therefore a $G_\delta$-set.
\end{proof}

We will now give a probabilistic proof of the existence of the Urysohn space in
the spirit of Erd\"os Theorem \ref{t:gr:ERDOS}. This procedure will also give
an idea of a random metric space. To emphasize the principle idea we only give
an intuitive but not formally rigorous presentation:

Starting with a single point we successively construct a random sequence
$(M_n,d_n)$ of $n$-point metric spaces (or $n$-dimensional distance matrices
$r_n$) ,
\[
(M_0,d_0)\subseteq(M_1,d_1)\subseteq (M_2,d_2) \subseteq \ldots \subseteq
(M_n,d_n) \subseteq \ldots,
\]
as follows: to a given $n$-point metric space $M_n$ (with distance matrix
$r_n\in \mathcal R_n $) we randomly add a $n+1$-th point choosing the distances
between the new and the previous points (= admissible vector $\in\Adm (r_n)$)
according to a certain (conditional) probability distribution $\mu_{r_n}$ (this
is a probability measure on $\Adm(r_n)$).

To ensure that, with probability one, the so obtained space is Urysohn (or
equivalently, its distance matrix is universal), we choose the distributions
$\mu_r$ as follows: On the one-dimensional admissible cone $\mathbb R^+$ we
take any fixed measure $\mu_\emptyset$ which supports the whole half-line (i.e.
to any open subset $B$ of $\mathbb R^+$, $\mu_\emptyset(B)>0$). Now we continue
inductively via the following procedure:

Suppose we had constructed all the measures $\mu_{r_n}$ for all one-dimensional
distance matrices $r_n\in \mathcal R_n$ such that its support $\supp \mu_{r_n}$
is always the whole admissible cone $\Adm(r_n)$. For any $n+1$-dimensional
distance matrix $r_{n+1}\in \mathcal R_{n+1}$, recall that
\[
\Adm(\pi_n r_{n+1}) \stackrel{\pi_n}\leftarrow \Adm(r_{n+1}),
\]
where the projection is onto. Now in $\Adm(r_{n+1})$ we take any measure
$\mu_{r_{n+1}}$ such that $\pi_n \mu_{r_{n+1}} = \mu_{r_n}$ and
\[
\supp \mu_{r_{n+1}} = \Adm(r_{n+1})
\]
Such a measure does exist, but we won't give the detailed construction here.

On the cone $\mathcal R_1$ we put a probability measure $\mu_1$, $\mu_1 =
\mu_\emptyset$. Using the measures $\mu_{r}$, we define probability measures
$\mu_n$ on $\mathcal R_n$ via
\[
\mu_n( \:.\: | \pi_{n-1} r ) = \mu_{\pi_{n-1} r} (\tilde \pi_{n-1} \:.\:),
\]
where $\tilde \pi_{n-1} (r_{ij})_{i,j=1}^n = (r_{1,n}, r_{2,n}, \ldots,
r_{n-1,n})$. Note that $\tilde \pi_{n-1}$ maps each matrix $r\in \mathcal
R_{n}$ into the the admissible cone $\Adm(\pi_{n-1} r)$, hence this definition
makes sense.

The so constructed family $\mu_n$ is consistent under projection,
\[
\pi_m \mu_n = \mu_m,    \qquad m\leq n,
\]
hence it defines a probability measure $\mu$ on $\mathcal R$. By construction
the probability that the random distance matrix is universal equals one, thus
\[
\mu(\mathcal U) = 1.
\]

\begin{rem}
To assure that, with probability one, the random distance matrix is universal,
it is certainly not necessary that the conditional distributions are consistent
under projections, i.e.
\[
\mu_{\pi_m r} = \pi_m \mu_r,   \qquad r\in \mathcal R_n, m\leq n,
\]
as assumed in the discussion above (see \cite{VERSH01}). Anyway, note that the
measure $\mu$ in the above construction is generically not
$S_\infty$-invariant.
\end{rem}








At the end of this section we gather

\begin{itemize}
\item (cf. Theorem \ref{t:U SPACE EXISTENCE})
  There exists polish space $(\mathfrak U,d)$ which is Urysohn, i.e. universal and homogeneous.
  This space is unique up to isometric equivalence.
\item (cf. Theorem \ref{t:U SPACE HOMOTOPY TRIVIAL})
  The Urysohn space $(\mathfrak U,d)$ is path-wise connected.
  All homotopy groups $\pi_n$ of $(\mathfrak U,d)$, and therefore all homology groups, are trivial.
\item Open question: Is $(\mathfrak U,d)$ contractible?
\item Open question: Find familiar spaces to which $(\mathfrak U,d)$ is homeomorphic.
\item (cf. Theorem \ref{t:U MATRIX U PROPERTY}) A space is Urysohn if and only if its distance
  matrix of any (= some) everywhere dense countable subset is universal.
\item(cf. Theorem \ref{t:U MATR DENSE GDELTA})
  The set of all universal matrices is dense $G_\delta$ subset of $\mathcal R$,
  which is invariant under finite  permutations.
\end{itemize}

\subsection{Random Metric Space}

 Here we will give a sketch of the construction of the random metric
space. For this we will define a probability measure on the space
of distance matrices which is concentrated on the subset of universal
matrices. This construction is analogue to the same construction
of the random graph but more complicate because it is not possible
to use independence of entries (triangle inequality is the obstruction
to that).
  Choose some measure $\gamma$ on the half line ${\bf R}_+$ which has full support
(e.g. gaussian measure on the half line) and let entries
$$r_{1,2}, \dots r_{1,n}, \dots$$
are i.i.d with distribution $\gamma$.
We will define the conditional distribution of the element of distance
matrix $r_{m,n}, (n > m)$ under the condition that all the elements
with indices $(i,k)$ are fixed where $1 \leq i \leq m-1, 1 \leq j \leq n$

  Then the conditional distribution of the element $r_{m.n}$ is uniform
distribution on the interval $[a,b]$ where
$$ a=\max_{i=1, \dots m-1} |r_{i,m}-r_{i,n}|; \mbox
b=\min_{i=1 \dots m-1} |r_{i,m}+r_{i,n}|$$

  Lemma 2.10 shows that $a \leq b$ so interval $[a,b]$ is not empty
and we can by induction to define the distributions of all entries
of the distance matrix. Remark that distribution of the element
$r_{m,n}$ actually depends on the distribution of $r_{i,m}$ and $r_{i,n}$
for $i= 1, \dots m-1$ only. As result we had define a probability
measure $\mu_{\gamma}$ on the space of distance matrices with parameter
-- measure $\gamma$ on the halfline.

\begin{thm}
For any absolutely continuous measure $\gamma$  on the half line  $\bf R$
with positive density the set of universal distance matrices
has measure 1 with respect to the measure $\mu_{\gamma}$.
In another word. Let $r$ is a random distance matrix with distribution
$mu_{\gamma}$ in the space of all distance matrices; then
a metric space which is completion of the set of naturals $\bf N$
under the distance matrix $r$ is the Urysohn space with probability 1.
\end{thm}

 The proof uses the law of large numbers in the special situation but
we will not prove the theorem here. As in the case of graphs
we emphasize that the last fact is valid for very reach set of
measures on the space of distance matrices, -- we gave only one simple
example which is in a sense similar to the example with independent
entries for the graphs. Namely, as in paragraph 1 for the case of graph,
the set of probability measures on the space of distance matrices
for which subset of universal matrices has a full measure
is again everywhere dense $G_{\delta}$ subset
of the space of all probability measures with weak topology.

\bigskip

ACKNOWLEDGEMENT.

   Author is grateful to U.~Haboeck and Yu.~Yakubovich for
the help in the preparation of the manuscript.

\bigskip

%\bibliographystyle{amsplain}
%    \setlength{\baselineskip}{0.9 \baselineskip}
%    \bibliography{uli}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{BOG01}
S.~A.~Bogaty\u\i, \emph{Metrically homogeneous spaces. (russian. russian
  summary)}, Uspekhi Mat. Nauk \textbf{57} (2002), no.~2(344), 3--22,
  translation in Russian Math. Surveys 57 (2002), no. 2, 221--240.

\bibitem{CAM01}
P.~J.~Cameron, \emph{The random graph}, The mathematics of Paul Erd\"{o}s, II,
  333--351, Algorithms Combin., 14, Springer, Berlin, 1997.

\bibitem{DUG}
J.~Dugundji, \emph{Topology}, Allyn and Bacon, Boston, Mass., 1966.

\bibitem{ERD01}
P.~Erd\"{o}s and A.~R\'enyi, \emph{Asymetric graphs}, Acta. Math. Acad. Sci.
  Hungar \textbf{14} (1963), 295--315.

\bibitem{HUHU01}
G.~E.~Huhunai\v{s}vili, \emph{On a property of {Uryson's} universal metric
  space.(russian)}, Dokl. Akad. Nauk SSSR (N.S.) \textbf{101} (1955), 607--610.

\bibitem{KATE01}
M.~Kat\v{e}tov, \emph{On universal metric spaces}, General topology and its
  relations to modern analysis and algebra, VI (Prague,1986), pp. 323--330,
  Heldermann, Berlin, 1988.

\bibitem{LIND01}
J.~Lindenstrauss, G.~Olsen, and Y.~Sternfeld, \emph{The {Poulsen} simplex},
  Ann. Inst. Fourier (Grenoble) \textbf{28} (1978), no.~1,vi, 91--114.

\bibitem{LUSK01}
W.~Lusky, \emph{The {Gurarij} spaces are unique}, Arch. Math. (Basel)
  \textbf{27} (1976), no.~6, 627--635.

\bibitem{PHELP01}
R.~R.~Phelps, \emph{Lectures on {Choquet's Theorem}}, Van Nostrand Mathematical
  Studies, vol.~7, Van Nostrand Company, Canada, 1966.

\bibitem{URY01}
P.~S.~Urysohn, \emph{Sur un espace metrique universel}, Bull. Sci. Math.
  \textbf{51} (1927), 1--38.

\bibitem{USP01}
V.~V.~Uspenskij, \emph{On the group of isometries of the {Urysohn} universal
  metric space}, Comment. Math. Univ. Carolin. \textbf{31} (1990), no.~1,
  181--182.

\bibitem{VERSH01}
A.~M.~Vershik, \emph{Random and universal metric spaces}, Preprint of the Erwin
  Schr\"odinger Institute, No. 1234;  to appear in Fundamental
Mathematics Today, publ. by MCCMI (Moscow), 2003.

\bibitem{VERSH02}
A.~M.~Vershik, \emph{Classification of
measurable functions of several arguments and invariantly
distributed random matrices}, Funct. Anal. Appl. \textbf{36} (2002), 
no.~2, 12--27 

\bibitem{VERSH03}
A.~M.~Vershik, \emph{Random matrix space is Urysohn space},
Dokl. Russian Acad. of Sci. \textbf{386} (2002), no.~6.

\end{thebibliography}

\end{document}
