§E13.16マトロイドの回路と階数

証明.$\mathcal D=\{D\subseteq A:\ D\notin\mathcal I\}$と置く。$A\in\mathcal D$であるから$\mathcal D\ne\emptyset$であり、$E$が有限集合であるから$\mathcal D$も有限集合である。ゆえに$\mathcal D$の元の濃度の集合は空でない有限な非負整数の集合であり、最小値をとる元$C\in\mathcal D$が存在する。

$C$が回路であることを示す。$C$は従属集合である。$C'\subsetneq C$かつ$C'\notin\mathcal I$を満たす$C'$が存在したとすると、$C'\subseteq A$より$C'\in\mathcal D$であり$\lvert C'\rvert<\lvert C\rvert$となって$C$の最小性に反する。ゆえに$C$の真部分集合はすべて独立であり、$C$は極小な従属集合、すなわち回路である。▨

証明.$A\in\mathcal I$とし、$C\subseteq A$を満たす回路$C$が存在したとする。回路は従属集合であるが、§E13.15 定義 1.1 条件 (b)より$C\subseteq A\in\mathcal I$から$C\in\mathcal I$が従い、矛盾する。ゆえに$A$に含まれる回路は存在しない。

逆に$A\notin\mathcal I$とすると、命題 1.2より$C\subseteq A$を満たす回路$C$が存在する。対偶を取ると、$A$に含まれる回路が存在しないならば$A\in\mathcal I$である。▨

証明.定義 2.1 条件 (a)を示す。§E13.15 定義 1.1 条件 (a)より$\emptyset\in\mathcal I$であるから$\emptyset$は従属集合ではなく、回路ではない。

定義 2.1 条件 (b)を示す。$C_1,C_2\in\mathcal C$かつ$C_1\subseteq C_2$とする。$C_1\subsetneq C_2$と仮定すると、$C_2$が極小な従属集合であることから$C_1\in\mathcal I$となるが、$C_1$は回路であり従属集合であるから矛盾する。ゆえに$C_1=C_2$である。

定義 2.1 条件 (c)を示す。 相異なる$C_1,C_2\in\mathcal C$と$x\in C_1\cap C_2$を取り、$X=C_1\cup C_2$と置く。命題 1.3により、$X\setminus\{x\}$に含まれる回路が存在しないことと$X\setminus\{x\}\in\mathcal I$は同値であるから、$X\setminus\{x\}\in\mathcal I$と仮定して矛盾を導けばよい。

まず$C_2\setminus C_1\ne\emptyset$である。実際$C_2\subseteq C_1$とすると定義 2.1 条件 (b)より$C_1=C_2$となって仮定に反する。$y\in C_2\setminus C_1$を一つ取る。$C_2$は極小な従属集合であるから$C_2\setminus\{y\}\in\mathcal I$であり、$C_2\setminus\{y\}\subseteq X$である。

$\{I\in\mathcal I:\ C_2\setminus\{y\}\subseteq I\subseteq X\}$は$C_2\setminus\{y\}$を含む空でない有限族であるから、包含に関して極大な元$I$を取ることができる。$I$は$\{J\in\mathcal I:\ J\subseteq X\}$においても極大である。実際、$I\subsetneq J\subseteq X$かつ$J\in\mathcal I$ならば$C_2\setminus\{y\}\subseteq I\subseteq J$であるから$J$は上の族に属し、$I$の極大性に反する。

$y\notin I$である。実際$y\in I$とすると$C_2=(C_2\setminus\{y\})\cup\{y\}\subseteq I$となり、§E13.15 定義 1.1 条件 (b)より$C_2\in\mathcal I$が従って$C_2$が従属であることに反する。

$C_1\not\subseteq I$である。実際$C_1\subseteq I$とすると同様に$C_1\in\mathcal I$となって矛盾する。ゆえに$z\in C_1\setminus I$が存在する。$y\in C_2\setminus C_1$より$y\notin C_1$であるから$z\ne y$である。$y,z\in X$かつ$y,z\notin I$であるから$\lvert I\rvert\le\lvert X\rvert-2$が成り立つ。

