Dependence relation

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a dependence relation is a <a href="/facts/Binary_relation/r9BwGgaK">binary relation</a> which generalizes the relation of <a href="/facts/Linear_dependence/8JrHfIIa">linear dependence</a>.
Let 
 
 
 
 X
 
 
 {\displaystyle X}
 
 be a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a>. A (binary) relation 
 
 
 
 ◃
 
 
 {\displaystyle \triangleleft }
 
 between an element 
 
 
 
 a
 
 
 {\displaystyle a}
 
 of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 and a <a href="/facts/Subset/SJGERmbA">subset</a> 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is called a dependence relation, written 
 
 
 
 a
 ◃
 S
 
 
 {\displaystyle a\triangleleft S}
 
, if it satisfies the following properties: 

<ol><li>if 
 
 
 
 a
 ∈
 S
 
 
 {\displaystyle a\in S}
 
, then 
 
 
 
 a
 ◃
 S
 
 
 {\displaystyle a\triangleleft S}
 
;</li>
<li>if 
 
 
 
 a
 ◃
 S
 
 
 {\displaystyle a\triangleleft S}
 
, then there is a <a href="/facts/Finite_set/za1newlP">finite</a> subset 
 
 
 
 
 S
 
 0
 
 
 
 
 {\displaystyle S_{0}}
 
 of 
 
 
 
 S
 
 
 {\displaystyle S}
 
, such that 
 
 
 
 a
 ◃
 
 S
 
 0
 
 
 
 
 {\displaystyle a\triangleleft S_{0}}
 
;</li>
<li>if 
 
 
 
 T
 
 
 {\displaystyle T}
 
 is a subset of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 such that 
 
 
 
 b
 ∈
 S
 
 
 {\displaystyle b\in S}
 
 implies 
 
 
 
 b
 ◃
 T
 
 
 {\displaystyle b\triangleleft T}
 
, then 
 
 
 
 a
 ◃
 S
 
 
 {\displaystyle a\triangleleft S}
 
 implies 
 
 
 
 a
 ◃
 T
 
 
 {\displaystyle a\triangleleft T}
 
;</li>
<li>if 
 
 
 
 a
 ◃
 S
 
 
 {\displaystyle a\triangleleft S}
 
 but 
 
 
 
 a
 ⋪
 S
 −
 {
 b
 }
 
 
 {\displaystyle a\ntriangleleft S-\lbrace b\rbrace }
 
 for some 
 
 
 
 b
 ∈
 S
 
 
 {\displaystyle b\in S}
 
, then 
 
 
 
 b
 ◃
 (
 S
 −
 {
 b
 }
 )
 ∪
 {
 a
 }
 
 
 {\displaystyle b\triangleleft (S-\lbrace b\rbrace )\cup \lbrace a\rbrace }
 
.</li></ol>
Given a dependence relation 
 
 
 
 ◃
 
 
 {\displaystyle \triangleleft }
 
 on 
 
 
 
 X
 
 
 {\displaystyle X}
 
, a subset 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is said to be independent if 
 
 
 
 a
 ⋪
 S
 −
 {
 a
 }
 
 
 {\displaystyle a\ntriangleleft S-\lbrace a\rbrace }
 
 for all 
 
 
 
 a
 ∈
 S
 .
 
 
 {\displaystyle a\in S.}
 
 If 
 
 
 
 S
 ⊆
 T
 
 
 {\displaystyle S\subseteq T}
 
, then 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is said to span 
 
 
 
 T
 
 
 {\displaystyle T}
 
 if 
 
 
 
 t
 ◃
 S
 
 
 {\displaystyle t\triangleleft S}
 
 for every 
 
 
 
 t
 ∈
 T
 .
 
 
 {\displaystyle t\in T.}
 
 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is said to be a basis of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 if 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is independent and 
 
 
 
 S
 
 
 {\displaystyle S}
 
 spans 
 
 
 
 X
 .
 
 
 {\displaystyle X.}
 
 
If 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is a non-empty set with a dependence relation 
 
 
 
 ◃
 
 
 {\displaystyle \triangleleft }
 
, then 
 
 
 
 X
 
 
 {\displaystyle X}
 
 always has a basis with respect to 
 
 
 
 ◃
 .
 
 
 {\displaystyle \triangleleft .}
 
 Furthermore, any two bases of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 have the same <a href="/facts/Cardinality/m6VPojwT">cardinality</a>.
If 
 
 
 
 a
 ◃
 S
 
 
 {\displaystyle a\triangleleft S}
 
 and 
 
 
 
 S
 ⊆
 T
 
 
 {\displaystyle S\subseteq T}
 
, then 
 
 
 
 a
 ◃
 T
 
 
 {\displaystyle a\triangleleft T}
 
, using property 3. and 1.

Dependence relation open-in-new

Dependence relation