声に出して読めなくもない数学(2) - エレファント・コンピューティング調査報告

前回の議論を「エレファント化」していきます。すなわち、定義から数式の変換で証明できるようにしていきます。

$X$ を有限次元ベクトル空間 $V = K^\nu$ の有限部分集合とするとき、 $X$ の元の個数を $\#X$ 、 $X$ で張られた部分空間を $\langle X \rangle$ と書くことにします。 $\langle X_1 \cup \cdots \cup X_n \rangle$ を $\langle X_1, \cdots, X_n \rangle$ と書き、 $X_i = \{x\}$ のとき $X_i$ のかわりに $x$ と書いても良いということにします。 $X = Y \cup Z$ 、 $Y \cap Z = \varnothing$ のとき $X = Y + Z$ と書くことにします。 $X = Y + Z$ のとき $\#X = \#Y + \#Z$ となります。

1次独立と1次従属

$V = K^\nu$ の有限部分集合 $X$ が1次独立であるということを以下のように帰納的に定義します。

(1) 空集合は1次独立
(2) $X$ は1次独立かつ $v \notin \langle X \rangle$ ならば $X + \{v\}$ は1次独立

空集合から (2) を繰り返してできる集合を1次独立とし、そうではない集合を1次従属とします。

(3) $X$ は1次独立かつ $X = Y + \{v\}$ ならば $Y$ は1次独立

[証明] $\#Y$ に関する帰納法で示します。 $\#Y = 0$ のときは1次独立の定義 (1) から成り立ちます。
$\#Y \ge 1$ として $\#Y$ より小さいときは成り立っていると仮定します。1次独立の定義より $X = Z + \{u\}$ を満たす1次独立な $Z$ とベクトル $u$ が存在します。 $Y = Z$ のときは成り立ちます。 $Y \ne Z$ とすると $u \ne v$ 、 $Y = (Y \cap Z) + \{u\}$ 、 $Z = (Y \cap Z) + \{v\}$ となります。帰納法の仮定より $Y \cap Z$ は1次独立となり、(2) より $Y$ は1次独立となります。[証明終わり]

(4) $X$ は1次独立かつ $Y \subseteq X$ ならば $Y$ は1次独立

[証明] (3) を繰り返せば成り立ちます。[証明終わり]

(5) $Y \subseteq X$ かつ $Y$ は1次従属ならば $X$ は1次従属

[証明] (4) より成り立ちます。[証明終わり]

(6) $v \in \langle X \rangle \setminus X$ ならば $X + \{v\}$ は1次従属

[証明] $v \in \langle X \rangle$ かつ $X + \{v\}$ は1次独立と仮定します。 $X + \{v\}$ は空集合ではないので (2) より $X + \{v\} = Y + \{w\}$ かつ $Y$ は1次独立、 $w \notin \langle Y \rangle$ である $V$ の部分集合 $Y$ と $w \in V$ が存在します。 $w = v$ または $w \in X$ となります。

$w = v$ のときは $X + \{v\} = Y + \{v\}$ かつ $v \notin \langle Y \rangle$ となります。 $X = Y$ となるので $v \notin \langle X \rangle$ となって $v \in \langle X \rangle$ に反します。

$w \in X$ のときは $X = X' + \{w\}$ となる $X$ の部分集合 $X'$ が存在します。 $X' + \{w\} + \{v\} = Y + \{w\}$ 、 $X' + \{v\} = Y$ 、 $v \in \langle X \rangle = \langle X', w \rangle$ となり、 $X' = \{u_1, u_2, \cdots, u_n\}$ とすると $v = a_1 u_1 + a_2 u_2 + \cdots + a_n u_n + bw$ と表すことができて $v \notin \langle X' \rangle$ より $b \ne 0$ となります。よって $w = \cfrac{1}{b}( -(a_1 u_1 + a_2 u_2 + \cdots + a_n u_n) + v ) \in \langle X', v \rangle = \langle Y \rangle$ となるので $w \notin \langle Y \rangle$ に反します。[証明終わり]

(7) $X + Y$ は1次独立、 $v \in \langle X, Y \rangle \setminus \langle Y \rangle$ ならば

$X^- = X \setminus \{u\}$ 、 $Y^+ = Y + \{v\}$ 、 $\langle X, Y \rangle = \langle X^-, Y^+ \rangle$ を満たす $u \in X$ が存在する
[証明] $X = \{u_1, u_2, \cdots, u_n\}$ 、 $Y = \{w_1, w_2, \cdots, w_m\}$ とすると $v = a_1 u_1 + a_2 u_2 + \cdots + a_n u_n + b_1 w_1 + b_2 w_2 + \cdots + b_m w_m$ と表すことができます。 $v \notin \langle Y \rangle$ よりある $a_k \ne 0$ となります。

