結合則を用いた一般結合則の証明

結合則は一部の演算について成立する法則である。じつは結合則が成立する場合には必ず一般結合則も成立するのだが、そのことをこの記事で示していく。

はじめに

結合則とは、同じ演算が2回連なっているときにそのどちらを先に計算しても結果が変わらないという法則である。例えば、整数の足し算について\[(a+b)+c=a+(b+c)\]が成り立つので、整数の足し算について結合則が成り立つということになる。

では3回連なる場合はどうかと考えると\begin{eqnarray}(a+b)+(c+d)&=&((a+b)+c)+d \\= (a+(b+c))+d &=& a+((b+c)+d)\\=a+(b+(c+d))&&\end{eqnarray}が成り立つ。このように同じ演算が何回連なっている場合でもそのどれを先に計算しても結果が変わらないという法則を、一般結合則と呼ぶ。この記事では、一般結合則が結合則から導くことができることを示す。その結論として、結合則が成立する演算についてはかならず一般結合則も成り立つといえる。

結合則

結合則も一般結合則も二項演算についての法則であるが、二項演算とは簡単に言うと「2つの何かをもとに1つの何かを得る操作」のことである。たとえば整数の足し算 ($+$) は「2つの整数を元に1つの整数を得る操作」であるから二項演算である。同様にしていくらでも二項演算の例を考えることができるが、これ以降は二項演算を記号 $\cdot$ で代表することにする。そして、$a\cdot b$ と書くときに演算記号を省略して $ab$ と書いてもよいとする (算数で習う掛け算記号の省略と同じ)。こうすることで以降の証明などが読みやすくなるだろう。

では結合則について述べておく。

定義$\cdot$ を二項演算とする。$a_1$, $a_2$, $a_3$ がこの演算の対象であれば必ず\[(a_1\cdot a_2)\cdot a_3 = a_1\cdot(a_2 \cdot a_3)\]となるとき、この二項演算について結合則が成立するという。

算数や中学・高校数学で習う演算は (おそらく) すべてこの法則が成り立つであろうから、上のような定義を持ち出す意味がないと考える者もいるだろう。しかし、結合則が成り立たない二項演算も作ることはできるので、結合則が成立することが当たり前というわけではない。

結合則が成り立つ演算であれば、$(a\cdot b)\cdot c$ と $a\cdot(b\cdot c)$ は同じ結果になるため区別する必要がない。そこで、たいていはこれらのことを簡単に $a\cdot b\cdot c$ と書く。

一般結合則

結合則は3つの対象に対する演算についての法則であるが、これを一般の $n$ 個の対象に対する演算にも拡張した法則が一般結合則である。たとえば $n=4$ についての一般結合則は\begin{eqnarray}&&(a_1(a_2a_3))a_4 = ((a_1a_2)a_3)a_4 = (a_1a_2)(a_3a_4)\\ &=& a_1(a_2(a_3a_4)) = a_1((a_2a_3)a_4)\end{eqnarray}であるという法則である。この $n=4$ については括弧のつけ方がたった5通りしかないので、結合則を繰り返し適用することで難なく証明できる。しかし、一般にはカタラン数だけ括弧のつけ方が存在し、その数はとても大きいため(\(n=5\) では14通り、\(n=6\) では42通り)、結合則を順番に適応して確かめることは現実的ではない。そこで別の方法での証明をする。

一般結合則の証明

大雑把に一般結合則を言葉にすると「$n$個の対象に対する $n-1$ 回の演算があるとき、どの演算記号を優先して計算しても結果は変わらない」という法則である。この証明でポイントとなるのは、次のように考えて数学的帰納法を使うことである。$n-1$ 回の演算の順番を考えるときに、とりあえず最後の演算に注目することにする。そうすると、$n-1$ 回の演算をそれより回数の少ない演算に分割することができるので、数学的帰納法の手順で進めていれば分割してできた各部分の演算 (つまり先に注目した最後の演算以外の演算) は自由に順番を決めてよいと言える。あとは最後の演算がどれでもよいことを示せばよい。

証明を簡単に書くための準備として、括弧がない場合の計算順序をとりあえず定めてしまうことにする。

定義$n$ 個の対象に対する演算を\[a_1a_2\dots a_{n-1}a_n = (a_1a_2\dots a_{n-1})a_n\]と定める。

この定義から、たとえば $abcd=(abc)d=((ab)c)d$ となり、つまり括弧がない場合には左から計算するということになる。この取り決めは後の証明を書きやすくするための処置であり、いったん一般結合則が証明できてしまえばこの取り決めは無意味なものになる (一般結合則が成り立つなら演算の順番を気にする必要がなくなるため)。

準備が整ったので、前の節で述べた通りの手順で証明していく。

定理$n$ を3以上の自然数とし、二項演算 $\cdot$ について結合則が成立するとする。この二項演算が $n-1$ 個連なるとき、どの演算記号から計算しても左から順に計算するときと同じ結果になる。

(証明) $n$ についての数学的帰納法で証明する。$n=3$ に固定すると、定理の主張は結合則に一致するので成立する。

$n\lt k$ のときに成立するならば $n=k$ のときにも成立することを示す。まず最後に適用する演算記号を $r$ 個目の演算記号とする。このときその計算結果は数学的帰納法の仮定より\begin{eqnarray}(a_1\cdots a_r)(a_{r+1}\cdots a_k) &=& (a_1\cdots a_r)((a_{r+1}\cdots a_{k-1})a_k) \\ &=& ((a_1\cdots a_r)(a_{r+1}\cdots a_{k-1}))a_k \\ &=& (a_1\cdots a_r a_{r+1}\cdots a_{k-1})a_k \\ &=& a_1\cdots a_r a_{r+1}\cdots a_k \end{eqnarray}であり、最後の演算をどこに設定しても、左から順に計算するときと同じ結果になる。また、$a_1\cdots a_r$ と $a_{r+1}\cdots a_k$ の部分も数学的帰納法の仮定よりどの順で計算しても同じ結果になるので、最後の演算以外の順番も含めてどのように設定しても同じ結果になる。

数学  2018/05/08  k.izumi