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

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

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

Теорема. При сделанных предположениях существует одна и только одна функция значения которой удовлетворяют заданному соотношению.

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

Чтобы доказать существование, рассмотрим отрезки А множества (Отрезок А — это по-прежнему множество элементов, предшествующих некоторому элементу а.) Они составляют вполне упорядоченное множество (с отношением с В как отношением порядка); действительно, каждому элементу а взаимно однозначно соответствует отрезок А, состоящий из тех х, для которых и из следует В а А. Возьмем в качестве последнего отрезка

само множество тогда множество отрезков окажется вполне упорядоченным.

Теперь мы хотим доказать индукцией по А, что на каждом из А существует функция (определенная для всех х из А), удовлетворяющая заданным соотношениям. Пусть этот факт существования уже доказан для всех отрезков, предшествующих заданному отрезку А. Есть только два случая:

1. Отрезок А обладает последним элементом а. На множестве А, которое получается из А отбрасыванием элемента а, функция уже определена, потому что А предшествует отрезку А. Но с помощью совокупности значений и с помощью заданного соотношения определяется значение Если выбрать его, то функция будет определена на всех элементах отрезка А и на всех этих элементах без исключения будет удовлетворять заданному соотношению.

2. Отрезок А не имеет последнего элемента. Таким образом, каждый элемент а из А принадлежит уже предшествующему отрезку В. Но на каждом предшествующем отрезке В функция уже определена. Мы хотим определить:

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

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