Dependence relation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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:

  • if a \in S, then a \triangleleft S;
  • if a \triangleleft S, then there is a finite subset S_0 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.


See also[edit]

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