§E13.24マトロイドの双対

証明.$x\notin B_1$であり$B_1$は包含に関して極大な独立集合であるから$B_1\cup\{x\}\notin\mathcal I$である。§E13.16 系 3.2より、$B_1\cup\{x\}$に含まれる回路はただ一つであり、その回路を$C$と書くと$x\in C$である。

$B_2\in\mathcal I$であるから$C\not\subseteq B_2$であり、$y\in C\setminus B_2$が存在する。$x\in B_2$であるから$y\ne x$であり、$C\subseteq B_1\cup\{x\}$より$y\in B_1$である。ゆえに$y\in B_1\setminus B_2$である。

$D=(B_1\cup\{x\})\setminus\{y\}$と置き、$D\in\mathcal I$を示す。$D\notin\mathcal I$とすると、§E13.16 命題 1.2より$C'\subseteq D$を満たす回路$C'$が存在する。$C'\subseteq D\subseteq B_1\cup\{x\}$であり、$B_1\cup\{x\}$に含まれる回路は$C$だけであるから$C'=C$である。しかし$y\in C$かつ$y\notin D$であるから$C\not\subseteq D$となって矛盾する。ゆえに$D\in\mathcal I$である。

$x\notin B_1$かつ$y\in B_1$であるから$\lvert D\rvert=\lvert B_1\rvert+1-1=\lvert B_1\rvert$である。§E13.15 系 2.4より$D$は基底である。▨

証明.§E13.15 定義 3.1 条件 (a)を示す。§E13.15 命題 2.2より$\mathcal B\ne\emptyset$であるから$\mathcal B^{*}\ne\emptyset$である。

§E13.15 定義 3.1 条件 (b)を示す。$B_1^{*},B_2^{*}\in\mathcal B^{*}$と$x\in B_1^{*}\setminus B_2^{*}$を取る。$B_1^{*}=E\setminus B_1$、$B_2^{*}=E\setminus B_2$を満たす$B_1,B_2\in\mathcal B$を取る。$x\in B_1^{*}$は$x\notin B_1$を意味し、$x\notin B_2^{*}$は$x\in B_2$を意味するから$x\in B_2\setminus B_1$である。

補題 1.1より$y\in B_1\setminus B_2$が存在して$B_3=(B_1\cup\{x\})\setminus\{y\}\in\mathcal B$となる。$y\in B_1$より$y\notin B_1^{*}$であり、$y\notin B_2$より$y\in B_2^{*}$であるから$y\in B_2^{*}\setminus B_1^{*}$である。

$B_3$の補集合を計算する。$x\notin B_1$かつ$y\in B_1$であるから$E\setminus B_3=E\setminus\bigl((B_1\cup\{x\})\setminus\{y\}\bigr)=\bigl((E\setminus B_1)\setminus\{x\}\bigr)\cup\{y\}=(B_1^{*}\setminus\{x\})\cup\{y\}$である。$B_3\in\mathcal B$であるから$E\setminus B_3\in\mathcal B^{*}$であり、$(B_1^{*}\setminus\{x\})\cup\{y\}\in\mathcal B^{*}$が成り立つ。ゆえに$\mathcal B^{*}$は§E13.15 定義 3.1 条件 (b)を満たす。

マトロイドであること.§E13.15 定理 4.3 (1)より、§E13.15 定義 3.1 条件 (a)と§E13.15 定義 3.1 条件 (b)を満たす$\mathcal B^{*}$から$\mathcal I^{*}=\{A\subseteq E:\ \exists B^{*}\in\mathcal B^{*},\ A\subseteq B^{*}\}$と定めると$(E,\mathcal I^{*})$はマトロイドであり、その基底全体は$\mathcal B^{*}$に一致する。

二重双対.$M^{*}$の基底全体は$\mathcal B^{*}$であるから、$(M^{*})^{*}$の基底全体は$\{E\setminus B^{*}:\ B^{*}\in\mathcal B^{*}\}=\{E\setminus(E\setminus B):\ B\in\mathcal B\}=\mathcal B$である。§E13.15 定理 4.3により、マトロイドはその基底全体によって一意に定まるから$(M^{*})^{*}=M$である。▨

証明.(1)を示す。$A\in\mathcal I^{*}$であることは、$A\subseteq B^{*}$を満たす$B^{*}\in\mathcal B^{*}$が存在することである。$B^{*}=E\setminus B$（$B\in\mathcal B$）と書くと、$A\subseteq E\setminus B$であることと$A\cap B=\emptyset$であることは同値である。

(2)を示す。(1)の否定を取ればよい。$A\notin\mathcal I^{*}$であることは、すべての$B\in\mathcal B$について$A\cap B\ne\emptyset$であることと同値である。▨

証明. 右辺が左辺以下であること.$B\in\mathcal B$とする。$A\cap B\subseteq B\in\mathcal I$であるから§E13.15 定義 1.1 条件 (b)より$A\cap B\in\mathcal I$であり、$A\cap B\subseteq A$であるから§E13.16 定義 4.1より$\lvert A\cap B\rvert\le r(A)$である。

