
\documentclass[12pt]{article}
\usepackage{amssymb}
\hoffset =-0.7in
\voffset =-0.5in
\textheight =9in
\textwidth =6.5in
\def\baselinestretch{1.2}
\renewcommand{\arraystretch}{1.0}

%---------------------------------------------------------------------
%DEFINITIONS
\def\be{\begin{equation}}
\def\ee{\end{equation}}
\def\disp{\displaystyle}
\def\foot{\footnotesize}
\def\scri{\scriptsize}
\def\ve{\varepsilon}
\def\th{\theta}
\def\lam{\lambda}
\def\publogo{\hfil}
\def\R{{\sf I\kern-.2em R}}
\def\N{{\sf I\kern-.2em N}}
\def\C{\kern.1em{\raise.47ex\hbox{$\scriptscriptstyle
$}}\kern-.40em{\sf C}}
\def\Z{{\sf Z\kern-.32em Z}}
\def\Arr{\Longrightarrow}
\def\hat{\widehat}
\def\arr{\longrightarrow}
\def\Top{\text{\rm Top}\,}
\def\Lie{\text{\rm Lie}\,}
\def\deg{\text{\rm deg}\,}
\def\hat{\widehat}
\def\be{\begin{equation}}
\def\ee{\end{equation}}
\def\disp{\displaystyle}
\def\foot{\footnotesize}
\def\scri{\scriptsize}
\def\ve{\varepsilon}
\def\th{\theta}
\def\lam{\lambda}

