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 $X$ be a set. A (binary) relation $\triangleleft$ between an element $a$ of $X$ and a subset $S$ of $X$ is called a dependence relation, written $a\triangleleft S$, if it satisfies the following properties:

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

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

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

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

Examples

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

See also

• matroid

References

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