Dependence relation

Not to be confused with Dependency relation, which is a binary relation that is symmetric and reflexive.

In mathematics, a dependence relation is a binary relation which generalizes the relation of linear dependence.

Let ${\displaystyle X}$ be a set. A (binary) relation ${\displaystyle \triangleleft }$ between an element ${\displaystyle a}$ of ${\displaystyle X}$ and a subset ${\displaystyle S}$ of ${\displaystyle X}$ is called a dependence relation, written ${\displaystyle a\triangleleft S}$, if it satisfies the following properties:

1. if ${\displaystyle a\in S}$, then ${\displaystyle a\triangleleft S}$;
2. if ${\displaystyle a\triangleleft S}$, then there is a finite subset ${\displaystyle S_{0}}$ of ${\displaystyle S}$, such that ${\displaystyle a\triangleleft S_{0}}$;
3. if ${\displaystyle T}$ is a subset of ${\displaystyle X}$ such that ${\displaystyle b\in S}$ implies ${\displaystyle b\triangleleft T}$, then ${\displaystyle a\triangleleft S}$ implies ${\displaystyle a\triangleleft T}$;
4. if ${\displaystyle a\triangleleft S}$ but ${\displaystyle a\ntriangleleft S-\lbrace b\rbrace }$ for some ${\displaystyle b\in S}$, then ${\displaystyle b\triangleleft (S-\lbrace b\rbrace )\cup \lbrace a\rbrace }$.

Given a dependence relation${\displaystyle \triangleleft }$ on ${\displaystyle X}$, a subset ${\displaystyle S}$ of ${\displaystyle X}$ is said to be independent if ${\displaystyle a\ntriangleleft S-\lbrace a\rbrace }$ for all ${\displaystyle a\in S.}$ If ${\displaystyle S\subseteq T}$, then ${\displaystyle S}$ is said to span${\displaystyle T}$ if ${\displaystyle t\triangleleft S}$ for every ${\displaystyle t\in T.}$${\displaystyle S}$ is said to be a basis of ${\displaystyle X}$ if ${\displaystyle S}$ is independent and ${\displaystyle S}$spans${\displaystyle X.}$

If ${\displaystyle X}$ is a non-empty set with a dependence relation ${\displaystyle \triangleleft }$, then ${\displaystyle X}$ always has a basis with respect to ${\displaystyle \triangleleft .}$ Furthermore, any two bases of ${\displaystyle X}$ have the same cardinality.

If ${\displaystyle a\triangleleft S}$ and ${\displaystyle S\subseteq T}$, then ${\displaystyle a\triangleleft T}$, using property 3. and 1.

Examples

• Let ${\displaystyle V}$ be a vector space over a field ${\displaystyle F.}$ The relation ${\displaystyle \triangleleft }$, defined by ${\displaystyle \upsilon \triangleleft S}$ if ${\displaystyle \upsilon }$ is in the subspace spanned by ${\displaystyle S}$, is a dependence relation. This is equivalent to the definition of linear dependence.
• Let ${\displaystyle K}$ be a field extension of ${\displaystyle F.}$ Define ${\displaystyle \triangleleft }$ by ${\displaystyle \alpha \triangleleft S}$ if ${\displaystyle \alpha }$ is algebraic over ${\displaystyle F(S).}$ Then ${\displaystyle \triangleleft }$ is a dependence relation. This is equivalent to the definition of algebraic dependence.

See also

• matroid

This article incorporates material from Dependence relation on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.