Transfinitní rekurze

Technology

12 hours ago

Author

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). +moref(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 \,\. +more 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 \isin \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 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 \,\. +more 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 \,\. +more ) 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ů.

Important

Ordinální číslo

transfinitní indukce

Kategorie:Ordinální čísla

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 pro limitní \alpha \,\!

Jaké vlastnosti má takto definovaná funkce. * Pro konečné ordinály (tj. +more 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 * 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. +more 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 \isin Y \,\. +more - 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 \,\. +more ( 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).