<   2014年 08月 ( 13 )   > この月の画像一覧

自由群と随伴関手

やっと、自由群が随伴関手の例であることを確認できる所まで来た。まず Wikipedia の随伴関手の記事から自由群に関する部分を引用してみる。

自由群

自由群の構成は極めて普通の随伴による構成であり、上記の詳細の分かりやすくて便利な例である。
関手F : Grp ← Setは各集合YにYの要素の生成する自由群を対応させるものとし、関手G : Grp → Setは群Xにその台集合を対応させる忘却関手とする。以下に示すようにFはGの左随伴となる。

hom集合の随伴。自由群FYから群Xへの群準同型は正確に集合Yから集合GXへの写像に対応する。すなわち、FYからXへの射は生成元への作用により完全に決定される。この対応が自然同型であることも直接確認できる。よって(F,G)に対応するhom集合の随伴が得られた。

これも十分抽象的でわかりづらいので、整理してみる。まず集合の圏 Grp と群の圏 Set がある。また Grp の対象の群 X と Set の対象の集合 Y が取り出してある。また、関手 F を Grp の対象の集合とそれが生成する自由群とを対応させる関手とし、関手 G を群とその台集合を対応させる関手とする。つまり、

F : Set -> Grp
G: Grp -> Set

で両者は domain と codomain が逆になっている。ここで、集合 Y から集合 GX (群XのGの対象関数による像)への写像を f とする。

f : Y -> GX

このような関数の任意のもの f について、自由群の普遍性から、全ての a ∈ Y について、次の条件を満たす FY から G への準同型写像 f~ が一意的に決まる。

f~ a = f a

これは、自由群 FY は集合 Y の要素を生成元として全ての要素を生成できるので、準同型写像 f~ : FY -> G も集合Y の要素から決定できるからだ。φ : f |-> f~ が全単射であることの証明は省くがこれは全単射になる。したがって、

home(FY, X) ~= home(Y, GX)

となり、また、f~ a = f a から次の可換式が成り立つ。

Gf~F = f

したがって、関手 F と関手 G は随伴である。このとき、関手 F は関手 G の左随伴であり、関手 G は関手 F の右随伴である。

これから得られる随伴関手のイメージはつぎのようになるのではないだろうか。

圏 Set の世界と 圏 Grp の世界があり、Set の対象 Y は関手 F で Grp の対象 FY に写される。また、Grp の対象 X は関手 G によって Set の対象 GX に写される。そうして集合の世界の集合と集合の関係である写像 f : Y -> GX は群の世界の群と群の関係である準同型写像 f~ : FY -> Gに写される。

さらに射の可換性によって、集合の世界の対象が関手 F によって群の世界に写しだされ、処理を受けた後関手 G によって、集合の世界に移し戻された結果が、集合の世界の対応する変化と呼応している。

これが、具体的に何の役に立つのかと言われても答えられないが、集合の世界と群の世界の緊密な交流を随伴関手で行っているといえるのではないだろうか。参考までに、Wikipedia の随伴関手の記事をもう一つ引用する。

William Lawvereによる非常に一般的な解説[2]によると「構文と意味」は随伴である。つまり、Cを全ての論理(公理化)からなる集合とし、Dを全ての数学的構造からなる集合の冪集合とする。Cの各理論Tに対して、F(T)を公理Tを満たす構造全てからなる集合とし、各数学的構造の族Sに対して、G(S)はSの最小の公理化とする。このとき、F(T)がSの部分集合であることと、G(S)がTの論理的帰結であることは同値であり、「意味関手」Fは「構文関手」Gの左随伴である。

詳しいことは理解できなかったが、論理学における構文と意味との関係が随伴であることが証明されているらしい。構文の構造と数学的構造の関連性を問う意味論を、随伴によって厳密に記述できるという意味だろうか。

こうしてみると、圏論は数学的構造という掴み難いものに共通のパターンを与えるのに強力な働きをしているような気がする。これは、おそらくプログラミングの抽象化とも関連して将来的にはプログラミングをする上で重要な基礎知識になるのではないかと思えるが、そろそろ Haskell の実際のプログラミングに戻りたくなったので、圏論のシリーズはしばらくおしまいにする。知識が溜まって書きたくなったら再挑戦するかもしれない。
[PR]
by tnomura9 | 2014-08-31 12:07 | 圏論 | Comments(4)

自由群の準同型写像の作り方