$u = u_k$ 、 $X^- = X \setminus \{u\} = \{u'_1, u'_2, \cdots, u'_{n-1}\}$ とおきます。 $v = a_k u + a'_1 u'_1 + a'_2 u'_2 + \cdots + a'_{n-1} u'_{n-1} + b_1 w_1 + b_2 w_2 + \cdots + b_m w_m \in \langle X^-, Y, u \rangle$ 、 $u = \cfrac{1}{a_k}( -(a'_1 u'_1 + a'_2 u'_2 + \cdots + a'_{n-1} u'_{n-1}) - (b_1 w_1 + b_2 w_2 + \cdots + b_m w_m) + v ) \in \langle X^-, Y, v \rangle$ より $\langle X^-, Y, u \rangle \subseteq \langle X^-, Y, v \rangle$ かつ $\langle X^-, Y, v \rangle \subseteq \langle X^-, Y, u \rangle$ となって $\langle X^-, Y, u \rangle = \langle X^-, Y, v \rangle$ となります。 $\langle X, Y \rangle = \langle X^-, Y, u \rangle = \langle X^-, Y, v \rangle = \langle X^-, Y^+ \rangle$ となります。[証明終わり]

(8) $X, Y$ は1次独立、 $Y \subseteq \langle X \rangle$ ならば

$X = Y' + Z$ 、 $\#Y = \#Y'$ 、 $\langle X \rangle = \langle Y, Z \rangle$ 、 $Y \cap Z = \varnothing$ 、 $Y + Z$ は1次独立となる $Y', Z \subseteq X$ が存在する
[証明]
$n = \#Y$ に関する帰納法で示します。 $n = 0$ のときは $Y' = Y$ 、 $Z = X$ が条件を満たします。 $n \ge 1$ として $n-1$ のとき成り立つと仮定します。

$X = \{u_1, u_2, \cdots, u_{n-1}, u_n, u_{n+1}, \cdots, u_m\}$ 、 $Y = \{v_1, v_2, \cdots, v_{n-1}, v_n\}$ は1次独立で $Y \subseteq \langle X \rangle$ とします。

$Y_{n-1} = \{v_1, v_2, \cdots, v_{n-1}\}$ とおくと $Y_{n-1}$ は1次独立、 $Y_{n-1} \subseteq \langle X \rangle$ となるので帰納法の仮定より $X = Y'_{n-1} + Z_{n-1}$ 、 $\#Y_{n-1} = \#Y'_{n-1}$ 、 $\langle X \rangle = \langle Y_{n-1}, Z_{n-1} \rangle$ 、 $Y_{n-1} \cap Z_{n-1} = \varnothing$ 、 $Y_{n-1} + Z_{n-1}$ は1次独立となる $Y'_{n-1}, Z_{n-1} \subseteq X$ が存在します。 $X$ の順序を入れ替えて $X' = \{u'_1, u'_2, \cdots, u'_{n-1}, u'_n, u'_{n+1}, \cdots, u'_m\}$ としたとき $Y'_{n-1} = \{u'_1, u'_2, \cdots, u'_{n-1}\}$ 、 $Z_{n-1} = \{u'_n, u'_{n+1}, \cdots, u'_m\}$ とします。

$v_n \in Z_{n-1}$ のときは $Y' = Y'_{n-1} + \{v_{n}\}$ 、 $Z = Z_{n-1} \setminus \{v_{n}\}$ とおくと $X = Y' + Z$ 、 $\#Y = \#Y'$ 、 $\langle X \rangle = \langle Y, Z \rangle$ 、 $Y \cap Z = \varnothing$ 、 $Y + Z$ は1次独立となります。

$v_n \notin Z_{n-1}$ とします。

$v_n \in Y \subseteq \langle X \rangle = \langle Y_{n-1}, Z_{n-1} \rangle$ 、 $v_n \in \langle Y_{n-1}, Z_{n-1} \rangle \setminus \langle Y_{n-1} \rangle$ 、 $Y_{n-1} + Z_{n-1}$ は1次独立であることから (7) より $Z_{n} = Z_{n-1} \setminus \{w\}$ 、 $Y_n = Y _{n-1}+ \{v\}$ 、 $\langle Y_{n-1}, Z_{n-1} \rangle = \langle Y_{n}, Z_{n} \rangle$ を満たす $w \in Z_{n-1}$ が存在します。

$v_n \in \langle Y_{n-1}, Z \rangle$ とすると $w \in \langle Y, Z \rangle = \langle Y_{n-1}, Z, v_n \rangle = \langle Y_{n-1}, Z \rangle$
(6) より $Y_{n-1} + Z + \{w\} = Y_{n-1} + Z_{n-1}$ は1次従属となります。 $Y_{n-1} + Z_{n-1}$ は1次独立なので $v_n \notin \langle Y_{n-1}, Z \rangle$ となって (2) より $Y + Z$ は1次独立となります。

$v_n \notin Z_{n-1}$ なので $Y \cap Z = (Y _{n-1}+ \{v_n\}) \cap (Z_{n-1} \setminus \{w\}) = \varnothing$ となります。[証明終わり]

(9) $X, Y$ は1次独立、 $Y \subseteq \langle X \rangle$ ならば $\#Y \le \#X$

[証明] $m = \#X$ 、 $n = \#Y$ とおき、 $n \ge m$ とします。 $Y = Y_1 + Y_2, \ \#Y_1 = m$ となる $Y_1, Y_2$ をとることができます。(4) より $Y_1$ は1次独立となります。(8) より $X = X' + Y', \ \#Y_1 = \#Y', \ \langle X \rangle = \langle X', Y_1 \rangle$ を満たす $X', Y'$ が存在します。 $m = \#X = \#X' + \#Y' = \#X' + \#Y_1 = \#X' + m$ より $\#X' = 0$ となって $X' = \varnothing$ となります。 $Y_2 \subseteq Y \subseteq \langle X \rangle = \langle X', Y_1 \rangle = \langle Y_1 \rangle$ となって $Y_1$ は1次独立なので (6) より $Y_2 = \varnothing$ となります。 $n = \#Y = \#Y_1 + \#Y_2 = \#Y_1 = m$ より $n \ge m$ ならば $n = m$ となります。よって $n \le m$ となり $\#Y \le \#X$ となります。[証明終わり]