Dependence relation

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:

• if $a \in S$, then $a \triangleleft S$;
• if $a \triangleleft S$, then there is a finite subset S₀ of S, such that $a \triangleleft S_0$;
• if T is a subset of X such that $b \in S$ implies $b \triangleleft T$, then $a \triangleleft S$ implies $a \triangleleft T$;
• if $a \triangleleft S$ but $a \not\!\triangleleft 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 \not\!\triangleleft 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.

Remark. 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.

Examples

• Let V be a vector space over a field F. The relation $\triangleleft$, defined by $\upsilon \triangleleft S$ if υ 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 α is algebraic over F(S). Then $\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.