Dependence relation

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

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

• if [math]\displaystyle{ a \in S }[/math], then [math]\displaystyle{ a \triangleleft S }[/math];
• if [math]\displaystyle{ a \triangleleft S }[/math], then there is a finite subset [math]\displaystyle{ S_0 }[/math] of [math]\displaystyle{ S }[/math], such that [math]\displaystyle{ a \triangleleft S_0 }[/math];
• if [math]\displaystyle{ T }[/math] is a subset of [math]\displaystyle{ X }[/math] such that [math]\displaystyle{ b \in S }[/math] implies [math]\displaystyle{ b \triangleleft T }[/math], then [math]\displaystyle{ a \triangleleft S }[/math] implies [math]\displaystyle{ a \triangleleft T }[/math];
• if [math]\displaystyle{ a \triangleleft S }[/math] but [math]\displaystyle{ a \ntriangleleft S-\lbrace b \rbrace }[/math] for some [math]\displaystyle{ b \in S }[/math], then [math]\displaystyle{ b \triangleleft (S-\lbrace b \rbrace)\cup\lbrace a \rbrace }[/math].

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

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

Examples

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

See also

• matroid