前回に引き続いて群 G = {a1,a2,a3,a4,a5,a6} について見ていく。
群 G の要素 a をひとつ取りその累乗 e, a, a2, a3, ... を作っていくと必ず等しいものがあるはずだ。それでなければ G の要素数が無限に増えることになり、Gが有限群であるという仮定に反してしまう。 例えばGの要素 a2 を取り上げてこれを見てみよう。 *Main> toS $ a2 base "a2" *Main> toS $ (a2 . a2) base "a3" *Main> toS $ (a2 . a2 . a2) base "a1" *Main> toS $ (a2 . a2 . a2 . a2) base "a2" となって、a24 は a2 に戻ってしまった。 ここで少し数学を使う。a の累乗のうちで ar と as が等しいとする。ただし r > s とする。こう仮定しても一般性は失われない。つまり、 ar = as 両辺に a-s を右から掛けると、 ara-s = asa-s ar-s = e つまり a は r - s > 0 だけ掛け合わせると単位元に等しくなるはずだ。このような r - s の最少の数を要素 a の位数と名づける。上の例で言うと a2 の位数は 3 である。すなわち、a2 . a2 . a2 = e である。ここから次の定理が導き出される。定理の証明は『代数的構造』に書かれているので省略する。 定理2 Gの要素 a の位数を m とすると、 g = {e, a, a2, ... , am-1}はGの部分群であり、その位数は 3 である。 上の例で言えば、{e(=a1), e2, (e2.e2)} は G の部分群である。これは次のように table 関数で演算表を作ってみると確認できる。 *Main> table [a1, a2, (a2 . a2)] [a1, a2, (a2 . a2)] ["a1","a2","a3"] ["a2","a3","a1"] ["a3","a1","a2"] これは結局 {a1, a2, a3} という G の部分群と同じだから次の定理が成り立つ。 定理3 群 G の要素の位数は G の位数の約数である。 要するに群 G の任意の要素を繰り返し掛けていって、その値が e になった時に、それまでの値と e を集めて集合を作るとそれが部分群になるということだ。こうやると、G の全ての部分群を機械的に求めることができる。 定理4は少しややこしい形をしている。 定理4 G の部分群を g = {a1,a2, ... ,ar} とし、G を g によって左剰余類に分けた時、それを、 gb1,gb2, ... ,gbnとする。 この時、Gの任意の要素は aibk (i=1,2, ... ,r k= 1,2, ... ,s)という形にただ一通りの形に書ける。 定理の証明は『代数的構造』に書いてあるので、ここでは上の定理の意味を考えてみることにする。 まず群 G = {a1,a2,a3,a4,a5} を部分群 {a1,a4} で左剰余類に類別してみる。 *Main> table [a1,a4] [a1,a2,a3,a4,a5,a6] ["a1","a2","a3","a4","a5","a6"] ["a4","a5","a6","a1","a2","a3"] 左剰余類だから、剰余類の集合は列で見ていく。そうすると G は部分群 {a1,a4}, {a2,a5}, {a3,a6} の3つの部分集合に類別される。 そこで a1 . a2 を計算すると次のようになる。 *Main> table [a1] [a2] ["a2"] つまり、a1 . a2 = a2 で {a2, a5} の要素になる。また、a4 . a2 を計算すると、 *Main> table [a4] [a2] ["a5"] a4 . a2 = a5 で、やはり {a2, a5} の要素だ。すなわち、{a2, a5} の要素はその類の代表元 a2 と部分群 {a1, a4} の要素の結合で全て表現できる。同じ事は {a2, a5} の代表元を a5 に取ってもいえる。 *Main> table [a1] [a5] ["a5"] *Main> table [a4] [a5] ["a2"] 順序が変わっているが、{a2,a5} を代表元と部分群の要素の結合で表現できることには変わりない。 これがどういうことを意味するかというと、左剰余類の代表元だけを集めた集合 {a1,a2,a5} と部分群 {a1,a4} の結合で群 G = {a1,a2,a3,a4,a5,a6} の全ての操作が作り出せるということになる。 実際に左余剰類 {a1,a4}, {a2,a5}, {a3,a6} の代表元の集合 {a1, a2, a3} と部分群 {a1, a4} の演算表を作ってみると次のようになる。 *Main> table [a1,a4] [a1,a2,a3] ["a1","a2","a3"] ["a4","a5","a6"] 群G の要素が過不足なく計算されていることがわかる。実は、a1 は単位元で正三角形を全く動かさない操作だし、a4 は正三角形を頂点を通り底辺に垂直な軸の周りに反転させる操作になる。また、a2 は正三角形を時計方向に60度回転させる操作で、a3 は正三角形を120度回転させる操作だ。結局のところこれらの4つの操作で全ての正三角形を重ね合わせる操作は表現できることになる。 これはまた、見方を変えると、群Gの要素は、部分群 g = {a1,a4} とgによる左剰余類の代表元の集合 B = {a1,a2,a3} の要素の組み (a1,a1) や (a4,a3)、一般化すると (ai, bj) で表せる事が分かる。つまり G = g × B (集合 g と集合 B の直積) である。 集合の要素に演算が定義できて、結合法則を満たし、単位元と逆元を持つというゆるい条件の群が、部分群を持っていたり、部分群で類別できたり、部分群と類別の代表元の集合との直和に分解できたりなど、複雑な構造を持っていることが分かった。 また群の定義は抽象的なので、この定義に当てはまる集合にはどれにも部分群などの議論が当てはまる。集合の演算にゆるい4つのルールが成立していれば、その集合の内部構造を知らなくても、その集合について直和分解などの構造を適用することができる。 群論の及ぼす影響は広範なので、加減乗除や幾何学や微分積分や線形代数などとならんで、基礎的な教養として考えられなくてはならないのかもしれない。 『代数的構造』には群について、この他にも同型、同型写像、自己同型群、部分集合の乗法、準同型、準同型写像、正規部分群、剰余群、対称群、自己同型、共役類、中心、可換群、複合構造、素構造、単生群などの解説が進んでいくが、Haskell のプログラム perm.hs のモデルでは追いつかないようなので、プログでの記事はここで終わる。 群の単純な定義の割には内容豊富な構造があるのにびっくりした。Haskell は圏論を元にしているといっても、群論だけでこれだけ内容が豊富なのだから、予備知識無しに圏論の教科書を読んでも難しいだろうということは分かった。 Haskell でプログラムを組むのに、数学の知識は必要ないが、しかし、数学の抽象的な考え方というのが応用力のある強力なアルゴリズムを提供してくれるのではないかという気がした。
by tnomura9
| 2012-08-13 14:53
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||