Transfinitní indukce

Z Wikipedie, otevřené encyklopedie

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.

Obsah

1 Věty o transfinitní indukci
- 1.1 Verze první
- 1.2 Verze druhá
2 Příklad použití
3 Podívejte se také na

[editovat] Věty o transfinitní indukci

Zatímco princip matematické indukce je považován za natolik samozřejmý, že je uváděn jako součást Peanovy axiomatiky přirozených čísel, 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:

[editovat] 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 \and ( \forall \alpha \isin On)(\alpha \subseteq X \implies \alpha \isin X)) \implies X = On$

[editovat] 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 \,\!$ 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
Rozepsáno do lidské :o) podoby:
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$

[editovat] 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 \,\!$ -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.)