Dependence relation explained

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 ;

1. if

a \triangleleft S , then there is a finite subset S _{0} of S , such that a \triangleleft S _{0} ;

1. if

T is a subset of X such that b \in S implies b \triangleleft T , then a \triangleleft S implies a \triangleleft T ;

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