Зоопарк метрик · Введение в топологию

В прошлом уроке мы выяснили, что метрика — это любая функция, которая удовлетворяет трём аксиомам. Теперь посмотрим, какие метрики встречаются на самом деле. Каждая из них чему-то учит: одни показывают, что разные метрики могут давать одни и те же открытые множества, другие ломают привычные картинки, а третьи позволяют мерить расстояние между вещами, которые совсем не похожи на точки.

Метрики на ℝⁿ

Расстояние между точками $x = (x_1, \dots, x_n)$ и $y = (y_1, \dots, y_n)$ можно мерить по-разному. Вот три самых частых способа:

\rho_1(x, y) = \sum_{i=1}^n |x_i - y_i|, \qquad \rho_2(x, y) = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}, \qquad \rho_\infty(x, y) = \max_i |x_i - y_i| .

Первая — манхэттенская (такси едет по сетке кварталов), вторая — обычная евклидова, третья — максимум (так ходит шахматный король). Все они входят в одно семейство: при $p \ge 1$

\rho_p(x, y) = \Bigl(\sum_{i=1}^n |x_i - y_i|^p\Bigr)^{1/p},

а $\rho_\infty$ получается как предел при $p \to \infty$ . Ниже единичный шар $\rho_p$ на плоскости: при $p = 1$ это ромб, при $p = 2$ круг, при $p = \infty$ квадрат. Попробуйте сделать $p < 1$ : шар перестанет быть выпуклым. Это верный признак того, что ломается неравенство треугольника, и при $p < 1$ формула метрику уже не задаёт.

Шары у этих метрик разные, но открытые множества одни и те же. Дело в том, что метрики сравнимы: на картинке квадрат, круг и ромб можно вложить друг в друга с каким-то множителем.

Утверждение (сравнимые метрики).

Пусть для метрик $\rho$ и $\sigma$ на множестве $X$ есть числа $a, b > 0$ , такие что $a\,\rho(x, y) \le \sigma(x, y) \le b\,\rho(x, y)$ для всех $x, y$ . Тогда открытые множества у $\rho$ и $\sigma$ одни и те же. В частности, $\rho_\infty \le \rho_2 \le \rho_1 \le n\,\rho_\infty$ , поэтому на $\mathbb{R}^n$ все три метрики задают одни и те же открытые множества.

Схема доказательства

Неравенство $\sigma \le b\rho$ значит, что шар $B_\rho(x, r/b)$ лежит в шаре $B_\sigma(x, r)$ . Значит, если в $G$ помещается $\sigma$ -шар вокруг $x$ , то помещается и $\rho$ -шар. Второе неравенство даёт то же самое в обратную сторону.

Доказательство

Пусть $G$ открыто для $\sigma$ и $x \in G$ . Тогда $B_\sigma(x, r) \subset G$ для некоторого $r > 0$ . Если $\rho(x, y) < r/b$ , то $\sigma(x, y) \le b\rho(x, y) < r$ , то есть $B_\rho(x, r/b) \subset B_\sigma(x, r) \subset G$ . Значит, $G$ открыто для $\rho$ . Обратно, из $a\rho \le \sigma$ так же получаем $B_\sigma(x, ar) \subset B_\rho(x, r)$ .

Неравенства для $\mathbb{R}^n$ : максимум из $|x_i - y_i|$ не больше корня из суммы квадратов, корень из суммы квадратов не больше суммы модулей (возведите обе части в квадрат), а сумма $n$ модулей не больше $n$ максимумов.

Замечание (Сравнимость достаточна, но не необходима).

Метрики с одними и теми же открытыми множествами называют эквивалентными. Сравнимые метрики эквивалентны, но обратное неверно. Вспомните метрику $|x^3 - y^3|$ на $\mathbb{R}$ из прошлого урока. Её открытые множества те же, что у $|x - y|$ : отображение $x \mapsto x^3$ непрерывно в обе стороны и переводит интервалы в интервалы. Но $\frac{|x^3 - y^3|}{|x - y|} = x^2 + xy + y^2$ , и это отношение около нуля сколь угодно мало, а вдали от нуля сколь угодно велико. Так что никакими множителями $a$ и $b$ эти метрики не сравнить.

А раз открытые множества одни и те же, то одинаковы и сходимость, и непрерывность: в первых уроках мы видели, что они выражаются только через открытые множества.

Задача. Какая последовательность точек плоскости сходится к $(0, 0)$ в метрике $\rho_\infty$ , но не сходится в метрике $\rho_1$ ?

