マトロイド

（I1）空の族は線形独立である。（I2）線形独立な族の部分族は線形独立である。（I3）$I,J$ が独立で $|I|< |J|$ とし、$W$ を $\{v(e)\}_{e\in I}$ が張る部分空間とする。$\dim W=|I|$ である。もし $J$ のすべての元 $e$ について $v(e)\in W$ なら、$\{v(e)\}_{e\in J}$ は $W$ の中の $|J|$ 個の線形独立なベクトルになり、$|J|\le\dim W=|I|$ に反する。よって $v(e)\notin W$ となる $e\in J$ がある。$v(e)\notin W$ から $e\notin I$ であり、$v(e)$ は $v(I)$ の元のどれとも異なる。線形独立な族に、その張る空間の外のベクトルを加えた族は線形独立なので、$I+e$ は独立である。$\square$

段 1（成分の個数）．辺を 1 本ずつ加えていく。辺 $e$ を $(V,F)$ に加えるとき、$e$ の両端が異なる成分にあれば、2 つの成分がつながって成分は 1 つ減り、新しい閉路はできない（新しい閉路は $e$ を通り、$e$ を除くと両端を結ぶ $F$ の道が残るはずだが、両端は $F$ で結ばれていない）。$e$ の両端が同じ成分にあれば（ループの場合を含む）、両端を結ぶ $F$ の道と $e$ で閉路ができる。したがって、森 $F$ の辺を順に加えると、各段で成分はちょうど 1 つずつ減る。辺のないとき成分は $|V|$ 個なので、$c(F)=|V|-|F|$ である。
段 2（公理）．（I1）（I2）は、辺のないグラフは閉路を含まず、閉路を含まないグラフの部分グラフも閉路を含まないことによる。（I3）$F_1,F_2$ を森とし $|F_1|< |F_2|$ とする。段 1 により $c(F_2)< c(F_1)$ である。もし $F_2$ のどの辺も両端が $(V,F_1)$ の同じ成分にあるなら、$(V,F_2)$ の各成分は $(V,F_1)$ のある成分に含まれ、$c(F_2)\ge c(F_1)$ となって矛盾する。よって両端が $(V,F_1)$ の異なる成分にある辺 $e\in F_2$ がある。$e\notin F_1$ であり、段 1 により $F_1+e$ は森である。$\square$

$I,J\subset A$ を $A$ の中で極大な独立集合とし、$|I|< |J|$ と仮定する。（I3）により $e\in J\setminus I$ で $I+e$ が独立なものがある。$e\in A$ なので $I+e\subset A$ であり、$I$ の極大性に反する。よって $|I|=|J|$ である。$A=E$ の場合が基についての主張である。$\square$

（R1）（R2）は定義から明らかである（$A$ の中の極大な独立集合は、$B$ の中の極大な独立集合に広げられる）。
（R3）$A\cap B$ の中の極大な独立集合 $J$ をとり、これを $A\cup B$ の中の極大な独立集合 $K\supset J$ に広げる。lem-mat-maximal により $|K|=r(A\cup B)$、$|J|=r(A\cap B)$ である。$K\cap A\cap B$ は $J$ を含む独立集合で $A\cap B$ に含まれるので、$J$ の極大性から $K\cap A\cap B=J$ である。$K\cap A$、$K\cap B$ はそれぞれ $A$、$B$ に含まれる独立集合なので $|K\cap A|\le r(A)$、$|K\cap B|\le r(B)$ である。よって
$$ r(A)+r(B)\ge|K\cap A|+|K\cap B|=|K\cap(A\cup B)|+|K\cap A\cap B|=|K|+|J|=r(A\cup B)+r(A\cap B) $$
である。$\square$

（C1）は $\emptyset$ が独立であること、（C2）は閉路が極小な従属集合であることによる。
（C3）閉路 $C$ の真部分集合は独立なので $r(C)=|C|-1$ である。$C_1\neq C_2$ と（C2）から $C_1\cap C_2$ は $C_1$ の真部分集合であり、独立なので $r(C_1\cap C_2)=|C_1\cap C_2|$ である。prop-mat-rank-axioms の（R3）により
$$ r(C_1\cup C_2)\le r(C_1)+r(C_2)-r(C_1\cap C_2)=|C_1|+|C_2|-|C_1\cap C_2|-2=|C_1\cup C_2|-2 $$
である。（R2）により $r((C_1\cup C_2)-e)\le|C_1\cup C_2|-2< |(C_1\cup C_2)-e|$ なので、$(C_1\cup C_2)-e$ は従属であり、極小な従属部分集合として閉路を含む。
最後の主張：独立集合の部分集合は独立なので閉路を含まない。従属集合 $A$ は、元の個数が最小の従属部分集合を含み、それは閉路である。$\square$

$I+e$ は従属なので閉路を含み（prop-mat-circuit-axioms）、$I$ は閉路を含まないので、その閉路は $e$ を含む。異なる 2 つの閉路 $C_1,C_2\subset I+e$ があれば、どちらも $e$ を含むので、（C3）により閉路 $C_3\subset(C_1\cup C_2)-e\subset I$ があり、$I$ が独立であることに反する。$\square$

