Трансфинитная индукция - это расширение математической индукции до упорядоченных наборов, например, до наборов порядковые числа или кардинальные числа.
Пусть будет свойство определено для всех порядковых номеров . Предположим, что всякий раз, когда верно для всех , тогда также верно. Тогда трансфинитная индукция говорит нам, что верно для всех порядковых чисел.
Обычно доказательство разбивается на три случая:
Все три случаи идентичны, за исключением типа рассматриваемого порядкового номера. Формально их не нужно рассматривать отдельно, но на практике доказательства обычно настолько разные, что требуют отдельного представления. Ноль иногда считается предельным порядковым номером и затем может иногда рассматриваться в доказательствах в том же случае как предел или диналы.
Трансфинитная рекурсия аналогична трансфинитной индукции; однако вместо того, чтобы доказывать, что что-то верно для всех порядковых чисел, мы строим последовательность объектов, по одному для каждого порядкового номера.
В качестве примера, основу для (возможно, бесконечномерного) векторного пространства можно создать, выбрав вектор и для каждого порядкового номера α выбирая вектор, который не входит в span векторов . Этот процесс останавливается, когда нельзя выбрать вектор.
Более формально мы можем сформулировать теорему о трансфинитной рекурсии следующим образом:
Как и в случае индукции, мы можем обрабатывать разные типы ординалов отдельно: другая формулировка трансфинитной рекурсии следующая:
Обратите внимание, что нам нужны области G 2, G 3, чтобы быть достаточно широким, чтобы сделать вышеуказанные свойства значимыми. Единственность последовательности, удовлетворяющей этим свойствам, можно доказать с помощью трансфинитной индукции.
В более общем смысле, можно определять объекты трансфинитной рекурсией на любом хорошо обоснованном отношении R. (R даже не обязательно должен быть набором; он может быть надлежащим классом, при условии, что это отношение , подобное множеству ; т.е. для любого x совокупность всех y таких, что yRx является набором.)
Доказательства или построения с использованием индукции и рекурсии часто используют аксиому выбора для создания упорядоченного отношения, которое можно рассматривать с помощью трансфинитной индукции. Однако, если рассматриваемое отношение уже хорошо упорядочено, часто можно использовать трансфинитную индукцию, не прибегая к аксиоме выбора. Например, многие результаты о борелевских множествах доказываются трансфинитной индукцией по порядковому рангу множества; эти ранги уже упорядочены, поэтому аксиома выбора не нужна для их упорядочения.
Следующая конструкция множества Витали показывает один из способов использования аксиомы выбора в доказательстве с помощью трансфинитной индукции:
Вышеупомянутый аргумент существенно использует аксиому выбора в самом начале, чтобы правильно упорядочить числа. После этого шага аксиома выбора больше не используется.
Другие варианты использования аксиомы выбора более тонкие. Например, конструкция с помощью трансфинитной рекурсии часто не будет указывать уникальное значение для A α + 1, учитывая последовательность до α, но будет указывать только условие, что A α + 1 должен удовлетворять и утверждать, что существует по крайней мере один набор, удовлетворяющий этому условию. Если невозможно определить уникальный пример такого набора на каждом этапе, тогда может возникнуть необходимость задействовать (в некоторой форме) аксиому выбора, чтобы выбрать один такой на каждом этапе. Для индукций и рекурсий счетной длины достаточно более слабой аксиомы зависимого выбора. Поскольку существуют модели теории множеств Цермело – Френкеля, представляющие интерес для теоретиков множеств, которые удовлетворяют аксиоме зависимого выбора, но не полной аксиоме выбора, знание того, что конкретное доказательство требует только зависимого выбора, может быть полезным.