一方、仮定より$X\setminus\{x\}\in\mathcal I$であり、$X\setminus\{x\}\subseteq X$かつ$\lvert X\setminus\{x\}\rvert=\lvert X\rvert-1>\lvert I\rvert$である。$I$と$X\setminus\{x\}$はともに$X$に含まれる独立集合であるから、§E13.15 定義 1.1 条件 (c)を対$(I,\ X\setminus\{x\})$へ適用すると、$w\in(X\setminus\{x\})\setminus I$が存在して$I\cup\{w\}\in\mathcal I$となる。$w\in X$であるから$I\cup\{w\}\subseteq X$であり、$I$が$\{J\in\mathcal I:\ J\subseteq X\}$の極大元であることに反する。

ゆえに$X\setminus\{x\}\notin\mathcal I$であり、命題 1.2より$(C_1\cup C_2)\setminus\{x\}$に含まれる回路が存在する。▨

証明.$A\cup\{x\}\notin\mathcal I$であるから、$\mathcal I$の定義より$C\subseteq A\cup\{x\}$を満たす$C\in\mathcal C$が存在する。$A\in\mathcal I$より$C\not\subseteq A$であるから$x\in C$である。したがって$A\cup\{x\}$に含まれる$\mathcal C$の元はすべて$x$を含む。

一意性を示す。$C_1,C_2\subseteq A\cup\{x\}$を$\mathcal C$の相異なる元とすると、いずれも$x$を含むので$x\in C_1\cap C_2$である。定義 2.1 条件 (c)より$C_3\subseteq(C_1\cup C_2)\setminus\{x\}$を満たす$C_3\in\mathcal C$が存在する。$C_1\cup C_2\subseteq A\cup\{x\}$であるから$(C_1\cup C_2)\setminus\{x\}\subseteq A$であり、$C_3\subseteq A$となる。これは$A\in\mathcal I$に反する。ゆえに$A\cup\{x\}$に含まれる$\mathcal C$の元はただ一つである。▨

証明.定理 2.2より$M$の回路全体$\mathcal C$は定義 2.1 条件 (a)、定義 2.1 条件 (b)、定義 2.1 条件 (c)を満たす。また命題 1.3より$\mathcal I=\{A\subseteq E:\ \forall C\in\mathcal C,\ C\not\subseteq A\}$が成り立つ。ゆえに補題 3.1を適用することができ、主張を得る。▨

証明. 極大な元への延長.$I\in\mathcal I_A$とする。$\{J\in\mathcal I_A:\ I\subseteq J\}$は空でない有限族であるから、濃度が最大の元$J$を取ることができる。$J\subsetneq J'$かつ$J'\in\mathcal I_A$ならば$I\subseteq J'$となって$J$の最大性に反するから、$J$は$\mathcal I_A$の極大な元である。

極大な元の等濃度性.$I,J$を$\mathcal I_A$の極大な元とし、$\lvert I\rvert<\lvert J\rvert$と仮定する。$I,J\in\mathcal I$であるから§E13.15 定義 1.1 条件 (c)より$x\in J\setminus I$が存在して$I\cup\{x\}\in\mathcal I$となる。$x\in J\subseteq A$であるから$I\cup\{x\}\subseteq A$であり、$I\cup\{x\}\in\mathcal I_A$となって$I$の極大性に反する。ゆえに$\lvert I\rvert<\lvert J\rvert$は成り立たず、役割を入れ替えて$\lvert I\rvert=\lvert J\rvert$を得る。

共通の濃度が$r(A)$であること.$r(A)$を与える$\mathcal I_A$の元$I_0$、すなわち$\lvert I_0\rvert=r(A)$を満たす$I_0\in\mathcal I_A$を取る。$I_0$は$\mathcal I_A$の極大な元である。実際$I_0\subsetneq J$かつ$J\in\mathcal I_A$ならば$\lvert J\rvert>r(A)$となって階数の定義に反する。ゆえに極大な元の共通の濃度は$r(A)$である。▨

