マトロイドには等価な定義がいくつか知られていますが，このうち基族を用いた定義には二つ有名なものがあります (本記事では基交換公理による定義と同時交換公理による定義と呼びます)．しかし，教科書によってはどちらか一方のみしか書かれていない場合もあり，私がマトロイドについて学び始めたばかりのころは混乱しました．本記事では基交換公理による定義と同時交換公理による定義を紹介し，これらが等価であることを示します．
集合 $X \subseteq E$ と $i \in E$ に対し，$X+i,\ X-i$ はそれぞれ $X \cup \Set{i},\ X \setminus \Set{i}$ の略記であるとします．$+$ や $-$ を複数個連ねる場合もあります．例えば，$X \subseteq E$ と $i,\ j,\ k,\ l \in E$ に対し，$X-i+j$ は $(X \setminus \Set{i}) \cup \Set{j}$，$X+i-j$ は $(X \cup \Set{i}) \setminus \Set{j}$，$X-k+l-i+j$ は $(((X \setminus \Set{k}) \cup \Set{l}) \setminus \Set{i}) \cup \Set{j}$ を表します．
まずは基交換公理によるマトロイドの定義を述べます．
$E$ を有限集合とする．$\BasisFamily \in 2^E$ が
(B-0) $\BasisFamily \neq \emptyset$，
(B-1) $X,\ Y \in \BasisFamily$ ならば，任意の $i \in X \setminus Y$ に対し，ある $j \in Y \setminus X$ が存在して $X-i+j \in \BasisFamily$
を満たすとき，$(E,\ \BasisFamily)$ をマトロイド，$\BasisFamily$ を基族という．
(B-1) は $X$ から $i$ という要素を除いて $j$ という要素を加えても再び $\BasisFamily$ に属する，すなわち $i$ という要素と $j$ という要素を交換できることを表しており，基交換公理と呼ばれています．
マトロイドには様々な公理が知られており，基族を用いた公理以外にも独立集合族を用いた公理やランク関数を用いた公理，サーキット族を用いた公理などが知られています．また，基族を用いた公理には他にもよく知られたものがあり，それが次に紹介する同時交換公理 (B-1') を用いたものです．
$E$ を有限集合とします．$\BasisFamily \in 2^E$ が
(B-0) $\BasisFamily \neq \emptyset$，
(B-1') $X,\ Y \in \BasisFamily$ ならば，任意の $i \in X \setminus Y$ に対し，ある $j \in Y \setminus X$ が存在して $X-i+j,\ Y+i-j \in \BasisFamily$
を満たすとき，$(E,\ \BasisFamily)$ をマトロイド，$\BasisFamily$ を基族という．
(B-1') は (B-1) によく似ていますが，$Y+i-j \in \BasisFamily$ という部分が異なります．すなわち，$X$ において $i$ と $j$ という要素を交換することができるだけでなく，同時に $Y$ においても $i$ と $j$ という要素を交換することができるということを表しています．今回は定義 1 と定義 2 による二つのマトロイドの定義が等価であること，つまり以下の定理を証明します．
$E$ を有限集合，$\BasisFamily \in 2^E$ は (B-0) を満たすとする．このとき，以下の (B-1)，(B-1') は等価である．
(B-1) $X,\ Y \in \BasisFamily$ ならば，任意の $i \in X \setminus Y$ に対し，ある $j \in Y \setminus X$ が存在して $X-i+j \in \BasisFamily$．
(B-1') $X,\ Y \in \BasisFamily$ ならば，任意の $i \in X \setminus Y$ に対し，ある $j \in Y \setminus X$ が存在して $X-i+j,\ Y+i-j \in \BasisFamily$．
(B-1') $\Rightarrow$ (B-1) は明らかなので，逆向きの(B-1) $\Rightarrow$ (B-1') を示すことになります．まずは補題として，$\BasisFamily$ に属する集合は全て要素数が等しいことを示します．
$E$ を有限集合とする．$\BasisFamily \in 2^E$ は (B-0)，(B-1) を満たすとする．このとき，任意の $X,\ Y \in \BasisFamily$ に対し $\Card{X} = \Card{Y}$ が成り立つ．
$\Card{X} > \Card{Y}$ であるとして矛盾を導く．$\Card{X} > \Card{Y}$ より，$i \in X \setminus Y$ となる $i$ が存在する．したがって (B-1) より，$j \in Y \setminus X$ が存在して $X-i+j \in \BasisFamily$ が成り立ち，$\Card{Y\setminus X} > \Card{Y \setminus (X-i+j)}$ である．$\Card{X-i+j} = \Card{X} > \Card{Y}$ より，$X-i+j,\ Y$ に (B-1) を適用し，その結果得られた集合に再び (B-1) を適用するという操作を繰り返すことで，$\Card{Z} = \Card{X} > \Card{Y}$ かつ $\Card{Y \setminus Z} = 0$ を満たす $Z \in \BasisFamily$ を得ることができる．これは $i \in Z \setminus Y$ となる $i$ が存在し，かつ $j \in Y \setminus Z$ となる $j$ が存在しないことを意味するが，(B-1) に矛盾する．
次に，定理 1 を証明します．
(B-1') $\Rightarrow$ (B-1) は明らか．(B-1) $\Rightarrow$ (B-1') を示す．
$\BasisFamily$ が (B-1') を満たさないと仮定すると，$X,\ Y \in \BasisFamily$ で以下の性質 ($*$) を満たすものが存在する．
($*$) $i \in X \setminus Y$ が存在して，任意の $j \in Y \setminus X$ に対して $X-i+j \notin \BasisFamily$ または $Y+i-j \notin \BasisFamily$．
そのような $X,\ Y$ のうち，$\Card{\SymSetMinus{X}{Y}}$ が最小なものをとる．(B-1') を満たさないことと補題 2 より，$\Card{\SymSetMinus{X}{Y}} \geq 4$ である．したがって，$k \in (X-i) \setminus Y$ を満たす $k$ が存在する．
集合 $I,\ J$ を
$$
I = \left\{ j \in Y \setminus X\ \middle|\ X-k+j \in \BasisFamily \right\} , \\
J = \left\{ j \in Y \setminus X\ \middle|\ Y+i-j \in \BasisFamily \right\}
$$
と定める．(B-1) より，$I \neq \emptyset$ である．$l \in I$ を，$I \cap J \neq \emptyset$ ならば $l \in I \cap J$，そうでないならば任意にとる．$\Card{\SymSetMinus{(X-k+l)}{Y}} = \Card{\SymSetMinus{X}{Y}} - 2$ より，もしも $X-k+l,\ Y$ が性質 ($*$) を満たすことがいえれば $\Card{\SymSetMinus{X}{Y}}$ の最小性に矛盾する．以下これを示す．すなわち，任意の $j \in Y \setminus (X-k+l)$ に対し，$Y+i-j \in \BasisFamily$ ならば $Z := X-k+l-i+j \notin \BasisFamily$ であることを示す．
$I \cap J \neq \emptyset$ ならば，$l \in J$ より $Y+i-l \in \BasisFamily$ である．よって ($*$) より，$X-i+l \notin \BasisFamily$ である．さらに，$Y+i-j \in \BasisFamily$ であるから，$X-i+j \notin \BasisFamily$ である．よって，$X,\ Z$ と $i \in X \setminus Z$ に対して (B-1) の対偶を適用すると，$Z \notin \BasisFamily$ であることがいえる．
$I \cap J = \emptyset$ とする．先ほどの場合と同様，$Y+i-j \in \BasisFamily$ であるから，$X-i+j \notin \BasisFamily$ である．$I \cap J = \emptyset$ であることから，$j \notin I$，すなわち $X-k+j \notin \BasisFamily$ が成り立つ．したがって，$Z,\ X$ と $j \in Z \setminus X$ に対して (B-1) の対偶を適用すると，$Z \notin \BasisFamily$ であることがいえる．
文献 [1] では，マトロイドの基族の概念を整数格子上に一般化した概念である M 凸集合の性質が詳しく述べられており，定理 1 を M 凸集合へと一般化したものが証明されています．