{{Short description|Relation showing how elements rely on each other}} {{distinguish|text=Dependency relation, which is a binary relation that is symmetric and reflexive}} {{unsourced|date=March 2023}} In mathematics, a '''dependence relation''' is a binary relation which generalizes the relation of linear dependence.
Let <math>X</math> be a set. A (binary) relation <math>\triangleleft</math> between an element <math>a</math> of <math>X</math> and a subset <math>S</math> of <math>X</math> is called a ''dependence relation'', written <math>a \triangleleft S</math>, if it satisfies the following properties: # if <math>a \in S</math>, then <math>a \triangleleft S</math>; # if <math>a \triangleleft S</math>, then there is a finite subset <math>S_0</math> of <math>S</math>, such that <math>a \triangleleft S_0</math>; # if <math>T</math> is a subset of <math>X</math> such that <math>b \in S</math> implies <math>b \triangleleft T</math>, then <math>a \triangleleft S</math> implies <math>a \triangleleft T</math>; # if <math>a \triangleleft S</math> but <math>a \ntriangleleft S-\lbrace b \rbrace</math> for some <math>b \in S</math>, then <math>b \triangleleft (S-\lbrace b \rbrace)\cup\lbrace a \rbrace</math>.
Given a ''dependence relation'' <math>\triangleleft</math> on <math>X</math>, a subset <math>S</math> of <math>X</math> is said to be ''independent'' if <math>a \ntriangleleft S - \lbrace a \rbrace</math> for all <math>a \in S.</math> If <math>S \subseteq T</math>, then <math>S</math> is said to ''span'' <math>T</math> if <math>t \triangleleft S</math> for every <math>t \in T.</math> <math>S</math> is said to be a ''basis'' of <math>X</math> if <math>S</math> is ''independent'' and <math>S</math> ''spans'' <math>X.</math>
If <math>X</math> is a non-empty set with a dependence relation <math>\triangleleft</math>, then <math>X</math> always has a basis with respect to <math>\triangleleft.</math> Furthermore, any two bases of <math>X</math> have the same cardinality.
If <math>a \triangleleft S</math> and <math>S \subseteq T</math>, then <math>a \triangleleft T</math>, using property 3. and 1.
==Examples== * Let <math>V</math> be a vector space over a field <math>F.</math> The relation <math>\triangleleft</math>, defined by <math>\upsilon \triangleleft S</math> if <math>\upsilon</math> is in the subspace spanned by <math>S</math>, is a dependence relation. This is equivalent to the definition of linear dependence. * Let <math>K</math> be a field extension of <math>F.</math> Define <math>\triangleleft</math> by <math>\alpha \triangleleft S</math> if <math>\alpha</math> is algebraic over <math>F(S).</math> Then <math>\triangleleft</math> is a dependence relation. This is equivalent to the definition of algebraic dependence.
==See also== * matroid
==References== {{reflist}}
{{PlanetMath attribution|id=5792|title=Dependence relation}}
Category:Linear algebra Category:Binary relations