証明.$(V,F)$の連結成分を$H_1,\dots,H_{c(F)}$とし、$H_i$の頂点集合を$V_i$、辺集合を$F_i$と書く。$F$の各辺は両端点が同一の連結成分に属するから、$F=F_1\sqcup\dots\sqcup F_{c(F)}$であり、$V=V_1\sqcup\dots\sqcup V_{c(F)}$である。

第一段（極大な独立集合の構成）. 各$H_i$は連結であるから、§D2.7 命題 3.9より$V_i$を頂点集合とする$H_i$の全域木が存在する。その辺集合を$T_i\subseteq F_i$と書き、$T=T_1\cup\dots\cup T_{c(F)}$と置く。

$T$が$F$に含まれる$M(G)$の独立集合であることを示す。$(V,T)$が閉路をもつとする。$T\subseteq F$であるから、閉路の頂点は$(V,F)$において互いに到達可能であり、§D2.7 定義 2.3より同一の連結成分に属する。その頂点集合を$V_i$とすると、閉路の各辺は両端点が$V_i$に属する$T$の辺である。$T_j\subseteq F_j$の辺は両端点が$V_j$に属し、相異なる添字の$V_j$は互いに素であるから、閉路の各辺は$T_i$に属する。$(V_i,T_i)$は$H_i$の全域木であって§D2.7 定義 3.1の意味で木であるから閉路をもたず、矛盾する。ゆえに$(V,T)$は閉路をもたず$T\in\mathcal I$である。

$T$が$\{I\in\mathcal I:\ I\subseteq F\}$の包含に関して極大な元であることを示す。$e\in F\setminus T$を取り、$e=\{u,v\}$と書く。$e\in F_i$を満たす添字$i$を取ると、$u$と$v$はともに$V_i$に属する。$T_i$は$H_i$の全域木の辺集合であるから、§D2.7 定理 3.6の定義 2.1 条件 (a)から (4) への含意により$u$と$v$を結ぶ$(V_i,T_i)$の道$P$が存在する。$e\notin T_i$であるから$P$は$e$を用いず、$P$に$e$を加えると閉路が得られる。ゆえに$T\cup\{e\}\notin\mathcal I$であり、$T$は極大である。

第二段（極大性から階数へ）.命題 4.2を$A=F$に対して適用すると、$\{I\in\mathcal I:\ I\subseteq F\}$の極大な元の濃度はすべて$r(F)$に等しい。第一段より$T$はその極大な元であるから$\lvert T\rvert=r(F)$である。

第三段（辺数の勘定）.$(V,T)$は閉路をもたないから、§E13.15 補題 6.2を$T$へ適用することができる。$(V,T)$の連結成分は$H_i$の全域木$(V_i,T_i)$そのものであり、その個数は$c(F)$である。実際、$T_i$は$V_i$を頂点集合とする木の辺集合であるから$(V_i,T_i)$は連結であり、相異なる添字の$V_i$の間には$T$の辺が存在しない。ゆえに$r(F)=\lvert T\rvert=\lvert V\rvert-c(T)=\lvert V\rvert-c(F)$である。▨

証明. 左側の不等式は$A\subseteq A\cup\{x\}$と定義 4.4 条件 (b)による。

右側の不等式を示す。$x\in A$ならば$A\cup\{x\}=A$であるから明らかである。$x\notin A$とする。定義 4.4 条件 (c)を$A$と$\{x\}$へ適用すると$A\cup\{x\}$と$A\cap\{x\}=\emptyset$について$r(A\cup\{x\})+r(\emptyset)\le r(A)+r(\{x\})$となる。定義 4.4 条件 (a)より$r(\emptyset)\ge0$かつ$r(\{x\})\le\lvert\{x\}\rvert=1$であるから$r(A\cup\{x\})\le r(A)+1$である。

