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 ${\displaystyle f(1)=1\,\!}$ a ${\displaystyle f(n+1)=(n+1).f(n)\,\!}$
• Fibonacciho čísla, kde ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle G\,\!}$ je třídové zobrazení, které každé množině ${\displaystyle x\,\!}$ přiřazuje množinu ${\displaystyle G(x)\,\!}$. Pak existuje právě jedno třídové zobrazení ${\displaystyle F\,\!}$ na třídě ${\displaystyle \mathbb {O} n\,\!}$ všech ordinálních čísel takové, že
${\displaystyle (\forall \alpha \in \mathbb {O} n)(F(\alpha )=G(F|\alpha ))\,\!}$

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

Pro pochopení této věty je důležité si uvědomit, že pro ordinální čísla platí ${\displaystyle \alpha <\beta \Leftrightarrow \alpha \in \beta \,\!}$ a zápis
${\displaystyle F(\alpha )=G(F|\alpha )\,\!}$
neříká tedy nic jiného než:
hodnota ${\displaystyle F\,\!}$ pro ${\displaystyle \alpha \,\!}$ závisí (pomocí předpisu ${\displaystyle G\,\!}$) na hodnotách ${\displaystyle F\,\!}$ pro menší ordinální čísla než ${\displaystyle \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 ${\displaystyle x\,\!}$ a dvě třídová zobrazení ${\displaystyle G,H\,\!}$ definovaná pro každou množinu, pak existuje právě jedno třídové zobrazení ${\displaystyle F\,\!}$ na třídě ${\displaystyle \mathbb {O} n\,\!}$ všech ordinálních čísel takové, že

• ${\displaystyle F(0)=x\,\!}$
• ${\displaystyle F(\alpha +1)=G(F(\alpha ))\,\!}$
• ${\displaystyle F(\alpha )=H(F|\alpha )\,\!}$ pro limitní ordinál ${\displaystyle \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 ${\displaystyle \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:

• ${\displaystyle F(0)=1\,\!}$
• ${\displaystyle F(\alpha +1)=F(\alpha ).(\alpha +1)\,\!}$
• ${\displaystyle F(\alpha )=sup\{F(\beta ):\beta <\alpha \}\,\!}$ pro limitní ${\displaystyle \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 ${\displaystyle F(\omega )=sup\{F(\beta ):\beta <\omega \}=\omega \,\!}$
• ${\displaystyle F(\omega +1)=F(\omega ).(\omega +1)=\omega ^{2}+\omega \,\!}$
• ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle \alpha \,\!}$ a hledané zobrazení ${\displaystyle f\,\!}$.
Podle axiomu výběru lze z každé podmnožiny ${\displaystyle Y\subseteq X\,\!}$ vybrat jeden její prvek ${\displaystyle y\in Y\,\!}$ - označme ${\displaystyle g\,\!}$ toto výběrové zobrazení, které je vlastně selektor na potenční množině ${\displaystyle \mathbb {P} (X)\,\!}$.
Třídové zobrazení ${\displaystyle F\,\!}$ zkonstruuji rekurzí pomocí selektoru ${\displaystyle g\,\!}$ (${\displaystyle Rng\,\!}$ je zde použito pro obor hodnot):

• ${\displaystyle F(\emptyset )=g(X)\,\!}$
• je-li ${\displaystyle X-Rng(F|\beta )\neq \emptyset \,\!}$, pak ${\displaystyle F(\beta )=g(X-Rng(F|\beta ))\,\!}$
• je-li ${\displaystyle X-Rng(F|\beta )=\emptyset \,\!}$, pak ${\displaystyle F(\beta )=\emptyset \,\!}$

Je-li ${\displaystyle \alpha \,\!}$ nejmenší ordinální číslo, pro které platí ${\displaystyle F(\alpha )=\emptyset \,\!}$, pak ${\displaystyle f=F|\alpha \,\!}$ je hledané prosté zobrazení ${\displaystyle \alpha \,\!}$ na ${\displaystyle 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