Transfinitní rekurze

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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 | editovat zdroj]

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 | editovat zdroj]

Základní varianta[editovat | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]

Rekurzivně definované třídové zobrazení[editovat | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]