最後の主張を示す。$t=\lvert T\rvert$と置き、$T=\{x_1,\dots,x_t\}$と書き、$A_0=A$、$A_j=A_{j-1}\cup\{x_j\}$（$1\le j\le t$）と置く。非負整数$j$についての述語$P(j)$を、$0\le j\le t$のときは「$r(A_j)\le r(A)+j$が成り立つ」、$j>t$のときは恒に真であると定める。

$P(0)$は$A_0=A$より等号として成り立つ。$0\le j<t$を満たす$j$について$P(j)$を仮定すると、上で示した不等式より$r(A_{j+1})\le r(A_j)+1\le r(A)+j+1$であるから$P(j+1)$が成り立つ。$j\ge t$のときは$P(j+1)$が定義により真である。ゆえに§D2.1 命題 1.2の単純帰納法によりすべての非負整数$j$について$P(j)$が成り立つ。とくに$j=t$として$r(A\cup T)=r(A_t)\le r(A)+t=r(A)+\lvert T\rvert$を得る。▨

証明.定義 4.4 条件 (a)を示す。$\emptyset\subseteq A$かつ$\emptyset\in\mathcal I$であるから$r(A)\ge0$である。$A$に含まれる独立集合$I$は$I\subseteq A$を満たすから$\lvert I\rvert\le\lvert A\rvert$であり、$r(A)\le\lvert A\rvert$である。

定義 4.4 条件 (b)を示す。$A\subseteq B$とする。$A$に含まれる独立集合は$B$に含まれる独立集合でもあるから、最大値をとる範囲が広がり$r(A)\le r(B)$である。

定義 4.4 条件 (c)を示す。$A,B\subseteq E$とする。命題 4.2より、$A\cap B$に含まれる独立集合のうち極大なもの$I$を取ることができ、$\lvert I\rvert=r(A\cap B)$である。$I\subseteq A\cup B$かつ$I\in\mathcal I$であるから、同じ命題により$I\subseteq J$を満たす$\{J'\in\mathcal I:\ J'\subseteq A\cup B\}$の極大な元$J$が存在し、$\lvert J\rvert=r(A\cup B)$である。

$J\cap(A\cap B)=I$を示す。$I\subseteq J$かつ$I\subseteq A\cap B$より$I\subseteq J\cap(A\cap B)$である。逆に$J\cap(A\cap B)$は$A\cap B$に含まれる独立集合であり$I$を含むから、$I$が$A\cap B$に含まれる独立集合の中で極大であることより$J\cap(A\cap B)=I$である。

$J\cap A$は$A$に含まれる独立集合であるから$\lvert J\cap A\rvert\le r(A)$であり、同様に$\lvert J\cap B\rvert\le r(B)$である。$J\subseteq A\cup B$であるから包除原理（§D2.3 定理 1.2）により$\lvert J\rvert=\lvert J\cap(A\cup B)\rvert=\lvert J\cap A\rvert+\lvert J\cap B\rvert-\lvert J\cap A\cap B\rvert\le r(A)+r(B)-r(A\cap B)$となる。左辺は$r(A\cup B)$であるから定義 4.4 条件 (c)を得る。

一元追加についての性質. いま示した定義 4.4 条件 (a)、定義 4.4 条件 (b)、定義 4.4 条件 (c)へ補題 4.5を適用すればよい。▨

証明.(1)$\Rightarrow$(2)を示す。命題 4.2の証明のうち「極大な元の等濃度性」の段は§E13.15 定義 1.1 条件 (a)、§E13.15 定義 1.1 条件 (b)、§E13.15 定義 1.1 条件 (c)だけを用いているから、そのまま適用することができる。

(2)$\Rightarrow$(1)を示す。$A,B\in\mathcal I$かつ$\lvert A\rvert<\lvert B\rvert$とし、すべての$x\in B\setminus A$について$A\cup\{x\}\notin\mathcal I$と仮定する。$X=A\cup B$と置き、$\mathcal I_X=\{I\in\mathcal I:\ I\subseteq X\}$と置く。

