Трансфинитная индукция
Материал из Википедии — свободной энциклопедии
Трансфинитная индукция — метод доказательства, обобщающий математическую индукцию на случай несчетного числа значений параметра.
Трансфинитная индукция основана на следующем утверждении:
|
Пусть M — вполне упорядоченное множество, P(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. Утверждение индукции доказано.