$(1/n,\, 1/n)$
$(1/n,\, 1)$
$(1/\sqrt{n},\, 0)$
Такой последовательности нет

Разбор

Открытые множества у $\rho_1$ и $\rho_\infty$ одни и те же, поэтому и сходящиеся последовательности одни и те же. Это видно и напрямую: $\rho_1(x_n, 0) \le 2\rho_\infty(x_n, 0)$ , так что если правая часть стремится к нулю, то и левая тоже.

Парижская метрика

Представьте страну, где все железные дороги идут лучами из столицы, а между собой не соединены. Чтобы попасть из одного города в другой, надо ехать через Париж, если только оба города не стоят на одной ветке.

Определение (парижская метрика).

На плоскости отметим точку $P$ («Париж»). Положим

\rho(x, y) = \begin{cases} |x - y|, & \text{если } x \text{ и } y \text{ лежат на одном луче из } P,\\ |x - P| + |P - y|, & \text{иначе.} \end{cases}

Шар вокруг самого Парижа — обычный круг. А вот шар вокруг другой точки $x$ выглядит странно. Если радиус $r$ меньше расстояния от $x$ до Парижа, то никуда, кроме своей ветки, не доехать, и шар — это отрезок на луче. Если радиус больше, то мы успеваем доехать до Парижа и ещё отъехать от него на $r - |x - P|$ в любую сторону. Тогда шар — отрезок на луче плюс круг вокруг Парижа.

Задача.

Проверьте, что парижская метрика удовлетворяет неравенству треугольника.

Подсказка

Разберите случаи: лежат ли точки $x$ , $y$ , $z$ на одном луче или на разных. Если путь из $x$ в $z$ идёт через Париж, то $\rho(x, z) = |x - P| + |P - z|$ , и полезно заметить, что всегда $\rho(x, y) \ge \bigl||x - P| - |y - P|\bigr|$ .

Задача. Париж — начало координат. Сходится ли последовательность $x_n = (1,\, 1/n)$ к точке $(1, 0)$ в парижской метрике?

Да, как и в обычной
Нет

Разбор

Точки $(1, 1/n)$ и $(1, 0)$ лежат на разных лучах, поэтому $\rho(x_n, (1, 0)) = \sqrt{1 + 1/n^2} + 1 > 2$ . Расстояние не стремится к нулю. Чтобы сходиться к точке $x \ne P$ , последовательность должна в конце концов сесть на её луч. Значит, открытые множества здесь совсем не такие, как у обычной метрики: например, отрезок луча без концов открыт.

Парижское расстояние никогда не меньше обычного: путь через Париж не короче прямого, так что $\rho(x, y) \ge |x - y|$ . Посмотрим, что это даёт для непрерывности.

Задача. Рассмотрим тождественное отображение $x \mapsto x$ между плоскостью с парижской метрикой и обычной плоскостью. Что верно?

Из парижской плоскости в обычную оно непрерывно, а обратно нет
Из обычной плоскости в парижскую оно непрерывно, а обратно нет
Оно непрерывно в обе стороны
Оно не непрерывно ни в одну сторону

Разбор

Из парижской в обычную: если $\rho(x, x_0) < \varepsilon$ , то и $|x - x_0| \le \rho(x, x_0) < \varepsilon$ , так что подходит $\delta = \varepsilon$ . Обратно непрерывности нет: последовательность $(1, 1/n)$ сходится к $(1, 0)$ в обычной плоскости, а в парижской, как мы видели, не сходится. Получилась непрерывная биекция, у которой обратное отображение не непрерывно.

Ультраметрика

Иногда неравенство треугольника выполняется в гораздо более сильной форме.

Определение (ультраметрика).

Метрика $\rho$ называется ультраметрикой, если для любых $x, y, z$

\rho(x, z) \le \max\bigl(\rho(x, y),\, \rho(y, z)\bigr).

Главный пример — дерево. Возьмём бесконечные последовательности из нулей и единиц и положим $\rho(a, b) = 2^{-n}$ , где $n$ — длина общего начала $a$ и $b$ . Чем дольше последовательности совпадают, тем они ближе. Последовательность — это бесконечный путь по двоичному дереву, а расстояние определяется тем, где пути разошлись. Если $a$ и $b$ разошлись на шаге $n$ , а $b$ и $c$ на шаге $m$ , то $a$ и $c$ совпадают по крайней мере до шага $\min(n, m)$ . Отсюда и усиленное неравенство.

