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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Теорема о трансфинитной рекурсии (версия 2) . Для множества g ₁ и функций классов G ₂ , G ₃ существует единственная функция F : Ord → V такая, что
• F (0) = g ₁ ,
• F ( α + 1) = G ₂ ( F ( α )) для всех α ∈ Ord,
• F ( λ ) = G ₃ ( F λ ) для любого предела λ ≠ 0.${\ displaystyle \ upharpoonright}$

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

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

Отношение к аксиоме выбора

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

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

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

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

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

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

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

Примечания

использованная литература

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

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

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