# dependence relation

Let $X$ be a set. A (binary) relation  $\prec$ between an element $a$ of $X$ and a subset $S$ of $X$ is called a dependence relation, written $a\prec S$, when the following conditions are satisfied:

1. 1.

if $a\in S$, then $a\prec S$;

2. 2.

if $a\prec S$, then there is a finite subset $S_{0}$ of $S$, such that $a\prec S_{0}$;

3. 3.

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

4. 4.

if $a\prec S$ but $a\not\prec S-\{b\}$ for some $b\in S$, then $b\prec(S-\{b\})\cup\{a\}$.

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

Examples:

Title dependence relation DependenceRelation 2013-03-22 14:19:25 2013-03-22 14:19:25 CWoo (3771) CWoo (3771) 9 CWoo (3771) Definition msc 03E20 msc 05B35 LinearIndependence AlgebraicallyDependent Matroid  AxiomatizationOfDependence