Fundovaná relace

Z Wikipedie, otevřené encyklopedie

Fundovaná relace je matematický pojem z oboru teorie množin, který popisuje druh relace podobný dobrému uspořádání.

Obsah

[editovat] Definice

Relace R je fundovaná na třídě A, jestliže každá její neprázdná podmnožina \emptyset \neq B \subseteq A \,\!R-minimální prvek označovaný symbolem min_R(B) \,\! .
Prvek x = min_R(B) \,\! označíme za R-minimální prvek množiny B, pokud je platí
x \isin B \and ( \forall y \isin B) \neg ( [y,x] \isin R ) \,\!

[editovat] Vysvětlení a vlastnosti pojmu

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ě \{ 1,2,3 \} \,\! definujme relaci R = \{ [1,2], [2,3] \} \,\! . Snadno se dá ověřit, že taková relace je fundovaná, ale není tranzitivní - to by totiž musela obsahovat i uspořádanou dvojici [1,3] \,\! .

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 [3,1] \,\!, vznikla by relace R  = \{ [1,2], [2,3], [3,1] \} \,\!, která již není fundovaná - množina \{ 1,2,3 \} \,\! nemá v tomto případě žádný R-minimální prvek.

Fundovaná relace nesmí obsahovat žádnou nekonečnou klesající posloupnost (v tom se podobá dobrému uspořádání).
Pokud najdu posloupnost prvků a_0, a_1, a_2, \ldots \,\! takových že pro každé i je [a_{i+1},a_i] \isin R \,\!, pak množina \{ a_0, a_1, a_2, \ldots \} \,\! nemá žádný R-minimální prvek.

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í R  = \{ [1,2], [2,3], [3,1] \} \,\!, můžu sestojit nekonečnou klesající posloupnost \{ 3,2,1,3,2,1,3,2,1,3, \ldots \} \,\!.

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.

[editovat] Význam pojmu

Motivace k zavedení pojmu a jeho význam vyplývá z axiomu fundovanosti.

Tento axiom lze v ekvivalentní podobě zapsat jako \mathbb{WF} = \mathbb{V} \,\!, kde \mathbb{WF} \,\! je fundované jádro a \mathbb{V} \,\! univerzální třída, tj. třída všech množin.

Podstatou důkazu výše uvedené ekvivalence, je věta, podle které je \mathbb{WF} \,\! největší tranzitivní třída, na které je relace \isin \,\! fundovaná.

[editovat] Podívejte se také na

Související články obsahuje:
 Portál Matematika