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

Трансфинитная индукция — метод доказательства, обобщающий математическую индукцию на случай несчётного числа значений параметра.

Трансфинитная индукция основана на следующем утверждении:

Пусть $M$ — вполне упорядоченное множество, $P(x)$ при $x\in M$ — некоторое утверждение. Пусть для любого $x\in M$ из того, что $P(y)$ истинно для всех $y<x$ следует, что верно $P(x)$. Тогда утверждение $P(x)$ верно для любого $x$.

Связь с математической индукцией

Математическая индукция является частным случаем трансфинитной индукции. Действительно, пусть $M$ — множество натуральных чисел. Тогда утверждение трансфинитной индукции превращается в следующее: если для любого натурального $n$ из одновременной истинности утверждений $P(1)$, $P(2)$, $\ldots$, $P(n-1)$ следует истинность утверждения $P(n)$, то истинны все утверждения $P(n)$. При этом база индукции, то есть $P(1)$, оказывается тривиальным частным случаем при $n=1$.

Примеры использования трансфинитной индукции

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

В качестве примера докажем, что можно провести некоторое множество окружностей так, чтобы через каждую точку плоскости проходило ровно 2 окружности. (В данном случае можно привести и явную конструкцию, однако для случая трёх окружностей доказательство ниже лишь слегка изменяется, а явная конструкция пока не известна.)

Вполне упорядочим точки плоскости так, чтобы мощность множества точек, меньших $x$ была меньше, чем континуум (можно показать, что любое множество можно вполне упорядочить так, чтобы для любого его элемента множество меньших его имело меньшую мощность). В качестве $P(x)$ возьмем следующее утверждение: можно провести менее, чем континуальное множество различных окружностей так, чтобы каждая точка меньшая или равная $x$ была покрыта ровно 2 окружностями, а остальные точки были покрыты не более, чем двумя окружностями, а также для любой точки $y<x$ это множество можно выбрать таким, чтобы оно содержало множество окружностей для точки $y$. Если $x$ — минимальная точка, то возьмем любые 2 различные окружности проходящие через эту точку. Утверждение $P(x)$ для минимального $x$ доказано. Пусть теперь $x$ — любая точка и известно, что утверждение верно для любого $y<x$. Возьмем объединение наборов окружностей для всех точек $y<x$. По предположению индукции можно считать, что наборы окружностей для больших точек включают наборы окружностей для меньших точек, поэтому полученный набор будет покрывать точки плоскости не более двух раз. Так как множество элементов меньших $x$ меньшее, чем континуум и каждое объединяемое множество меньше, чем континуум, то полученное множество будет также иметь мощность меньшую, чем континуум. Построенное множество окружностей уже 2 раза покрывает все точки, меньшие $x$.

Покажем теперь, как покрыть $x$. Через $x$ проходит континуум непересекающихся окружностей. Заметим, что любая пара окружностей пересекается не более, чем в двух точках, а значит мощность множества точек плоскости, покрытых 2 раза, меньше, чем континуум (здесь используется утверждение, что $A\times A$ равномощно $A$, если $A$ — бесконечное множество). Значит найдется континуум окружностей, на которых нет точек, покрытых 2 раза. Возьмем из них одну или две, в зависимости от количества окружностей, уже проходящих через точку $x$. Утверждение индукции доказано.

Литература

• Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970. — 416 с.

См. также

• Математическая индукция
• Трансфинитное число
• Вполне упорядоченное множество