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_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 \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

{{PlanetMath attribution, id=5792, title=Dependence relation

Linear algebra
Binary relations