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
má R-minimální prvek označovaný symbolem
.
Prvek
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 ) \,\!](../../../math/7/e/f/7ef187c658b05d12879cb847fe49ef8e.png)
[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ě
definujme relaci
. Snadno se dá ověřit, že taková relace je fundovaná, ale není tranzitivní - to by totiž musela obsahovat i uspořádanou dvojici
.
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.
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.
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 sestojit nekonečnou klesající posloupnost
.
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
, 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á.
[editovat] Podívejte se také na
| Související články obsahuje: |

