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

Представление порядковых чисел до $\omega ^{\omega }$. Каждый виток спирали представляет собой одну степень $\omega$. Трансфинитная индукция требует доказательства базового случая (используется для 0), случая-преемника (используется для тех порядковых номеров, у которых есть предшественник) и предельного случая (используется для порядковых номеров, у которых нет предшественника).

Трансфинитная индукция — это расширение математической индукции на хорошо упорядоченные множества , например, на множества порядковых или кардинальных чисел . Его корректность является теоремой ZFC .

Индукция по случаям

Позволять $P(\alpha )$ быть свойством, определенным для всех порядковых номеров $\alpha$. Предположим, что всякий раз, когда $P(\beta )$ верно для всех $\beta <\alpha$, затем $P(\alpha )$ это тоже правда. Тогда трансфинитная индукция говорит нам, что $P$ верно для всех ординалов.

Обычно доказательство разбивается на три случая:

• Нулевой случай: Докажите, что $P(0)$ это правда.
• Случай преемника: докажите, что для любого порядкового номера преемника $\alpha +1$, $P(\alpha +1)$ следует из $P(\alpha )$ (и при необходимости $P(\beta )$ для всех $\beta <\alpha$).
• Предельный случай: докажите, что для любого предельного порядкового номера $\lambda$, $P(\lambda )$ следует из $P(\beta )$ для всех $\beta <\lambda$.

Все три случая идентичны, за исключением рассматриваемого типа ординала. Формально их не нужно рассматривать отдельно, но на практике доказательства обычно настолько различны, что требуют отдельного представления. Ноль иногда считается предельным порядковым номером , а затем иногда может рассматриваться в доказательствах в том же случае, что и предельные порядковые номера.

Трансфинитная рекурсия

Трансфинитная рекурсия аналогична трансфинитной индукции; однако вместо того, чтобы доказывать, что что-то справедливо для всех порядковых чисел, мы создаем последовательность объектов, по одному для каждого порядкового номера.

Например, основу (возможно, бесконечномерного) векторного пространства можно создать, начав с пустого набора и для каждого порядкового номера α > 0 выбрав вектор, который не входит в диапазон векторов. $\{v_{\beta }\mid \beta <\alpha \}$. Этот процесс останавливается, когда вектор не может быть выбран.

Более формально мы можем сформулировать теорему о трансфинитной рекурсии следующим образом:

Теорема о трансфинитной рекурсии (версия 1) . Учитывая функцию класса G : V → V (где V — класс всех множеств), существует единственная трансфинитная последовательность F : Ord → V (где Ord — класс всех ординалов) такая, что

$F(\alpha )=G(F\upharpoonright \alpha )$ для всех ординалов α , где $\upharpoonright$ обозначает ограничение области определения F порядковыми числами < α .

Как и в случае индукции, мы можем рассматривать разные типы ординалов отдельно: другая формулировка трансфинитной рекурсии следующая:

Теорема о трансфинитной рекурсии (версия 2) . Учитывая множество g ₁ и функции классов G ₂ , G ₃ , существует единственная функция F : Ord → V такая, что

• F (0) = г ₁ ,
• F ( α 1) = G2 ₊ ( F ( α )), для всех α ∈ Ord,
• $F(\lambda )=G_{3}(F\upharpoonright \lambda )$, для всех пределов λ ≠ 0.

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

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

Связь с аксиомой выбора

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

Следующая конструкция множества Витали показывает один из способов использования выбранной аксиомы в доказательстве методом трансфинитной индукции:

Во-первых, правильно упорядочите действительные числа (именно здесь вступает в силу аксиома выбора через теорему о правильном порядке ), давая последовательность $\langle r_{\alpha }\mid \alpha <\beta \rangle$, где β — ординал мощности континуума . Пусть v ₀ равно r ₀ . Тогда пусть v ₁ равно r _{α 1} , где α ₁ наименьшее такое, что r _{α 1} − v ₀ не является рациональным числом . Продолжать; на каждом шаге используйте наименее вещественный из последовательности r , который не имеет рационального различия ни с одним элементом, построенным на данный момент в последовательности v . Продолжайте до тех пор, пока не будут исчерпаны все действительные числа в последовательности r . Последняя последовательность v будет перечислять набор Витали.

Приведенный выше аргумент с самого начала существенно использует аксиому выбора, чтобы правильно упорядочить реальность. После этого шага аксиома выбора больше не используется.

Другие варианты использования аксиомы выбора более тонкие. Например, конструкция с помощью трансфинитной рекурсии часто не будет определять уникальное значение для A _{α +1} , учитывая последовательность до α , а будет указывать только условие , которому должно удовлетворять A _{α +1} , и доказывать, что существует хотя бы один множество, удовлетворяющее этому условию. Если невозможно определить уникальный пример такого набора на каждом этапе, то может потребоваться вызвать (в той или иной форме) аксиому выбора, чтобы выбрать один такой набор на каждом этапе. Для индукций и рекурсий счетной более слабой аксиомы зависимого выбора длины достаточно . Поскольку существуют модели теории множеств Цермело-Френкеля, представляющие интерес для теоретиков множеств, которые удовлетворяют аксиоме зависимого выбора, но не полной аксиоме выбора, знание того, что конкретное доказательство требует только зависимого выбора, может быть полезным.

См. также

• Математическая индукция
• ∈-индукция
• Трансфинитное число
• Хорошо обоснованная индукция
• Лемма Цорна

Ссылки

• Суппес, Патрик (1972), «Раздел 7.1», Аксиоматическая теория множеств , Dover Publications , ISBN  0-486-61630-4

Внешние ссылки

• Эмерсон, Джонатан ; Лезама, Марк и Вайсштейн, Эрик В. «Трансфинитная индукция» . Математический мир .