Fundovaná relace
Fundovaná relace je matematický pojem z oboru teorie množin, který popisuje druh relace podobný dobrému uspořádání.
Definice
[editovat | editovat zdroj]Relace R je fundovaná na třídě A, jestliže každá její neprázdná podmnožina má R-minimální prvek označovaný symbolem .
Prvek označíme za R-minimální prvek množiny B, pokud platí
![{\displaystyle x\in B\land (\forall y\in B)\neg ([y,x]\in R)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd4d20fd02acc7f2d7b1281721e83187555fa4d3)
Vysvětlení a vlastnosti pojmu
[editovat | editovat zdroj]R-minimální prvek je takový prvek nějaké podmnožiny B, pro který neexistuje žádný menší (ve smyslu relace R) v této podmnožině. Důvod, proč nemluvíme rovnou o minimálním prvku je ten, že nikde není řečeno, že fundovaná relace R je uspořádání – což ostatně opravdu nemusí být pravda.
Fundovaná relace totiž opravdu nemusí být uspořádání, i když na první pohled trochu připomíná ostré uspořádání. Problém je v tom, že fundovaná relace nemusí být (na rozdíl od uspořádání) tranzitivní.
Příklad: Na tříprvkové množině definujme relaci . Snadno se dá ověřit, že taková relace je fundovaná, ale není tranzitivní – to by totiž musela obsahovat i uspořádanou dvojici .
![{\displaystyle R=\{[1,2],[2,3]\}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1b79a24d9168c715936536fb056f3f3821da4df)
![{\displaystyle [1,3]\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d867ae9bcd7784ffe053bbda1ff8f5545d328549)
Fundovaná relace nesmí obsahovat žádný konečný cyklus (v tom se podobá ostrému uspořádání).
Kdybychom v předchozím příkladě přidali dvojici , vznikla by relace , která již není fundovaná – množina nemá v tomto případě žádný R-minimální prvek.
![{\displaystyle [3,1]\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdfd7ed945764aad4fd896f05d3d3934142caed4)
![{\displaystyle R=\{[1,2],[2,3],[3,1]\}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d526f366c366f57d6bae691388510f2d172bc651)
Fundovaná relace nesmí obsahovat žádnou nekonečnou klesající posloupnost (v tom se podobá dobrému uspořádání).
Pokud najdu posloupnost prvků takových že pro každé i je , pak množina nemá žádný R-minimální prvek.
![{\displaystyle [a_{i+1},a_{i}]\in R\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e8ce2f5e72d63697f6494b0495800cbeaf33c00)
Konečný cyklus je zvláštní případ, vedoucí na nekonečnou klesající posloupnost - pokud se vrátím k předchozímu příkladu s relací , můžu sestrojit nekonečnou klesající posloupnost .
![{\displaystyle R=\{[1,2],[2,3],[3,1]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ef53417d1663e184b11f81dabba2ec82823cecf)
Z axiomu výběru se dá ukázat, že relace R je fundovaná tehdy a jen tehdy, když neobsahuje nekonečnou klesající posloupnost.
Význam pojmu
[editovat | editovat zdroj]Axiom fundovanosti
[editovat | editovat zdroj]Motivace k zavedení pojmu a jeho význam vyplývá z axiomu fundovanosti.
Tento axiom lze v ekvivalentní podobě zapsat jako , kde je fundované jádro a univerzální třída, tj. třída všech množin.
Podstatou důkazu výše uvedené ekvivalence, je věta, podle které je největší tranzitivní třída, na které je relace fundovaná.
Transfinitní indukce a rekurze
[editovat | editovat zdroj]Na každé třídě s fundovanou relací takovou, že levým obrazem každého prvku je množina (a ne vlastní třída), se dá provádět fundovaná indukce a fundovaná rekurze, jejichž speciálním případem je transfinitní indukce a transfinitní rekurze přes fundovanou operaci náležení na ordinálních číslech; ještě speciálnějšími případy jsou matematická indukce a rekurze přes přirozená čísla.