一般の結合則、交換則

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

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

仮定

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

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

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

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

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

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

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

$A_0=(a_1,a_2,a_3,\ldots,a_n)$, $B=(b_1,b_2,b_3,\ldots,b_n)$とする。
$A_0$,$B$の初めの$m$項が一致するとき、
両者の部分列$(a_{m+1},\ldots,a_n)$, $(b_{m+1},\ldots,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$に一致させることができる。