\newtheorem{theorem}{\noindent Theorem}
\newtheorem{lemma}{\noindent Lemma}
\newtheorem{definition}{\noindent Definition}
\newtheorem{corollary}{\noindent Corollary}
\newtheorem{conjecture}{\noindent Conjecture}
\newtheorem{statement}{\noindent Statement}
\newtheorem{remark}{\noindent Remark}
\newcommand{\proof}[1]{{\bf Proof.} #1 \rule{2mm}{2mm} \medskip}
\newcommand{\Proof}[1]{{\bf Proof.} #1 \rule{2mm}{2mm} \medskip}
%\renewcommand{\proof}{äÏËÁÚÁÔÅÌØÓÔ×Ï}
%\newcommand{example}

\begin{document}

\begin{titlepage}

\begin{center}
{\LARGE \bf Random metric spaces and the universal Urysohn space.}
 \bigskip
\bigskip


{\large A.~M.~VERSHIK $^{1}$}
\bigskip

{\sl
$^{1}$ Steklov Institute of Mathematics at St.~Petersburg,\\
Fontanka 27,
119011 St.~Petersburg, Russia.\\
and
\sl MSRI (Berkeley).

Partially supported by RFBR, grant 02-01-00093, (Research at MSRI supported also 
by CDRF, grant RMI-2244).}
\end{center}
\bigskip
\centerline{06.05.02.}
\bigskip
\begin{center} ABSTRACT
\end{center}

   We introduce a model of the set of all Polish  (=separable complete metric)
   spaces which is the cone $\cal R$ of distance matrices, and consider the geometrical
   and probabilistic problems connected with this object. We prove that the generic 
   Polish space in the sense of this model is the so called
   universal Urysohn space which was defined by P.S.Urysohn in the 1920-th.
   Then we consider the metric spaces with measures (metric triples)
   and define a complete invariant of its - matrix distribution.
   We give an intrinsic characterization of matrix distribution and using
   the ergodic theorem give a new proof of Gromov's reconstruction theorem.
   A natural construction of a wide class of measures on the cone  $\cal R$ 
   is given and for these we show that with probability one the random Polish 
   space is again the Urysohn space. There is a tight link of these questions
   with metric classification of measurable functions of several arguments 
   and classification of the actions of infinite symmetric group (\cite{V1,V2})
   Applications to the statistical theory of metric space will follow.


\begin{center} CONTENT
\end{center}

1.The cone of the distance matrices as the set of all Polish spaces.

2.Geometry and topology of the cone of distance matrices.

3.Universal matrices and Urysohn space.

4.Matrix distribution as complete invariant of the metric triples
  and its characterization.

5.General classification of the measures of the cone
  of the distance matrices.

Bibliography.

\end{titlepage}
\newpage


\section{Introduction: The cone $\cal R$ of distance matrices as a set of all 
the Polish spaces}

Consider the set of all infinite real matrices
 $${\cal R} =\{\{r_{i,j}\}_{i,j=1}^{\infty}:  r_{i,i}=0,\,r_{i,j}\geq 0,\,
 r_{i,j}=r_{j,i},\,  r_{i,k}+r_{k,j}\geq r_{i,j},{\rm \,\,for\,\,} i,j,k=1,2, \dots\}$$

We will call the elements of $\cal R$  {\it distance matrices}.
Each such matrix defines a semi-metric on the set of natural numbers $\bf N$.
(We allow zeros away from the principal diagonal, so that in general  $\rho$ is  only a
semi-metric). If matrix has no zeros away from the principal diagonal we will call
it {\it a proper distance matrix}.

The set of all distance matrices is a weakly closed convex cone in the
real linear space $Mat_{\bf N}({\bf R})={\bf R^N}^2$  endowed with the ordinary weak topology.
We always consider the cone ${\cal R}$ with this topology and will call it the
cone of distance matrices. The subset of proper distance matrices is everywhere dense open
set in ${\cal R}$.

If the distance matrix $r$ is proper then the completion of
metric space $({\bf N},r)$ which is a complete separable metric (=Polish)
($X_r,\rho_r)$ with distinguish everywhere dense countable set
$\{x_i\}$ which is image of natural numbers in the completion.
 A general distance matrix
(with possible zeros away from the diagonal)
defines on the set of natural numbers the structure of
{\it semi-metric space}. By the completion of $({\bf N},r)$ in this case
we mean the completion of the corresponding quotient metric space of the classes
of points with zero distances. For example zero matrix is a distance matrix
on the natural numbers  with zero distances between each two numbers
and its ``completion'' is the singleton metric space. Thus finite metric spaces also could
be considered in this setting.

Suppose now that we have some  Polish  space $(X, \rho)$,
and the set $\{x_i\}_{i=1}^\infty$ is an ordered everywhere dense countable subset in it.
Defining the matrix $r=\{r_{i,j}\} \in \cal R$ by
$r_{i,j}=\rho(x_j,x_j), i,j =1\dots$  we obtain a proper distance matrix.
which we interpret as a {\it metric on the set of natural numbers}.
Clearly this distance matrix contains complete information about original
space $(X,\rho)$, because  $(X,\rho)$ is the canonical
completion of the set of naturals with this metric.
Any invariant property of the metric space such as
topological and homological etc. could be expressed in terms of the
distance matrix for any dense countable subsets of that space. Some of them are
easy to express explicitly (say, compactness) another are more subtle (like dimension).

We will study the theory of Polish spaces from this point of view and consider
the cone of distance matrices ${\cal R}$ as {\it the universe of
all separable complete metric spaces} with a fixed dense countable subset.
We can view $\cal R$ as a ``fibering'', whose base is
the collection of all individual Polish spaces, and the fiber over a given space is
the set of all countable ordered dense subsets in this metric
space. Because of the universality of the Urysohn space $\cal U$ (see below) the set of all
closed subsets of $\cal U$  could be considered as a base of this bundle.
The space $\cal R$  plays the role of "tautology fibration" over
the space of classes of isometric Polish spaces, analogously to common
topological constructions of tautology fiber bundle.

The question arises: what kind of distance matrix is ``generic''
in the sense of the topology of the $\cal R$. One of the main results (section 3)
is the Theorem 1, which is a generalization of Urysohn's results
and which asserts that Urysohn space is generic  (=dense $G_{\delta}$ set in $\cal R$)
in this sense. The main tool is the notion of universal distance matrices,
in indirect way it was actually used by P.S.Urysohn in his pioneer paper \cite{U}.
We give a new version of his main results and a new proof in the section 3.

Introduce a partition $\xi$ of the $\cal R$ into the equivalence classes of 
distance matrices which produce an isometric completions.
The quotient space over the partition $\xi$ (or space of the classes of equivalence)
is the set of the {\it isometry classes} of the Polish spaces.
As was conjectured in  \cite{V1} and proved in the paper \cite{CK01} the quotient
by this equivalence relation is not "smooth", in
the sense that it has no good Borel or topological structure and thus
the problem of the classification of the Polish spaces up to
isometry is ``wild''.  At the same time the restricted
problem for the case of compact Polish spaces is smooth (see \cite{G})
and the space of all isometry classes of compact metric spaces
has a natural topology. Surprisingly, if we consider the problem
of classification of the Polish spaces with measure (metric triples)
up-to isometry which preserves the measures, this classification is ``smooth'',
and we will consider in details a complete invariant (``matrix distribution'')
of the metric triples (section 4). One direction -the completeness of invariant -
was proved in the book by M.Gromov \cite{G}; we will give another proof
of his reconstruction theorem based on the ergodic methods and a new description
of the invariant. Then we prove a theorem about precise description of the matrix
distribution of the metric triples (section 5) as a measure on $\cal R$.
 The section 2 is devoted to the elementary geometry of the space $\cal R$
which we use along all the paper and especially in the section 6 in which we
consider the various measures on the cone $\cal R$ and method of the construction
of its. The measure on the above cone is nothing more than random metric on the
set of naturals. Thus we can construct a ``random'' metric space as the result
of completion of the random metric on the natural numbers. In this way we prove
that loosely speaking a randomly constructed Polish space with very natural
procedure gives us with probability 1 again this remarkable Urysohn space.
One of the previous analog of such a theorems is the theorem due to
P.Erd{\"o}s and A.R\'{e}nyi about random graphs \cite{ER,Ca}.
The results of the paper about the  genericity of the Urysohn space
(Theorem 1) and probabilistic typicality of its (Theorem 7) show
that coincideness these two properties of the universal objects
in the category of the Polish spaces (as well as in the more simple category of the
infinite graphs) perhaps has more a general and deep feature
and is true in the other categories.

\newpage
\section{Geometry and topology of the cone ${\cal R}$}
\subsection{Convex structure}

Analogously to $\cal R$ let us define the finite dimensional 
cone ${\cal R}_n$ of distance matrices
of order $n$. Cone ${\cal R}_n$ is a polyhedral cone
inside the positive orthant in $ Mat_n({\bf R})\equiv {\bf R}^{n^2}$.
Denote by ${\bf M}^s_n({\bf R})\equiv {\bf M}^s_n$ of the space
{\it symmetric matrices with zeros on the  principal diagonal}.  We have
${\cal R}_n \subset {\bf M}^s_n$ and the latter space is evidently
the linear hull of the cone: span$({\cal R}_n)={\bf M}^s_n$, 
because the interior of ${\cal R}_n$
is not empty. It is clear that $span({\cal R})\subset {\bf M}^s_{\bf N}$,
where  ${\bf M}^s_{\bf N}$ is the space of all real infinite symmetric matrices with
zero principal diagonal, but the geometry of the cone $\cal R$ is very complicate.

Each  matrix $r \in {\cal R}_n$ defines a (semi)metric
space $X_r$ on  the  of $n$-point set.

Define the projection $$p_{m,n}:{\bf M}^s_m \longrightarrow {\bf M}^s_n, m >n $$
which associates with the matrix $r$ of order $m$ its NW-corner of order $n$.
The  cones ${\cal R}_n$ are consisted with projection i.e. 
$p_{n.m}: p_{m,n}({\cal R}_m)={\cal R}_n$
The projection $p_{n,m}$ are natural extends to the space of infinite
symmetric matrices with zero diagonal - $p_n: M^s_{\bf N}  \longrightarrow M^s_n({\bf R})$
and $p_n$ also preserve the cones: $p_n({\cal R})={\cal R}_n$.
It is clear that ${\cal R}$ is the inverse limit as topological space (in weak topology)
of  the system $({\cal R}_n,\{p_n\})$.
We will omit the first index and write $p_{N,n}=p_n$.

An important but evident property of the cones ${\cal R}_n$
is its invariance under the action of symmetric group  $S_n$
with simultaneous permutations of the rows and columns of the
matrices.

Let us consider a geometrical structure of ${\cal R}_n$ and ${\cal R}$.

It is interesting to describe the extremal rays (in the sense
of convex geometry)
of the convex polyhedral cone ${\cal R}_n, n=2, \dots, \infty$.
(for $n=1$ the cone is trivial: ${\cal R}_1=\{0$\}).

This is well-known problem - see \cite{DL, Av} and list of literature there.
Recall that an extremal ray $L$ of the convex cone $K$ is a half-line
($L=\{\lambda \cdot l:\lambda \geq 0\} \subset K$)
such that if $l=a\cdot l_1+b\cdot l_2; a,b>0; l\in L, l_1,l_2 \in K$,
then $l_1,l_2 \in L$.

Each extremal ray in ${\cal R}_n, n \leq 4$ is of the type
$\{\lambda \cdot l: \lambda \geq 0\}$,
where $l$ is a symmetric $0-1$-
distance matrix which corresponds to the semi-metric space
whose quotient metric space has just two points. 
For $n \geq 5$ there are extremal rays of other type.

The complete description of the set extremal rays is rather difficult
and very interesting combinatorial problem. The most important question for us
concerns to the asymptotic properties of cone ${\cal R}_n$ and especially
description of the set of extremal rays of the infinite dimensional 
cone ${\cal R}$. It happens that this set is every dense $G_{\delta}$-set in
${\cal R}$ and some of so called universal distance matrices (see par 3.)
are extremal. This is in concordance with the estimation in \cite{Av} 
of the numbers of extremal rays of ${\cal R}_n$ which grows very rapidly.
The algebro-geometric structure and stratification
of the cones ${\cal R}_n$  as semi-algebraic sets.
are also very intriguing.
In order to clarify topological and convex structure of the cones ${\cal R}_n$ 
we will use an {\it inductive description} of these cones and
will study it in the next subsection.


\subsection{Admissible vectors and structure of the $\cal R$}

Suppose $r=\{r_{i,j}\}_1^n$ is a distance matrix of order $n$ ($r \in {\cal R}_n$),
choose a vector $a \equiv \{a_i\}_{i=1}^n \in {\bf R}^n$
such that if we attaching to the matrix $r$ with vector $a$ as the last
column and the last row then the new matrix of order $n+1$ still belongs
to  ${\cal R}_{n+1}$. We will call such vector {\it an admissible vector}
for fixed distance matrix $r$ and denote the set of of all admissible vectors
for $r$ as $A(r)$. For given $a \in A(r)$ denote as $(r^a)$,
distance matrix of order $n+1$ obtained from  matrix $r$
adding vector $a \in A(r)$ as the last row and column.
It is clear that $p_n(r^a)=r$. The matrix $r^a$ has the form


 $$\left( \begin{array}{ccccc}
 0    &r_{1,2}& \ldots&  r_{1,n}&a_1\\
 r_{1,2} &0& \ldots &r_{2,n} &a_2 \\
 \vdots &  \vdots&
\ddots & \vdots &\vdots\\
r_{1,n}&r_{2,n}& \ldots &0  &a_n\\
  a_1&  a_2  & \ldots & a_n& 0
\end{array}\right)$$

The (semi)metric space $X_{r^a}$ corresponding to matrix $r^a$ is an extension
of $X_r$: we add one new point $x_{n+1}$ and $a_i, i=1 \dots n$ is the distance
between $x_{n+1}$ and $x_i$.
The admissibility  of $a$ is equivalent to the following set of inequalities :
vector $a=\{a_i\}_{i=1}^n$ must satisfy to the series of
triangle inequalities
for all $i,j,k=1,2 \dots n$; (matrix $\{r_{i,j}\}_{i,j=1}^n$ is fixed):
\begin{equation}
\label{trivial} |a_i-a_j|\leq r_{i,j}\leq a_i+a_j
\end{equation}

So, for given distance matrix $r$ of order $n$ the set of admissible vectors
is $A(r)=\{\{a_i\}_{i=1}^n:|a_i-a_j|\leq r_{i,j}\leq a_i+a_j, i,j=1 \dots n\}$.
It makes sense to mention that we can view on vector $a=\{a_i\}$ as on a {\it Lipshits
function} $f(.)$  on the space $X_r=\{1,2 \dots n\}$ with $r$ as a distance:
$f_a(i)=a_i$  with Lipshits constant equal $1$. This point of view
helps to consider a general procedure of the extension of the metric space.

Geometrically the set $A(r)$ can be identified with 
the intersection of cone ${\cal R}_{n+1}$ and affine subspace
which consists of matrices of order $n+1$ with 
given matrix $r$ as a NW-corner of order $n$.
It is clear from the linearity of inequalities that 
the set $A(r)$ is an
unbounded closed convex polyhedron in ${\bf R}^n$.
If $r_{i,j} \equiv 0, i,j=1 \dots n\geq 1$,
then $A(r)$ is diagonal: $A(0)=\Delta_n \equiv \{(\lambda,
\dots \lambda): \lambda \geq 0\}\subset {\bf R}^n_+$.
Let us describe the structure of $A(r)$ more carefully.

\begin{lemma}
{For each true distance matrix $r$ of order $n$
the set of admissible vectors $A(r)$
is a closed convex polyhedron in orthant ${\bf R}_+^n$, namely it is a Minkowski sum:
$$A(r)= M_r +\Delta_n,$$
where  $\Delta_n $ is the nonnegative diagonal of the
space ${\bf R}_+^n$,
 and $M_r=$ is a compact convex polytope of dimension
$n$. This polytope $M_r$ is the convex hull of extremal points 
of the polyhedron $A(r)$:   $M_r= conv(ext A(r))$ 
The set $A(r)$ is homeomorphic  to the closed half-space
of the dimension $m$
where $m$ if the geometric rank of $r$; if $r$ is proper distance matrix
then $m=n$.}
\end{lemma}

\begin{proof}
{The set $A(r) \subset {\bf R}^n$ is the intersection of finitely many closed
subspaces, evidently it does not contain straight lines, so, by a
general theorem of convex geometry $A(r)$ is a sum of the convex closed polytope
and some cone (which does contain straight lines) with the vertex at origin.
This convex polytope is the convex hull of the extremal points of convex set $A(r)$.
But this cone must be one dimensional, namely - diagonal in ${\bf R}^n$ because
if it contains any half-line different from the diagonal then
the triangle inequality is violated. The dimension of $A(r)$
depends on matrix $r$ and could be less than $n$ for some matrix $r$;
while the dimension of $M_r$ is equal to $\dim A(r)$ or to $\dim A(r)-1$.
The assertion about topological structure
of $A(r)$ follows from what was claimed above.}
\end{proof}

A simple but important property of the correspondence $r \rightarrow A(r)$ is the following
covariance.
\begin{lemma}
{ For any $r\in {\cal R}_n$ we have covariance:$A(grg^{-1})=g(A(r))$,
 where $g \in S_n$ is element of symmetric group $S_n$ which acts in a natural way
on the set of matrices (as simultaneous permutation of rows and columns), and on the 
vectors vector spaces.}
\end{lemma}

The convex structure of polytopes $M_r, A(r)$ is very interesting and seems to
have not been studied before. For dimensions higher than 3 {\it
combinatorial type}
of the polytope $M_r$ hardly depends on $r$ but for
dimension three the combinatorial type of polytopes $M_r$,
and consequently
combinatorial structure of the sets $A(r)$ is the same for
all true distances matrices $r$.
We will give the precise answer.

{\bf Example}
For $n=3$ the description of the set $A(r)$ and of its extremal
points is the following.
Let $r$ be a matrix
 $$\left( \begin{array}{ccc}
  0 & r_{1,2} & r_{1,3}\\
  r_{1,2}& 0 & r_{2,3} \\
  r_{1,3} &r_{2,3}&0 \\
\end{array}\right)$$
Denote $r_{1,2}=\alpha,  r_{1,3}= \beta,  r_{2,3}=\gamma$, then
 $r^a$ be the matrix:

 $$\left( \begin{array}{cccc}
 0    &\alpha  &  \beta & a_1\\
 \alpha &0& \gamma & a_2 \\
 \beta & \gamma &0  & a_3\\
  a_1&  a_2  &  a_3 &  0
\end{array}\right)$$

Denote $\delta=\frac{1}{2}(\alpha+\beta+\gamma)$
There are seven extremal points $a=(a_1,a_2,a_3)$ of $A(r)$ :
 the first one is a vertex which is the closest to the origin:
$(\delta-\gamma, \delta-\beta, \delta-\alpha)$,
then another three non degenerated extremal points:
$(\delta,\delta-\alpha, \delta-\gamma),
(\delta-\beta, \delta, \delta-\alpha),(\delta-\gamma, \delta-\beta, \delta)$,
and  three degenerated extremal points
$ (0, \alpha, \beta), (\alpha, 0, \gamma), (\beta, \gamma, 0)$.

If $\alpha=\beta=\gamma=1$
then those seven points are as follows

$(1/2,1/2,1/2), (3/2,1/2,1/2),(1/2,3/2,1/2),(1/2,1/2,3/2),
(0,1,1),(1,0,1)(1,1,0).$

Remark that all non-degenerated extremal points in the example
defines the finite metric spaces which can not be isometrically embedded to Euclidean space.


\subsection{Projections and isomorphisms}

Let $r$ be a distance matrix of order $N$ and $p_n(r)$ its NW-corner of order $n<N$.
Then we can define a projection
$\chi^r_n$ of $A(r)$ to $A(p_n(r)$:
$\chi^r_n:(b_1, \dots b_n, b_{n+1},\dots b_N) \mapsto (b_1 \dots b_n)$.
(We omit index $N$ in the notation of $\chi^r_n$)
The next simple lemma plays very important role for our construction.
\begin{lemma}
{Let $r\in {\cal R}_n$ be a distance matrix of order $n$. For any two vectors
$a=(a_1, \dots a_n) \in A(r)$ and  $b=(b_1, \dots b_n) \in A(r)$ there exists
a real nonnegative number $h \in {\bf R}$ such that vector
${\bar b}=(b_1,\dots b_n,h)$ satisfied $\bar b \in A(r^a)$.}
\end{lemma}

The claim of this lemma is equivalent to the assertion that for each
$r$ the projection $\chi^r_n$ defined above is an epimorphism of $A(r^a)$ to $A(r)$:
\begin{corollary}
{For each $r \in {\cal R}_n$ and $a \in A(r)$ the map
$\chi^r_{n+1,n}: (b_1, \dots b_n, b_{n+1}) \mapsto (b_1 \dots b_n)$ of  $A(r^a) \to A(r)$
is epimorphism of $A(r^a)$ onto $A(r)$ (by definition $p_{n+1,n}(r^a)=r$)}
\end{corollary}
\begin{proof}
{The assertion of Lemma as we will see, follows from the simple geometrical observation:
suppose we have two finite metric spaces
$X=\{x_1, \dots x_{n-1}, x_n\}$ with metric $\rho_1$
and $Y=\{y_1, \dots y_{n-1},y_n \}$ with metric $\rho_2$. Suppose the subspaces
of the first $n-1$ points $\{x_1, \dots x_{n-1}\}$ and $\{y_1, \dots y_{n-1}\}$
are isometric, i.e. $\rho_1(x_i,x_j)=\rho_2(y_i,y_j), i,j=1, \dots n-1$,
then there exists the third space $Z=\{z_1,\dots z_{n-1},z_n,z_{n+1}\}$ with metric
$\rho$ and two isometries  $I_1,I_2$ of both spaces $X$ and $Y$ to the space
$Z$ so that $I_1(x_i)=z_i,I_2(y_i)=z_i, i=1, \dots n-1, I_1(x_n)=z_n,
I_2(y_n)=z_{n+1}$.
In order to prove existence of $Z$ we need to show that it is possible to
define only nonnegative number $h$ which will be
the distance $\rho(z_n,z_{n+1})=h$ between $z_n$ and $z_{n+1}$ (images of $x_n$ and $y_n$
in $Z$ correspondingly)
such that all triangle inequalities
are valid in the space $Z$.
The existence of $h$ follows from the inequalities:
$$\rho_1(x_i,x_n)-\rho_2(y_i,y_n) \leq \rho_1(x_i,x_n)+\rho_1(x_i,x_j)-\rho_2(y_i,y_n)=$$
$$=\rho_1(x_i,x_n)+\rho_2(y_i,y_j)-\rho_2(y_i,y_n)\leq \rho_1(x_i,x_n)+\rho_2(y_i,y_n)$$
for all $i,j=1, \dots n-1$.

 Consequently $$\max_i |\rho_1(x_i,x_n)-\rho_2(y_i,y_n)| \equiv m
\leq  M \equiv  \min_j (\rho_1(x_i,x_n)+\rho_2(y_i,y_n)).$$
Thus, a number $h$ could be chosen as an arbitrarily number from the nonempty closed interval
$[M,m]$ and we set $ \rho(z_n,z_{n+1}) \equiv h$;
it follows from the definitions that all triangle inequalities are satisfied.
Now suppose we have a distance matrix $r$ of order $n-1$ and admissible vector $a \in A(r)$,
so we have metric space $\{x_1, \dots x_{n-1}, x_n\}$ (first $n-1$ points correspond
to matrix $r$ and all space - to extension matrix $r^a$. Now suppose we choose
another admissible vector $b \in A(r)$, distance matrix $r^b$ defined space
$\{y_1, \dots y_{n-1},y_n\}$ where subset of first $n-1$ points is isometric (the same)
to the space $\{x_1, \dots x_{n-1}\}$. As we proved we can define space $Z$ whose
distance metric $\bar r$ of order $n+1$ gives the required property.}
\end{proof}

Now we can formulate the general assertion about projections $\chi^r$.
\begin{lemma}
{For arbitrary natural numbers $N$ and $n$, $N>n$, and any $r \in {\cal R}_N$
 the map $\chi^r_n$ is epimorphism of $A(r)$ onto $A(p_n(r))$. In other words
for each $a=(a_1, \dots a_n) \in A(p_n(r))$
there exists a vector $(b_{n+1},\dots b_N)$ such that
 $b=(a_1,\dots a_n,  b_{n+1}, \dots b_N) \in A(r)$.}
\end{lemma}
\begin{proof}
{The above proof shows how to define the first number $b_{n+1}$.
But the projection $\chi^r_n$ seen as a map from  $A(r), r\in {\cal R}_N$ to $A(p_n(r)$
is the product of projections $\chi^r_n\cdots \chi^r_{N-1}$.
Lemma 4 shows that all those factors are epimorphisms.}
\end{proof}

It is convenient for our goals to represent the infinite distance matrices
$r \equiv \{r_{i,j}\} \in {\cal R}$
as a sequence of the admissible vectors of increasing lengths
\begin{equation}
r(1)=\{r_{1,2}\},
r(2)=\{r_{1,3},r_{2,3}\}, \dots r(k)=\{r_{1,k+1},r_{2,k+1}, \dots r_{k,k+1}\}\dots,
k=1,2 \dots,
\end{equation}
satisfying conditions
$r(k) \in A(p_k(r))$, (recall that $p_k(r)$ is the NW-projection of matrix $r$ on the space
${\bf M}^s_k$ defined above), so each vector $r(k)$ is admissible
for the {\it previous distance matrix $p_k(r)$}. 
We can consider the following sequence of the cones and maps:

\begin{equation}
\label{trivial}0={\cal R}_1\stackrel{p_2}{\longleftarrow}
{\cal R}_2={\bf R}_+\stackrel{p_3}{\longleftarrow}{\cal R}_3
{\longleftarrow} \dots
{\longleftarrow}{\cal R}_{n-1}\stackrel{p_n}{\longleftarrow}{\cal R}_n{\longleftarrow} \dots
\end{equation}
the projection $p_n$ here is the restriction of the projection defined
above onto the cone ${\cal R}_n$. 
A preimage of the point $r \in {\cal R}_{n-1}$ (fiber over $r$)
is the set $A(r)$ which the structure described in the Lemma 2.
Remark that this is not fibration in usual sense: the preimages of the points could be 
not even homeomorphic to each other for  various $r$
(even dimensions could be different). But because of this sequence the cone $\cal R$
is an inverse limit of the cones ${\cal R}_n$.
We will use the sequence (3) in order to define the measures
on the cone ${\cal R}$
in the spirit of the theory of the Markov processes.

\section{Universality and Urysohn space}
\subsection{Universal distance matrices}

The following definition plays a crucial role.
\begin{definition}
{1.An infinite proper distance matrix 
$r=\{r_{i,j}\}_{i,j=1}^{\infty} \in {\cal R}$
is called a \uchyph=0 UNIVERSAL distance matrix if the following condition is satisfied:

for any $\epsilon >0$, $n \in \bf N$ and for any
vector $a=\{a_i\}_{i=1}^n \in A(p_n(r))$
there exists $m \in \bf N$  such that
$\max_{i=1 \dots n}|r_{i,m}-a_i| < \epsilon.$

In another words: for each $n \in \bf N$ the set of vectors
$\{\{r_{i,j}\}_{i=1}^n\}_{j=n+1}^{\infty}$ is everywhere dense in the set
of admissible vectors  $A(p_n(r))$.

2.An infinite proper distance matrix 
$r=\{r_{i,j}\}_{i,j=1}^{\infty} \in {\cal R}$
is called a weakly universal distance matrix if 
for any $n \in \bf N$ the set of all submatrices 
$\{r_{i_k,i_s}\}_{k,s=1}^n$ of the matrix  $r$ of order $n$
over all $n$-tuples $\{i_k\}_{k=1}^n \subset \bf N$ is dense
in the cone ${\cal R}_n$.}
\end{definition}

Let us denote the set of universal distance  matrices by $\cal M$.
We will prove that $\cal M$ is not empty but before we 
formulate some properties of universal matrices.

\begin{lemma}
{Each universal distance matrix is weakly universal.
There exists the nonuniversal but weakly universal distance matrices.
}
\end{lemma}

\begin{proof}
{Choose any distance matrix $q \in {\cal R}_n$; we will prove that for given positive
$\epsilon$ it is possible to find a set $\{i_k\}_{k=1}^n \subset \bf N$
such that $\max_{k,s=1,\dots n}|r_{i_k,i_s} - q_{k,s}|<\epsilon$. 
Because $r^1=\{r_{1,1}=0\}$ then $A(r^1)={\bf R}_+$
(see 2.2), and by universality of $r$ the sequence
$\{r_{1,n}\}_{n=2}^\infty$ must be dense in ${\bf R}_+ $, so we can
choose some
$i_1$ such that $|r_{1,i_1}-q_{1,2}|<\epsilon$, then using density
of the columns of length 2 which follows from the universality condition
we can choose a natural number $i_2$ such that
$|r_{1,i_2}-q_{1,3}|< \epsilon, |r_{2,i_2}-q_{2,3}|< \epsilon$, etc.

There are many examples of weakly universal but nonuniversal 
distance matrix. The distance matrix of the arbitrary countable everywhere 
dense set of any universal but not homogeneously universal (see below)
polish spaces (like $C([0,1])$) gives such a counterexample,
but the simplest one is the distance matrix of the disjoint union of all 
finite metric spaces with the rational distance matrices (B.Weiss's example).}
\end{proof}

The following corollary of the universality gives the useful tool
which was used by Urysohn:

\begin{corollary}("$\epsilon$-extension of the isometry")
{Suppose $r$ is an infinite universal distance matrix and $q$ is a finite
distance matrix of order $N$ such that for some $n<N,  
r_{i,j}=q_{i,j}, i,j=1 \dots n$. Denote \uchyph=0 $i_k=k, k= 1 \dots n$.
 Then for any positive $\epsilon$ there exists the natural numbers 
$i_{n+1} \dots i_N$ such that $\max_{k,s=1 \dots N}|r_{i_k,i_s}-q_{k,s}|<\epsilon$.

In another words, we can enlarge the set of the first $n$ natural numbers with 
some set of $N-n$ numbers $i_{n+1}, \dots i_N$ in such a way that the distance 
matrix of whole set {\uchyph=0 $1,2 \dots n, n+1, \dots N$} is equal up-to $\epsilon$ to $q$.
Conversely, if distance matrix $r$ has property that for any finite distance
matrix $q$ the above property is true, then $r$ is universal.}
\end{corollary}

\begin{proof}
{For $N=n+1$ the claim follows directly from the definition of universality of $r$,
then we can use induction on $N$. The second claim follows from the definition.}
\end{proof}

From other side the existence of universal distance matrix as well as existence
of Urysohn space is not evident. We strengthen Urysohn's existence
theorem and prove the following 

\begin{theorem}
{The set $\cal M$ of the universal matrices is nonempty. 
Moreover, this set is  everywhere dense $G_{\delta}$-set in the cone $\cal R$ 
in the weak topology.}
\end{theorem}

\begin{proof}
{We will use representation described in the lemmas in previous section for construction
of at least one universal true distance matrix in the cone ${\cal R}$.

Let us fix sequence  $\{m_n\}_{n=1}^\infty$ of natural numbers in which each
natural number occurs infinitely many times and for each $n,  m_n \leq n; m_1=1$.
For each proper finite distance matrix $r \in {\cal R}_n$ let us choose an ordered countable dense
subset $\Gamma_r \subset A(r)$ of the vectors with positive coordinates:
$\Gamma_r=\{\gamma^r_k\}_{k=1}^\infty \subset A(r){\subset \bf R}^n$ and
choose any metric in  $ A(r)$, say Euclidean norm from $\bf R^n$.

The first step consists of the choice of positive real number
$\gamma_1^1 \in \Gamma_1 \subset A(0)={\bf R}_+^1$
so that we define a distance matrix $r$ of order $2$ with element $r_{1,2}=\gamma_1^1$.

Our construction of the universal matrix $r$ used its representation
as a sequence of admissible vectors $\{r(1),r(2),\dots\}$ with increasing lengths (see (2)),
- the index in the brackets is a dimension of the vector, -the conditions
on the vectors are as follows $r(k) \in A(p_k (r_{k+1})$. The
sequence of the corresponding matrices $r_n, n=1 \dots $
is stabilized to the infinite matrix $r$.
Suppose  after  $(n-1)$-th step we obtain finite matrix $r_{n-1}$,
then we choose a new admissible vector $r(n) \in  A(r_{n-1})$. The choice of
this vector (denote it $a$) is defined by the condition that
distance in $A(r_{m_{n}})$ (in norm) between projection $\chi^r_{m_n}(a)$
of the vector $a$ onto subspace of admissible vectors $A(r_{m_n})$
and point $\gamma^{m_n}_s \in \Gamma_{r_{m_n}} \subset A(r_{m_n}) $
must be less than $2^{-n}$, where $s =|i: m_i=m_n, 1\leq i \leq n|+1$:
$$\|\chi^r_{m_n}(a) - \gamma^{r_{m_n}}_s\|<2^{-n}.$$
 Recall now  that projection $\chi^r_{m_n}$ is epimorphism from $A(r)$ to $A(p_{m_n}(r))$,
(lemma 4), hence a vector $a \in A(r_n)$ with these properties does exist.
Number $s$ is nothing just the number of the points of $\Gamma_{r_{m_n}}$
 which occur on the previous steps of the construction.
After infinitely many steps we obtain the infinite distance
matrix $r$.

 Universality of $r$ is evident, because for each $n$ projection $\chi^r_n$
 of vectors $r(k), k=n+1 \dots$  is a dense set in $A(r_n)$ by construction.
 This proves the existence of the universal matrix.

 
Now remark that the property of universality of the matrix preserved 
under the action of finite simultaneous permutations of the rows and columns,
and also under the NW-shift which cancels the first row and first column of the matrices.
Also the set of universal matrices $\cal M$ is invariant under the changing
of the finite part of the matrix. Consequently, $\cal M$ contains together with
the given matrix also its permutations and shifts. But because of the weak
universality of any universal distance matrices $r$, 
even the orbit of matrix $r$ under the action of the group of permutations 
$S_{\bf N}$ is everywhere dense in $\cal R$ in weak topology. More so the
$\cal M$ is everywhere dense in $\cal R$.

Finally, the formula which follows directly from the
definition of universality shows us immediately that
the set of all universal matrices $\cal M$
is a $G_{\delta}$-set:

$${\cal M} =\cap_{k \in {\bf N}}\cap_{n \in {\bf N}}
\cap_{a \in A(r^n)} \cup_{m \in {\bf N}, m>n}\{r\in
{\cal R}:\max_{i=1,\dots n}
|r_{i,m}-a_i|< \frac {1}{k} \}.$$}
\end{proof}

Now, let us fix some infinite universal proper distance matrix $r$,
and provide the set of all natural numbers $\bf N$ with metric $r$. Denote
the completion of the space $({\bf N},r)$ with respect to metric $r$ 
as a metric space $({\cal U}_r, \rho_r)$. Evidently, it is a Polish space.

\begin{lemma}
{The distance matrix of any everywhere dense countable subset $\{u_i\}$ 
of the space $\cal U$  is a universal distance matrix.}
\end{lemma}

\begin{proof}
{1.Let us identify the set ${\bf N}$ with $\{x_i\} \subset {\cal U}_r$, then 
by definition $\rho(x_i,x_j)=r_{i,j}$
By definition the universality of $r$ means that for any $n$ closure in 
${\bf R}^n$ of the set of vectors coincide with the set of  the admissible 
vectors of NW-corner of $r$ of order $n$:
$Cl(\cup_{j>n}\{\{\rho(x_i,x_j)\}_{i=1}^n\}=A(p_n(r))$.
Because the set $\{u_i\}$ is also everywhere dense in $({\cal U}_r, \rho_r$ 
we can replace the previous set on the following: 
$Cl(\cup_{j>n}\{\{\rho(x_i,u_j)\}_{i=1}^n\}=A(p_n(r))$. But because
$\{x_i\}$ is everywhere dense in $(U_r, \rho_r)$ we can change this on
$Cl(\cup_{j>n}\{\{\rho(u_i,u_j)\}_{i=1}^n\}=A(p_n(r'))$, where $r'$
is distance matrix for $\{u_i\}$.}
\end{proof}

We will see that that $({\cal U}_r, \rho_r)$ is so called Urysohn space
and the universality is not only necessary but sufficient condition to
be a countable everywhere dense set in Urysohn space.

Make sense to mention also that there exist some proper distance 
universal matrices which are extremal points in the distance cone $\cal R$.
(see section 1.) 
  
\subsection{Urysohn universal space and universal matrices.}

Now we introduce the remarkable Urysohn space.
In one of his last papers \cite{U} Urysohn gave a concrete construction of the
universal Polish space which we will call "Urysohn space".
There is no notion of universality in \cite{U} because Urysohn did not consider
infinite matrices at all but he actually have proved
several theorems which we summarize as the following theorem:

\begin{theorem}(Urysohn \cite{U})

{A.There exists the polish(=separable complete metric) 
space $\cal U$ with the properties:

1)(Universality) For each polish space $X$ there exists
the isometric embedding of $X$ to the space $\cal U$;

2)(Homogeneity) For each two isometric finite subsets $A=(a_1 \dots a_m)$
and $B=(b_1 \dots b_m)$ of $\cal U$ there exists isometry $J$
of the whole space $\cal U$ which brings $A$ to $B$: $JX=Y$ ;

B.(Uniqueness) Two polish spaces with the previous properties 1) and
2) are isometric}.
\end{theorem}

The main result of this section is the following
theorem which includes the previous Urysohn's theorem.

\begin{theorem}
{1.The completion $({\cal U}_r, \rho_r)$ of $({\bf N},r)$ with respect 
to metric $r$ which is universal proper distance matrix is the Urysohn 
space $({\cal U}, \rho)$, e.g. it satisfies to the properties 
1) and 2) of the above theorem.

2.(Uniqueness). For any two universal distance matrices $r$ and $r'$ 
the completions of the spaces $({\bf N},r)$ and  $({\bf N},r')$ 
are isometric.}
\end{theorem}


\begin{corollary}
 {The isometric type of the space $(U_r, \rho_r)$ does not depend 
on the choice of universal matrix $r$.
The universality of the distance matrix is necessary
and sufficient condition to be a distance matrix
of the countable everywhere dense set of the Urysohn space.}
\end{corollary}


\begin{proof}
Suppose that matrix $r=\{r(i,j)\}_{i,j=1}^{\infty} \in {\cal R}$ be an arbitrary 
universal proper distance matrix (it is convenient now 
to write $r(i,j)$ instead of $r_{i,j}$)
and the space ${\cal U}_r$ is the completion of the countable 
metric space $(\bf N,r)$, denote the corresponding metric on ${\cal U}_r$ as 
$\rho_r$, but we will omit the index $r$. 

1. First of all we will prove that the 
metric space $(\cal U,\rho)$ is universal in the sense of property 1) 
of the theorem 2) and then that it is  homogeneous (property 2)).

Let $(Y,q)$ is an arbitrary Polish spaces. In order to prove 
there is an isometric embedding of $(Y,q)$ into $(\cal U,\rho)$
it is enough to prove that there exists an isometric  embedding of 
some countable everywhere dense set $\{y_n\}_1^{\infty}$ of the space $(Y,q)$ 
to $(\cal U,\rho)$. Because $(Y,q)$ is an arbitrary
polish space, it means that we must prove that for any distance 
matrix $q=\{q(i,j)\} \in \cal R$ there exist some countable set $\{u_i\} \subset \cal U$ 
with distance matrix equal to $q$. In turn for this we need to construct the set 
of the fundamental sequences in the space $({\bf N}, r)$, namely
$N_i=\{n^{(m)}_i\}_{m=1}^{\infty} \subset {\bf N}, i=1,2 \dots$ 
such that 

$$\lim_{m \to {\infty}} r(n^{(m)}_i,n^{(m)}_j)=q(i,j), i,j=1 \dots  \qquad
\mbox{and}\qquad \forall i,  \lim_{m,k \to \infty} r(n^{(m)}_i,n^{(k)}_i)=0$$.

 The convergence of the sequence $\{n^{(m)}_i\}$
in $(\cal U,\rho)$ when $m \to \infty$ to some point $u_i, i=1,2 \dots $ follows 
from the fundamentality (the last property),
and because of the first property the distance matrix
of the limit set $\{u_i\}$ coincided with matrix $q$.

 We will construct the sets $\{N_i\}_{i=1}^{\infty} \subset \bf N$ 
by induction. 
Choose arbitrarily a point $n^{(1)}_1 \in \bf N$, and suppose for given $m>1$ 
we already have defined the sets $L_k=\{n^{(k)}_i\}_{i=1}^k \subset {\bf N}$ 
for $k=1, 2 \dots m$ with property 
$\max_{i,j=1,\dots k} |r(n^{(k)}_i, n^{(k)}_j)-q(i,j)|=\delta_k < 2^{-k}, k=1, \dots m$. 

Because our construction of the set $L_{m+1}$ will use only the set $L_m$ 
we can for simplicity renumber $L_m$ as follow: $n^{(m)}_i=i$.
Now we will construct a new set $L_{m+1}=\{n^{(m+1)}_i\}_{i=1}^{m+1} \subset \bf N$ 
with the needed properties in the following way. Consider
the finite metric space $(V,d)$ with $2m+1$ points 
$y_1, \dots y_m; z_1, \dots z_m, z_{m+1}$
with the distances: $ d(y_i,y_j)= r(n^{(m)}_i,n^{(m)}_j),
d(z_i,z_j)= q(i,j), i,j=1,\dots m+1; d(y_i,z_j)=q(i,j),i=1 \dots m, j=1\dots m+1;
i \ne j,  \qquad
d(y_i,z_i)= \delta_m, i=1 \dots m.$
It is easy to check that this is correct definition of the distances
(it is important the choice of $\delta$). Denote the distance matrix of the space $(V,d)$
as $q_m$. Now apply corollary 2 and enlarge the set $L_m=\{1, 2 \dots m\}$ 
with the set of $m+1$ new points $\{n^{(m+1)}_i\}_{i=m+1}^{2m+1} \subset \bf N$ 
in such a way that the distance matrix of $L_{m+1}$ differs on a small quantity from 
the corresponding submatrix of the matrix $q$ on $2^{-(m+1)}$:  
$\max_{i,j} r(n^{(m+1)}_i,n^{(m+1)}_j)-q_m(i,j)|=\delta_{m+1}<2^{-(m+1)}$
(remember that NW corners of order $m$ of matrices $q_m$ and $r$ are coincided.
Now the construction of $L_{m+1}$ is over and we can see that 
for each $i$ the sequences $\{n^{(m_i)}\}_{m=1}^{\infty}$ is fundamental and 
$\lim_{m \to \infty} r(n^{(m)}_i,n^{(m)}_j)=q(i,j)$. Thus we prove that each polish space can 
be isometrically embedded to $({\cal U}_r,\rho_r)$.

We can essentially refine now the corollary 2 as follow.
\begin{corollary}("Extension of isometry").
{The space $({\cal U}_r,\rho_r)$ has the following property: for any finite
set $A=\{a_i\}_{i=1}^n \in {\cal U}_r$ and distance matrix  $q$ of order $N, N>n$
with NW-corner of order $n$ which is equal to the matrix 
$\{\rho(a_i,a_j)\}_{i,j=1}^n$ there exist the set points $a_{n+1} \dots a_N$
such that distance matrix of whole set $\{a_i\}_{i=1}^N$ is equal to $q$.}
\end{corollary}

The proof follows from corollary 2 and the arguments which we use above.
 
\begin{remark}
As we have mentioned there exist many examples of universal but not homogeneous
Polish spaces (f.e. Banach space $C([0,1])$). The corollary above shows that 
the main differences between such universal spaces and Urysohn space is the following
we can isometrically embed to the any universal spaces a given metric space; 
but in the case of Urysohn space we can do more: the image of embedding 
metric space has a given distances with the fixed finite (or even compact) 
set of points.
\end{remark} 

2.In order to prove homogeneity let us fix two finite $n$-point sets 
$A=\{a_i\}_{i=1}^n$  and $B=\{b_i\}_{i=1}^n$ of  $({\cal U}_r,\rho_r)$
and construct two isometric countable dense subsets one of which ($C$) 
begins with $A$ and the second $D$ begins with $B$. 
The method of constrution is well-known and called "back and forced". 
First of all we fix some countable everywhere dense subset $F$ in 
$({\cal U}_r,\rho_r), F \cap A =F \cap B=\emptyset $, and represent 
it as union of the increasing parts
$F=\cup F_n$. Put $C_1=A \cup F_1$, find the set  $D_1=B \cup F'_1$ in
such a way that isometry of $A$ and $B$ extends to $F_1$ and $F'_1$
thus $D_1$ is isometric to $C_1$. It is possible to define because 
corollary 4 (extension of isometry).
Then, choose $D_2=D_1 \cup F_2$ and $C_2=C_1 \cup F'_2$
and again extend the isometry  from the part on which it was defined before
to whole set so we construct isometry between $D_2$ and $C_2$ and so on.
The alternating process gives us two every dense isometrical sets 
$\cup C_i$ and $\cap D_i$ and isometry between extends isometry of $A$ 
and $B$.  

3.Uniqueness. Let $r$ and $r'$ - two universal proper distance matrices and the spaces
$({\cal U}_r, \rho_r)$ and $({\cal U}_r', \rho_r')$  are their completions. 
We will constract in the both spaces a countable everywhere dense sets $F_1$ 
and $F_2$ so isometry between them will extend the whole space.
Denote $\{x_i\}$ and $\{u_i\}$ everywhere dense subsets of
$({\cal U}_r, \rho_r)$ and $({\cal U}_r', \rho_r')$ correspondingly which is generated by
matrices $r$ and $r'$. Now we repeat the same arguments as in the proof of the first 
part of the theorem. We start with finite number of the points $\{x_i\}_{i=1}^{n_1}$ 
in $({\cal U}_r, \rho_r)$ and append to them the set of points 
$\{u'_i\}_{i=1}^{m_1} \subset {\cal U}_r$ with the same distance matrix 
as the distance matrix of the set of points $\{u_i\}_{i=1}^{m_1}$; 
this is possible because of universality of the $({\cal U}_r, \rho_r)$ (property 1) 
which had been already proved). Then append to the set $\{u_i\}_{i=1}^{m_2}, (m_2 > m_1)$ 
in the space ${\cal U}_r'$ the set of points $\{x'_i\}_{i=1}^{n_2}, (n_2 > n_1)$ 
in such a way that the distance matrix of the subset  $\{u_i\}_{i=1}^{m_1} \cup
\{x'_i\}_{i=1}^{n_1}$ of the set $\{u_i\}_{i=1}^{m_2} \cup
\{x'_i\}_{i=1}^{n_2}$  coincides with the distance matrix of the 
set $\{u'_i\}_{i=1}^{m_1} \cup \{x_i\}_{i=1}^{n_1}$ etc. 
continuing this process ad infinity as the result 
of this construction we obtain two sets -
the first is $\{x_i\}_{i=1}^{\infty} \cup \{u'_i\}_{i=1}^{\infty} \subset {\cal U}_r$ 
and the second is 
$\{u_i\}_{i=1}^{\infty} \cup \{x'_i\}_{i=1}^{\infty} \subset {\cal U}_r'$  -
which are everywhere dense in their spaces and are isometric. This concludes the proof
of the theorem.
\end{proof}

 As a result of the Theorem 1 we obtain 
the remarkable fact that "typical" (generic) distance 
matrix is universal matrix, and consequently {\it typical
(generic) of Polish space in our universum $\cal R$ 
is Urysohn space $\cal U$}!
 Urysohn gave an example of the countable space with rational 
distance matrix (indeed that was universal space over rationals $\bf Q$).
More simple iterative method of the construction of the universal space
was suggested  in 80-th by Katetov, and the similar idea was
used later by Gromov  in his book \cite{G}. Our method of construction
is different, - we construct the universal matrix using the geometry
of the cone $\cal R$, and we will see in the next section that this method
allows to interpret our the construction of Urysohn space
in probabilistic terms. 
 
Urysohn also pointed out that there exist universal metric space of 
the given diameter. It is possible to define in the same spirit
the notion of universal matrix with entries from interval $[0,1]$,
in this case we will obtain universal metric space of diameter 1
and the analog of all assertions of the theorems of this 
paragraph takes place for that space.

In the next section we will prove the measure theoretic versions
of these facts for  the metric spaces with measure.


\section{Matrix distribution as complete invariant of the metric triple
and its characterization.}
\subsection{Matrix distribution and Uniqueness Theorem}
Now we begin to consider the metric spaces with measure and the
random metrics on the natural numbers.

Suppose $(X,\rho,\mu)$ is a Polish spaces with metric $\rho$ and with
borel probability measure $\mu$. We will call {\it metric triple}
(In \cite{G} the author used term ``mm-space'' another term is ``probability metric space'').
 Two triples  $(X_1,\rho_1, \mu_1)$ and
$(X_2, \rho_2, \mu_2)$ are {\it isomorphic} if there exists isometry
$V$ which preserve the measure $$\rho_2(Vx,Vy)=\rho_2(x,y),  V \mu_1=\mu_2$$.
We have  mentioned before that the classification of the Polish space (non compact)
is non smooth problem. Surprisingly the classification of metric triple has a good answer.

For triple  $T=(X,\rho, \mu)$ define the infinite product Bernoulli measure
$(X^{\bf N},\mu^{\bf N})$
and the map $F: X^{\bf N} \to {\cal R}$ as follows

$$ F_T(\{x_i \}_{i=1}^\infty) =\{\rho(x_i,x_j)\}_{i,j=1}^\infty \in {\cal R}$$
The $F_T$-image of the measure $\mu^{\bf N}$ which we denoted as $D_T$ will be called
{\it matrix distribution of the triple $T$} :$F_T \mu^{\infty} \equiv D_T$.

The group of all finite permutations of the natural numbers
(infinite symmetric group $S_{\bf N}$) acts on the cone of the distance
matrices $\cal R$ as simultaneous permutations of rows and
columns of matrix.
\begin{lemma}
{Measure $D_T$ is Borel probability measure on  $\cal R$
which is invariant and ergodic with respect to the action of
infinite symmetric group, and invariant and ergodic
with respect to simultaneous shift
in vertical and horizontal directions (shortly NW-shift):
$NW(r)_{i,j}=r_{i+1,j+1}; i,j=1,2 \dots$).}

\end{lemma}
\begin{proof}
{All facts follow from the same properties of measure $\mu^{\infty}$
which is invariant under the shift and permutations of the coordinates,
and because map $F_T$ commutes with action of the shifts and permutations.}
\end{proof}

Let us call a measure on the metric space non-degenerated
if there are no nonempty
open sets of zero measure.
\begin{theorem}
{Two metric triples $T_1=(X_1,\rho_1, \mu_1)$ and $(X_2,\rho_2,\mu_2)$ with
non-degenerated measures  are equivalent iff its matrix distributions coincide:
$D_{T_1}=D_{T_2}$ as the measures on the cone $\cal R$.}
\end{theorem}

\begin{proof}
{The necessity of the coincidence of the matrix distributions is evident:
if there exists the isometry $V:X_1 \to X_2$ between $T_1$ and $T_2$ which preserves measures then
the infinite power $V^{\infty}$ preserve the method of the Bernoulli measures: $V^{\infty}(\mu_1^{\infty})=
\mu_2^{\infty}$ and because of equality $F_{T_2}X_2^{\infty}=F_{T_2}(V^{\infty}X_1^{\infty}$),
the image of these measure is the same: $D_{T_2}=D_{T_1}$.
Suppose now that  $D_{T_2}=D_{T_1}=D$. Then $D$-almost all distance matrices
$r$ are the images under the maps $F_{T_1}$ and $F_{T_2}$, say
$r_{i,j}=\rho_1(x_i,x_j)=\rho_2(y_i,y_j)$ but this means that the identification
of $x_i \in X_1$ and  $y_i\in X_2$ for all $i$ is an isometry $V$ between these countable
sets $V(x_i)=y_i$. The crucial point of the arguments: by ergodic (with respect to NW-shift) theorem
$\mu_1$-almost all sequences $\{x_i\}$ and $\mu_2$-almost all sequences
$\{y_i\}$ are uniformly distributed on $X_1$ and $X_2$ respectively.
This means that the $\mu_1$ measure of each ball
$B^l(x_i) \equiv \{z\in X_1:\rho_1(x_i,z)<l\}$
is equal to $$\mu_1(B^l(x_i))
=\lim_{n \to \infty}\frac{1}{n} \sum_{k=1}^n 1_{[0,l]}(\rho_1(x_k,x_i)). $$
But because of isometry $V$ ($r_{i,j}=\rho_1(x_i,x_j)=\rho_2(y_i,y_j)$
- see above) the same quantity is a $\mu_2$-measure of the ball:
$B^l(y_i) \equiv \{u\in X_2:\rho_2(y_i,u)<l\}$
 $$\mu_2(B^l(y_i))
=\lim_{n \to \infty}\frac{1}{n} \sum_{k=1}^n 1_{[0,l]}(\rho_2(y_k,y_i))= \mu_1(B^l(x_i)). $$
Finally, both measures are non-degenerated, consequently each of the sequences $\{x_i\}$
and $\{y_i\}$ is everywhere dense in its own space. Because
both measures are Borel it is enough to conclude their coincidence
if we established that the measures of the all such balls are the same.}
\end{proof}

\begin{corollary}
{Matrix distribution is complete invariant of the equivalence classes
(up-to isometries which preserve the measure) of the of metric triples
with non-degenerated measures.}
\end{corollary}

  We can call this theorem as ``Uniqueness Theorem'' because it
asserts the uniqueness up-to isomorphism of the metric triple with
the given matrix distribution.  Firstly this theorem
as ``Reconstruction Theorem'' in another formulation
has been proved in the book \cite{G} pp.117-123 by Gromov.
He formulated it in the terms of finite dimensional distributions
of what we called matrix distribution and proved using
analytical method. He asked me in 1997 about this theorem
and I suggested  the proof which is written here (see also in \cite{V1})
and which he had quoted (pp.122-123) in the book.
Gromov had invited the readers to compare two proofs, one of which is
rather analytical (Weierstrass approximations) and another (above)
in fact uses only the reference to the
ergodic theorem. One of the explanations of this
difference is the same as in all applications of the ergodic theorem -
it helps us to replace the methods of space approximation by operations
with infinite (limit) orbits. In our case the consideration of infinite
matrices and cone $\cal R$ with invariant measures gives a possibility
to reduce the problem to the investigation of ergodic action of infinite groups.
In \cite {V2,V3} we use more general technique which also based on the ergodic
methods in order to prove the analog of uniqueness theorem for the classification
of arbitrary measurable functions of two variables
(in the case above this was a metric as a function of two arguments).


\subsection{Properties of matrix distributions and Existence Theorem}

A matrix distribution of the metric triple $T=(X,\rho, \mu)$ nondegenerated
is by definition a measure  $D_T$ on the cone $\cal R$.
Clearly it can be considered as a  random (semi)metric
on the natural numbers. In this section we will characterize
those random metrics or those measures on $\cal R$
which are matrix distribution, in other words those which is appeared
as a random distance matrices for the independent sequence of the the points $\{x_i\}$ of
metric space $(X,\rho)$ which are distributed with 
measure $\mu$.
As we mentioned any measure $D_T$ must be invariant and ergodic with respect to
action of infinite symmetric group and to NW-shift. But this is not
sufficient and there is an additional condition to which it satisfies.
We mention below necessary and sufficient conditions (see also
\cite{V3})
for that but will start from the counterexamples.

{\bf Examples.}

1.A trivial example of invariant ergodic measure which is not matrix distribution
is the following. Denote $r^0$ a distance matrix:
$r^0_{i,j}=\delta (i-j)$ (where $\delta (n)=1$ if $n=0$ and $=0$ otherwise);  this
is nothing than distance matrix of the countable set such that the distance between two different
points is equal to $1$. Let a measure $\mu^0$ be a delta-measure at the matrix $r^0$.
Clearly $\mu^0$ is invariant, ergodic and does not correspond to any metric triple.


2. Now remark that each symmetric matrix with zeros on the principal diagonal
and with entries $r_{i,j}$ from the interval $[1/2,1]$ when $i \ne j$ is a proper distance
matrix; indeed the triangle inequality is valid for each three numbers in this case.
Consequently for each nondegenerated (=not delta measure) probability measure $m$
on  $[1/2,1]$ the  product measure $m^{\infty}$ on ${\bf M}^s_{\bf N}(\bf R)$
with the factor $m$ (this means that all entries upper diagonal are independent
and identically distributed) is supported on the cone
$\cal R$. This measure evidently is invariant under permutations and NW-shift as well
as is ergodic measure.
But again this continuous measure is not matrix distribution for any metric triple because with
$m^{\infty}$-probability equal to one all distance matrices
define the discrete topology on the natural numbers $\bf N$
(because of the absence of nontrivial fundamental sequences in  $\bf N$) and
so, completion of $\bf N$ is  $\bf N$ and matrix distribution cannot be continuous measure.
In a sense this is a general example of such type.

The explanation of those effects will be clear from the proof of the next theorem.
The next theorem gives one of the  characterizations o matrix distribution.

\begin{theorem}(Existence of metric triple with given matrix distribution)

{Let $D$ be a probability measure on the cone $\cal R$,which is invariant
and ergodic with respect to action of infinite symmetric group
(=group of all finite permutations of the naturals).

1)The following condition is necessary and sufficient for $D$ to be a matrix distribution
for some metric triple $T=(X,\rho, \mu)$ or $D=D_T$:

for each $\epsilon>0$ there exists integer $N$ such that
\begin{equation}
D\{r=\{r_{i,j}\} \in {\cal R}: \lim_{n \to \infty} \frac{|\{j:1\leq\ j \leq n,
\min_{1 \leq i \leq N}
 r_{i,j} <\epsilon \}|}{n}> 1- \epsilon \}>1-\epsilon.
\end{equation}

2)The following more stronger condition is necessary and sufficient for $D$
to be a matrix distribution for some metric triple with compact
metric space: for each $\epsilon >0$ there exists integer $N$ such that
\begin{equation}
D\{r=\{r_{i,j}\} \in {\cal R}: \mbox{for all} \, j>N,
\min_{1\leq i \leq N} r_{i,j} <\epsilon\}>1-\epsilon,
\end{equation}
then $D=D_T$ where $T=(X, \rho, \mu)$ and $(X, \rho)$ is compact.}
\end{theorem}


\begin{proof}
{1)The necessity in the case of compact space is evident:
the condition (5) express that fact that sufficiently long
sequence of the independent with respect to nondegenerated measure
points which (by ergodic theorem) uniformly distributed with respect to this
measure contains the $\epsilon$-net of the space.
The necessity of the conditions (4) follows automatically from  the
well-known property of the borel probability measures on the complete separable metric space:
namely the set of full measure is sigma-compact, consequently for each $\epsilon$ there exist
a compact of measure $>1-\epsilon$. Indeed, because of countably additivity
of our measure  for any $\epsilon >0$ the exist finite number of the points
such that the measure of the union of $\epsilon$-balls with the centers at those
points is greater than $1-\epsilon$ and using a standard procedure we can obtain
the compact with needed property.

2) Suppose now that we have a invariant and ergodic measure $D$ on $\cal R$ with
condition(4). The plan of the proof is the following: we will construct a metric space
with measure (metric triple) using only one distance matrix $r$  with some property
and then rewrite all properties of the measure $D$ in term of $r$.
 Invariance of $D$ under the group $S_\infty$ (simultaneous permutations
of the rows and columns) leads to the invariance of the restrictions
of the measure $D$ on the submatrix $\{r_{i,j}: i=1,2 \dots n, j=1,2\dots \}$
with respect to the shift $j \to j+1$ for any $n$.
Using ergodic theorem for this shift (which is not ergodic!)
we can find the set $F \subset \cal R$  of full $D$-measure
of such distance matrices $r=\{r_{i,j}\}$ for which the following limits exist for
any natural numbers $k$ and positive real numbers $\{h_i\} \, i=1,2 \dots k$:
\begin{equation}
   \lim_{n \to \infty}\frac{1}{n}\sum_{j=1}^n \prod_{i=1}^k 1_{[0,h_i]}(r_{i,j})
\equiv \mu^{h_1, \dots h_k}
\end{equation}

  Now let us use an invariance of the measure $D$ under the action of symmetric group $S_\infty$.
By the ergodic theorem (more exactly by martingale theorem) for action of $S_\infty$
as locally finite group we can assert that for almost
all $r$ and fixed Borel set $B \in {\cal R}_n$  the following limits exist
\begin{equation}
\lim_{N\to \infty}1/N!\sum_{g \in S_N}1_B (g(r^{(n)})) \equiv \Lambda^{(n)}_r(B)
\end{equation}
where $ g(r^{(n)})=\{r_{g(i),g(j}\}_{i,j=1}^n$, $g$ is a permutation i.e. element
of $S_N$, which permutes first $N$ naturals numbers,  $1_B$ is a characteristic
function of the Borel set $B \subset{\cal R}_n $; a measure
 $\Lambda^{(n)_r}(.)$ in ${\cal R}_n$ is called  empirical distribution
of matrix $r \in{\cal R}_n$.
These empirical distributions as a family of measures on the cones ${\cal R}_n$
are concordant with respect to projections $p_n$ (see section 2) and consequently define
an $S_\infty$-invariant measure on $\cal R$. Our assumption about matrix $r$
is that this measure coincides with initial measure $D$; it is possible to assume
because of ergodicity of action of $S_\infty$. If we choose the countable basis
of the Borel sets $\{B_i^n\}_{i=1}^{\infty}$ in ${\cal R}_n; n=1,2 \dots $
then for $D$-almost all $r$ the existence is valid for all $B_i^n, i,n=1,2 \dots $.

Finally let us retell the condition (4) in terms of distance matrix $r$.
It follows from (4) that the for $D$-almost all $r$ the following is true:
for each $k$ there exist integer $N$ such that

\begin{equation}
 \lim_{n \to \infty} \frac{|\{j:1\leq\ j \leq n,
\min_{1 \leq i \leq N}
 r_{i,j} < k^{-1} \}|}{n}> 1- k^{-1}.
\end{equation}

Let us fix  one of such distance matrix $r=\{r_{i,j}\}$ which satisfies all three types of
conditions and consider it as a metric on the set of natural numbers $\bf N$
numbers. Define the completion $X_r$ of metric space $({\bf N},r)$, denote the metric
in this completion by $\rho_r\equiv \rho$, and the natural numbers as a dense countable
set in this completion by $X_r$ by $x_1, x_2, \dots $.
Denote by $B^h(x)$  the ball of the
radius $h$ with the center at the point $x$ in the space $X_r$ and by
$\cal A$ the {\it algebra of the subsets} of $X_r$ generated
by all the balls with the center at the  points $x_i, i=1,2 \dots $ and arbitrary radius.
By  the definition put the measure $\mu_r$ of the finite
intersections of the balls as follow
\begin{equation}
\mu_r(\cap_{i=1}^k B^{h_i}(x_i))=  \mu^{h_1, \dots h_k}
\end{equation}
It is easy to check that this equality is correctly defines an nonnegative
finitely additive normalized measure $\mu_r$ on {\it algebra} $\cal A$
of the sets generated by the mentioned balls,  but in general it is NOT sigma-additive
and consequently can not be extended to sigma-algebra of all Borel set in $X_r$
as countable additive
probability measure. This is just the case in our counterexamples: we had countable space
and the definition above gave a measure which takes value zero on each finite set but equal
to 1 on the whole space. In a sense we are in the situation which occurs in Kolmogorov's
theorem about extension of the cylindric measures in the infinite dimensional linear spaces
as true probability measure. But our situation is not linear and differ from that.

Now we will use the condition (4) in the form (8) for $r$.
Choose  $\epsilon > 0$,
condition (8) allows to find for each $k$ a finite
union of the balls, say, $C$ in $X_r$ of the measure more than $1-\epsilon$.
and then to normalize our measure on  $C$ on $1$, denote it as $\bar \mu_r$.
Using induction on $k$ we can construct a set of balls with radius
$2^{-k}$ such that the intersection of union of $C_k$ and $C$ has  the $\bar \mu_ r$-measure
more than $1-2^{-k}\epsilon$; $k=1,2 \dots$.
It means that the intersection of all these sets $ C \cap (\cap_k C_k)$ has $\bar \mu_r$-measure more
than $1-2\epsilon$ and is a totally bounded set (i.e.has an $\epsilon$-net for all
$\epsilon$); a because of completeness of $X_r$ this intersection is a compact.
But any  finite additive measure which is defined on the algebra of the sets dense in the
sigma algebra of the Borel sets in the compact is countable additive. So we found
a compact $C$ in $X_r$ such that $\mu$-measure of it is not
less than $1-3\epsilon$. Because
$\epsilon$ is an arbitrary positive  we have constructed the true probability
measure $\mu$ in $X_r$ which is supported with sigma-compact. If we use instead of
conditions (4) and (8) the condition (5) and its individualization for $r$
we obtain along the same construction a compact of full measure in $X_r$.

Actually, we have constructed a metric triple  $T_r=(X_r,\rho_r,\mu_r)$
where the measure $\mu$ is true probability measure on the
Polish space $(X_r,\rho_r)$ with full support
and with distinguish dense countable subset $\{x_i\}$ which is
{\it uniformly distributed (with respect to measure} $\mu_r$), and
also satisfied to the condition (7). The final part of the proof consists
in the verification of the fact that matrix distribution $D_{T_r}$  of the metric
triple $T_r=(X_r, \rho_r, \mu_r)$ and initial measure $D$
are equal as the measures on the cone $\cal R$.
We formulate this as a Lemma which is useful in more general situations also
and which completes the proof of the theorem.}
\end{proof}

\begin{lemma}
{Suppose $r \in \cal R$ is a matrix for which all the limits (6) 
do exist and equation (7),(8) is also valid. 
Using matrix $r$ construct the metric triple
$T_r=(X_r, \rho_r, \mu_r)$ using 
the equations (6) and (8).
Then matrix distribution $D_{T_r}$ of this triple
is equal to the $S_{\infty}$-invariant measure which is generated
with matrix $r$ by formulas (7).}
\end{lemma} 


\begin{proof}
For the proof we must check
the coincideness of the finite dimensional distributions of both measures.
Let us illustrate this for the case of the distribution of the element
$r_{1,2}, (n=2)$;  for general $n$ the verification is similar.
$$
\begin{array}{l}
\int_{X_r}\int_{X_r} {\bf 1}_B(\rho_r(u,z))d\mu_r(u)d\mu_r(z)=
\lim_{n \to \infty}n^{-1} \sum_{i=1}^n \lim_{m \to \infty}m^{-1}\sum_{j=1}^{m}
 {\bf 1}_B(r_{i,j})=\\
\lim_{n \to \infty}n^{-2}\sum_{i,j=1}^n {\bf 1}_B(r_{i,j})=
\lim_{N \to \infty}({N!})^{-1}\sum_{g \in S_N}{\bf 1}_B(r_{g(1),g(2)})=
\Lambda^{(2)}_r(B).
\end{array}.
$$
 Here $B \subset {\bf R}_+$; the last equality follows from (7);
the equalities above used the
uniformity of the distribution of the sequence $\{x_i\}$
in the space $(X_r, \mu_r)$.
This concludes the proof of the theorem, because by the condition (7)
the $S_{\infty}$-invariant measure on $\cal R$ which is generated by 
matrix $r$ is just the measure $D$.
\end{proof}

\begin{remark}
{The condition (4) could be replaced by another condition from the paper \cite{V3}
(simplicity of $S_{\infty}$-invariant measure). That condition guarantees
that measure D appeared from {\it some} measurable function of two variables
as matrix distribution which is sufficient for our goals.}
\end{remark}

\subsection{The space of the measure-theoretical metric triples.}
Now we can extend the notion of the space of the metric spaces (see section 1)
and introduce the same space for the metric triples. Instead of the ordinary
point of view when one consider the set of all Borel measures on the given topological
space, we in opposite, consider the set of all {\it measurable (semi)metrics}
on the fixed Lebesgue space with continuous measure. (see \cite{V4}, par.6).

  Let $(X,\mu)$ be a Lebesgue space with continuous measure $\mu$
(say, interval [0,1] with Lebesgue measure), and $S_{\mu}(X)$- the space of all classes
$mod 0$ of measurable functions;  define ${\cal R}^c \subset S_{\mu}(X)$
as a  cone of measurable metrics e.g. the cone of the classes $mod 0$
of symmetric measurable functions $\rho :(X\times X, \mu \times \mu)) \to {\bf R}_+$
with the triangle inequality:

$$\rho(x,y)+\rho(y,z) \geq \rho(x,z) \mbox {for} \qquad  (\mu \times \mu \times \mu)-
\mbox {almost all} \qquad  (x,y,z)\in (X \times X \times X).$$

It is important that $\rho$ is not individual function but the class of $mod 0$
equivalent functions, so it is not
evident a priori that such $\rho$ defines the structure of metric space on $X$.
The cone ${\cal R}^c$ is a continual generalization of the cone $\cal R$ (section 1)
when instead of the set of natural numbers $\bf N$ with counting measure
we consider space $(X,\mu)$ with continuous measure.

Suppose $\rho \in {\cal R}^c$ is a pure function (see \cite{V3})
and the measure $ D_{\rho}$ on the space $\bf M_{\infty}(\bf R)$
is a matrix distribution of measurable function $\rho$.
(see definition in the previous section).
Using ergodic theorem we can prove that
$D_{\rho}(r \in {\cal R}:r_{i,k}+r_{j,k}\geq r_{i,k})=1$  for each $i,j,k \in \bf N$
and consequently $D_{\rho}({\cal R})=1$. From this  using characterization of
matrix distributions from \cite{V4} we  conclude that the following
assertion is true:
\begin{lemma}
{The measure $ D_{\rho}$ concentrates of the cone $\cal R$ (e.g.$D_{\rho}({\cal R})=1$)
and is ergodic $S_{\infty}$-invariant measure.
Consequently, each pure function $\rho \in {\cal R}^c$ on $(X \times X, \mu \times \mu)$
defines a true metrics $mod 0$ on the space $(X,\mu)$.}
\end{lemma}
As we have proved the matrix distribution is complete invariant of the {\it measurable
metrics} up-to measure preserving transformation.
Thus the studying of the measurable metrics is reduced to the studying of the metric
triple when $X$ is a Lebesgue space with true $mod 0$ metric.
The notion of the cone  ${\cal R}^c$ is useful in some situations (see \cite{V4}).

\section{General classification of the measures on the cone of distance matrices.}
\subsection{Definitions}
Now let us consider the arbitrary measures on the cone $\cal R$,
or - an arbitrary random metrics on the naturals and choose some denotations.

{\bf Denotations.}
Denote  $\cal V$ the set of all probability Borel measures \footnote{we use later the
term ``measure'' in the meaning ``Borel probability measure''} on the cone $\cal R$
and endow it with weak topology,- this is a topology of inverse
limit of the sets of probability measures on the finite dimensional cones ${\cal R}_n$
with its usual weak topology. The convergence in this topology is
convergence on the cylindric sets with open bases.
 All classes of measures which we define below are the subsets of $\cal V$ with
induced topology.
 Let $\cal D$  be  the subset in $\cal V$ of the matrix distributions;
as we proved this is the set of all metric triples. The constructive description
of  $\cal D$ follows from the existence theorem (section 4).

The set $\cal P$ is a subset of  $\cal V$ of measures which is concentrated
on the set of universal distance matrices:
$\nu \in \cal P$ iff $\nu({\cal M})=1$;

The set ${\cal Q} \subset \cal D$ consists with the measures which corresponds
to the metric triples $T=(X, \rho, \mu)$ in which $(X,\rho)$ is Urysohn space.
Or in other words (Theorem 1) this is the set of matrix distributions
with Urysohn space as a metric space;

Denote also by $\cal H$ the set of measures $\mu$ in  $\cal V$ which has
the following  property: $\mu$-almost all distance matrices give the same
(isometrical) metric spaces. The measures $\mu \in \cal H$ induced a
{\it random everywhere dense sequence of points} of the given space. 
From this point of view the elemetns of $\cal D$ induced a random everywhere 
dense  subset of the special type, namely
infinite independent sampling of the points of the given metric triple; and 
the elements of $\cal Q$ induced a random independent sampling of the  points 
in the Urysohn space with nondegenerated measure.

We have embeddings
$$  {\cal V} \supset {\cal D} \supset {\cal Q} \subset
{\cal P} \subset {\cal H} \subset {\cal V};
\qquad {\cal Q}= {\cal P}\cap{\cal D} $$
Remark that the set of non-degenerated measures is of course everywhere dense $G_\delta$
set in $\cal V$

\begin{theorem}
{1.The subset ${\cal P} \subset \cal V$
is an everywhere dense $G_\delta$ subset in $\cal V$.
This means that for generic measures $\nu$ on $\cal R$
$\nu$-almost all distance matrices 
are universal and consequently $\nu$-almost all distance matrix  $r$ defines the
metric on the naturals such that completion of naturals with respect to this
metric is the Urysohn space.

2.The subset ${\cal Q} \subset \cal D$
is everywhere dense $G_\delta$-set in $\cal D$. This means that generic
metric triple $T=(X, \rho, \mu)$ has Urysohn space as the space $(X,\rho)$.}
\end{theorem}

\begin{proof}
{The first claim follows from Theorem 1 which stated in particular
that the set of universal distance matrices is a set of type $G_\delta$
in $\cal R$, and from a general fact we can deduce that the set all measures
on separable metrizable space such that everywhere dense $G_\delta$-set
(in our case - $\cal M$)
has measure 1, is in its turn everywhere dense $G_\delta$ - set in the space
of all measures in weak topology.
The second claim follows from the fact that intersection
of $G_\delta$-set with any subspace in Polish space is also $G_\delta$-set in
induced topology.}
\end{proof}

\subsection{Examples of the measures which are concentrated on the universal matrices.}

Now we can give a probabilistic (markov) construction of the measures
on the cone $\cal R$ and in particular to represent the examples
of the measures from $\cal P \subset \cal H \subset \cal V$
which are supported by universal matrices. This gives a new proof of the existence
of the Urysohn space but actually our arguments in the section 3 had the same
probabilistic interpretation.  Also the method gives
a concrete illustration how to construct a random metric space.

Let $\gamma$ be an arbitrary continuous measure on half-line ${\bf R}^1_+$
with full support - for example Gaussian measure on the half-line.
We will define inductively the measure $\nu$ on the cone of distance matrices
$\cal R$ by construction of its finite dimensional projection on
the cones ${\cal R}_n^0$ as follows
The distribution of the entry $r_{1,2}$ is distribution $\gamma$.
So we have defined the measure on ${\cal R}_2$, denote it as $\nu_2$.
  Suppose we already defined the joint distribution of the
entries $\{r_{i,j}\}_{i,j=1}^n$ which means that we defined
a measure $\nu_n$ on ${\cal R}_n^0$.
 By Lemma 4 the  cone  ${\cal R}_{n+1} $ is a fibration over
cone ${\cal R}_n$ with the fibers $A(r)$ over matrix $r\in {\cal R}_n$
We use only the structure of this fibration:
projection ${\cal R}_n\stackrel{p_{n+1}}{\longleftarrow}{\cal R}_{n+1}$ -
in order to define a measure on ${\cal R}_{n+1}$ with given projection.
So we need to define a conditional measure on $A(r)$ for all $r \in \cal R$
which in the measurable way depends on $r$. In probabilistic sense it means
that we want to define the transition probabilities from given distance matrix
$r$ of order $n$ to the distance matrix $r^a$ (see section 2) of order $n+1$.
Let us recall the geometrical structure of the set of admissible vectors $A(r)$.
It is Minkowski sum: $$A(r)= M_r +\Delta_n,$$ (see 2.2) or as projection
of the direct product  $\pi:M_r \times \Delta_n \to  M_r +\Delta_n=A(r)$.
Consider product measure on
$M_r \times \Delta_n :\gamma_r=m_r \times \gamma$
where $m_r$ is for example normalized Lebesgue measure on the compact
polytope $M_r$ or another measure with full support on $M_r$,
with the conditions which we formulate below.
Let $\pi \gamma_r$ be its projection on $A(r)$.
 We define {\it conditional measure} on $A(r)$ as $\pi \gamma_r$.
So, we have
$$ \mbox{Prob}(r^{da}|r)=\pi(m_r \times \gamma)(da). $$
The conditions on the measures $m_r$ are the following:
on each step of the construction
for each $N$ and $n>N$ the projection of measure
$m_r, r \in {\cal R}_n$ to the set of admissible vectors $A(p_N(r))$
are uniformly positive on the open sets; this means that for any
open set $B \subset A(p_N(r))$ there exist
$\epsilon >0$ such that for any $n>N$ the value of projection of the measure
$m_r, r \in {\cal R}_n$ on the set $B$ more than $\epsilon$.
Thus we define a measure $L_n$ on ${\cal R}_{n+1}$.
By construction all these measures are concordant and define the a measure $L$ on $\cal R$.

 More intuitive and combinatorial variant of this description is the following:
 to the given $n$-point metric space we randomly add a $n+1$-th  point
 choosing the distances between the new and the previous points,
 or, equivalently, choosing the  admissible vector with natural probability
 which is positive on all open sets of admissible vectors. We can not choose
 an admissible vector indecently  (except the degenerated cases
 - see counterexample in the section 5) so we try to define transition
 probabilities as soon as possible close to independence.
 Of course the transition probabilities are the parameters of
 our procedure as well as initial measures $\gamma$.
 Denote such measure as $L=L(\gamma, \{m_r:r \in {\cal R}_n, n=1,2 \dots \})$.
\begin{theorem}
{The constructed measures $L$ belong to the cone $\cal P$
which means that $L$ concentrated on the set of universal matrices.
and therefore the completion of $({\bf N},r)$ is Urysohn space $L$-almost sure.}
\end{theorem}
The sketch of the proof: from the conditions on the measures $m_r$ above
follows the asymptotic independence of the admissible vectors; this is
enough to prove the universality
of matrices with probability 1, or to prove the coincideness
of the support of the empirical and theoretical distributions.
Universality of matrices follows from the criteria of the Theorem 1.

We can say that our construction leads to the following conclusion:
{\it a random countable metric space is everywhere dense subset of the Urysohn space}
or completion of the random countable metric space with probability one is the
the Urysohn space. Here ``random'' means randomness respectively to that
natural procedure which was defined above and which is in a
sense very close to the independence and has a very wide variations
which allow to define the measures on $\cal R$.

Much more complicate problem is to construct a measure on $\cal R$
form $\cal Q $, which is a matrix distribution for some measure on $\cal U$;
 or even to construct a measure from the set $\cal D$ (matrix distribution
of some metric triple.
It is not clear even what kind of the distributions may occur as their distribution
of the element $r_{1,2}$ if we consider a measure from  the set $\cal D$.

The properties of the measure in the Urysohn space
are very intriguing; the studying of non-degenerated measure on the Urysohn
space and general structure of that space seems very important and interesting.
Here is a concrete question about measures on $\cal U$: is it possible
to define a measure on $\cal U$ such that distance matrix of random
and independently chosen $n$ points has a given (for example Gaussian)
distribution? We know very few facts about this as well as about the topology,
group of isometry of Urysohn space.
Another important problem is the calculation of the matrix distributions for
concrete metric triples and the spectra of those random matrices.
Even finite dimensional distributions for compact Lie groups
with Haar measure or for some simple manifolds, as I know, never was found
But infinite-dimensional case is especially interesting.

Returning back to the Theorem 7, I must recall a very interesting
old theorem by  Erd{\"o}s-R\'{e}nyi
\cite{ER} that a random graph is with probability one is a universal graph
in the sense Rado (see \cite{Ra,Ca}). In some sense this is very  partial case
of the our theorem (instead of distance matrices one can consider the arbitrary
$0-1$-matrices). This case is more simpler because we can choose the
independent entries. As we had mentioned, perhaps there are several examples
of generic and typical universal objects in the other categories.

\begin{thebibliography}{10}

\bibitem{CK01}J.Clemens,A.Kechris.
\newblock Polish metric spaces:their classification and isometry groups.
\newblock{\em Bull. Symb. Logic}, 7(30), 361-375, 2001.

\bibitem{G} Misha Gromov.
\newblock  Metric Structures for Riemannian and Non-Riemannian
Spaces. Birkhuaser, 1998.

\bibitem{U}P.S.Urysohn.
\newblock  Sur un espace metrique universel.
\newblock {\em Bull.Sci.Math.}, 51, 1-38, 1927.

\bibitem{V1}A.Vershik.
\newblock The Universal Urysohn space, Gromov's triples, and random
metrics on the series of natural numbers.
\newblock{\em Russian Math.Surveys.}, 53, 5, 57-64, 1998.

\bibitem{ER}P.Erd{\"o}s, A.R\'{e}nyi.
\newblock Assymetric graphs.
\newblock{\em Acta Math.Acad.Sci.Hungar}, 14, 295-315, 1963.

\bibitem{Ca}P.Cameron.
\newblock The random graphs.
\newblock {The Mathematics of Paul Erdos.} (J.Nesetril, R.L.Graham, eds)
331-351 Springer, 1996.

\bibitem{Ra}R.Rado.
\newblock Universal graphs and universal functions.
\newblock {\em Acta Arith.}, 9,331-340, 1964.

\bibitem{V2}A.Vershik.
\newblock Classification of the measurable functions of several arguments
and invariant measure on the space of the matrices and tensors,1.Classification.
Preprint of Erwin Schrodinger Institute, No. 1107, 2001

\bibitem{V3}A.Vershik.
\newblock Classification of the measurable functions of several arguments
and invariant distributions of random matrices.
\newblock {\em Functional anal. and its appl.}, 2, 36, 1-16, 2002.

\bibitem{V4}A.Vershik.
\newblock Dynamical theory of the growth in the groups: entropy, boundary,examples.
\newblock {Russian Mathematical Surveys}, 55,4(434),60-128, 2000.


\bibitem{DL}M.Deza, M.Laurent. 
\newblock Geometry of cuts and metrics. 
\newblock Springer-Verlag, Berlin 1997.

\bibitem{Av} D.Avis. 
\newblock On the extreme rays of the metric cone.
\newblock Canad. J. Math. 8,1, 126-144 1980.
\end{thebibliography}
%\end
 \end{document}