В таких пространствах геометрия очень непривычная.

Утверждение (свойства ультраметрики).

Любой треугольник равнобедренный, причём две равные стороны не короче третьей.
Любая точка шара — его центр: если $y \in B(x, r)$ , то $B(y, r) = B(x, r)$ .
Два шара либо не пересекаются, либо один лежит в другом.

Схема доказательства

На дереве всё видно: шар — это поддерево, а у поддерева нет выделенной «середины». Два поддерева либо не пересекаются, либо одно растёт из другого.

Доказательство

Пусть $\rho(x, y) < \rho(y, z)$ . Тогда $\rho(x, z) \le \max(\rho(x, y), \rho(y, z)) = \rho(y, z)$ и $\rho(y, z) \le \max(\rho(y, x), \rho(x, z))$ . Во втором неравенстве максимум не может быть равен $\rho(x, y)$ , поэтому $\rho(y, z) \le \rho(x, z)$ . Итого $\rho(x, z) = \rho(y, z)$ .
Пусть $\rho(x, y) < r$ и $z \in B(x, r)$ . Тогда $\rho(y, z) \le \max(\rho(y, x), \rho(x, z)) < r$ , то есть $B(x, r) \subset B(y, r)$ . Обратное включение такое же.
Пусть шары $B(x, r)$ и $B(y, s)$ , $r \le s$ , имеют общую точку $z$ . По пункту 2 $B(x, r) = B(z, r) \subset B(z, s) = B(y, s)$ .

Задача. В ультраметрическом пространстве две стороны треугольника равны $2$ и $5$ . Какой может быть третья?

$2$
$3$
$5$
$7$

Ещё один знаменитый пример — 2-адическое расстояние на рациональных числах: числа тем ближе, чем на большую степень двойки делится их разность, $\rho(x, y) = 2^{-k}$ , если $x - y = 2^k \cdot \frac{a}{b}$ с нечётными $a$ и $b$ . В нём $2^n \to 0$ , и поэтому

1 + 2 + 4 + 8 + \dots = -1 .

Действительно, частичная сумма равна $2^n - 1$ , а её расстояние до $-1$ равно $\rho(2^n, 0) = 2^{-n} \to 0$ .

Расстояния где угодно

Метрика — это просто функция от пары объектов, поэтому мерить расстояние можно между чем угодно.

Между функциями. Для непрерывных функций на $[a, b]$ есть $\rho(f, g) = \max_{x} |f(x) - g(x)|$ , наибольшее расхождение графиков. Сходимость в этой метрике — это равномерная сходимость из анализа. А есть $\rho(f, g) = \int_a^b |f(x) - g(x)|\,dx$ , площадь между графиками, и сходимость в ней уже другая.
Между словами. Расстояние Хэмминга — в скольких позициях слова одной длины отличаются. Расстояние Левенштейна — сколько букв надо вставить, удалить или заменить. Так работает исправление опечаток.
В графах. Длина кратчайшего пути: по дорогам между городами или по знакомствам между людьми.
Между множествами. Расстояние Хаусдорфа между двумя фигурами — насколько далеко приходится отойти от одной фигуры, чтобы накрыть другую, и наоборот.
Между самими пространствами. Есть даже расстояние Громова–Хаусдорфа между метрическими пространствами. С ним можно говорить, что одно пространство близко к другому.

Задача. Чему равно расстояние $\max_{x \in [0, 1]} |f(x) - g(x)|$ между $f(x) = x$ и $g(x) = x^2$ ?

$0$
$1/4$
$1/2$
$1$

Разбор

Разность $x - x^2$ на $[0, 1]$ неотрицательна и максимальна при $x = 1/2$ , где она равна $1/2 - 1/4 = 1/4$ .

Что получилось

Метрики $\rho_1$ , $\rho_2$ , $\rho_\infty$ на $\mathbb{R}^n$ разные, но задают одни и те же открытые множества, а значит, одну и ту же сходимость и непрерывность.
В парижской метрике шары — отрезки и «отрезки с кругом», а сходимость совсем не такая, как на обычной плоскости.
В ультраметрике все треугольники равнобедренные, а любая точка шара — его центр.
Расстояние можно мерить между функциями, словами, множествами и даже пространствами.

Мы всё время видим одно и то же: важна не сама метрика, а то, какие множества получаются открытыми. В следующем уроке мы сделаем из этого определение.