マトロイド
独立性システム ( E , F ) {\displaystyle (E,F)} の閉包 (closure) 関数 σ : 2 E → 2 E {\displaystyle \sigma \colon 2^{E}\to 2^{E}} は、 X ⊆ E {\displaystyle X\subseteq E} に対して
σ ( X ) := { y ∈ E : r ( X ∪ y ) = r ( X ) } {\displaystyle \sigma (X):=\{y\in E:r(X\cup {y})=r(X)\}}
で定義される。 σ ( X ) {\displaystyle \sigma (X)} を X の閉包と呼ぶ。
マトロイド ( E , F ) {\displaystyle (E,F)} の閉包関数 σ : 2 E → 2 E {\displaystyle \sigma \colon 2^{E}\to 2^{E}} は次の性質を持つ。
(L1) 任意の X ⊆ E {\displaystyle X\subseteq E} に対して、 X ⊆ σ ( X ) {\displaystyle X\subseteq \sigma (X)}
独立性システム (E, F) の階数 (rank) 関数 r : 2 E → R {\displaystyle r:2^{E}\to \mathbb {R} } は、 X ⊆ E {\displaystyle X\subseteq E} に対して
r ( X ) := max { | Y | : Y ⊆ X , Y ∈ F } {\displaystyle r(X):=\max\{|Y|:Y\subseteq X,Y\in F\}}
と定義される。マトロイドならば、公理(A3) から E の部分集合 X に対して X のどの基も元数は等しいため、階数関数を X {\displaystyle X} の基の大きさと定義しても構わない。
例えば、E = {1, 2, 3}, F={{},{1},{2},{1,2}} というマトロイドならば r({1}) = 1, r({1, 2}) = 2, r({1, 2, 3}) = 2, r({1, 3}) = 1 等となる。
独立性システム ( E , F ) {\displaystyle (E,F)} の階数関数 r : 2 E → R {\displaystyle r:2^{E}\to \mathbb {R} } は任意の X , Y ⊆ E {\displaystyle X,Y\subseteq E} と x , y ∈ E {\displaystyle x,y\in E} について次の性質を持つ。
そうでない場合、例えば E = { 1 , 2 , 3 } , B = { { 1 , 2 } , { 2 , 3 } , { 1 , 3 } } {\displaystyle E=\{1,2,3\},{\mathcal {B}}=\{\{1,2\},\{2,3\},\{1,3\}\}} とすると B {\displaystyle {\mathcal {B}}} は(B1)および(B2)を満たす。このような基の族を持つマトロイドは、一様マトロイド U 3 2 {\displaystyle U_{3}^{2}} ただ1つに決まることが分かる。また、基族が B = { { 1 , 2 } , { 3 } } {\displaystyle {\mathcal {B}}=\{\{1,2\},\{3\}\}} のときは(B2)を満たさないため、この基族ではマトロイドにならない。事実、 F = { { 1 } , { 2 } , { 3 } , { 1 , 2 } } {\displaystyle F=\{\{1\},\{2\},\{3\},\{1,2\}\}} とすると、この例の基族となるが、(A3)を満たさずマトロイドになっていない。