$A$は$\mathcal I_X$の極大な元である。実際、$A\subsetneq J$かつ$J\in\mathcal I_X$とすると、$x\in J\setminus A\subseteq X\setminus A=B\setminus A$を取ることができ、§E13.15 定義 1.1 条件 (b)より$A\cup\{x\}\subseteq J$から$A\cup\{x\}\in\mathcal I$が従って仮定に反する。

一方$B\in\mathcal I_X$であるから、$\{J\in\mathcal I_X:\ B\subseteq J\}$の中で濃度が最大の元$B'$を取ると、$B'$は$\mathcal I_X$の極大な元であり$\lvert B'\rvert\ge\lvert B\rvert>\lvert A\rvert$である。これは(2)に反する。ゆえに仮定は誤りであり、§E13.15 定義 1.1 条件 (c)が成り立つ。▨

証明. (1)の§E13.15 定義 1.1 条件 (a).定義 2.1 条件 (a)より$\emptyset\notin\mathcal C$である。$C\subseteq\emptyset$を満たす集合は$\emptyset$だけであるから、$\emptyset$に含まれる$\mathcal C$の元は存在せず$\emptyset\in\mathcal I$である。

(1)の§E13.15 定義 1.1 条件 (b).$A\in\mathcal I$かつ$A'\subseteq A$とする。$C\subseteq A'$を満たす$C\in\mathcal C$があれば$C\subseteq A$となって$A\in\mathcal I$に反する。ゆえに$A'\in\mathcal I$である。

(1)の§E13.15 定義 1.1 条件 (c).補題 5.1により、任意の$X\subseteq E$について$\mathcal I_X=\{I\in\mathcal I:\ I\subseteq X\}$の極大な元がすべて同じ濃度をもつことを示せばよい。

$X\subseteq E$を固定する。$\lvert I\rvert<\lvert J\rvert$を満たす$\mathcal I_X$の極大な元の対$(I,J)$が存在したとする。$\mathcal I_X$は有限族であるから、そのような対のうち$\lvert I\setminus J\rvert$が最小のものを一つ取り、あらためて$(I,J)$と書く。

$I\setminus J=\emptyset$とすると$I\subseteq J$であり、$J\in\mathcal I_X$と$I$の極大性から$I=J$となって$\lvert I\rvert<\lvert J\rvert$に反する。ゆえに$e\in I\setminus J$を取ることができる。

$e\in I\subseteq X$かつ$e\notin J$であり、$J$は$\mathcal I_X$の極大な元であるから$J\cup\{e\}\notin\mathcal I$である。補題 3.1より、$J\cup\{e\}$に含まれる$\mathcal C$の元はただ一つであり、それを$C$と書くと$e\in C$である。

$I\in\mathcal I$であるから$C\not\subseteq I$であり、$f\in C\setminus I$が存在する。$e\in I$であるから$f\ne e$であり、$C\subseteq J\cup\{e\}$より$f\in J\setminus I$である。

$J'=(J\cup\{e\})\setminus\{f\}$と置く。$J'\in\mathcal I$を示す。$D\subseteq J'$を満たす$D\in\mathcal C$が存在したとする。$D\subseteq J\cup\{e\}$であり、$J\cup\{e\}$に含まれる$\mathcal C$の元は$C$だけであるから$D=C$である。しかし$f\in C$かつ$f\notin J'$であるから$C\not\subseteq J'$となって矛盾する。ゆえに$J'\in\mathcal I$である。

$e\in X$かつ$J\subseteq X$より$J'\subseteq X$であるから$J'\in\mathcal I_X$であり、$f\in J$かつ$e\notin J$より$\lvert J'\rvert=\lvert J\rvert$である。$J'$を含む$\mathcal I_X$の極大な元$J''$を取ると（命題 4.2の延長の議論は§E13.15 定義 1.1 条件 (a)と§E13.15 定義 1.1 条件 (b)と有限性だけを用いるので、ここで用いることができる）、$\lvert J''\rvert\ge\lvert J'\rvert=\lvert J\rvert>\lvert I\rvert$である。

