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

проверено

Условие обрыва возрастающих цепочек

Определение 1. Пусть $S$ — частично упорядоченное множество, и пусть любая возрастающая последовательность $x_1\preccurlyeq x_2\preccurlyeq\ldots$ в $S$ стационарна, то есть существует такое $n\in\mathbb{N}$ , что $x_n=x_{n+1}=\ldots$ . Тогда говорят, что $S$ удовлетворяет условию обрыва возрастающих цепочек¹⁾.

Предложение 1. Условие обрыва возрастающих цепочек равносильно существованию в произвольном непустом подмножестве $S$ максимального элемента.

Доказательство.

Пусть для $S$ выполнено условие обрыва возрастающих цепочек, и пусть в $S$ найдется подмножество $T$ , не имеющее максимального элемента, тогда по индукции можно построить бесконечную возрастающую цепочку, выбирая на $i$ -м шаге элемент $x_i$ такой, что $x_{i-1}\preccurlyeq x_i$ . Обратно, пусть в каждом непустом подмножестве $M$ из $S$ существует максимальный элемент, тогда множество $M=\{x_n\}$ , состоящее из элементов возрастающей последовательности $x_1\preccurlyeq x_2\preccurlyeq\ldots$ имеет максимальный элемент , а следовательно, последовательность стабилизируется. $\blacksquare$

Условие обрыва убывающих цепочек

Определение 2. Пусть $S$ — частично упорядоченное множество с упорядочением $\succcurlyeq$ , и пусть любая убывающая последовательность $x_1\succcurlyeq x_2\succcurlyeq\ldots$ в $S$ стационарна, то есть существует такое $n\in\mathbb{N}$ , что $x_n=x_{n+1}=\ldots$ . Тогда говорят, что $S$ удовлетворяет условию обрыва убывающих цепочек²⁾.

Определение 3. Частично упорядоченное множество $S$ называется фундированным³⁾, если любое его непустое подмножество имеет минимальный элемент.

Пример 1. Множество натуральных чисел $\mathbb{N}$ со стандартным упорядочением $\leqslant$ является фундированным множеством.

Предложение 2. Условие обрыва убывающих цепочек равносильно существованию в произвольном непустом подмножестве $S$ минимального элемента.

Доказательство.

Пусть для $S$ выполнено условие обрыва убывающих цепочек, и пусть в $S$ найдется подмножество $T$ , не имеющее минимального элемента, тогда по индукции можно построить бесконечную убывающую цепочку, выбирая на $i$ -м шаге элемент $x_i$ такой, что $x_{i-1}\succcurlyeq x_i$ . Обратно, пусть в каждом непустом подмножестве $M$ из $S$ существует минимальный элемент, тогда множество $M=\{x_n\}$ , состоящее из элементов убывающей последовательности $x_1\succcurlyeq x_2\succcurlyeq\ldots$ имеет минимальный элемент, а следовательно, последовательность стабилизируется. $\blacksquare$

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

Принцип трансфинитной индукции

Теорема (принцип трансфинитной индукции)⁴⁾. Пусть $\mathcal{A}$ — фундированное множество и $\mathcal{B}$ — подмножество множества $\mathcal{A}$ . Если для любого $\alpha\in\mathcal{A}$ из того, что $\beta\in\mathcal{B}$ для всех $\beta<\alpha$ ⁵⁾ следует, что $\alpha\in\mathcal{B}$ , то $\mathcal{A}=\mathcal{B}$ .