結合律 | 一般の結合法則の証明をn個で【半群も】
結合律 （結合法則）は、3 個の元について成立すれば、一般の結合法則といって、n 個の元について成立します。ただし、それらの n 個の元の配列順序は固定された状態で括弧をつけます。
このことから、乗法について、累乗が定義できるようになり、指数計算ができて役立ちます。その根幹となる定理になります。
私が高校生のときに、一般の結合法則の証明を見たときに、とても難しいと思いました。括弧だらけの複雑な記号の羅列のように見えたものです。
しかし、二項演算に括弧をたくさんつけているけれども、証明をするときに、規則的に括弧をつけています。
つまり、数学的帰納法で、繰り返し処理を証明しているので、何が繰り返されているのかを見切ると、証明が理解できます。
一般の自然数 n についての証明の理解に自信が持てなさそうなときには、4 個や 5 個の元についての乗法で、確かめて見ると証明の内容が分かってくるかと思います。
行列の乗法についての結合律と、その累乗（べき乗）の定義などは、一般の結合律から納得できます。
また、集合算でも、n 個の集合の和集合を考えるときに、安心して括弧のつけ方に依らずに判断できます。
結合律 :半群の定義から始めます
空集合でない集合 S について、以下の結合律（結合法則）が成立しているときに、S を半群（モノイド）といいます。
【結合律】
S の任意の元 a, b, c について、
a(bc) = (ab)c となるとき、S における二項演算が結合律を満たすという。
この集合 S において定義されている二項演算を乗法といいます。
結合法則だけが成立していて、交換法則などについては、不明な状態です。
この状態から、すぐに導けるのが、一般の結合法則（一般結合律）です。
一般の結合法則とは
半群 S において、S の任意の元を
a1, a2, … , an とする。ただし、n は 3 以上の自然数。
このとき、配列の順番を a1 から an の順に固定して、どのように括弧をつけたとしても、
乗法を (n － 1) 回だけ行ったときに得られる値は、すべて次と等しくなる。
すなわち、( … ((a1a2)a3) … )an
この値は、まず a1 と a2 で乗法を計算し、そして a3 を掛け、その後も添え字の通りに順に乗法を計算したものです。最後に an を掛けています。
n が 3 のときには、半群なので、結合律が成立していて、しかも括弧のつけ方は一通りしかないため成立していることが分かります。
しかし、n が 4 以上のときには、配列の順番を a1 から an の順に固定して括弧をつける方法が複数通りあります。
n が 50 くらいだと、莫大な括弧のつけ方があり、すべて書き出すのは人間技ではありません。
一般の結合律は、n がどんなに大きな自然数であっても、括弧のつけ方に依らずに値が全て同じになるということを保証しています。
結合律 :定理の証明
3 以上の自然数についての数学的帰納法で証明をします。
【n = 3 のとき】
半群 S において結合律が成立しているため、証明したい結論が成立しています。そのため、以下において、n は 4 以上の自然数とします。
【n ≧ 4 のとき】
(n － 1) 個以下の S の元について、成立すると仮定します。
a1, a2, … , an の配列順を固定して、
(n － 1) 回の乗法を行ったときの値は S の元です。その値を t とおきます。
k を 1 以上 n － 1 以下の自然数とすると、t は、a1, … , ak に(k － 1) 回の乗法を行って得られた値である x と、ak+1, … , an に (n － k － 1) 回の乗法を行って得られる値 y のとの積になります。
ここで、k は次の 3 通りの場合に分かれます。
（ア） k = 1
（イ） 2 ≦ k ≦ n － 2
（ウ） k = n － 1
（ア）と（ウ）の場合は、すぐに証明できます。厄介なのが、（イ）のときの証明です。
（ア）や（ウ）のときで様子を見ておくと、（イ）の部分を理解するときの参考になるかと思います。
【（ア）のとき】
a1 と a2, … , an に分断されています。このときは、x = a1 です。
帰納法より、a2 から an までの乗法の値は、括弧のつけ方に関わらず、
( … ((a2a3)a4) … an－1)an となります。
ここで、
a1, ( … ((a2a3)a4) … an－1), an という三個の S の元について、結合律を適用すると、
a1{( … ((a2a3)a4) … an－1)}an
= {a1( … ((a2a3)a4) … an－1)}an
a1, a2, … , an－1 について、
(n － 1) 個の S の元なので、帰納法が使え、値が一つに確定します。
つまり、
a1( … ((a2a3)a4) … an－1)
= ( … ((a1a2)a3) … an－2)an－1 と、添え字の順番どおりに乗法を計算した結果となります。
よって、
a1{( … ((a2a3)a4) … an－1)}an
= {( … ((a1a2)a3) … an－2)an－1}an
= (( … ((a1a2)a3) … an－2)an－1)an
これで、（ア）の場合は、到達したい結論に至りました。
（ウ）のときも、同じ要領でできるので、同様にして成立します。
（ウ）のときの証明
一番、記号が煩雑になる部分です。ただ、証明の要領は（ア）のときの発想です。
k の位置で分断してから帰納法です。
三個には半群 S において成立している結合律を使い、(n － 1) 個には帰納法と押さえておくと理解しやすいかと思われます。
a1, … , ak と ak+1, … , an－1, an に分断されています。そのぞれについて、帰納法を適用させます。
値は、添え字の順番通りに乗法を計算したものとなります。
x =
( … ((a1a2)a3) … ak－1)ak,
y =
( … ((ak+1ak+2)ak+3) … an－1)an
t = xy は、次の三個の S の元で乗法を計算した値となっています。
( … ((a1a2)a3) … ak－1)ak と ak と
( … ((ak+1ak+2)ak+3) … an－1)an の乗法を計算した値が t です。三個の S の元についての乗法なので、結合律を適用できます。
( … ((a1a2)a3) … ak－1) と
( … ((ak+1ak+2)ak+3) … an－1) と an の三個の乗法の値は、結合律から次のようになります。
大括弧の中が添え字の順番通りに乗法を計算した形になり、求める結論に到達します。
xy =
((…((a1a2)a3)…)an-1)an
これで、（イ）の場合の証明も完成しました。
場合分けをしたすべての場合について、
帰納法と S における結合律を使って、証明が完成しました。【証明終了】
今、示した内容を具体例で確認します。
例で確認
理解できたか分からないのかという状態に陥ったら具体例で証明の仕組みを確認すると良いかと思います。
一般結合律の証明については、4 個だと少なすぎるので、5 個や 6 個の元についての乗法で確認をすると分かりやすいです。
先ほどの証明の（イ）の場合を確認します。
a1, a2, a3, a4, a5, a6 について、k = 3 の位置で分断をしてみます。
これら 6 個の配列順をこのまま固定して、括弧をつけて計算した値が t です。
{a1(a2a3)}{a4(a5a6)} と分断され、x と y の値が出てきたとします。
x = a1(a2a3),
y = a4(a5a6)
x と y は (6 － 1) 個以下の元の乗法なので、帰納法が適用できます。
x = (a1a2)a3,
y = (a4a5)a6
帰納法によって、添え字の順番通りに乗法を計算した値となります。
帰納法よりという部分は、同じことの繰り返し処理を表しています。
一番大きい添え字を最後に掛けるように変形するときに、同じことができる再帰性に注目します。
そして、xy を計算するときに、つなぎ目の a3 を結合律を使って、右側へ移動させます。
xy = {(a1a2)a3}× {(a4a5)a6}
= (a1a2) × [a3{(a4a5)a6}]
右側の 4 個の元 a3 から a6 までは、(6 － 1) 個以下なので、帰納法が適用できます。
そうすると、添え字の順通りに乗法を計算した値となります。
xy = (a1a2) × {(a3a4)a5}a6
a1a2 と (a3a4)a5 と a6 の三個の乗法ですので、結合律が適用できます。
{(a1a2) × {(a3a4)a5)} × a6 が、
xy = t の値となります。
一番大きい添え字の a6 を最後に掛ける形にすると、a1 から a5 の (6 － 1) 個に帰納法を適用させ、添え字の順番通りに乗法を計算した値となります。
(( … ((a1a2)a3) … )a5)a6に xy の値は必ずなり、t の値が一つに確定します。
【まとめ】
・三個のときには半群の結合律
・(n － 1) 個のときには帰納法で添え字の順に乗法をした値
具体的に見ると、この二点を意識して、ゴールを目指しているという証明だったと分かります。括弧のつけ方の表記ミスに注意です。
それでは、一般の結合律が役に立つのが、どういう場面かということについて述べます。
結合律 :半群について
空集合ではない集合 S に二項演算が定義されていて、その二項演算について結合律が成立しているときに、S を半群（モノイド）と、この記事の始めの方で述べました。
例えば、実数全体 R は、通常の乗法について半群となっています。
他にも、実数を成分とする n 次正方行列全体は、乗列の乗法について半群となっています。
他にも、実数を係数とする多項式全体も、多項式の乗法について半群となっています。
複素数全体も、通常の複素数の乗法について半群となっています。
このように、結合律が成立する場面は、上で証明した一般の結合律が成立します。
一般の結合律のおかげで、括弧のつけ方に依らずに値が定まるため、累乗を定義することができます。
群論などでも、群は結合律を満たす二項演算を備えているので、累乗を考えることができます。
巡回群などは、その典型となります。
直積集合という記事で、順序対についての二項演算について述べています。大学の数学では、集合系といって、集合たちのあつまりを考えることもあります。
S を集合たちの集まりである集合系で、空ではないとします。この集合系に、集合算という二項演算を定めることができるときがあります。
大袈裟な言い方をしていますが、高校で学習した和集合をとる、共通部分をとるということが、集合系 S における二項演算となることがあります。
A, B ∈ S について、必ず和集合 A ∪ B が S に含まれているときに、次のように二項演算が定義されていると考えることができます。
S × S → S
(A, B) → A ∪ B
(A, B) という集合の組に対して、A ∪ B を二項演算の結果としています。
この二項演算についても、結合律が成立しています。
※ 共通部分をとるということについても、同様の考察ができます。
論理記号というブログ記事の最後の方で、この和集合をとるということについて結合律が成立することを証明しています。
それでは、これで今回のブログ記事を終了します。
一般の結合律は、群の公理から群論を学習し始めるときに、頻繁に使うので、括弧のつけ方に依らずに値が定まるということに慣れておくと良いかと思います。
また、加法と乗法が定義されているときの一般の分配律についての記事も投稿しています。
読んで頂き、ありがとうございました。