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

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

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

Пусть 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. Утверждение индукции доказано.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home