結合法則

質問

M：空でない集合
φ：M×M→M　φ(φ(x,y),z)＝φ(x,φ(y,z)) (∀x,y,z∈M)…☆

が成立しているとする。

X1,…,Xn∈Mが与えられたとき、Xi,X(i+1)に対しφを作用させる。次にn-1個の元X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xnを改めてY1,…,Y(n-1)と記し、またYj,Y(j+1)に対しφを作用させる。この操作を繰り返し最後に残った元をZとする。

このとき、X1,…,Xnに対しZを対応させる写像ψn:M^n→Mはφを作用させる場所によらず(つまりiやjなどによらず)well-definedである。

以上のことを証明してみたのですがあっているかどうかわからないので、教えて下さい。

(証明)
nに関する帰納法で示す。
n=2…明らか
n=3…☆により明らか。

ψ(n-1)までがwell-definedであると仮定する。
ψnがwell-definedであることを示すには

ψ(n-1)(φ(X1,X2),X3,…,Xn)＝…＝ψ(n-1)(X1,…,X(n-2),φ(X(n-1),Xn))
(∀Xi∈M,i=1,…n)をいえばよい。

ψ(n-1)(X1,…,X(j-1),φ(Xj,X(j+1)),X(j+2),…,Xn)とψ(n-1)(X1,…,Xj,φ(X(j+1),X(j+2)),X(j+3),…,Xn)が等しいことをいえばOK。(j=1,…,n-2)

ψ(n-1)のwell-defined性より
ψ(n-1)(X1,…,X(j-1),φ(Xj,X(j+1)),X(j+2),…,Xn)＝ψ(n-2)(X1,…,X(j-1),φ(φ(Xj,X(j+1)),X(j+2)),X(j+3),…,Xn)…(1)

ψ(n-1)(X1,…,Xj,φ(X(j+1),X(j+2)),X(j+3),…,Xn)＝ψ(n-2)(X1,…,X(j-1),φ(Xj,φ(X(j+1),X(j+2))),X(j+3),…,Xn)…(2)

☆より(1)＝(2)がわかるから

ψ(n-1)(X1,…,X(j-1),φ(Xj,X(j+1)),X(j+2),…,Xn)とψ(n-1)(X1,…,Xj,φ(X(j+1),X(j+2)),X(j+3),…,Xn)が等しい。

したがってψnはwell-definedである。

回答No.6

Tacosan

え～と, 証明の流れはこれで OK です.
ψ(n) の定義を式で書けるといいなあとは思いますが, 厳密に書くと面倒だしねぇ.
「P2 = { 1 }, Pn = { 1, ..., n-1 } × Pn-1 (n ≧ 3) とおいて, I = (i, I') ∈ Pn に対し
ψI(n)(x1, ..., xi-1, xi, xi+1, ..., xn) = ψI'(n-1)(x1, ..., xi-1, φ(xi, xi+1), ..., xn)
(ψ1(2)(x1, x2) = φ(x1, x2))
と定義して, 全ての I ∈ Pn に対し ψI(n)(x1, ..., xn) が一致することを証明する」とか?
うわ～いやすぎ....

お礼

いろいろとありがとうございました。
ψ(n) の定義を厳密に書こうとすると確かに大変ですね^^;

回答No.5

Tacosan

「2分木～」のところは, そんな感じです. 「値を変えずに特定の順序に変化できるから, もともとが同じ値だった」という証明ですね.
で後半ですが, いちおう書いておいたんだけどなぁ....
ψ(n)(X1,X2,…,Xn)＝ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2), …,Xn) (i = 1, ..., n-1)
は, 「定義としては」使えませんが, 「結果的に」成り立ちます. もちろんこれを証明しても OK. あくまで「定義として使えない」という指摘です.
もっとも,
ψ(n-1)(x1, ..., xn-1) = φ(φ( ... φ(x1, x2), ...), xn-1)
と仮定して
ψ(n)(x1, ..., xn) = φ(φ( ... φ(x1, x2), ...), xn)
を証明した方が楽じゃないかなぁという気はしますが.
ψ(n)(x1, ..., xn) = ψ(n-1)(x1, ..., xi-1, φ(xi, xi+1), ..., xn)
であるような i と ψ(n-1) が存在し, ψ(n-1) に対しては帰納法の仮定から
ψ(n-1)(x1, ..., xn-1) = φ(φ( ... φ(x1, x2), ...), xn-1)
なので
ψ(n)(x1, ..., xn) = φ( ... φ(φ( ... φ(x1, x2), ..., xi-1), φ(xi, xi+1)), ..., xn)
= φ( ... φ(φ(φ( ... φ(x1, x2), ..., xi-1), xi), xi+1), ..., xn)
です.
「well-defined なのでどんな順序で計算しても同じ値になる, だからそのときどきにあわせて一番使いやすい順序を使う」というのは確かに正しいんだけど, 読む人が不要に混乱をまねいてしまうおそれがあります. なので, 「順序を 1通りに決めてしまう」方が見通しがよくなるような気がします.

