# Dependence relation

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Dependence_relation
> Markdown URL: https://mediated.wiki/source/Dependence_relation.md
> Source: https://en.wikipedia.org/wiki/Dependence_relation
> Source revision: 1347197720
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Relation showing how elements rely on each other}}
{{distinguish|text=[Dependency relation](/source/Dependency_relation), which is a binary relation that is symmetric and reflexive}}
{{unsourced|date=March 2023}}
In [mathematics](/source/mathematics), a '''dependence relation''' is a [binary relation](/source/binary_relation) which generalizes the relation of [linear dependence](/source/linear_dependence).

Let <math>X</math> be a [set](/source/set_(mathematics)). A (binary) relation <math>\triangleleft</math> between an element <math>a</math> of <math>X</math> and a [subset](/source/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](/source/finite_set) 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](/source/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](/source/vector_space) over a [field](/source/field_(mathematics)) <math>F.</math> The relation <math>\triangleleft</math>, defined by  <math>\upsilon \triangleleft S</math> if <math>\upsilon</math> is in the [subspace](/source/linear_subspace) spanned by <math>S</math>, is a dependence relation. This is [equivalent](/source/logical_equivalence) to the definition of [linear dependence](/source/linear_independence).
* Let <math>K</math> be a [field extension](/source/field_extension) of <math>F.</math> Define <math>\triangleleft</math> by  <math>\alpha \triangleleft S</math> if <math>\alpha</math> is [algebraic](/source/algebraic_element) over <math>F(S).</math> Then <math>\triangleleft</math> is a dependence relation. This is equivalent to the definition of [algebraic dependence](/source/algebraic_dependence).

==See also==
* [matroid](/source/matroid)

==References==
{{reflist}}

{{PlanetMath attribution|id=5792|title=Dependence relation}}

Category:Linear algebra
Category:Binary relations

---
Adapted from the Wikipedia article [Dependence relation](https://en.wikipedia.org/wiki/Dependence_relation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Dependence_relation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.