勝手に選んだ集合 S と群 G があるとする。また、集合 S と群 G の台集合 G (群と同じ名前) の間の関数を適当に f : S -> G とする。これらの S、G、f を元に S の上の自由群 F(S) と群 G の間の準同型写像 f~ : F(S) -> G を作ってみよう。

まず集合 S の要素と1対1対応する文字の集合 S' = {a, b, .. } を考える。さらに、S' に対応させて文字の集合 S'' = {a-1, b-1, .. } を考える。この二つの文字集合と空文字 '' をあわせて文字集合 S~ を作ると、

S~ = {'', a, a-1, b, b-1, .. }

となる。そこで、この文字集合 S~ の文字を並べてつくた文字列を要素とする集合 Sm をつくると次のようになる。

Sm = {'', a, a-1, aa, aa-1, ab, .. }

またこの文字列の集合 S に二項演算 * を導入するが、* は二つの文字列を連結する操作にする。つまり、

abc * def = abcdef

である。さらに文字列の集合 Sm に簡約の規則を導入する。すなわち aa-1 のように文字とその逆元がならんだらそれは空白文字 '' と置き換えることができるとする。つまり、

aa-1 = a-1a = ''

である。このような簡約を続けていってそれ以上簡約できなくなった文字列は既約であるということにする。証明は省くが、簡約を続けて得られる既約の文字列がおなじになる文字列の間の関係は同値関係になるから、それらの文字列を集めると、規約の文字列を代表元とする同値類になる。この同値類の集合が前回も述べたような S' 上の自由群 F(S') となる。すなわち、

