Transfinitní indukce

Transfinitní indukce je důkazová metoda, která zobecňuje matematickou indukci na případ nespočetného množství hodnot parametrů.

Popis

Transfinitní indukce je založena na následujícím tvrzení:

Nechť je dobře založená množina (tj. částečně uspořádaná množina , ve které má každá neprázdná podmnožina minimální prvek) a nechť je nějaký příkaz. Ať pro cokoli z toho, co platí pro všechny , vyplývá, že je to pravda . Pak je tvrzení pravdivé pro všechny . $M$ $P(x)$ $x\v M$ $x\v M$ $P(y)$ $y<x$ $P(x)$ $P(x)$ $X$

Vztah s matematickou indukcí

Matematická indukce je speciální případ transfinitní indukce. Nechť je skutečně množina přirozených čísel (zvláštní případ dobře uspořádané množiny). Pak se tvrzení o transfinitní indukci změní na následující: jestliže pro jakýkoli přirozený současná pravda výroků , , , implikuje pravdivost výroku , pak jsou pravdivá všechna tvrzení . V tomto případě se indukční základna, tedy , ukazuje jako triviální speciální případ pro . $M$ $n$ $P(1)$ $P(2)$ $\ldots$ $P(n-1)$ $P(n)$ $P(n)$ $P(1)$ $n=1$

Příklady použití

V mnoha případech se transfinitní indukce používá ve spojení se Zermelovým teorémem , který říká, že jakákoliv množina může být dobře uspořádána. Zermelova věta je ekvivalentní axiomu výběru , takže důkaz je nekonstruktivní .

Jako příklad si dokažme, že je možné nakreslit určitou sadu kružnic tak, aby každým bodem roviny procházely právě 2 kružnice. (V tomto případě lze také uvést explicitní konstrukci, ale pro případ tří kruhů se níže uvedený důkaz mění jen nepatrně a explicitní konstrukce ještě není známa).

Body roviny zcela uspořádáme tak, že mohutnost množiny bodů menší než je menší než kontinuum (lze ukázat, že kteroukoli množinu lze zcela uspořádat tak, že pro jakýkoli její prvek má množina menších menší mohutnost). Vezměme si jako příklad následující tvrzení: je možné nakreslit méně než souvislou sadu různých kružnic tak, že každý bod menší nebo rovný je pokryt přesně 2 kružnicemi a zbývající body jsou pokryty maximálně dvěma kružnicemi. a pro jakýkoli bod lze tuto množinu vybrat tak, že obsahuje množinu kružnic pro daný bod . Pokud je minimální bod, pak vezmeme libovolné 2 různé kružnice procházející tímto bodem. Tvrzení pro minimum je dokázáno. Nechť je nyní libovolný bod a je známo, že výrok platí pro jakýkoli . Vezměte spojení sad kruhů pro všechny body . Indukční hypotézou můžeme předpokládat, že množiny kružnic pro velké body zahrnují množiny kružnic pro menší body, takže výsledná množina pokryje body roviny maximálně dvakrát. Protože množina prvků menší než , je menší než kontinuum a každá spojená množina je menší než kontinuum, bude mít výsledná množina také mohutnost menší než kontinuum. Sestrojená množina kružnic již pokrývá všechny body méně než 2krát . $X$ $P(x)$ $X$ $y<x$ $y$ $X$ $P(x)$ $X$ $X$ $y<x$ $y<x$ $X$ $X$

Nyní si ukážeme, jak zakrýt . Prochází jím kontinuum neprotínajících se kružnic . Všimněte si, že jakákoliv dvojice kružnic se protíná nejvýše ve dvou bodech, což znamená, že mohutnost množiny bodů 2krát pokryté roviny je menší než kontinuum (zde používáme výrok, který je ekvivalentní k if je nekonečná množina ). To znamená, že existuje kontinuum kruhů, na kterých nejsou žádné body pokryté dvakrát. Vezměme si jeden nebo dva z nich, v závislosti na počtu kruhů, které již procházejí bodem . Indukční tvrzení je dokázáno. $X$ $X$ $A\krát A$ $A$ $A$ $X$

Viz také

Literatura

Kuratovský K., Mostovský A. Teorie množin. - M .: Mir, 1970. - 416 s.