Перегляд вихідного коду сторінки Трансфінітна індукція

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

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

== Зв'язок з математичною індукцією ==
[[Математична індукція]] є частковим випадком трансфінітної індукції. Дійсно, нехай <math>M</math> — множина [[натуральні числа|натуральних чисел]]. Тоді твердження трансфінітної індукції перетворюється в наступне: якщо для будь-якого натурального <math>n</math> із одночасної істинності тверджень <math>P(1)</math>, <math>P(2)</math>, <math>\ldots</math>, <math>P(n-1)</math> випливає істинність твердження <math>P(n)</math>, тоді істинні всі твердження <math>P(n)</math>. При цьому база індукції, тобто <math>P(1)</math>, виявляється тривіальним частковим випадком при <math>n=1</math>.

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

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

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

Покажемо тепер, як покрити <math>x</math>. Через <math>x</math> проходить континуум кіл, які не [[перетин множин|перетинаються]]. Помітимо, що будь-яка пара кіл перетинається не більше, ніж в двох точках, а значить потужність множини точок площини, покритих 2 рази, менша, ніж континуум (тут використовується твердження, що множина <math>A\times A</math> є [[Рівнопотужність|рівнопотужною]] до <math>A</math>, якщо <math>A</math> — нескінченна множина). Це означає, що знайдеться континуум кіл, на яких немає точок, покритих 2 рази. Візьмемо з них одну або дві, в залежності від кількості кіл, що вже проходять через точку <math>x</math>. Твердження індукції доведено.

== Див. також ==
* [[Математична індукція]]
* [[Цілком впорядкована множина]]

== Джерела ==
* {{cite book |автор=Андрійчук В.І., Комарницький М.Я., Іщук Ю.Б. |url=http://moodle.nati.org.ua/mod/resource/view.php?id=9295 |назва=Вступ до дискретної математики |місце=Львів |видавництво=Видавничий центр ЛНУ ім. І.Франка |рік=2003 |pages=41{{ndash}}42 }}
* {{Куратовский.Мостовский.Теория множеств}}

{{Теорія множин}}
{{Математична логіка}}

[[Категорія:Математична логіка]]
[[Категорія:Теорія множин]]