Relace závislosti

Relace závislosti je v matematice binární relace, která zobecňuje relaci lineární závislosti.

Definice

Nechť $X$ je množina. Binární relace $◃$ mezi prvkem $a$ z $X$ a podmnožinou $S$ z $X$ se nazývá relace závislosti, kterou značíme $a◃S$, pokud splňuje následující podmínky:

1. Je-li $a\in S$, pak $a◃S$;
2. Je-li $a◃S$, pak existuje konečná podmnožina $S_0$ z $S$, taková, že $a◃S_0$;
3. Je-li $T$ podmnožinou $X$ takovou, že $b\in S$ implikuje $b◃T$, pak $a◃S$ implikuje $a◃T$;
4. Je-li $a◃S$, ale $a⋪S-\{b\}$ pro nějaké $b\in S$, pak $b◃(S-\{b\})\cup \{a\}$.

Je-li dána relace závislosti $◃$ na $X$, řekneme, že podmnožina $S$ z $X$ je nezávislá, jestliže $a⋪S-\{a\}$ pro všechny $a\in S.$ Pokud $S\subseteq T$, pak o $S$ říkáme, že pokrývá $T,$ jestliže $t◃S$ pro každé $t\in T$. Říkáme, že $S$ je bází $X,$ jestliže $S$ je nezávislá a $S$ pokrývá $X.$

Je-li $X$ neprázdná množina s relací závislosti $◃$, pak $X$ má vždy bázi vzhledem k $◃.$ Navíc libovolné dvě báze $X$ mají stejnou mohutnost.

Pokud $a◃S$ a $S\subseteq T$, pak $a◃T$, s využítím vlastností 3. a 1.

Příklady

• Nechť $V$ je vektorový prostor nad komutativním tělesem $F.$ Relace $◃$, definovaná $\upsilon ◃S$ pokud je $\upsilon$ v podprostoru, který pokrývá $S$, je relací závislosti. To je ekvivalentní definici lineární závislosti.
• Nechť $K$ je nadtělesem $F.$ Definujeme $◃$ podle $\alpha ◃S$ pokud $\alpha$ je algebraické nad $F(S).$ Pak $◃$ je závislostní relace. To je ekvivalentní s definicí algebraické závislosti.

Odkazy

Reference

• Tento článek obsahuje materiál z článku Dependence relation na PlanetMath, který je publikován pod licencí Creative Commons Attribution/Share-Alike.

Související články

• Matroid