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

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

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

Определение 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}$ .

Пример 2. Частным случаем принципа трансфинитной индукции является принцип математической индукции, стоит лишь положить $\mathcal{A}=\mathbb{N}$ .

Литература

Атья М., Макдональд И. «Введение в коммутативную алгебру», Мир, 1972.
Верещагин Н.К., Шень А. «Лекции по математической логике и теории алгоритмов. Начала теории множеств», МЦНМО, 1999.
Гордон Е.И., Полотовский Г.М. «Мощность бесконечных множеств», Издательство ННГУ, 1998.
Ершов Ю.Л., Палютин Е.А. «Математическая логика», Наука, 1987.

¹⁾ ACC, ascending chain condition

²⁾ DCC, descending chain condition

³⁾ well-founded set

⁴⁾ transfinite induction

⁵⁾ По определению $\beta<\gamma$ , если $\beta\leqslant\gamma$ и $\beta\neq\gamma$ .

glossary/induction/transfinite.txt · Последние изменения: 15.01.2010 22:19:40 ladilova

Наверх