====== Трансфинитная индукция ====== проверено ===== Условие обрыва возрастающих цепочек ===== __Определение 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>"теория множеств" "вполне упорядоченное множество" "трансфинитная индукция" "условие обрыва возрастающих цепочек" "условие обрыва убывающих цепочек" "фундированное множество" "частично упорядоченное множество"}}