マトロイド
有限集合 E と B ⊆ 2 E {\displaystyle {\mathcal {B}}\subseteq 2^{E}} とする。 B {\displaystyle {\mathcal {B}}} がマトロイド (E, F) の基族であるための必要十分条件は次の(B1),(B2)が成り立つことである。
(B1) B ≠ ∅ {\displaystyle {\mathcal {B}}\neq \emptyset }
(B2) 任意の B ′ , B ′′ ∈ B , x ∈ B ′ ∖ B ′′ {\displaystyle B',B''\in {\mathcal {B}},x\in B'\setminus B''} について ( B ′ ∖ { x } ) ∪ { y } ∈ B {\displaystyle (B'\setminus \{x\})\cup \{y\}\in {\mathcal {B}}} となる y ∈ B ′′ ∖ B ′ {\displaystyle y\in {B''}\setminus {B'}} が存在する。
基が1つしかない場合は明らかにマトロイドとなる。
集合Eとその部分集合の族Fが(A1)から(A3)を満たすときマトロイドと呼ぶことにし、そこから基やランクを定義した。だが、実はこれらの性質を持つ族あるいは関数からマトロイドとなる F を得ることができる。