お礼

ありがとうございます。
何度も説明してもらっているのに申し訳ないのですが、

＞ψ(n)(X1,X2,…,Xn)＝ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2), …,Xn) (i = 1, ..., n-1)
は, 「定義としては」使えませんが, 「結果的に」成り立ちます.

私も上の式はψ(n)の定義としては使っていません。(少なくとも私の頭の中では^^;)

私が書いたψ(n)の定義は
「X1,…,Xn∈Mが与えられたとき、Xi,X(i+1)に対しφを作用させる。次にn-1個の元X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xnを改めてY1,…,Y(n-1)と記し、またYj,Y(j+1)に対しφを作用させる。この操作を繰り返し最後に残った元をZとする。」…♯
です。(もちろんiやjなどによらずwell-definedであるかどうかはまだわかっていない。)
そこで、帰納法でψ(n-1)までがwell-definedであると仮定すれば、
ψ(n)はiのみに依ることが分かります。(∵Xi,X(i+1)をφ(Xi,X(i+1))に置き換えればその後の行き先はjなどによらず
ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xn)に行くから)
さらにiにも依らないことを示せばよいと思います。

それで、iにも依らないことを示せて「結果として」
ψ(n)(X1,X2,…,Xn)＝ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xn) (i = 1, ..., n-1)
がわかる。

だから、なにが言いたいかというと私はψ(n)を「♯」と定義してそれがwell-definedであることを示して「その結果として」
ψ(n)(X1,X2,…,Xn)＝ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xn)がわかったということです。

Tacosanさんの方法はψ(n)の定義をφの結合のたくさんある可能性から1つ取り出しそれをψ(n)の定義として、その後、「どんな順番でφを結合していってもψ(n)に行き着くことができる」ということを示すというかんじでしょうか？

だから例えば、
ψ(2)＝φ
ψ(3)＝φ(ψ(2)( , ), )＝φ(φ( , ), )
ψ(4)＝φ(ψ(3)( , , ), )＝φ(φ(φ( , ), ), )
…
ψ(n)＝φ(ψ(n-1)( ,…, ), )
などと定義して
「n-1個の元が与えられたとき、どんな順番でφを結合していってもψ(n-1)に行き着くことができる」を仮定して
「n個の元が与えられたとき、どんな順番でφを結合していってもψ(n)に行き着くことができる」を示す

といった感じでしょうか？

あと、最後に私の証明はどこか間違っている部分はありますか？

以上です。長々と失礼しました。

補足

すみません。＃３のお礼での

＞ψ(n)(X1,X2,…,Xn)＝ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xn) (i＝1,…,n-1)が成立すると思うんですが正しいのでしょうか？

は多分僕が勘違いしていました。これは「ψ(n)がwell-definedであることがわかって始めて分かることですよね^^;」

回答No.4

Tacosan

