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

Математическая концепция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Примечания

1. J. Schlöder, Ordinal Arithmetic. Дата обращения 24.03.2022.
2. Здесь нет необходимости отдельно предполагать, что верно. Поскольку нет меньше 0, то бессмысленно верно, что для всех верно. ${\displaystyle P(0)}$ ${\displaystyle \beta }$ ${\displaystyle \beta <0}$ ${\displaystyle P(\beta )}$
3. Функция класса — это правило (в частности, логическая формула), назначающее каждый элемент в левом классе элементу в правом классе. Это не функция, поскольку ее домен и кодомен не являются множествами.
4. На самом деле, область отношения даже не обязательно должна быть множеством. Она может быть собственным классом, при условии, что отношение R является множеством: для любого x совокупность всех y таких, что y  R  x, должна быть множеством.

Ссылки

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

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

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