lem-mat-maximal により $|B_1|=|B_2|$ で、元の個数が $|B_1|$ の独立集合は基である。
1：$|B_1-x|< |B_2|$ なので、（I3）により $y\in B_2\setminus(B_1-x)$ で $(B_1-x)+y$ が独立なものがある。$x\notin B_2$ なので $y\neq x$、したがって $y\in B_2\setminus B_1$ であり、$(B_1-x)+y$ は $|B_1|$ 元の独立集合なので基である。
2：$B_1$ は基なので $B_1+x$ は従属であり、lem-mat-fundamental-circuit によりただ 1 つの閉路 $C\ni x$ を含む。$C\subset B_2$ なら $B_2$ が従属になるので、$y\in C\setminus B_2$ がある。$x\in B_2$ なので $y\neq x$、したがって $y\in B_1\setminus B_2$ である。$(B_1+x)-y$ は閉路 $C$ を含まず、$B_1+x$ のほかの閉路もないので、閉路を含まず独立であり、$|B_1|$ 元なので基である。$\square$

段 1（$\mathcal B$ の元の大きさはそろう）．$|B_1|>|B_2|$ となる $B_1,B_2\in\mathcal B$ があったとし、そのような組のうち $|B_1\setminus B_2|$ が最小のものをとる。$B_1\subset B_2$ なら $|B_1|\le|B_2|$ なので、$x\in B_1\setminus B_2$ がある。（B2）により $y\in B_2\setminus B_1$ で $B_1':=(B_1-x)+y\in\mathcal B$ となるものがある。$|B_1'|=|B_1|>|B_2|$ かつ $|B_1'\setminus B_2|=|B_1\setminus B_2|-1$ なので、最小性に反する。
段 2（増加公理）．（I1）は（B1）から、（I2）は定義から明らかである。（I3）を示す。$I_1,I_2\in\mathcal I_{\mathcal B}$、$|I_1|< |I_2|$ とする。$B_1\supset I_1$、$B_2\supset I_2$ となる $B_1,B_2\in\mathcal B$ のうち、$|B_2\setminus(I_2\cup B_1)|$ が最小のものをとる。
$B_2\setminus(I_2\cup B_1)$ に元 $x$ があるとすると、$x\in B_2\setminus B_1$ に（B2）を当てて $y\in B_1\setminus B_2$ で $B_2':=(B_2-x)+y\in\mathcal B$ となるものがとれる。$x\notin I_2$ なので $B_2'\supset I_2$ であり、$|B_2'\setminus(I_2\cup B_1)|$ は 1 だけ小さくなって最小性に反する。よって $B_2\setminus B_1\subset I_2$ である。
次に、$B_1\setminus(I_1\cup B_2)$ に元 $x$ があるとする。（B2）により $y\in B_2\setminus B_1$ で $B_1':=(B_1-x)+y\in\mathcal B$ となるものがある。上で示したことから $y\in I_2$ であり、$y\notin B_1\supset I_1$ である。$x\notin I_1$ なので $I_1+y\subset B_1'$ で、$I_1+y\in\mathcal I_{\mathcal B}$、$y\in I_2\setminus I_1$ となって（I3）が成り立つ。
残るのは $B_1\setminus B_2\subset I_1$ の場合である。このとき $I_1\setminus B_2=B_1\setminus B_2$、$I_2\setminus B_1=B_2\setminus B_1$ であり、段 1 から $|B_1\setminus B_2|=|B_2\setminus B_1|$ なので
$$ |I_1\cap B_2|=|I_1|-|B_1\setminus B_2|< |I_2|-|B_2\setminus B_1|=|I_2\cap B_1| $$
である。$I_1\cap B_2$ と $I_2\cap B_1$ はともに $B_1\cap B_2$ に含まれるので、$y\in(I_2\cap B_1)\setminus I_1$ がある。$I_1+y\subset B_1$ なので $I_1+y\in\mathcal I_{\mathcal B}$ である。
段 3（基は $\mathcal B$）．$\mathcal I_{\mathcal B}$ の極大元は $\mathcal B$ の極大元である。段 1 により $\mathcal B$ の元は同じ大きさで互いに包含関係にないので、$\mathcal B$ の元はすべて極大であり、基全体は $\mathcal B$ に一致する。$\square$

