Cesko.wiki Transfinitní indukce
Author
Albert FloresSpirála znázorňující všechna ordinální čísla menší než ωω. Transfinitní indukce je postup důkazu používaný v teorii množin obdobný jako klasická matematická indukce, ale rozšířený z přirozených čísel na ordinální čísla.
Věty o transfinitní indukci
Přestože princip matematické indukce je uváděn jako součást Peanovy axiomatiky přirozených čísel, je třeba jej v axiomatice teorie množin ZF dokázat jako větu, neboť přirozená čísla v ní nejsou elementární pojem, ale je třeba je zkonstruovat. Stejně tak v případě transfinitní indukce se jedná o věty (i když s poměrně snadným důkazem), které poskytují návod, jak při důkazu postupovat:
Verze první
Je-li X třída ordinálních čísel, pro kterou platí, že každou svou podmnožinu obsahuje zároveň jako prvek, pak je X shodná s třídou On všech ordinálních čísel.
(X \subseteq On \land ( \forall \alpha \isin On)(\alpha \subseteq X \implies \alpha \isin X)) \implies X = On
Verze druhá
Pokud je X třída ordinálních čísel, která obsahuje prázdnou množinu, s každým ordinálem \alpha \,\. zároveň ordinál \alpha + 1 \,\. +more a pro každý limitní ordinál \alpha \,\. , který je podmnožinou X platí, že \alpha \,\. je zároveň prvkem X, pak tato třída X obsahuje všechna ordinální čísla, tj. X = On.
Jinými slovy pokud platí následující čtyři podmínky, pak X = On: # X \subseteq On # \emptyset \isin X # ( \forall \alpha \isin On)(\alpha \isin X \implies \alpha \cup \{ \alpha \} \isin X) # pro každý limitní ordinál \alpha \,\! platí \alpha \subseteq X \implies \alpha \isin X
Příklad použití
Transfinitní indukce se používá při důkazu značného množství vět z ordinální aritmetiky, mimo jiné například při důkazu, že mocnění na ordinálních číslech je rozšířením mocnění na přirozených číslech:
# ( \forall \alpha,\beta,\gamma \isin On) ( \alpha^{\beta+\gamma} = \alpha^\beta . \alpha^\gamma) # ( \forall \alpha,\beta,\gamma \isin On) ( \alpha^{\beta.\gamma} = (\alpha^\beta)^\gamma)
Důsledkem principu transfinitní indukce je princip transfinitní rekurze, tj. možnost jednoznačně definovat zobrazení na ordinálních číslech předpisem, který využívá pro výpočet \alpha \,\. +more -té hodnoty hodnot pro ordinální čísla menší než \alpha \,\. . (Je tomu obdobně, jako u běžného aritmetického principu matematické indukce, ze kterého vyplývá možnost používat rekurzi na přirozených číslech. ).