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

editovat

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

editovat

Základní varianta

editovat

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

editovat

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

editovat

Rekurzivně definované třídové zobrazení

editovat

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

editovat

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

editovat