段 1（補題）．$A\subset E$、$X\subset E$ とし、すべての $e\in X$ で $r(A+e)=r(A)$ とする。このとき $r(A\cup X)=r(A)$ である。実際、$X'\subset X$ で $r(A\cup X')=r(A)$ とし、$e\in X\setminus X'$ をとると、（R3）を $A\cup X'$ と $A+e$ に当てて
$$ r(A\cup X'+e)+r(A)\le r(A\cup X'+e)+r((A\cup X')\cap(A+e))\le r(A\cup X')+r(A+e)=2r(A) $$
となる（左の不等号は（R2））。よって $r(A\cup X'+e)\le r(A)$ で、（R2）から等号が成り立つ。$X'$ を 1 元ずつ大きくすればよい。
段 2（公理）．（I1）：（R1）から $r(\emptyset)=0$ である。（I2）：$r(A)=|A|$、$B\subset A$、$C:=A\setminus B$ とする。（R3）と（R1）から $|A|=r(A)\le r(A)+r(\emptyset)\le r(B)+r(C)\le r(B)+|C|$ なので $r(B)\ge|B|$ であり、（R1）から $r(B)=|B|$ である。（I3）：$r(I)=|I|$、$r(J)=|J|$、$|I|< |J|$ とし、どの $e\in J\setminus I$ についても $r(I+e)\neq|I|+1$ と仮定する。（R2）と、（R3）から出る $r(I+e)\le r(I)+r(\{e\})\le r(I)+1$ により $r(I+e)=r(I)$ である。段 1 により $r(I\cup J)=r(I)=|I|< |J|=r(J)$ となり、（R2）に反する。
段 3（階数関数は $r$）．$A\subset E$ とし、$J$ を $A$ に含まれる $\mathcal I_r$ の極大元とする。$e\in A\setminus J$ なら $r(J+e)\neq|J|+1$ なので、段 2 と同じ議論で $r(J+e)=r(J)$ である。段 1 により $r(A)=r(J)=|J|$ である。$|J|$ は $\mathcal I_r$ に関する $A$ の階数なので、$\mathcal I_r$ の階数関数は $r$ である。$\square$

（I1）（C1）により $\emptyset$ は $\mathcal C$ の元を含まない。（I2）は定義から明らかである。
（I3）が成り立たないと仮定し、$I_1,I_2\in\mathcal I_{\mathcal C}$、$|I_1|< |I_2|$ で、どの $e\in I_2\setminus I_1$ についても $I_1+e\notin\mathcal I_{\mathcal C}$ となる組のうち、$|I_1\setminus I_2|$ が最小のものをとる。$I_1\subset I_2$ なら $e\in I_2\setminus I_1$ について $I_1+e\subset I_2$ は（I2）により $\mathcal I_{\mathcal C}$ に属するので、$e\in I_1\setminus I_2$ がある。
組 $(I_1-e,I_2)$ は $|I_1-e|< |I_2|$ で、$|(I_1-e)\setminus I_2|$ がより小さいので（I3）の結論をみたす。$e\notin I_2$ なので、$f\in I_2\setminus I_1$ で $T:=(I_1-e)+f\in\mathcal I_{\mathcal C}$ となるものがある。組 $(T,I_2)$ も $|T|=|I_1|< |I_2|$、$|T\setminus I_2|=|I_1\setminus I_2|-1$ なので、$g\in I_2\setminus T$ で $T+g\in\mathcal I_{\mathcal C}$ となるものがある。$g\in I_2\setminus I_1$、$g\neq f$ である。
仮定から $I_1+g$、$I_1+f$ は $\mathcal C$ の元 $C_1\subset I_1+g$、$C_2\subset I_1+f$ を含む。$C_1\not\subset T+g=(I_1-e)+f+g$ なので $e\in C_1$ であり、同様に $C_2\not\subset T$ から $e\in C_2$ である。$I_1\in\mathcal I_{\mathcal C}$ なので $g\in C_1$ で、$g\notin I_1+f\supset C_2$ だから $C_1\neq C_2$ である。（C3）により $C_3\in\mathcal C$ で $C_3\subset(C_1\cup C_2)-e\subset T+g$ となるものがあり、$T+g\in\mathcal I_{\mathcal C}$ に反する。
閉路が $\mathcal C$ であること：$\mathcal I_{\mathcal C}$ で従属な集合は $\mathcal C$ の元を含む集合である。$C\in\mathcal C$ の真部分集合が $C'\in\mathcal C$ を含めば（C2）により $C'=C$ となって矛盾するので、$C$ は極小な従属集合である。逆に極小な従属集合 $D$ は $C\in\mathcal C$ を含み、$C$ は従属なので $D=C$ である。$\square$

要点：1 は主定理の証明の補題（階数が増えない元を加えても階数は変わらない）から、2 は $F_1$ と $(F_1\cap F_2)+e$ に劣モジュラ性を当てることからしたがう。

thm-mat-cryptomorphism の 1 により、$\mathcal B^*$ が（B1）（B2）をみたすことを示せばよい。（B1）は明らかである。$B_1^*=E\setminus B_1$、$B_2^*=E\setminus B_2$ とし、$x\in B_1^*\setminus B_2^*=B_2\setminus B_1$ とする。prop-mat-basis-exchange の 2 により $y\in B_1\setminus B_2=B_2^*\setminus B_1^*$ で $(B_1+x)-y$ が基となるものがある。その補集合は $(B_1^*-x)+y$ なので、これは $\mathcal B^*$ に属する。補集合を 2 回とると元に戻るので $(M^*)^*=M$ である。$\square$