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 $◃$ between an element $a$ of $X$ and a subset $S$ of $X$ is called a dependence relation, written $a◃S$, if it satisfies the following properties:

1. if $a\in S$, then $a◃S$;
2. if $a◃S$, then there is a finite subset $S_0$ of $S$, such that $a◃S_0$;
3. if $T$ is a subset of $X$ such that $b\in S$ implies $b◃T$, then $a◃S$ implies $a◃T$;
4. if $a◃S$ but $a⋪S-\{b\}$ for some $b\in S$, then $b◃(S-\{b\})\cup \{a\}$.

Given a dependence relation $◃$ on $X$, a subset $S$ of $X$ is said to be independent if $a⋪S-\{a\}$ for all $a\in S.$ If $S\subseteq T$, then $S$ is said to span $T$ if $t◃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 $◃$, then $X$ always has a basis with respect to $◃.$ Furthermore, any two bases of $X$ have the same cardinality.

If $a◃S$ and $S\subseteq T$, then $a◃T$, using property 3. and 1.

Examples

• Let $V$ be a vector space over a field $F.$ The relation $◃$, defined by $\upsilon ◃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 $◃$ by $\alpha ◃S$ if $\alpha$ is algebraic over $F(S).$ Then $◃$ is a dependence relation. This is equivalent to the definition of algebraic dependence.

See also

• matroid

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