$f\notin I$であるから$I\setminus J'=I\setminus\bigl((J\cup\{e\})\setminus\{f\}\bigr)=I\setminus(J\cup\{e\})=(I\setminus J)\setminus\{e\}$であり、$e\in I\setminus J$より$\lvert I\setminus J'\rvert=\lvert I\setminus J\rvert-1$である。$J'\subseteq J''$より$I\setminus J''\subseteq I\setminus J'$であるから$\lvert I\setminus J''\rvert\le\lvert I\setminus J\rvert-1$である。したがって対$(I,J'')$は$\lvert I\rvert<\lvert J''\rvert$を満たし、$\lvert I\setminus J''\rvert<\lvert I\setminus J\rvert$となって最小性に反する。

ゆえに$\mathcal I_X$の極大な元はすべて同じ濃度をもち、§E13.15 定義 1.1 条件 (c)が成り立つ。

(1)の回路の一致.$(E,\mathcal I)$の回路全体を$\mathcal C'$と書く。$C\in\mathcal C$とすると$C\subseteq C$より$C\notin\mathcal I$であり、$C$は従属集合である。$D\subsetneq C$かつ$D\notin\mathcal I$とすると、$C'\subseteq D$を満たす$C'\in\mathcal C$が存在し、$C'\subseteq D\subsetneq C$となって定義 2.1 条件 (b)より$C'=C$が従い、$C\subseteq D\subsetneq C$という矛盾を得る。ゆえに$C$の真部分集合はすべて独立であり$C\in\mathcal C'$である。

逆に$C'\in\mathcal C'$とすると$C'\notin\mathcal I$であるから、$C\subseteq C'$を満たす$C\in\mathcal C$が存在する。いま示したとおり$C$は従属集合であり、$C'$が極小な従属集合であることから$C=C'$である。ゆえに$\mathcal C=\mathcal C'$である。

(2)の準備.$r$は定義 4.4 条件 (a)、定義 4.4 条件 (b)、定義 4.4 条件 (c)を満たすから補題 4.5を用いることができる。

(2)の§E13.15 定義 1.1 条件 (a).定義 4.4 条件 (a)より$0\le r(\emptyset)\le\lvert\emptyset\rvert=0$であるから$r(\emptyset)=0=\lvert\emptyset\rvert$であり$\emptyset\in\mathcal I$である。

(2)の§E13.15 定義 1.1 条件 (b).$A\in\mathcal I$かつ$B\subseteq A$とする。補題 4.5を$B$と$T=A\setminus B$へ適用すると$\lvert A\rvert=r(A)=r(B\cup T)\le r(B)+\lvert A\rvert-\lvert B\rvert$であり、$r(B)\ge\lvert B\rvert$を得る。定義 4.4 条件 (a)より$r(B)\le\lvert B\rvert$であるから$r(B)=\lvert B\rvert$、すなわち$B\in\mathcal I$である。

(2)の§E13.15 定義 1.1 条件 (c).$A,B\in\mathcal I$かつ$\lvert A\rvert<\lvert B\rvert$とし、すべての$x\in B\setminus A$について$A\cup\{x\}\notin\mathcal I$と仮定する。$x\in B\setminus A$に対し$r(A\cup\{x\})\le\lvert A\rvert+1$が定義 4.4 条件 (a)から従い、$r(A\cup\{x\})=\lvert A\cup\{x\}\rvert=\lvert A\rvert+1$は仮定により成り立たないから$r(A\cup\{x\})\le\lvert A\rvert=r(A)$である。定義 4.4 条件 (b)より$r(A\cup\{x\})\ge r(A)$であるから$r(A\cup\{x\})=r(A)\qquad(x\in B\setminus A)$が成り立つ。

