高校数学解説

一般の結合則、交換則

結合則,交換則

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

はじめに

結合則と交換則が成り立つ → 任意の並べ替えが可能

これが昔からイマイチ分からなかったので考えてみました。
厳密な論理展開ができているかは不明ですが、そこそこ納得できる感じになった気がします。

結合則

$(a b) c = a (b c)$
のとき、結合則が成り立つという。

この記事では
$a b c$ のような「カッコなしの表記」は、前から順に計算すると約束しておく。

一般の結合則

$n$ を $3$ 以上の自然数とする。
$n$ 個の積に対して、どのようにカッコをつけても演算結果は変わらない。

数学的帰納法をつかって
「どのようにカッコを含んでいても、すべてのカッコを外せる」ことを示す。

$n = 3$ のとき、結合則の定義より成立する。

仮定

$n - 1$ 個までの積について命題が成立すると仮定する。
つまり、 $n - 1$ 個以下の積に対して、自由にカッコを付け外しできる。

数が $n$ 個の場合の検討

$n$ 個の数 $a_{1}$ , $a_{2}$ , $a_{3}$ , $\dots$ , $a_{n}$ の積があり、適当なカッコを含んでいるとする。
$a_{n}$ を含むカッコのうち一番外側にあるものに注目し、その開始位置を $k$ とする。
該当するカッコがない場合は、 $k = n$ とする。
$a_{1} (a_{2} a_{3}) a_{4} \dots a_{k - 1} (a_{k} \dots a_{n})$
積を、 $k$ 個目より前と $k$ 個目以降に分けて考える。
前者は $k - 1$ 個の積なので、仮定よりカッコはすべて外せる。
同様に
後者のカッコ内で入れ子になっているカッコはすべて外せる。
$a_{1} a_{2} a_{3} \dots a_{k - 1} (a_{k} \dots a_{n})$
よって $k = n$ のとき、すべてのカッコを外すことができる。
$k < n$ のとき、カッコを追加して以下の形にする。
$a_{1} a_{2} a_{3} \dots a_{k - 1} ((a_{k} \dots a_{n - 1}) a_{n})$
積の結果は数なので
$s_{1} = a_{1} a_{2} a_{3} \dots a_{k - 1}$
$s_{2} = a_{k} \dots a_{n - 1}$
とおくと、積は
$s_{1} (s_{2} a_{n})$
と書ける。結合則より
$s_{1} (s_{2} a_{n}) = s_{1} s_{2} a_{n}$
$s_{1}$ , $s_{2}$ を戻すと
$s_{1} s_{2} a_{n} = a_{1} a_{2} a_{3} \dots a_{k - 1} (a_{k} \dots a_{n - 1}) a_{n}$
仮定より
$a_{1} a_{2} a_{3} \dots a_{k - 1} (a_{k} \dots a_{n - 1})$
の部分はカッコを外せるので、積は
$a_{1} a_{2} a_{3} \dots a_{n - 1} a_{n}$
となる。よって、この場合にもすべてのカッコを外せる。
したがって、 $3$ 以上のすべての自然数 $n$ について命題が成立する。

交換則

$a b = b a$
のとき、交換則が成り立つという。

一般の交換則

$n$ を $2$ 以上の自然数とする。
積について結合則と交換則が成り立つとき、
$n$ 個の数の積に対して、積の順序をどのように変えても演算結果は変わらない。

交換則、結合則を用いて隣接互換を実現できることを示す。

次の積を考える。
$a_{1} a_{2} a_{3} \dots a_{k} a_{k + 1} \dots a_{n}$
一般の結合則より
$a_{1} a_{2} a_{3} \dots (a_{k} a_{k + 1}) \dots a_{n}$
カッコ内に交換則を適用して
$a_{1} a_{2} a_{3} \dots (a_{k + 1} a_{k}) \dots a_{n}$
カッコを外して
$a_{1} a_{2} a_{3} \dots a_{k + 1} a_{k} \dots a_{n}$
以上の変形から
「結合則と交換則の組み合わせにより任意の隣接互換を実現できる」と言える。
また一般に
有限回の隣接互換を用いて列を自由に並び替えることができる
したがって、命題が成り立つ。

隣接互換

列に対して「隣同士の要素を入れ替える操作」を隣接互換という

有限回の隣接互換を用いて任意の並びをつくることができる

隣接互換によって列 $A_{0}$ を並び替えて、任意の列 $B$ をつくれることを示す。

一般に、列において「直前の要素と入れ替える隣接互換」を繰り返すことで
特定の要素を先頭に移動させることができる。

$A_{0} = (a_{1}, a_{2}, a_{3}, \dots, a_{n})$ , $B = (b_{1}, b_{2}, b_{3}, \dots, b_{n})$ とする。
$A_{0}$ , $B$ の初めの $m$ 項が一致するとき、
両者の部分列 $(a_{m + 1}, \dots, a_{n})$ , $(b_{m + 1}, \dots, b_{n})$ を考える。
$a_{i} = b_{m + 1}$ なる $a_{i}$ について、 $a_{i}$ を部分列の先頭に移動する。
得られた列を $A_{1}$ とすると
$A_{1}$ と $B$ は、少なくとも初めの $m + 1$ 項が一致する。
同様の操作を繰り返すと、有限回( $t$ 回とする)の操作の後、 $A_{t}$ と $B$ が完全に一致する。
よって、 $A_{0}$ に有限回の隣接互換を行って $B$ に一致させることができる。