In mathematics, a dependence relation is a binary relation which generalizes the relation of linear dependence.

Let X {\displaystyle X} be a set. A (binary) relation ◃ {\displaystyle \triangleleft } between an element a {\displaystyle a} of X {\displaystyle X} and a subset 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:

1. if a ∈ S {\displaystyle a\in S} , then a ◃ S {\displaystyle a\triangleleft S} ;
2. if a ◃ S {\displaystyle a\triangleleft S} , then there is a finite subset S 0 {\displaystyle S_{0}} of S {\displaystyle S} , such that a ◃ S 0 {\displaystyle a\triangleleft S_{0}} ;
3. 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} ;
4. 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 } .

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 cardinality.

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.