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

Трансфінітна індукція — метод доведення, що узагальнює математичну індукцію на випадок незліченної кількості значень параметра.

Трансфінітна індукція базується на такому твердженні:

Нехай ${\displaystyle M}$ — цілком впорядкована множина, ${\displaystyle P(x)}$ при ${\displaystyle x\in M}$ — деяке твердження. Нехай для будь-якого ${\displaystyle x\in M}$ з того, що ${\displaystyle P(y)}$ істинне для всіх ${\displaystyle y<x}$, випливає, що істинним є твердження ${\displaystyle P(x)}$. Тоді твердження ${\displaystyle P(x)}$ є істинним для будь-якого ${\displaystyle x}$.

Зв'язок з математичною індукцією

Математична індукція є частковим випадком трансфінітної індукції. Дійсно, нехай ${\displaystyle M}$ — множина натуральних чисел. Тоді твердження трансфінітної індукції перетворюється в таке: якщо для будь-якого натурального ${\displaystyle n}$ із одночасної істинності тверджень ${\displaystyle P(1)}$, ${\displaystyle P(2)}$, ${\displaystyle \ldots }$, ${\displaystyle P(n-1)}$ випливає істинність твердження ${\displaystyle P(n)}$, тоді істинні всі твердження ${\displaystyle P(n)}$. При цьому база індукції, тобто ${\displaystyle P(1)}$, виявляється тривіальним частковим випадком при ${\displaystyle n=1}$.

Приклади використання трансфінітної індукції

У багатьох випадках трансфінітна індукція використовується разом із теоремою Цермело, яка стверджує, що будь-яку множину можна цілком упорядкувати. Теорема Цермело еквівалентна аксіомі вибору, тому доведення є неконструктивним^{[джерело?]}.

Як приклад покажемо, що можна задати деяку множину кіл таку, щоб через кожну точку площини проходило рівно два кола. Це твердження можна довести, побудувавши явну конструкцію.^{[уточнити]} Однак для випадку трьох кіл явна конструкція досі не відома, тоді як доведення її існування мало відрізнятиметься від наведеного нижче.^{[джерело?]}

Впорядкуємо всі точки множини так, щоб потужність множини точок, менших від ${\displaystyle x}$, була менша, ніж континуум (можна показати, що будь-яку множину можна цілком упорядкувати так, щоб для будь-якого її елемента множина менших від нього мала меншу потужність). Як ${\displaystyle P(x)}$ візьмемо таке твердження: можна провести меншу, ніж континуальну, множину різних кіл так, щоб кожна точка, менша або рівна ${\displaystyle x}$ була покрита рівно 2 колами, а всі інші точки були покриті не більше, ніж двома колами, а також для будь-якої точки ${\displaystyle y<x}$ цю множину можна вибрати такою, щоб вона містила множину кіл для точки ${\displaystyle y}$. Якщо ${\displaystyle x}$ — мінімальна точка, то візьмемо будь-які 2 різні кола, які проходять через цю точку. Твердження ${\displaystyle P(x)}$ для мінімального ${\displaystyle x}$ доведено. Нехай тепер ${\displaystyle x}$ — будь-яка точка, і відомо, що твердження є істинним для будь-якого ${\displaystyle y<x}$. Візьмемо об'єднання множин кіл для всіх точок ${\displaystyle y<x}$. Згідно з припущенням індукції можна вважати, що множини кіл для більших точок включають множини кіл для менших точок, тому отримана множина буде покривати точки площини не більше двох разів. Оскільки множина елементів, які менші ніж ${\displaystyle x}$, є меншою, ніж континуум, і кожна об'єднана множина менша, ніж континуум, то отримана множина також буде мати меншу потужність, ніж континуум. Побудована множина кіл уже двічі покриває всі точки, менші від ${\displaystyle x}$.

Покажемо тепер, як покрити ${\displaystyle x}$. Через ${\displaystyle x}$ проходить континуум кіл, які не перетинаються. Помітимо, що будь-яка пара кіл перетинається не більше, ніж у двох точках, а отже потужність множини точок площини, покритих двічі, менша, ніж континуум (тут використовується твердження, що множина ${\displaystyle A\times A}$ рівнопотужна до ${\displaystyle A}$, якщо ${\displaystyle A}$ — нескінченна множина). Це означає, що знайдеться континуум кіл, на яких немає точок, покритих 2 рази. Візьмемо з них одну або дві, в залежності від кількості кіл, що вже проходять через точку ${\displaystyle x}$. Твердження індукції доведено.

Див. також

• Математична індукція
• Цілком впорядкована множина

Джерела

• Андрійчук В.І., Комарницький М.Я., Іщук Ю.Б. (2003). Вступ до дискретної математики. Львів: Видавничий центр ЛНУ ім. І.Франка. с. 41—42.
• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)