じゃあ順に:
＞ψ(n)(X1,X2,…,Xn)＝ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2), …,Xn) (i＝1,…,n-1)が成立すると思うんですが正しいのでしょうか？
φ が結合法則を満たすことから, 結果的には成立します.
ただ, これは「定義」としては使えないですね. 流れからすると, ここの「ψ(n)」は「n 個の値 x1, ..., xn に対し任意の順序で φ を適用する」という, たくさん ((2n)Cn / (n+1) 個くらい?) ある関数のどれかを表しているものと考えられます. もちろん右辺の「ψ(n-1)」も, たくさんある関数のどれかです. だとすると, 上の式を「定義」として採用することはできません. なぜなら, 左辺の ψ(n) と右辺の ψ(n-1) では, φ の適用順序が違うかもしれないからです.

＞ψ(x1, x2, ..., xn) = φ(ψ'(x1, ..., xk), ψ''(xk+1, ..., xn))
＞この式のψ'とψ''がよくわかりません。私の記法で書くとψ'＝ψ(k) ψ''＝ψ(n-k)なのでしょうか？
まあ, そう思ってもらってかまいません. 厳密には, ψ, ψ', ψ'' はそれぞれ「ψ(n) の 1つ」, 「ψ(k) の 1つ」, 「ψ(n-k) の 1つ」なんですが.

＞あとψ(x1, x2, ..., xn) = φ(ψ'(x1, ..., xk), ψ''(xk+1, ..., xn)) が成り立つ理由もよくわかりません。
φ を適用するたびに (考慮しなければならない) 要素は 1個ずつ減っていき, 最後に φ を適用するときには (当然ながら) 2個になっています. つまり, 最終的には
ψ(x1, ..., xn) = φ(a, b)
という形でなければなりません. しかも, この a, b には x1, x2, ..., xn がちょうどこの順で 1回ずつ現れます. そこで, 「a には x1～xk が, b には xk+1～xn が現れる」と考えて
ψ(x1, ..., xn) = φ(ψ'(x1, ..., xk), ψ''(xk+1, ..., xn))
と書いています.

ん～, どう考えてもらうといいかなぁ.... 以下, 小さめの n に対して図を描いてもらうと理解しやすいと思うんですが:
例えば, ψを「x1, ..., xn を葉とし, φ の適用を内点 (子は φ を適用する要素) とする 2分木」で表現することができます. このとき, 「φ に対する結合法則」は「2分木において親子関係にある 2個の φ を入れ替える変換」に対応します. このように考えると, 今の問題は「任意の形をした 2分木が与えられたときに, この変換を (何回か) 行うことで『特定の形をした 2分木』に変換できることを示せ」と解釈することができます.
2分木がある性質を持つことを証明するときに, 木の高さに関する帰納法を使うと簡単になることがあります. これは, 2分木が「根とその左右の部分木」からなると見て, 「左右の部分木のそれぞれで性質が成り立つと仮定して, 組合せたときでもその性質が成り立つ」というものです. これは, 「木の構造に関する帰納法」でもあるため (単なる数値上の帰納法と区別して)「構造帰納法」と呼ぶことがあります.
#3 はこの視点に基づいて証明のアウトラインを描いています.

お礼

ありがとうございます。
2分木は聞いたことがないのですが、要するにトーナメント表みたいなものなのですか？それで、準決勝が終わるまでのトーナメント表は変換を何回か行うことで、特定のトーナメント表にできるとわかっていて、それで、決勝が終わるまでのトーナメント表を何回かの変換で特定のトーナメント表にできることを示す。ということなのですか？

＞＞ψ(n)(X1,X2,…,Xn)＝ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2), …,Xn) (i＝1,…,n-1)が成立すると思うんですが正しいのでしょうか？
φ が結合法則を満たすことから, 結果的には成立します.
ただ, これは「定義」としては使えないですね. 流れからすると, ここの「ψ(n)」は「n 個の値 x1, ..., xn に対し任意の順序で φ を適用する」という, たくさん ((2n)Cn / (n+1) 個くらい?) ある関数のどれかを表しているものと考えられます. もちろん右辺の「ψ(n-1)」も, たくさんある関数のどれかです. だとすると, 上の式を「定義」として採用することはできません. なぜなら, 左辺の ψ(n) と右辺の ψ(n-1) では, φ の適用順序が違うかもしれないからです.

ψ(n-1)までがwell-definedであれば、ψ(n)の可能性は
ψ(n-1)(φ(X1,X2),X3,…,Xn),ψ(n-1)(X1,φ(X2,X3),X4,…,Xn),…,ψ(n-1)(X1,…,X(n-2),φ(X(n-1),Xn))のn-1通りしかないと思います。(∵ψ(n-1)がwell-definedであるのでψ(n-1)の関数は一意に定まるから)
それで、そのn-1個の関数が全て等しいことを言えばψ(n)の可能性は1通りに定まるので、ψ(n)がwell-definedであるといえると思うんですが…

回答No.3

Tacosan

#2 で言われている通り, ψの定義があまり明確でないので証明の筋が難しいかもしれません.
ということで, ちょっと構造帰納法で考えてみます.
結局のところ, ψは定義から
ψ(x1, x2, ..., xn) = φ(ψ'(x1, ..., xk), ψ''(xk+1, ..., xn))
という式です. これが特定の計算順序で得られる値, 例えば
φ(x1, φ(x2, ... φ(xn-1, xn) ... ))
と等しいことを言えばいいわけです. ψ', ψ'' は帰納的に φ の式になり, 最後も
φ(x1, φ(x2, ... φ(xn-1, xn) ... )) = φ(φ( ... φ(x1, x2), ...), xn)
に気付けばさほど難しくないはずです.

お礼

ありがとうございます。

＞結局のところ, ψは定義から
ψ(x1, x2, ..., xn) = φ(ψ'(x1, ..., xk), ψ''(xk+1, ..., xn))
という式です. これが特定の計算順序で得られる値, 例えば
φ(x1, φ(x2, ... φ(xn-1, xn) ... ))
と等しいことを言えばいいわけです

あたりがよく分かりません。

私の記法だと、ψ(n)はX1,X2,…,XnのXi,X(i+1)にφを作用させ、
X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xnにまた同じことを繰り返していき
最後に残る元ZをX1,X2,…,Xnに対して対応させようとするものであるから、

ψ(n)(X1,X2,…,Xn)＝ψ(n-1)(X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xn) (i＝1,…,n-1)が成立すると思うんですが正しいのでしょうか？

ψ(x1, x2, ..., xn) = φ(ψ'(x1, ..., xk), ψ''(xk+1, ..., xn))
この式のψ'とψ''がよくわかりません。私の記法で書くとψ'＝ψ(k)
ψ''＝ψ(n-k)なのでしょうか？

あとψ(x1, x2, ..., xn) = φ(ψ'(x1, ..., xk), ψ''(xk+1, ..., xn))
が成り立つ理由もよくわかりません。

回答No.2

koko_u_

ψの定義自体が帰納的なものであることに注目しましょう。

しかし、その定義は明確ではありません。これをはっきりと帰納的な形に定式化することで、自ずと証明も見えてくるものと思われます。

お礼

ありがとうございます。

ψの定義のどのあたりが明確になっていないか分からないので、教えてもらえないでしょうか？

回答No.1

koko_u_

どの辺が怪しそうだと思ってる？

補足

ψnがwell-definedであることを示すには

ψ(n-1)(φ(X1,X2),X3,…,Xn)＝…＝ψ(n-1)(X1,…,X(n-2),φ(X(n-1),Xn))
(∀Xi∈M,i=1,…n)をいえばよい。

あたりです。

φ(ψ(n-1)(X1,…,X(n-1)),Xn)とかの場合をまったく考えていないのが、変な感じです。

ψ(n)の定義からはψ(n-1)(φ(X1,X2),X3,…,Xn)＝…＝ψ(n-1)(X1,…,X(n-2),φ(X(n-1),Xn))
(∀Xi∈M,i=1,…n)をいえばよい感じがするんですが…