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 a
- Fibonacciho čísla, kde
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 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 je třídové zobrazení, které každé množině přiřazuje množinu . Pak existuje právě jedno třídové zobrazení na třídě všech ordinálních čísel takové, že
v předchozí větě znamená zúžení zobrazení na množinu
Pro pochopení této věty je důležité si uvědomit, že pro ordinální čísla platí a zápis
neříká tedy nic jiného než:
hodnota pro závisí (pomocí předpisu ) na hodnotách pro menší ordinální čísla než .
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 a dvě třídová zobrazení definovaná pro každou množinu, pak existuje právě jedno třídové zobrazení na třídě všech ordinálních čísel takové, že
- pro limitní ordinál
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 ) 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:
- pro limitní
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
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 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 a hledané zobrazení .
Podle axiomu výběru lze z každé podmnožiny vybrat jeden její prvek - označme toto výběrové zobrazení, které je vlastně selektor na potenční množině .
Třídové zobrazení zkonstruuji rekurzí pomocí selektoru ( je zde použito pro obor hodnot):
- je-li , pak
- je-li , pak
Je-li nejmenší ordinální číslo, pro které platí , pak je hledané prosté zobrazení na . (Existenci takto definovaného F pak zaručuje právě věta o transfinitní rekurzi).
Související články