9. Трансфинитная индукция

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

1) утверждение верно;

2) для любого если все для {5} верны, то и верно.

В таком случае все утверждения верны.

Это и есть принцип трансфинитной индукции. Это, конечно, никакая не аксиома, а очень простая теорема.

Доказательство. Предположим, что среди есть неверное утверждение. Рассмотрим множество всех неверных утверждений. Оно непусто, поскольку хотя бы одно утверждение неверно. Возьмем в нем наименьший элемент (это можно сделать, поскольку , а множество вполне упорядочено). Получаем противоречие со свойством 2).

Рассмотрим задачу на применение трансфинитной индукции.

Задача. Разбить пространство на непересекающиеся окружности (ненулевого радиуса).

Для решения этой задачи переформулируем аксиому выбора: любое непустое множество можно вполне упорядочить, т. е. для любого непустого множества можно придумать такое отношение порядка, относительно которого оно будет вполне упорядоченным. Докажем эквивалентность двух формулировок.

В одну сторону почти очевидно. Старая формулировка аксиомы выбора эквивалентна такой: для любого множества существует функция, сопоставляющая любому его непустому подмножеству некоторый элемент этого подмножества. Если же множество вполне упорядоченно, каждому его подмножеству можно сопоставить наименьший элемент — это и есть функция выбора.

В другую сторону доказательство гораздо сложнее, не будем здесь на нем останавливаться.

Теперь будем разбивать на окружности. Введем на отношение вполне упорядоченности, причем потребуем, чтобы это отношение было минимальным, т. е. никакой левый луч с концом в (множество ) не был равномощен (или не имел бы мощность континуум). Такое отношение порядка всегда найдется. Действительно, рассмотрим множество всех левых лучей мощности континуум. Упорядочим их в соответствии с порядком между концами этих левых лучей. Возьмем наименьший луч мощности континуум и поставим его в соответствие всему , т. е. просто заменим на этот луч. Тогда все меньшие лучи будут иметь мощность меньше континуума, и мы получим минимальное отношение вполне упорядоченности. Пусть — наименьшая точка в (в смысле построенной нами минимальной вполне упорядоченности). Проведем через нее произвольную окружность — первую в требуемом множестве окружностей. Далее, пусть через все точки , которые меньше некоторого фиксированного , мы уже провели непересекающиеся окружности. Для возможны два случая.

Рис. 5

1. Точка уже лежит на одной из проведенных до этого окружностей. Тогда доказывать нечего.

2. Точка не лежит ни на одной из уже проведенных окружностей. Тогда поступим следующим образом. Рассмотрим все плоскости, проходящие через . Их континуум. Но окружностей, построенных до этого, меньше, чем континуум! Это следует из минимальности выбранного нами отношения порядка. Значит, найдется плоскость , проходящая через и не содержащая ни одной из проведенных окружностей. Каждая такая окружность пересекает не более чем в двух точках, поэтому общее "количество" таких точек (обозначим их объединение через ) меньше континуума. Проведем в плоскости семейство окружностей, попарно касающихся друг друга в точке (рис. 5). Каждая из точек объединения лежит не более чем на одной окружности из проведенного семейства, следовательно, найдется окружность, проходящая через и не пересекающая ни одну из уже проведенных, что и требовалось. А теперь, воспользовавшись трансфинитной индукцией, получаем множество непересекающихся окружностей, покрывающих каждую точку в .

Рис. 6

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

Рассмотрим шар, например, земной. Проведем окружность, проходящую через центр Земли и через Северный полюс, при этом полностью содержащуюся в шаре (рис. 6, а). Рассмотрим в этом шаре концентрические с ним сферы. Все они, кроме самой большой, имеют с окружностью две общие точки, а каждый, наверное, умеет разбивать сферу без двух точек на окружности (если эти точки — Северный и Южный полюса, то разбиение совсем простое, а дальше можно просто растягивать и сжимать сферу, рис. 6, б). С большой сферой без полюсов поступим также. Что в итоге получилось? Мы разбили шар без Южного полюса (Северный покрыт первой окружностью) на непересекающиеся окружности. А теперь поставим их друг на друга вдоль оси (в трехмерной системе координат). Остальные точки пространства покроем параллельными плоскости окружностями (т. е. лежащими в параллельных плоскостях) с центром на оси (рис. 6, в).

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

1. Построить функцию из в , график которой на плоскости пересекает любой отрезок{6}.

2. Доказать, что квадрат любого бесконечного множества равномощен самому множеству.

{5} По определению, , если и .

{6} Двумя чертами слева выделены тексты упражнений для самостоятельного решения.