左辺が右辺以下であること.§E13.16 命題 4.2より、$A$に含まれる独立集合であって濃度が$r(A)$のもの$I$が存在する。§E13.15 命題 2.2より$I\subseteq B$を満たす基底$B$が存在する。$I\subseteq A$かつ$I\subseteq B$であるから$I\subseteq A\cap B$であり、$r(A)=\lvert I\rvert\le\lvert A\cap B\rvert$である。

$\mathcal B$は空でない有限族であるから右辺の最大値は定まり、二つの不等式から等号を得る。▨

証明.補題 2.1を$M^{*}$へ適用すると$r^{*}(A)=\max\{\lvert A\cap B^{*}\rvert:\ B^{*}\in\mathcal B^{*}\}=\max\{\lvert A\cap(E\setminus B)\rvert:\ B\in\mathcal B\}=\max\{\lvert A\setminus B\rvert:\ B\in\mathcal B\}$である。$A\setminus B$と$A\cap B$は$A$の分割であるから$\lvert A\setminus B\rvert=\lvert A\rvert-\lvert A\cap B\rvert$であり、$r^{*}(A)=\lvert A\rvert-\min\{\lvert A\cap B\rvert:\ B\in\mathcal B\}$となる。

$\min\{\lvert A\cap B\rvert:\ B\in\mathcal B\}$を計算する。基底は$\{I\in\mathcal I:\ I\subseteq E\}$の包含に関して極大な元にほかならないから、§E13.16 命題 4.2を$A=E$に対して適用すると、すべての$B\in\mathcal B$について$\lvert B\rvert=r(E)$である（§E13.15 命題 2.3も同じ等濃度性を与える）。$B\cap A$と$B\cap(E\setminus A)$は$B$の分割であるから$\lvert A\cap B\rvert=\lvert B\rvert-\lvert B\cap(E\setminus A)\rvert=r(E)-\lvert B\cap(E\setminus A)\rvert$である。$B$を$\mathcal B$の上で動かすと、右辺が最小になるのは$\lvert B\cap(E\setminus A)\rvert$が最大になるときであり、補題 2.1よりその最大値は$r(E\setminus A)$である。ゆえに$\min\{\lvert A\cap B\rvert:\ B\in\mathcal B\}=r(E)-r(E\setminus A)$であり、$r^{*}(A)=\lvert A\rvert-r(E)+r(E\setminus A)$を得る。▨

証明.命題 1.4 (2)により、$A\subseteq E$が$M^{*}$の従属集合であることと、$A$がすべての$B\in\mathcal B$と交わることは同値である。

(1)$\Rightarrow$(2)を示す。$C^{*}$を余回路とする。$C^{*}$は$M^{*}$の従属集合であるから、上の同値によりすべての$B\in\mathcal B$と交わる。$D\subsetneq C^{*}$とすると、$C^{*}$が$M^{*}$の極小な従属集合であることから$D$は$M^{*}$の独立集合であり、上の同値により$D\cap B=\emptyset$を満たす$B\in\mathcal B$が存在する。

(2)$\Rightarrow$(1)を示す。$C^{*}$が(2)を満たすとする。$C^{*}$はすべての$B\in\mathcal B$と交わるから$M^{*}$の従属集合である。$D\subsetneq C^{*}$とすると、(2)より$D\cap B=\emptyset$を満たす$B\in\mathcal B$が存在するから、上の同値により$D$は$M^{*}$の従属集合ではなく独立集合である。ゆえに$C^{*}$は$M^{*}$の極小な従属集合、すなわち余回路である。▨

証明.(1)を示す。$r(\{x\})=0$であることは、$\{x\}$に含まれる独立集合が$\emptyset$だけであること、すなわち$\{x\}\notin\mathcal I$と同値である。$\{x\}$が従属であるとき、その真部分集合は$\emptyset$だけであり§E13.15 定義 1.1 条件 (a)より独立であるから、$\{x\}$は極小な従属集合、すなわち回路である。逆に$\{x\}$が回路ならば従属である。

$\{x\}\notin\mathcal I$であることと$x$がどの基底にも属さないことの同値性を示す。$x\in B$を満たす基底$B$が存在すれば§E13.15 定義 1.1 条件 (b)より$\{x\}\in\mathcal I$である。逆に$\{x\}\in\mathcal I$ならば§E13.15 命題 2.2より$\{x\}\subseteq B$を満たす基底$B$が存在する。

(2)を示す。$x$が coloop 元であることは、定義により$M^{*}$の loop 元であることである。(1)を$M^{*}$へ適用すると、これは$\{x\}$が$M^{*}$の回路であること、すなわち$\{x\}$が$M$の余回路であることと同値である。

$\{x\}$が$M^{*}$の従属集合であることは、命題 1.4 (2)により、すべての$B\in\mathcal B$について$\{x\}\cap B\ne\emptyset$、すなわち$x\in B$が成り立つことと同値である。$\{x\}$が$M^{*}$の従属集合であることと$M^{*}$の回路であることは、(1)の第一の同値を$M^{*}$へ適用して同値である。ゆえに三つの条件は同値である。▨