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

Материал из Википедии — свободной энциклопедии

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

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

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

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

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

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

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

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

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