F(S') = {[''], [a], [a-1], [ab], ... }

である。ここで、自由群 F(S') と 最初に選んだ群 G とのあいだの写像 f~ を段階的に定義していく。

まず S と S' は仮定から全単射で対応付けられているので S と S' を同一視する。たとえば f : S -> G のとき、g = f s だが、これを f : S' -> G と考え g = f 's' と同じものと考える。また、's' を s と同一視して s と記述することにする。

まず、集合 S = {a, b, c, ...} と群 G の台集合 G = {x, y, z, ... } の間の関数 f が、

f a = x, f b = y, f c = z, ...

であるとする。このとき自由群 F(S) と群 G の間に f を利用して f~ : F(S) -> G を作る。まず、F(S) の要素 [a], [b], [c], ... については f を使って、

f~ [a] = f a = x, f~ [b] = f b = y, ...

のようにする。また [a] の逆元 [a-1] については、次のように定義すれば、F(x) の逆元は f^ によって G の逆元に写される。

f~ [a-1] = (f a)-1 = x-1

さらに、演算子 * について f~ を次のように定義する。

f~ ([a] * [b]) = (f~ [a])(f~ [b]) = xy

F(S) のその他の元の f~ による値については上で定義されたルールによってすべて確定される。つまり、上の定義で f : S -> G を利用して、写像 f~ : F(S) -> G が定義できることが分かる。また、これは簡単な推論で F(S) -> G の準同型写像であることを証明できる。

また、定義から明らかであるが、f~ を S'' = {[a], [b], ... } に制限した写像では、

f~ [a] = f a

である。ここで、[a] と a を同一視すると上の等式は、

f~ a = f a

となる。これまでの操作はどのような f : S -> G についても同じ手続きで行うことができる。したがって、この操作は普遍的なのである。

以上の説明は証明ではなく、f : S -> G から f~ : F(S) -> G を導き出すときのアイディアを概観しただけであるが、これがわかれば自由群の普遍性についての次の記述を理解することができる。

自由群の普遍性 (自由群 - Wikipedia)

文字集合 X 上の自由群は自由群の普遍性 (universal property) と呼ばれる、以下の性質によって特徴付けられる。G を任意の群とし、f: X → G を任意の写像とすると、群の準同型

f~ : F(X) -> G

で、その X への制限写像について

f~ a = f a

が任意の a ∈ X に対して成立するようなものがただ一つ存在する。

自由群は、より一般の概念として圏論における自由対象 (free object) の一例である。多くの普遍的構造と同じく、それは一組の随伴関手を定める。

これによって、自由群の普遍性の意味は、集合 X から群の台集合 G への写像 f : X -> G はどんなものでも、自由群 F(X) から群 G への「同型写像」f~ : F(X) -> G へ拡張できることだということがわかる。

これで随伴関手の例のひとつを理解するための準備が整った。
[PR]
by tnomura9 | 2014-08-30 17:40 | 圏論 | Comments(0)

部分圏のイメージ

マックレーンの『圏論の基礎』には、部分圏の定義を次のように書いてある (p.18)。

圏 C の部分圏 (subcategory) S とは、C のいくつかの対象と、いくつかの射の集まりで、各射 f について対象 dom f と cod f の両方を含み、各対象 s について恒等射 1s を含み、合成可能な射の各対 s -> s' -> s'' についてその合成を含むものである。これらの条件は対象と射のこれらの集まりそのものが圏 S を構成することを保証する。

「いくつかの対象と、いくつかの射のあつまり」以外の部分は圏の定義と同じだから部分圏という限りは当然だ。問題はこの「いくつかの対象と、いくつかの射のあつまり」という部分だ。

構造的に閉じた部分集合というと、部分群を思い浮かべる。部分群は本質的には部分集合だ。もとの群の二項演算について閉じているが、本質的には集合の要素の部分的なあつまりだ。

部分圏の場合は、視野を対象と射の両方に広げなくてはならない。ここが一番いいたかったことだが、対象の数が元の圏と同じでも、射の数が少なければそれは部分圏になるということだ。部分群の場合は、少ないのは要素の数だったが、部分圏の場合は対象と射の両方が減っている。あるいはどちらかが同じでどちらかだけが減っている場合もある。

部分群のアナロジーで部分圏をとらえようとすると、参考書の記述と自分のイメージとが合致しないことが出てくるので注意が必要だ。

数学の記述は、適切な視覚的イメージを作ることができれば、理解できることが多い。理解できないと考えるときには自分のイメージにどこか問題があるのではないかと検討しててみることも必要だ。
[PR]
by tnomura9 | 2014-08-29 16:58 | 圏論 | Comments(9)

忘却関手のイメージ

群は集合 G と二項演算 * の組 (G, *) だ。したがって、群 G と G' の間の準同型写像 f : G -> G' といっても基本的には集合と集合の間の写像と変わらない。つまり、全射や単射や全単射などの性質はそのまま残っている。

ただし、準同型写像の場合は f によって構造が保存される。つまり、写像 f によって演算が1対1に対応する。具体的には f(xy) = f(x)f(y) という等式がなりたつ。したがって、単射の準同型写像や、全射の準同型写像や、全単射の準同型写像や、全射でも単射でもない準同型写像があるということだ。

しかし、f(xy) = f(x)f(y) を満たさない写像は準同型写像とは言えない事に注意が必要だ。準同型写像全体の集合を考えると、それは集合の写像全体の集合の部分集合になる。(参考:準同型 - Wikipedia

全ての群の圏 Grp とは群を対象とし、群と群との同型写像を射とする圏のことだ。また、小さな集合の圏 Set は集合を対象とし集合と集合の間の関数を射とする圏である。群の圏から集合の圏への「忘却関手」U : Grp -> Set とは、Grp の対象である群を Set の対象である集合に対応させ、Grp の射である準同型写像を Set の射である写像に対応させる。

忘却関手をイメージすると、Grp の対象である群の台集合をそのまま Set の対象とし、Grp の射である準同型写像をそのまま Set の射に写す。集合の圏では演算は定義されていないので f(xy) = f(x)f(y) という等式は意味がなくなってしまう。つまり、忘却関手とは群の圏から演算を取り去ってしまって、そのまま集合の圏の部分圏に写しだしたものと考えると良い。忘却関手の像の射の集合は集合の圏の射の集合の部分集合になっている。

したがって、忘却関手のイメージとは、群の圏を、集合の圏の部分圏へ写す関手と考える事ができる。

一方自由群は集合から作る事ができる。集合の圏の対象である文字集合をその上の自由群に対応させ、文字集合間の写像を対応する自由群間の準同型写像に対応させる関手(自由関手)を考えると、これは忘却関手とは反対方向の Set -> Grp の関手になる。自由関手は忘却関手の左随伴である。したがって、自由関手と忘却関手の関係が分かれば、随伴の実例のひとつを理解できることになる。
[PR]
by tnomura9 | 2014-08-29 05:33 | 圏論 | Comments(0)

いかさん

現役女子高生。男の声で歌っているのにびっくり。女の子の声でも歌える。そう書くと色物に聞こえるが、歌唱力が半端ではない。高校生でこれだけ歌えるのかと驚いた。

いかさん - YouTube

なんか、最近の若者はすごいことになっている。
[PR]
by tnomura9 | 2014-08-27 07:50 | ボーカロイド | Comments(0)

群と自由群

群とは一口に言うと。集合 G と二項演算 * の組 (G, *) のことだ。ただし、2項演算は結合法則を満たしており、単位元と逆元が存在するという3つの条件が成立している必要がある。

整数の集合 G = {..., -3, -2, -1, 0, 1, 2, 3, ... } と整数の加法 + の組は群となる。加法 + は次の例のように結合法則を満たしており、

(2 + 3) + 4 = 2 + (3 + 4) = 9

単位元 0 があり、

3 + 0 = 0 + 3 = 3

整数の要素の全てに逆元が存在する。

3 + (-3) = (-3) + 3 = 0

群は作用の集合だとか、2項演算は一般に非可換であるとか、面倒くさい話はここではなしにする。とにかく群とは集合と演算と結合法則と単位元と逆元でできているという事だけに注目する。

ただ、ひとつだけ取り上げておきたいのは、群の条件から逆元を取り除いた代数的構造がモノイドだということだ。また、モノイドに逆元が存在していればそれは群になる。

モノイドのなかには、自由モノイドというものがある。どいういうものかというと、文字の集合 X = {a, b, c} の文字を並べて文字列の集合 A = {'', a, b, c, ab, ac, bc, abc, ... } をつくり、文字列の連結 . という二項演算を導入するのだ。このとき、集合 A と二項演算 . の組 (A, . ) は自由モノイドになる。つまり、. はつぎのように結合法則を満たし、

(ab . bc) . cd = ab . (bc . cd) = abbccd

空文字 '' という単位元を持つ。

a . '' = '' . a = a

群ではないので逆元はない。

この自由モノイドに逆元を導入したのが自由群である。どうやるかというと、文字 a, b, c に逆元を作るために新しい文字 a-1, b-1, c-1 を導入する。これらは対応する a, b, c との連結をつくると単位元である空文字 '' になると定義する。すなわち、

a . a-1 = a-1 . a = ''
b . b-1 = b-1 . b = ''
c . c-1 = c-1 . c = ''

そこで、これらを含む文字集合 {a, b, c, a-1, b-1, c-1} の文字を並べて作った文字列 abc, bc-1a などの文字列を集めた集合 B を考えると (B, . ) の組はモノイドになる。しかし、これだけでは自由モノイドに逆元を導入できない。任意の文字列に対しその逆元を連結したときに単位元にならなければならないからだ。

そこで、文字列の中に aa-1 のように文字とその逆元が隣接している場合にはこれは '' で置き換える事ができるというルールを導入する。つまり、

baa-1c = bc

である。このような aa-1 を '' で置き換える事を簡約という。次の例のように簡約できる箇所が複数あるときは次々に簡約していく事ができる。

abb-1bc-1cc = abc-1cc = abc

左端の文字列はこれ以上は簡約できないので規約であるという。こういう簡約で最終的に同じ規約の文字列になる文字列の集合をまとめるのは便利だ。これを [abc] のように表記する。 abc はこの同値類の代表元である。この同値類の集合にも連結演算子 . を適用することができる。つまり、

[ab] . [cb] = [abcb]

である。また、空文字 '' の同値類を [] で表す事にするとこれは次のように単位元になる。

[abc] . [] = [] . [abc] = [abc]

さて、逆元だが、任意の文字列の順序を逆にし文字をその逆元と入れ替えたものを . 演算子で結合すると、上に述べた簡約を繰り返すことで、単位元である '' 文字になる。したがって、つぎのように、任意の文字列に逆元を作ることができる。

ac-1ba . a-1b-1ca-1 = ''

したがって、同値類で表現した逆元は次のようになる。

[ab-1c] . [c-1ba-1] = []

このようにして作られた群を文字集合 X 上の自由群といい F(X) と書く。

文字集合から群を作る手順が少々面倒だが、こうして作られた自由群には自由群の普遍性という特徴がある。つまり任意の群 G に対し g : F(X) -> G という準同型写像があるとき、g の X への制限写像について、任意の f : X -> G というXから群Gの台集合 G への関数について、任意の a ∈ X について g(a) = f(a) となるものがただひとつ存在するというものだ。

しかし、Wikipedia にはその証明は記述されていなかった。群論の教科書を読む必要があるらしい。

Wikipedia の随伴関手の記事によると集合の圏をその生成する自由群の圏に対応させる関手 F と群の圏を群の台集合の圏に対応させる関手 G は随伴の例であると書いてあった。以下がその引用だ。

自由群の構成は極めて普通の随伴による構成であり、上記の詳細の分かりやすくて便利な例である。
関手F : Grp ← Setは各集合YにYの要素の生成する自由群を対応させるものとし、関手G : Grp → Setは群Xにその台集合を対応させる忘却関手とする。以下に示すようにFはGの左随伴となる。

これで、自由群を理解すれば圏論の随伴が分かるのが分かった。群論の学習か ... 。

参考リンク

自由群 - Wikipedia
自由群の定義
[PR]
by tnomura9 | 2014-08-24 22:25 | 圏論 | Comments(0)

モノイドと自由モノイド

モノイドの定義を Wikipedia で調べてみた。

集合 S とその上の二項演算 • : S × S → S が与えられたとき、組 (S, • ) が以下の条件を満たすならば、これを モノイド という。

結合律
    S の任意の元 a, b, c に対して、(a • b) • c = a • (b • c)
単位元の存在
    S の元 e が存在して、S の任意の元 a に対して e • a = a • e = a

二項演算の結果 a • b を a と b の積[* 1]と呼ぶ。手短に述べれば、モノイドとは単位元を持つ半群のことである。モノイドに各元の可逆性を課せば、群が得られる。逆に任意の群はモノイドである。

二項演算の記号は省略されることが多く、たとえば先ほどの公理に現れる等式は (ab)c = a(bc), ea = ae = a と書かれる。本項でも明示する理由がない限り二項演算の記号を省略する。

こういうのは実例を見ればすぐ分かる。自然数 {1, 2, 3, ... }と自然数の乗法 * の組みあわせはモノイドだ。自然数の積の値は自然数だし、次のように結合法則をみたす。

(2 * 3) * 4 = 2 * (3 * 4) = 24

また自然数の単位元は 1 だ。なぜなら次の等式が成り立つからだ。

1 * 3 = 3 * 1 = 3

モノイドといっても、自然数の集合とその乗法演算という具体例でみるとなんということはない。ただ、具体例からだけはモノイドという数学的構造が自然数の集合 {1, 2, 3, ... } に与えられているというのは見えない。具体的な計算は目に見えるが、「数学的構造」は目には見えないからだ。しかし、具体例と定義の間を行ったり来たりしているうちに、目に見えない「代数的構造」というものが見えてくる。

自由モノイドというのも乗法の導入された自然数と同じモノイドだ。ウィキペディアから定義を引用すると次のようになる。

逆に、ある固定された文字集合 Σ 上の有限文字列全体(空文字列を含む)は、文字列の連接を二項演算とし単位元を空文字列としてモノイドとなる。このモノイドを Σ∗ で表す[* 2]と、これは Σ を生成系としてもち、公理の等式以外に元の間の関係式をもたないので Σ 上の自由モノイドと呼ぶ。自由モノイド(英語版)はモノイドの圏における自由対象である。

これも具体例で考えると簡単だ。Σ = {a, b, c} とする。a b c は文字を想定しているが引用符は面倒なので省略した。これに文字の連結を行う演算 . を導入すると次のようになる。

a . b = ab, ab . bc = abbc, ...

また、

(a . b) . c = ab . c = abc だし、a . (b . c) = a . bc = abc になるので次のような結合法則が成り立つ。

(a . b) . c = a . (b . c)

さらに文字がなんにもない空文字 '' は次のように単位元になる事が分かる。

a . '' = '' . a = a

つまり自由モノイドは文字列の集合 {'', a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, abc, ... } に文字列の連結という二項演算 . があり、単位元 '' があるというだけのものだ。蓋を開けてみるとなんということはない。この自由モノイド (A, .) が自然数と乗法のモノイド (N, *) と同じ代数的構造をもっていることは、上の実例を見比べてみると分かる。

自由モノイドの「自由」の意味がわからなかったが、二項演算が文字列の連結であるだけなので、2 * 3 = 6 というようなルールがない。文字の並べ替えの規則以外の規則が全くない(意味論がなく、統語論だけで話がすむ)からのようだ。

数学的構造はこのように、定義と実例の両方を知っていないと理解できない。逆に実例をたくさん知っていれば数学の表現はやさしく感じられるのかもしれない。数学の本を理解したければ、こういう実例を昆虫採集のようにたくさん集めるといいのだろう。圏論が難しいのはこの具体例自体が数学的構造だからだ。
[PR]
by tnomura9 | 2014-08-23 19:03 | 圏論 | Comments(0)

アナロジー

知らないことを学習するのに最も大切な技術は何かと考えたが、結局それはアナロジーではないかと思う。わかりにくいことを理解しようとするときに自分がよく知っているものに似ている部分はないかと考えるときに、アナロジーを使うが、用語の厳密な定義は知らなかった。そこで、アナロジーの定義を Kotobank.jp の記事から引用してみた。

アナロジー【analogy】

〈比例〉を意味するギリシア語analogiaに由来する言葉。当初は数学用語だったが,プラトン以後は哲学の分野で用いられ,類推,類比,比論などと訳される。論理学の用語としては〈同義性univocation〉つまり同一の言葉が同一の意味で用いられること(人間,馬,犬などが動物であると言われる場合)と,〈異義性equivocation〉つまりまったく異なった意味で用いられること(ある星座と動物がともに〈犬〉と呼ばれる場合)の中間を意味する。

元々は古代ギリシアの数学用語で比例を表すものだったらしい。哲学的な思考を行うのに便利だったようで、プラトンが転用したらしい。

要するに二つの異なるものの間に共通点を探るというパターン認識の手法だ。しかし、何のどこが似ているのかをはっきりと説明するのは通常難しく、直感に頼ることが多い。しかし、論理的な説明は難しいが直感的には分かっているというのは、脳の神経結合の力学の上では両者の類似点をはっきりと把握しているということでもある。その言葉では説明できないが、共通点があることを確信している状態が、一体どういう力学で脳の中で起こっているのかは興味のあるところだが、あまり良くわかっていないようだ。

直感は多くの場合正しく、有効ですらあるが、それは個人の頭のなかにしか存在せず、他の人と共有することが難しい。直感的な理解を他の人とも共有できるような論理的な表現に変換するという作業が重要な要件だ。

多くの群の間には共通の性質があるというのは直感的な理解だが、それを群の準同型写像という形で論理的な表現に翻訳することで、共通の性質というものを他の人と共有したり、議論したりできるようになる。

頭のなかに存在する直感を、他と共有するための論理的な表現を持たせる技術が重要な所以だ。

アナロジーのどこか似ているという直感は大切だが、これを有効に使うためには、意識的な検討が必要だ。まず、似ていると思ったら、どういうところが似ているのかに焦点を当てる必要がある。全く同じでない限り、似ているところと似ていないところとが必ずあるはずだ。似ているところと、似ていないところをはっきりと区別するように努力すると問題の焦点が見えてくることがある。

また、全く新しいものを見た時に、それに似ているパターンを思いつくためには、多くのパターンのストックがあった方がいい。引き出しは多ければ多いほどいいのだ。スズキ・アルトの設計の時に、フロントガラスを戦闘機の風防の形のような円錐形にしたのは、戦闘機乗りだったスタッフがいて、芸者を戦闘機に乗せるとみんな美人に見えたという体験をとりいれたという話を読んだことがある。思いもかけない事例とのパターンマッチを得るためには、雑学も必要かもしれない。

いずれにせよ、知識を理解したり、新しい発想を得るためのアナロジーの威力を再認識し、意識的に活用する方法を見つける必要があるような気がする。
[PR]
by tnomura9 | 2014-08-22 13:11 | 考えるということ | Comments(0)

二項演算

二項演算をなぜ圏論のカテゴリーの記事にしたかというと、随伴の実例の「右随伴が忘却関手で左随伴が自由モノイドである」ということの意味を知りたくなったからだ。説明の中の分からない用語を逆にたどっていくうちに「二項演算」にたどり着いたというわけだ。

予備知識がほとんどない状態で、知りたい事を知る過程のモデルになると思うので、忘却関手の随伴にたどりつくまで詮索を続けてみたいと思う。しばらく Haskell の記事はお休みにする。

まず、Wikipedia の二項演算の記事の引用からはじめる。

集合 A 上で定義される 2 変数の写像
μ: A × A -> A; (x, y) |-> μ(x, y)
を A 上の二項演算あるいは乗法などと呼び、集合 A を二項演算 μ の台集合 (underlying set) などと呼ぶ。A の 2 元 x, y に対し、順序対 (x, y) の二項演算 μ による像 μ(x, y) を x と y の積あるいは結合などと呼んで、多くの場合に中置記法に則って x μ y のように記す(混乱のおそれの無い場合には、しばしば xy と略記する)。また、A × A 上の写像 g が A 上の二項演算を与えるとき、A は二項演算 g について閉じているという。

数学の定義は考えられるどんな場合にも当てはまるような(抽象的な)書き方をしているので分かりにくい。判例のない法律の条文のようなものだ。法律の条文の意味は、その条文がどのような判例に適用されているかを知らないとさっぱり分からない。しかし、具体的な訴訟の判例にどのようにその条文が使われているのかがわかると途端にその意味が理解できるようになる。

したがって、数学の定義を見たらまずその用語が指し示す具体例を考える事が必要だ。上の定義の場合集合 A の具体例を考えるのがきっかけになる。そこで、集合 A の実例として次のような自然数の集合を考える。

A = {1, 2, 3, ... }

A × A は集合 A と集合 A の直積だから、集合 A の要素と集合 A の要素の組(順序対)の集合だ。つまり、

A × A = {(1,1), (1,2), (2,2),(2,1),(1,3),(2,3),(3,3),(3,2),(3,1), ... }

である。

二項演算 μ はこの A × A という集合から、集合 A への写像と考える。写像というのは A × A の要素を1つとり、それを A の要素の1つに対応させるという操作だ。たとえば (2, 3) -> 5 のようなものだ。このような対応付けが一般には A × A の全ての要素について行われる。それが、

μ : A × A -> A

の意味だ。1 足す 2 は 3 というのと随分感じが違うが、こういう見方をすることで、加算や乗算以外にいろいろな2項演算を共通の視点から自由に考えることができるようになる。

(x, y) |-> μ (x, y)

とは、A × A の任意の要素 (x, y) について、A の要素 μ (x, y) を対応させることを意味している。二項演算 μ の機能は、加算や乗算のみならず任意のものがとれる。例えば {1,2,3, ... } という数列を見出しの縦横に並べた演算表を作って、その枡を適当な自然数で埋めても良い。2項演算についての視点を変えることで、加減乗除にとらわれない様々な演算を考えることができるようになる。

2項演算 μ の始域の要素は順序対 (x, y) であることに注意する必要がある。2項演算 μ の値は引数の順序に依存する。自然数の乗算では x * y = y * x だが、一般的には x * y /= y * x のことのも多い。

このような2項演算のもとになる集合 A は台集合 (underlying set) と呼ばれる。上の例では A = {1,2,3, ... } が台集合だ。

話が抽象的になってきたので自然数の乗算を * で表すことにする。すると、

* : A × A -> A; (x, y) |-> x * y

である。具体的には例えば * (2,3) = 6, * (3,5) = 15, などになる。* は定義からは2変数関数 * (x, y) だが、演算子を引数の間において、x * y と中記法で記述することもある。この場合、2 * 3 = 6, 3 * 5 = 15 など小学校で習った計算式になる。また、x * y は混乱がなければ * を省略して xy のように表すこともある。中学校の代数でならった、3xy + 4xz = x(3y +4z) である。

自然数の乗算では二項演算の値は必ず自然数になる。たとえば、2 * 3 = 6 で値の 6 は自然数である。このように2項演算の値、すなわち写像 g (x, y) の値が全て台集合の要素になる時、集合 A は演算子 g について閉じているという。

台集合 A = {1,2,3, ... } は単なる集合だが、2項演算 μ を導入することで、集合の要素の間に関係性が生まれ、A は代数的構造をもった集合になる。

例えば自然数の乗算 * の場合、代数的構造の第1は、2項演算を複数回行った時、その順序によらず結果が同じだということだ。つまり、つぎのような結合法則が成立するということ。

(a * b) * c = a * (b * c)

第2は、単位元が存在するということだ。つまり、集合 A = {1,2,3, ... } のどんな要素 x に対しても

1 * x = x, x * 1 = x

だ。2項演算についてこのような性質のある要素を「単位元」という。

台集合が二項演算について閉じており、結合法則を満たし単位元を持つような代数的構造は「モノイド」という。自然数の集合 A = {1,2,3, ... } と乗算 * の組みはモノイドである。

自然数の乗法で 2 * 3 = 6 について自然数の集合である対象 A を始対象とし * 3 という射があり、同じ集合 A を終対象としているとみなすと。集合 A と 二項演算の第2引数に代表される射 からなるモノイドは、ただひとつの対象 A からなる圏と考えることができる。このときモノイドと他のモノイドの間の準同型は単一対象圏のあいだの関手とみなされる。

このように、数学を学ぶのはおもちゃで遊ぶのと似ている。自然数の値の書かれた駒をならべたり、対にしたり、糸で他の駒と結んだりなど、おもちゃをもてあそぶ感じで頭のなかでイメージを操作しているうちに、抽象的な記述の意味がわかってくる。子供に数学を教えるときには、このようなおもちゃを沢山用意して、手で色々と操作させてその法則性を見出させるのが有効かもしれない。
[PR]
by tnomura9 | 2014-08-21 01:34 | 圏論 | Comments(0)

System.Console.GetOpt の実験

久しぶりに Haskell をいじってみたくなったので、System.Console.GetOpt で遊んでみた。

GetOpt はコマンドライン引数のオプションをパースするライブラリだ。このブログでも扱った事があるが、サンプルプログラムでざっと使い方を見ただけなので、今回ゆっくり実験してみる事にした。というか、これが理解できていないと Cabal の解読が進まない。

まず、環境の準備。

Prelude> :set +m
Prelude> import System.Console.GetOpt
Prelude System.Console.GetOpt>

パースの結果は Flag 型に反映させるので、data で Flag 型を宣言する。コマンドラインオプションの使い方の理解に集中したいので Flag 型のコンストラクタは Foo だけにする。

Prelude System.Console.GetOpt> data Flag = Foo deriving Show

久しぶりの Haskell をつかったプログラミングだ。なんかうれしい。

コマンドラインオプションのパースのルールをまとめたリストを作成する必要があるが、それを options という名前で作成する。これも、分かりやすいようにルールのアイテムは1個だけにする。ルールのアイテムは OptDescr a 型のデータだ。

Prelude System.Console.GetOpt> let
Prelude System.Console.GetOpt| options :: [OptDescr Flag]
Prelude System.Console.GetOpt| options = [Option ['f'] ["foo"] (NoArg Foo) "the only one option 'foo'" ]
Prelude System.Console.GetOpt|

["--foo"] のようなオプションのリストをパースする関数は getOpt だ。getOpt の Permute はパースを全てのオプションについて行うスイッチだ。パースの方法を指定するスイッチはそのほかに、非オプションの文字列が出現した時点でパースを中止するものなどを含め全部で3種類ある。getOpt の第2の引数はパースのルールである [Optdescr Flag] 型のリストで。最後の引数が、コマンドラインオプションのリストだ。コマンドラインからコマンドラインオプションの文字列を取得するには System.Environment モジュールの getArgs を使うが、ここでは省略する。

Prelude System.Console.GetOpt> getOpt Permute options ["--foo"]
([Foo],[],[])

コマンドラインに非オプション文字列が存在するときは、GetOpt の値の3つ組の2番目のリストに納められる。

Prelude System.Console.GetOpt> getOpt Permute options ["--foo", "bar"]
([Foo],["bar"],[])

コマンドラインオプションのルール options に登録されていないオプションがオプションリストに現れたときは、3つ組の最後のリストにエラーメッセージ付きで納められる。

Prelude System.Console.GetOpt> getOpt Permute options ["--foo", "bar", "--baz"]
([Foo],["bar"],["unrecognized option `--baz'\n"])

パースの方式を指定するスイッチが Permute になっているときは、オプションの順序は問わない。

Prelude System.Console.GetOpt> getOpt Permute options ["bar", "--baz", "--foo"]
([Foo],["bar"],["unrecognized option `--baz'\n"])

これが getOpt 関数を使うときの基本的な操作になる。あとは Flag の種類を増やしたり、オプションのパラメータを扱えるようにしたりして、実際の用途に合わせていく。

やっぱり、Haskell のプログラミングは楽しい。

追記

System.Environment の getArgs の動作確認もしてみた。

Prelude System.Environment> let main = getArgs
Prelude System.Environment|
Prelude System.Environment> :main --foo bar --baz
["--foo","bar","--baz"]

コマンドライン引数のスペース区切りの文字列が字句解析されて、文字列のリストになる。-- や - などのオプションをあらわすハイフンもそのまま取り込まれる。したがって、getOpt にこのまま引数として渡す事ができる。
[PR]
by tnomura9 | 2014-08-13 18:31 | Haskell | Comments(0)