Transfinitní indukce

Spirá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\wedge (\mathrm{\forall }\alpha \in On)(\alpha \subseteq X⟹\alpha \in X))⟹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$ 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:

1. $X\subseteq On$
2. $\mathrm{\varnothing }\in X$
3. $(\mathrm{\forall }\alpha \in On)(\alpha \in X⟹\alpha \cup \{\alpha \}\in X)$
4. pro každý limitní ordinál $\alpha$ platí $\alpha \subseteq X⟹\alpha \in 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:

1. $(\mathrm{\forall }\alpha ,\beta ,\gamma \in On)({\alpha }^{\beta +\gamma }={\alpha }^{\beta }.{\alpha }^{\gamma })$
2. $(\mathrm{\forall }\alpha ,\beta ,\gamma \in 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.)

Související články

• Transfinitní rekurze
• Ordinální číslo
• Ordinální aritmetika
• Teorie množin
• Peanova aritmetika
• Matematická indukce
• Fundovaná indukce