Transfinitní rekurze

Transfinitní rekurze je matematický pojem z oboru teorie množin, který zobecňuje běžně používaný pojem rekurze z přirozených čísel na všechna ordinální čísla.

Motivace

Na množině přirozených čísel existuje řada funkcí, které jsou definovány „rekurzivně“, tj. hodnota pro další číslo v pořadí závisí na hodnotách pro předcházející (menší) přirozená čísla.

Příklady jsou:

• faktoriál, kde $f(1)=1$ a $f(n+1)=(n+1).f(n)$
• Fibonacciho čísla, kde $f(1)=1,f(2)=1,f(n+2)=f(n+1)+f(n)$

To, že definováním podobného předpisu jsme opravdu získali jednoznačně určenou funkci na celé množině přirozených čísel, zaručuje věta o rekurzi, která se dokazuje pomocí principu matematické indukce.

Tento princip lze rozšířit pomocí transfinitní indukce z množiny přirozených čísel na celou třídu $𝕆n$ všech ordinálních čísel - získáváme tím princip transfinitní rekurze, který zjednodušeně řečeno zaručuje jednoznačnost funkce, která je pro každé ordinální číslo definována pomocí hodnot pro menší ordinální čísla.

Věty o transfinitní rekurzi

Základní varianta

Předpokládejme, že $G$ je třídové zobrazení, které každé množině $x$ přiřazuje množinu $G(x)$. Pak existuje právě jedno třídové zobrazení $F$ na třídě $𝕆n$ všech ordinálních čísel takové, že
$(\mathrm{\forall }\alpha \in 𝕆n)(F(\alpha )=G(F|\alpha ))$

$F|\alpha$ v předchozí větě znamená zúžení zobrazení $F$ na množinu $\alpha$

Pro pochopení této věty je důležité si uvědomit, že pro ordinální čísla platí $\alpha <\beta \iff \alpha \in \beta$ a zápis
$F(\alpha )=G(F|\alpha )$
neříká tedy nic jiného než:
hodnota $F$ pro $\alpha$ závisí (pomocí předpisu $G$) na hodnotách $F$ pro menší ordinální čísla než $\alpha$.

Oddělení předpisu pro limitní ordinály

Běžnější (a přehlednější) verzí věty o transfinitní rekurzi je případ, kdy pro izolované ordinály závisí hodnota pouze na jeho předchůdci, zatímco pro limitní ordinály je předpis definován jiným způsobem:

Je-li dána množina $x$ a dvě třídová zobrazení $G,H$ definovaná pro každou množinu, pak existuje právě jedno třídové zobrazení $F$ na třídě $𝕆n$ všech ordinálních čísel takové, že

• $F(0)=x$
• $F(\alpha +1)=G(F(\alpha ))$
• $F(\alpha )=H(F|\alpha )$ pro limitní ordinál $\alpha$

To už je podobnější běžné (finitní) rekurzi na přirozených číslech. Důvod, proč se zde vyskytuje třetí předpis, je ten, že limitní ordinály (například $\omega$) nemají přímého předchůdce - hodnotu je tedy pro ně nutné rekurzivně definovat z hodnot nějaké množiny menších ordinálů.

Příklady

Rekurzivně definované třídové zobrazení

Zobecněním funkce faktoriál podle druhé verze věty o transfinitní rekurzi z předchozího odstavce získáváme:

• $F(0)=1$
• $F(\alpha +1)=F(\alpha ).(\alpha +1)$
• $F(\alpha )=sup\{F(\beta ):\beta <\alpha \}$ pro limitní $\alpha$

Jaké vlastnosti má takto definovaná funkce?

• Pro konečné ordinály (tj. přirozená čísla) se taková funkce shoduje s „normálním“ faktoriálem.
• Pro množinu všech přirozených čísel je $F(\omega )=sup\{F(\beta ):\beta <\omega \}=\omega$
• $F(\omega +1)=F(\omega ).(\omega +1)={\omega }^2+\omega$
• $\dots$

Důkaz pomocí transfinitní rekurze

Dalším příkladem využití transfinitní rekurze je důkaz, že z axiomu výběru vyplývá princip dobrého uspořádání:

Aby bylo možné nějakou množinu $X$ dobře uspořádat, je třeba na ní vzájemně jednoznačně zobrazit nějaké ordinální číslo. Dobré uspořádání tohoto ordinálního čísla se pomocí této funkce přenese i na původní množinu. Označme toto číslo $\alpha$ a hledané zobrazení $f$.
Podle axiomu výběru lze z každé podmnožiny $Y\subseteq X$ vybrat jeden její prvek $y\in Y$ - označme $g$ toto výběrové zobrazení, které je vlastně selektor na potenční množině $\mathbb{P}(X)$.
Třídové zobrazení $F$ zkonstruuji rekurzí pomocí selektoru $g$ ($Rng$ je zde použito pro obor hodnot):

• $F(\mathrm{\varnothing })=g(X)$
• je-li $X-Rng(F|\beta )\ne \mathrm{\varnothing }$, pak $F(\beta )=g(X-Rng(F|\beta ))$
• je-li $X-Rng(F|\beta )=\mathrm{\varnothing }$, pak $F(\beta )=\mathrm{\varnothing }$

Je-li $\alpha$ nejmenší ordinální číslo, pro které platí $F(\alpha )=\mathrm{\varnothing }$, pak $f=F|\alpha$ je hledané prosté zobrazení $\alpha$ na $X$. (Existenci takto definovaného F pak zaručuje právě věta o transfinitní rekurzi).

Související články

• Rekurze
• Transfinitní indukce
• Ordinální číslo
• Axiom výběru