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.4ベストアンサー
- 回答日時:
じゃあ順に:
>ψ(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.6
- 回答日時:
え~と, 証明の流れはこれで 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) が一致することを証明する」とか?
うわ~いやすぎ....
No.5
- 回答日時:
「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通りに決めてしまう」方が見通しがよくなるような気がします.
この回答への補足
すみません。#3のお礼での
>ψ(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) (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)に行き着くことができる」を示す
といった感じでしょうか?
あと、最後に私の証明はどこか間違っている部分はありますか?
以上です。長々と失礼しました。
No.3
- 回答日時:
#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.1
- 回答日時:
どの辺が怪しそうだと思ってる?
この回答への補足
ψ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)をいえばよい感じがするんですが…
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 N を2以上の自然数として,N 個のデータ{xn}を考える。以下の3条件が互いに同値であることを示し 1 2023/04/17 18:41
- 数学 リーマン和 1 2022/12/01 13:32
- 統計学 標本平均の分布 9 2022/06/08 09:47
- 統計学 第二種誤り確率について教えて下さい。 2 2022/07/24 03:26
- 数学 線形代数の対称行列についての問題がわからないです。 2 2023/01/08 14:59
- Excel(エクセル) エクセルで同じ数字同士を自動で線で結ぶVBAを教えてください 6 2022/04/26 23:13
- 経済学 国家公務員一般職試験の問題より 同じ財 X を生産する企業1、企業2からなる複占市場において、Xの需 2 2022/11/28 12:44
- Visual Basic(VBA) VBAプログラミング 2 2022/11/27 12:07
- その他(プログラミング・Web制作) Pythonにおける物理のシミュレーションでの単位変換について 2 2023/06/02 17:11
- 統計学 1/n^2Σ【i=1→n】V[Xi]=1/n V[X1]となるのはなぜですか? Xは確率関数です。 2 2023/08/19 13:28
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
10の-9乗ってどういう意味ですか?
-
確率の問題で、「5人の中から3...
-
ばらつきの掛け算
-
写真のような分配ばねの等価ば...
-
【至急!!】線形計画問題教えて...
-
微積分の証明問題についての質...
-
予測値と実測値の数値の乖離を...
-
高低差のある支持点で,電線の...
-
座標平面上での三角形の面積の...
-
ここの計算が分からないので教...
-
高校数学Ⅰ・Aです。 2200の正の...
-
線形代数 部分空間 基底
-
数学A 2桁以上の自然数Nについ...
-
dが平方因子を持たず、d>1であ...
-
レトロゲー「虹のシルクロード」
-
log-logの補間式
-
数学の問題で質問です。 行きは...
-
プラスとマイナスが入った比率...
-
経済学の教科書に載っていたパ...
-
滴定の実験で、結果をExcelで一...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
確率の問題で、「5人の中から3...
-
10の-9乗ってどういう意味ですか?
-
高低差のある支持点で,電線の...
-
数学A 2桁以上の自然数Nについ...
-
ばらつきの掛け算
-
log-logの補間式
-
数学の問題で質問です。 行きは...
-
二点の座標から直線の方程式を...
-
3次元図の角度と辺の長さを求め...
-
高校数学Ⅰ・Aです。 2200の正の...
-
閉形式 (closed form)
-
【至急!!】線形計画問題教えて...
-
再度、4点を通る曲線の方程式
-
接線の方程式
-
線形代数の対称行列についての...
-
dが平方因子を持たず、d>1であ...
-
写真のような分配ばねの等価ば...
-
多変数多項式の係数の求め方
-
3次曲線の長さの求め方
-
ユークリッド空間
おすすめ情報