====== Трансфинитная индукция ======
проверено
===== Условие обрыва возрастающих цепочек =====
__Определение 1.__ Пусть S --- [[:glossary:set:ordered:partially|частично упорядоченное множество]], и пусть любая возрастающая последовательность x_1\preccurlyeq x_2\preccurlyeq\ldots в S стационарна, то есть существует такое n\in\mathbb{N}, что x_n=x_{n+1}=\ldots. Тогда говорят, что S удовлетворяет **условию обрыва возрастающих цепочек**((ACC, ascending chain condition)).
__Предложение 1.__ Условие обрыва возрастающих цепочек равносильно существованию в произвольном непустом подмножестве S [[:glossary:set:ordered:partially|максимального элемента]].\\
Пусть для 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 удовлетворяет **условию обрыва убывающих цепочек**((DCC, descending chain condition)).
__Определение 3.__ Частично упорядоченное множество S называется **фундированным**((well-founded set)), если любое его непустое подмножество имеет минимальный элемент.
__Пример 1.__ [[:glossary:set:integer:positive|Множество натуральных чисел]] \mathbb{N} со стандартным упорядочением \leqslant является фундированным множеством.
__Предложение 2.__ Условие обрыва убывающих цепочек равносильно существованию в произвольном непустом подмножестве S [[:glossary:set:ordered:partially|минимального элемента]].\\
Пусть для 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
Последнее предложение показывает, что понятие фундированного множества эквивалентно понятию частично упорядоченного множества с условием обрыва убывающих цепочек.
===== Принцип трансфинитной индукции =====
__Теорема (принцип трансфинитной индукции)((transfinite induction)).__ Пусть \mathcal{A} --- фундированное множество и \mathcal{B} --- подмножество множества \mathcal{A}. Если для любого \alpha\in\mathcal{A} из того, что \beta\in\mathcal{B} для всех \beta<\alpha((По определению \beta<\gamma, если \beta\leqslant\gamma и \beta\neq\gamma.)) следует, что \alpha\in\mathcal{B}, то \mathcal{A}=\mathcal{B}.
__Пример 2.__ Частным случаем принципа трансфинитной индукции является [[:glossary:set:integer:positive|принцип математической индукции]], стоит лишь положить \mathcal{A}=\mathbb{N}.
===== Литература =====
* [[http://www.ozon.ru/context/detail/id/3249529/?partner=lds1938|Атья М., Макдональд И. «Введение в коммутативную алгебру», Факториал, 2003.]]
* [[http://www.ozon.ru/context/detail/id/94505/?partner=lds1938|Верещагин Н.К., Шень А. «Лекции по математической логике и теории алгоритмов. Начала теории множеств», МЦНМО, 2008.]]
* [[http://www.unn.ru/rus/books/book7.htm|Гордон Е.И., Полотовский Г.М. «Мощность бесконечных множеств», Издательство ННГУ, 1998.]]
* [[http://www.ozon.ru/context/detail/id/2191508/?partner=lds1938|Ершов Ю.Л., Палютин Е.А. «Математическая логика», Лань, 2005.]]
{{tag>"теория множеств" "вполне упорядоченное множество" "трансфинитная индукция" "условие обрыва возрастающих цепочек" "условие обрыва убывающих цепочек" "фундированное множество" "частично упорядоченное множество"}}