www.wikidata.uk-ua.nina.az

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

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

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

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

Нехай  — цілком впорядкована множина, при  — деяке твердження. Нехай для будь-якого з того, що істинно для всіх , випливає, що вірним є твердження . Тоді твердження є вірним для будь-якого .

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

Математична індукція є частковим випадком трансфінітної індукції. Дійсно, нехай  — множина натуральних чисел. Тоді твердження трансфінітної індукції перетворюється в наступне: якщо для будь-якого натурального із одночасної істинності тверджень , , , випливає істинність твердження , тоді істинні всі твердження . При цьому база індукції, тобто , виявляється тривіальним частковим випадком при .

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

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

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

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

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

Див. також Редагувати

Джерела Редагувати


Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Transfinitna indukciya metod dovedennya sho uzagalnyuye matematichnu indukciyu u vipadku nezlichennogo chisla znachen parametra Transfinitna indukciya bazuyetsya na nastupnomu tverdzhenni Nehaj M displaystyle M cilkom vporyadkovana mnozhina P x displaystyle P x pri x M displaystyle x in M deyake tverdzhennya Nehaj dlya bud yakogo x M displaystyle x in M z togo sho P y displaystyle P y istinno dlya vsih y lt x displaystyle y lt x viplivaye sho virnim ye tverdzhennya P x displaystyle P x Todi tverdzhennya P x displaystyle P x ye virnim dlya bud yakogo x displaystyle x Zmist 1 Zv yazok z matematichnoyu indukciyeyu 2 Prikladi vikoristannya transfinitnoyi indukciyi 3 Div takozh 4 DzherelaZv yazok z matematichnoyu indukciyeyu RedaguvatiMatematichna indukciya ye chastkovim vipadkom transfinitnoyi indukciyi Dijsno nehaj M displaystyle M nbsp mnozhina naturalnih chisel Todi tverdzhennya transfinitnoyi indukciyi peretvoryuyetsya v nastupne yaksho dlya bud yakogo naturalnogo n displaystyle n nbsp iz odnochasnoyi istinnosti tverdzhen P 1 displaystyle P 1 nbsp P 2 displaystyle P 2 nbsp displaystyle ldots nbsp P n 1 displaystyle P n 1 nbsp viplivaye istinnist tverdzhennya P n displaystyle P n nbsp todi istinni vsi tverdzhennya P n displaystyle P n nbsp Pri comu baza indukciyi tobto P 1 displaystyle P 1 nbsp viyavlyayetsya trivialnim chastkovim vipadkom pri n 1 displaystyle n 1 nbsp Prikladi vikoristannya transfinitnoyi indukciyi RedaguvatiU bagatoh vipadkah transfinitna indukciya vikoristovuyetsya razom z teoremoyu Cermelo yaka stverdzhuye sho bud yaku mnozhinu mozhna cilkom vporyadkuvati Teorema Cermelo ekvivalentna aksiomi viboru tomu dovedennya ye nekonstruktivnim dzherelo Yak priklad pokazhemo sho mozhna zadati deyaku mnozhinu kil taku shob cherez kozhnu tochku ploshini prohodilo rivno dva kola Ce tverdzhennya mozhna dovesti pobuduvavshi yavnu konstrukciyu Odnak dlya vipadku troh kil yavna konstrukciya dosi ne vidoma todi yak dovedennya yiyi isnuvannya malo vidriznyatimetsya vid nizhchenavedenogo dzherelo Vporyadkuyemo vsi tochki mnozhini tak shob potuzhnist mnozhini tochok menshih x displaystyle x nbsp bula mensha nizh kontinuum mozhna pokazati sho bud yaku mnozhinu mozhna cilkom vporyadkuvati tak shob dlya bud yakogo jogo elementa mnozhini menshih za nogo malo menshu potuzhnist Yak P x displaystyle P x nbsp vizmemo nastupne tverdzhennya mozhna provesti menshu nizh kontinualnu mnozhinu riznih kil tak shob kozhna tochka yaka ye menshoyu abo rivnoyu x displaystyle x nbsp bula pokrita rivno 2 kolami a vsi inshi tochki buli pokritimi ne bilshe nizh dvoma kolami a takozh dlya bud yakoyi tochki y lt x displaystyle y lt x nbsp cyu mnozhinu mozhna vibrati takoyu shob vona mistila mnozhinu kil dlya tochki y displaystyle y nbsp Yaksho x displaystyle x nbsp minimalna tochka todi vizmemo bud yaki 2 rizni kola yaki prohodyat cherez cyu tochku Tverdzhennya P x displaystyle P x nbsp dlya minimalnogo x displaystyle x nbsp dovedeno Nehaj teper x displaystyle x nbsp bud yaka tochka i vidomo sho tverdzhennya ye virnim dlya bud yakogo y lt x displaystyle y lt x nbsp Vizmemo ob yednannya mnozhin kil dlya vsih tochok y lt x displaystyle y lt x nbsp Zgidno z pripushennyam indukciyi mozhna vvazhati sho mnozhini kil dlya bilshih tochok vklyuchayut mnozhini kil dlya menshih tochok tomu otrimana mnozhina bude pokrivati tochki ploshini ne bilshe dvoh raziv Tak yak mnozhina elementiv yaki ye menshi nizh x displaystyle x nbsp ye menshoyu nizh kontinuum i kozhna ob yednana mnozhina mensha nizh kontinuum todi otrimana mnozhina takozh bude mati menshu potuzhnist nizh kontinuum Pobudovana mnozhina kil vzhe vdvichi pokrivaye vsi tochki menshi x displaystyle x nbsp Pokazhemo teper yak pokriti x displaystyle x nbsp Cherez x displaystyle x nbsp prohodit kontinuum kil yaki ne peretinayutsya Pomitimo sho bud yaka para kil peretinayetsya ne bilshe nizh v dvoh tochkah a znachit potuzhnist mnozhini tochok ploshini pokritih 2 razi mensha nizh kontinuum tut vikoristovuyetsya tverdzhennya sho mnozhina A A displaystyle A times A nbsp ye rivnopotuzhnoyu do A displaystyle A nbsp yaksho A displaystyle A nbsp neskinchenna mnozhina Ce oznachaye sho znajdetsya kontinuum kil na yakih nemaye tochok pokritih 2 razi Vizmemo z nih odnu abo dvi v zalezhnosti vid kilkosti kil sho vzhe prohodyat cherez tochku x displaystyle x nbsp Tverdzhennya indukciyi dovedeno Div takozh RedaguvatiMatematichna indukciya Cilkom vporyadkovana mnozhinaDzherela RedaguvatiKuratovskij K Mostovskij A Teoriya mnozhestv Set Theory Teoria mnogosci M Mir 1970 416 s ros Otrimano z https uk wikipedia org w index php title Transfinitna indukciya amp oldid 40282725