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:

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