Steinitzの交換補題

1：$y$ は $x_1,\dots,x_r$ の線形結合なので、取り替えた列の張る空間は $\operatorname{span}(x_1,\dots,x_r)$ に含まれる。逆に、$c_j\neq0$ なので
$$ x_j=c_j^{-1}\Bigl(y-\sum_{i\neq j}c_ix_i\Bigr) $$
であり、$x_j$ は取り替えた列の線形結合である。ほかの $x_i$（$i\neq j$）は取り替えた列にそのまま入っているので、$\operatorname{span}(x_1,\dots,x_r)$ は取り替えた列の張る空間に含まれる。
2：$ay+\sum_{i\neq j}a_ix_i=0$（$a,a_i\in K$）とする。$y$ を代入すると
$$ ac_j\,x_j+\sum_{i\neq j}(ac_i+a_i)\,x_i=0 $$
となる。$x_1,\dots,x_r$ の線形独立性から $ac_j=0$ であり、$c_j\neq0$ なので $a=0$ である。すると $a_i=ac_i+a_i=0$（$i\neq j$）も得られる。$\square$

$0\le k\le m$ について、次の主張 $P(k)$ を $k$ についての帰納法で示す。

$P(k)$：$k\le n$ であり、$u_1,\dots,u_n$ の番号を適当に付け替えると、$w_1,\dots,w_k,u_{k+1},\dots,u_n$ は $V$ を生成する。
$P(0)$ は仮定そのものである。$k< m$ として $P(k)$ を仮定し、$P(k+1)$ を示す。番号を付け替えたあとの列 $w_1,\dots,w_k,u_{k+1},\dots,u_n$ は $V$ を生成するので、$w_{k+1}\in V$ は
$$ w_{k+1}=\sum_{i=1}^{k}b_iw_i+\sum_{j=k+1}^{n}c_ju_j\qquad(b_i,c_j\in K) $$
と書ける（$k=n$ なら右辺の第 2 の和は空である）。
ここで $c_{k+1},\dots,c_n$ がすべて $0$ だったとすると（$k=n$ の場合を含む）、$w_{k+1}-\sum_{i=1}^kb_iw_i=0$ となり、$w_{k+1}$ の係数が $1$ の自明でない線形関係が得られて、$w_1,\dots,w_m$ の線形独立性に反する。したがって $k< n$、すなわち $k+1\le n$ であり、$c_j\neq0$ となる $j\ge k+1$ がある。$u_{k+1},\dots,u_n$ の番号を付け替えて $c_{k+1}\neq0$ としてよい。
lem-steinitz-one-step の 1 を、列 $w_1,\dots,w_k,u_{k+1},\dots,u_n$ と $y=w_{k+1}$、$j=k+1$ に当てはめると、$u_{k+1}$ を $w_{k+1}$ に取り替えた列 $w_1,\dots,w_{k+1},u_{k+2},\dots,u_n$ の張る空間は、取り替える前と同じ $V$ である。よって $P(k+1)$ が成り立つ。
帰納法により $P(m)$ が成り立ち、これは定理の 1 と 2 そのものである。$\square$

1：$u_1,\dots,u_n$ と $u'_1,\dots,u'_{n'}$ を基底とする。前者は線形独立、後者は生成系なので thm-steinitz-exchange の 1 から $n\le n'$、役割を入れ替えて $n'\le n$ である。
2：後半は thm-steinitz-exchange の 1 を、基底（$n$ 本の生成系）に当てはめればよい。前半を示す。$w_1,\dots,w_n$ が線形独立なら、thm-steinitz-exchange の 2 により、基底 $u_1,\dots,u_n$ のうち $n$ 本すべてを取り替えた $w_1,\dots,w_n$ が $V$ を生成する。線形独立な生成系なので基底である。
3：thm-steinitz-exchange の 2 により、番号を付け替えて $w_1,\dots,w_m,u_{m+1},\dots,u_n$ が $V$ を生成する。これが線形従属なら、自明でない関係 $\sum a_iw_i+\sum b_ju_j=0$ がある。$w$ は線形独立なので $b_j\neq0$ となる $j$ があり、その $u_j$ は残りの $n-1$ 本の線形結合である。$u_j$ を取り除いた $n-1$ 本の列も $V$ を生成するが、$V$ は $n$ 本の線形独立な $u_1,\dots,u_n$ を含むので、thm-steinitz-exchange の 1 から $n\le n-1$ となり矛盾する。よって線形独立であり、基底である。
4：$n:=\dim V$ とする。$W$ の線形独立な列は $V$ でも線形独立なので、thm-steinitz-exchange の 1 により長さが $n$ 以下である。そこで $W$ の線形独立な列のうち長さが最大のもの $x_1,\dots,x_k$ をとる（$k\le n$）。$x\in W$ が $\operatorname{span}(x_1,\dots,x_k)$ に入らなければ、線形独立 の命題「一ベクトルの追加」により $x_1,\dots,x_k,x$ は線形独立で、長さの最大性に反する。よって $x_1,\dots,x_k$ は $W$ の基底で、$\dim W=k\le n$ である。$k=n$ なら、2 により $x_1,\dots,x_n$ は $V$ の基底でもあり、$W=\operatorname{span}(x_1,\dots,x_n)=V$ である。$\square$

要点：$b$ の $B$ に関する座標関数を $\varphi$、$B'$ の各元 $b'$ に関する座標関数を $\psi_{b'}$ とすると、$1=\varphi(b)=\sum_{b'}\psi_{b'}(b)\varphi(b')$ の右辺に $0$ でない項がある。その $b'$ が求めるものである。

要点：各 $\ell\in L$ はある有限部分集合 $F\subset S$ の張る空間に入り、1 つの $F$ に割り当てられる $\ell$ は thm-steinitz-exchange により高々 $\lvert F\rvert$ 個である。