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

проверено

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

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

Предложение 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 $ удовлетворяет условию обрыва убывающих цепочек2).

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

Пример 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$

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

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

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

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

Литература

1)
ACC, ascending chain condition
2)
DCC, descending chain condition
3)
well-founded set
4)
transfinite induction
5)
По определению $\beta<\gamma$, если $\beta\leqslant\gamma$ и $\beta\neq\gamma$.
glossary/induction/transfinite.txt · Последние изменения: 09.01.2011 19:37:13 — Ладилова Анна
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0