$m=\lvert B\setminus A\rvert$と置き、$B\setminus A=\{x_1,\dots,x_m\}$と書き、$A_0=A$、$A_j=A_{j-1}\cup\{x_j\}$（$1\le j\le m$）と置く。非負整数$j$についての述語$P(j)$を、$0\le j\le m$のときは「$r(A_j)=r(A)$が成り立つ」、$j>m$のときは恒に真であると定める。

$P(0)$は$A_0=A$より成り立つ。$0\le j<m$を満たす$j$について$P(j)$を仮定する。$x_{j+1}\notin A_j$であるから$A_j\cap(A\cup\{x_{j+1}\})=A$かつ$A_j\cup(A\cup\{x_{j+1}\})=A_{j+1}$であり、定義 4.4 条件 (c)を$A_j$と$A\cup\{x_{j+1}\}$へ適用して$r(A_{j+1})+r(A)\le r(A_j)+r(A\cup\{x_{j+1}\})=r(A)+r(A)$すなわち$r(A_{j+1})\le r(A)$を得る。定義 4.4 条件 (b)より$r(A_{j+1})\ge r(A)$であるから$r(A_{j+1})=r(A)$であり、$P(j+1)$が成り立つ。$j\ge m$のときは$P(j+1)$が定義により真である。ゆえに§D2.1 命題 1.2の単純帰納法によりすべての非負整数$j$について$P(j)$が成り立つ。

とくに$j=m$として$r(A\cup B)=r(A_m)=r(A)=\lvert A\rvert$を得る。一方$B\subseteq A\cup B$と定義 4.4 条件 (b)より$r(A\cup B)\ge r(B)=\lvert B\rvert>\lvert A\rvert$であり、矛盾する。ゆえに§E13.15 定義 1.1 条件 (c)が成り立つ。

(2)の階数関数の一致.$(E,\mathcal I)$の階数関数を$r_{\mathcal I}$と書く。$A\subseteq E$とする。$I\subseteq A$かつ$I\in\mathcal I$ならば定義 4.4 条件 (b)より$\lvert I\rvert=r(I)\le r(A)$であるから$r_{\mathcal I}(A)\le r(A)$である。

逆向きを示す。命題 4.2より$\{I\in\mathcal I:\ I\subseteq A\}$の極大な元$I$を取ることができ、$\lvert I\rvert=r_{\mathcal I}(A)$である。$x\in A\setminus I$に対し$I\cup\{x\}\notin\mathcal I$であるから、上の§E13.15 定義 1.1 条件 (c)の証明と同じ計算により$r(I\cup\{x\})=r(I)$である。

そこで$A\setminus I$の元を一つずつ加える帰納法を、上の議論で$A$が果たした役割を$I$に、$B\setminus A$が果たした役割を$A\setminus I$に取り替えて実行する。$p=\lvert A\setminus I\rvert$と置き、$A\setminus I=\{x_1,\dots,x_p\}$と書き、$I_0=I$、$I_j=I_{j-1}\cup\{x_j\}$（$1\le j\le p$）と置く。$0\le j<p$のとき$x_{j+1}\notin I_j$であるから$I_j\cap(I\cup\{x_{j+1}\})=I$かつ$I_j\cup(I\cup\{x_{j+1}\})=I_{j+1}$であり、定義 4.4 条件 (c)を$I_j$と$I\cup\{x_{j+1}\}$へ適用して$r(I_{j+1})+r(I)\le r(I_j)+r(I\cup\{x_{j+1}\})$を得る。$r(I_j)=r(I)$と$r(I\cup\{x_{j+1}\})=r(I)$から$r(I_{j+1})\le r(I)$が従い、定義 4.4 条件 (b)と合わせて$r(I_{j+1})=r(I)$である。上と同じ形の帰納法（§D2.1 命題 1.2）により$0\le j\le p$を満たすすべての$j$について$r(I_j)=r(I)$が成り立つ。$j=p$として$r(A)=r\bigl(I\cup(A\setminus I)\bigr)=r(I_p)=r(I)=\lvert I\rvert=r_{\mathcal I}(A)$を得る。ゆえに$r=r_{\mathcal I}$である。