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 $\mathbb {O} 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ě $\mathbb {O} n\,\!$ všech ordinálních čísel takové, že
$(\forall \alpha \in \mathbb {O} 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 \Leftrightarrow \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ě $\mathbb {O} 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(\emptyset )=g(X)\,\!$
je-li $X-Rng(F|\beta )\neq \emptyset \,\!$ , pak $F(\beta )=g(X-Rng(F|\beta ))\,\!$
je-li $X-Rng(F|\beta )=\emptyset \,\!$ , pak $F(\beta )=\emptyset \,\!$

Je-li $\alpha \,\!$ nejmenší ordinální číslo, pro které platí $F(\alpha )=\emptyset \,\!$ , 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).