カテゴリ:圏論( 51 )

モナドにおける自然変換 μ の意味

以下の議論は参考書に書かれていたわけではないので正しいとは限らない。しかし、こういう考え方をすれば、モナドの自然変換 μ の意義が分かりやすいのではないかと思ったので記事にしてみた。内容についての保証は全くないのであらかじめ断っておく。

モナドが圏 C の自己関手 T であることがわかったが、モナドに付随するつぎのような自然変換はどのような意味を持っているのだろうか。

μ : T2 -.-> T, η : IC -.-> T

まず、T は自己関手なので圏 C の対象 c, c' は同じ圏 C の対象 Tc, Tc' に写像される。また、圏 C の射 f, g はやはり圏 C の Tf, Tg に写像される。したがって、このままなら h . Tf などのように自己関手で写像される前の射とも合成することができる。しかし、これは避けたい。自己関手 T で写像した射については、写像する前の射との合成を避けたい。自己関手などという手間をかけたのだから、モナドの世界にこれらの射を隔離しておきたい。

圏 C の射 f, g があるとき、その合成 g . f は関手 T によって T (g . f) に写像される。このとき、関手では射の合成は保存されるので

T (g . f) = T g . T f

となる。この場合は関手 T による g の像と f の像が普通の関数合成になっているが、関手 T による射の像の合成が普通の関数合成でなくても構わない。要するに

T (g. f) = T g * T f

のように演算が保たれていればいいのだ。

そこで T g . T f にもう一度関手 T を関数適用してみる。つまり、

T ( T g . T f)

だ。これは 次のように値が TTh -> TTh 型の射になる。

T (T g . T f) : T f -> T g -> TTh

さらに、この射に自然変換 μ : T2 -.-> T を適用すると、

μ T (T g . Tf) : T f -> T g -> Th

になる。これを改めて * という演算子として定義すると、

* : T f -> T g -> Th

となる。これは普通の関数合成とは違うが、つぎのように演算が保存されており、自己関数 T の射の合成として採用することができる。

T (g . f) = μT (T g . T f) = μ(TT g * TT f) = μTT g * μTT f = T g * T f

しかし g * T f の場合は g * T f = μTf * μTT f となって型不適合となって計算できない。自己関手の圏のモノイド対象である T を使うことによって、めでたくモナドの中に射をカプセル化することができる。

Haskell のモナドは圏のモナドを直接使うのではなく、モナド T についての Kleisli 圏について同様の工夫をしているようだ。おそらく、その方がプログラムするのに便利なのだろう。

要するに言いたかったのは Haskell のモナドというものは単なる自己関手あるいはデータコンストラクタ T であって、射の合成である >>= を工夫することによって射をモナドの中に閉じ込めるようにしたという単純な仕組みでしかないということだ。自然変換 μ の役割はこのような射の合成を定義するのに発揮されている。
[PR]
by tnomura9 | 2014-11-03 23:42 | 圏論 | Comments(0)

モナドと自然変換の水平合成

圏論のモナドは「単なる自己関手の圏のモノイド対象」だ。

これは、この文の要素を分解していくと理解できる。「自己関手」とは圏 C から圏 C への関手だ。自己関手 T : C -> C は C の対象 c を同じ圏 C の対象 c' に写像する。また、圏 C の射 f を同じ圏 C の射 f' に写像する。

次は、「自己関手の圏」だ。圏 C のこのような自己関手 T : C -> C を対象とし、自己関手 T の自然変換 η : T -.-> T' を考えると、自然変換の垂直合成は結合則を満たすので、自己関手の圏 A を考えることができる。

最後に「モノイド対象」だが、この対象は自己関手の圏 A の一つの対象 T のことだ。つまりモナドとは自己関手 T のことにほかならない。問題はこれが「モノイド」であるということがどういうことかということだ。

一般に圏の対象のうちでモノイドであるもの、すなわち、「モノイド対象」は次の可換図式を満たす対象のことだ。

M×M×M --( 1×μ)--> M×M
|                                |
(μ×1)                        (μ)
|                                |
v                                v
M×M ------(μ)-------> M

1×M -(η×1)-> M×M <-(1×η)- M×1
|                      |                    |
(λ)                   (μ)                 (ρ)
|                      |                    |
v                      v                   v
M        =           M         =        M

したがって、自己関手の圏 A の対象 T について上のような可換図式を作ることができれば T は「モノイド対象」であるということができる。すなわち T は「モナド」である。

実際、圏 C のモナドとは、圏 C の自己関手 (圏C から 圏 C への写像) T と次の2つの自然変換

η:IX -.-> T, μ:T2 -.-> T

からなり、次の図式を可換にするものだ。

T3 ----(Tμ)----> T2
|                       |
(μT)                (μ)
|                       |
v                       v
T2 -----(μ)----> T

IT ---(ηT)---> T2 <---(Tη)--- TI
|                    |                   |
|                   (μ)                 |
|                    |                   |
v                    v                  v
T        =         T         =        T

これを上のモノイドの可換図式と比べると対象の積 M×M が関手の合成 T2 に置き換えられ、射の積 1×μ が自然変換の水平合成 Tμ に置き換えられているが、全く同じ形の可換図式を持っていることが分かる。この意味でこの自己関手 T は自己関手の圏の「モノイド対象」なのだ。

圏のモノイドを数学的に理解するための最後の関門は「自然変換の水平合成」の理解だ。上の可換図式の IT や T2 (= TT) は関手の合成を意味しているし、μ や η は自然変換だ。しかし、μT や Tμ は一体何を意味しているのだろうか。

実はこれは自然変換 μ と自然変換 T の水平合成なのだ。ここで、T は大文字だが自己関手 T ではなく、

T : T -.-> T

という自然変換を意味している。つまり、関手 T を同じ関手 T へ変換する自然変換のことだ。したがってμTは自然変換と自然変換の水平合成だ。

自然変換の水平合成について述べる前に、先に自然変換の垂直合成について述べておく。水平合成より理解しやすいからだ。いま圏 C から圏 B への3つの関手 S, T, U があるとする。そうしてそれぞれの間の自然変換を σ : S -.-> T, τ : T -.-> U とすると、σ と τ のコンポーネントは 圏 B の射だから、射の合成を作ることができる。それらのコンポーネントの合成射の組みはやはり自然変換をつくり、これを τ . σ と表記すると、これは関手 T から関手 U への自然変換になる。つまり、

τ . σ : T -.-> U

である。このように自然変換の垂直合成は、同じ圏 B の自然変換となる。

自然変換にはもうひとつの合成が考えられる。これが本題の自然変換の水平合成だ。いま、C, B, A という3つの圏があり、それらの間に次の4つの関手 S, S', T, T' があるとする。すなわち、

S : C -> B, S' : B -> A
T : C -> B, T' : B -> A

このとき関手の合成 S'S : C -> A, T'T : C -> A を自然に考えることができる。ここで、圏 B について自然変換 τ : S -> T があり、圏 A について自然変換 τ’ : S' -> T' があるとき、自然変換 τ と τ' の水平合成、

τ'τ : S'S -.-> T'T

を定義することができる。これについての論証に関する考察は以前の記事に述べたので省略するが、単純に τ と τ’が順番に S と S' に作用して S が τ によって T に、S' が τ' によって T' に変換されると考えても実用的には十分だ。

そう考えると上の可換図式の自然変換の水平合成の部分は、その作用が合成関手の右側の関手から順に自然変換が適用されて、像となる自然変換になるとイメージしても差し支えない。

これで圏論のモナドというものを数学的に理解できたことになる。もちろん関手が何かとか、自然変換の仕組みがどのようなものであるかとか、自然変換の水平合成がどのように定義できるのかということは、各自が参考書と格闘する必要があるだろう。しかし、これで、謎の「IO モナド」のモナドが何かということは理解できる。それは単に一個の自己関手だったのだ。Haskell でいえばモナドとは単にデータコンストラクタ T のことだ。

Prelude> data T a = T a deriving Show
Prelude> T "hello"
T "hello"
Prelude> let mu (T(T x)) = T x
Prelude> mu (T(T "hello"))
T "hello"
Prelude> let eta x = T x
Prelude> eta "hello"
T "hello"
Prelude> mu (T (eta "hello"))
T "hello"

「モナドとは単なる自己関手の圏のモノイド対象だが、なにか問題でも?」という謎の言葉を追いかけていった結果、モナドとはやはり「単なる自己関手の圏のモノイド対象」だった。つまりパラメータが1個だけのデータコンストラクタ T だったというのがオチだ。

モナドとは何かがわかったからといって IO モナドのプログラムの書き方が分かるわけではないが、IOプログラムの書き方についてはこのブログの過去記事

IO モナドとの付き合い方(1)

を参照していただくと良いと思う。この記事はまだ圏論のことがよくわからない時に操作的な類推で書いた記事だ。今から見ると >>= 演算子は Kleisli 圏の射の合成であるのだが、操作的にはこの一連の記事で問題ないと思うし、ここに書いた3つのルールで IO モナドのプログラムは完全に使いこなすことができる。手前味噌だがおすすめだ。
[PR]
by tnomura9 | 2014-11-02 11:10 | 圏論 | Comments(0)

モノイド対象

Wikipedia によると
モノイドとはひとつの二項演算と単位元をもつ代数的構造
である。ざっくりと言うと、集合 M に二項演算と単位元が定義されている場合、集合 M はモノイドになる。たとえば、自然数の集合 {1, 2, 3, ... } には積という二項演算があり、(2 * 3) * 4 = 2 * (3 * 4) のように結合性がある。また 1 * n = n = n * 1 なので、1という単位元をもっている。したがって自然数の集合は積という二項演算についてモノイドになる。

少し正確にモノイドを定義すると次のようになる。
集合 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 と書かれる。本項でも明示する理由がない限り二項演算の記号を省略する。

上の定義は集合を使って定義したので定義に集合の要素が使われている。圏論の external の立場では集合の中の要素を意識的に言及せず、射の関係で対象の構造を表す。圏論で、モノイドを定義すると次のようになる(マックレーンの『圏論の基礎』の P. 3 を引用)。
モノイド (monoid) (恒等元を持つ半群) の概念は圏論において中心的な役割を果たす。モノイド M は、集合 M に二つの関数μ : M × M -> M, η : 1 -> M が付随していて μ と η を使って書かれた次の二つの図式

                   1 × μ
M × M × M ----------> M × M
  |                                |
  | μ × 1                       | μ
  |                                |
  v               μ               v
M × M -----------------> M 

          η × 1                1 × η
1 × M ------> M × M <------ M × 1
  | λ                 | μ               | ρ
  |                   |                  |
  v                   v                  v 
  M ========= M ========= M

を可換にするようなものとして記述することができる。ここで 1 × μ の 1 は恒等関数 M -> M であり、1 × M の 1 は一点集合 1 = {0} である。一方 λ と ρは λ<0, x> = x, ρ = x で与えられる全単射 λ : 1 × X -> X, ρ: X × 1 -> X である。これらの図式が可換であるということは、次の合成が等しいということを意味する。

μ◦ (1 × μ) = μ ◦ (μ × 1), μ ◦ (η × 1) = λ, μ ◦ (1 × η) = ρ
集合 M の要素には言及せず、射の関係のみでモノイドを定義するとこのような図式 (diagram) になる。

上の図式で M × M は集合 M と M の直積集合である。つまり、集合 M の要素 x と y の対 の集合である。従って 1 × M は集合 {0} と M の直積集合つまり 0 と M の要素 x の対 <0,x> の集合だ。このようなものも圏論では集合 M の要素に言及する事なく射と射の関係で定義できる事は、このブログの過去記事「対象の積」でも紹介した。

また、1 × μ は射の積だ。1は M の恒等写像で 1 : M -> M だ。また、μ は M と M の直積集合 M × M から M への写像だから、μ : M × M -> M である。射 1 と 射 μの積は 1 と μ のペア <1, μ> で M と (M × M) の直積 M × (M × M) から M × M への射になる。すなわち 1 × μ : M × (M × M) -> M × M である。射の積の作り方の詳細はこの記事では述べないが、参考書やこのブログの過去記事を参照してほしい。

要するに圏論のモナドは集合の圏 Set の対象である集合で、Set の中で上の射の図式を満たすものであるということだ。したがって、M は Set の「モノイド対象」である。

M の要素で定義すれば簡単に定義できるものを、射のみで定義する圏論によるモノイドの定義はこのように非常に複雑になる。しかし、モノイドの定義を射のみで定義する利点は、上の図式を満たせば、対象 M が集合ではなくて、M の要素のようなものが考えられない場合でも圏論的なモノイドとして扱う事ができるという事だ。

たとえば圏 C の自己関手を対象とし、自己関手と自己関手の自然変換を射とする圏を考える。この圏の自己関手のひとつ T をとり、T の合成 T2 を T の直積に置き換え、 次の二つの自然変換 η: Ix ----> T, μ : T2 ----> Tを考えると図式は省略するが上で述べたモノイドと同じ図式を作る事ができる。したがって、自己関手 T は自己関手の圏における「モノイド対象」である。対象である自己関手 T には集合 M にみられるような集合の要素はないが、external の立場からは図式を満たしているのでこれもまたモノイド対象である。

Haskeller を悩ます IO モナドのモナドの正体は、Haskell のプログラムという圏の自己関手の圏の対象の一つである自己関手 IO というモノイド対象だったのだ。これが分かったと言っても IO モナドの使い方には直接には結びつかないが、「モナドとは一体何なのだ?」という疑問には答えることができる。

これが Haskell で有名な「モナドとは単なる自己関手の圏のモノイド対象だけど、何か問題でも?」というフィリップ・ワドラーの謎の言葉の意味だ。

追記

圏のモノイド対象については、このブログの過去記事「圏のモノイド対象」があるが、理解が足りないところがあったので書き直した。参照していただければ幸いだ。

追記2

「モノイドは対象が一つだけの圏である」という文章を見ることがあるが、これはモノイドを集合の圏の対象としてみるのではなく、モノイドを対象を一つだけしか含まない圏として考えて定義をする場合のことだ。この場合 M × M は対象の積ではなく圏 M と 圏 M の積として考え、μ や η は関手と考える。しかし、モナドを理解するためにはこの観点は必要ないようなので深入りはしないことにする。
[PR]
by tnomura9 | 2014-10-13 11:40 | 圏論 | Comments(0)

圏の作り方

圏を作るにはまず対象と射を決める。集合の圏 Set の場合対象は集合で射は集合 A から集合 B への写像 f だ。これを f : A -> B で表記する。A と B は集合で f は写像だが、これらを対象と射として扱うときには、その内部構造は隠蔽されてしまう。つまり、A や B の個々の要素を見ることはできないし、f はAのどの要素がBのどの要素に対応させるのかなどの、AやBや f の内部構造は見えなくなる。

f には domain (始域) と codomain (終域) がある。f : A -> B の場合 domain は対象 A で codomain は対象 B だ。domain A の全ての要素には f の値であるBの要素が対応している必要がある。これは f : A -> B, g : B -> C のとき、どんな f と g に対しても f と g の合成 g . f が存在しなければならないからだ。codomain の対象 B については f は全射でも単射でもある必要はない。つまり、対象 B の要素のなかに射 f の像でないものがあってもいいし、対象 B の同じ要素に対象 A の異なる要素が f によって対応していてもいい。f : A -> B のとき A = dom f, B = cod f と表記する。

射には合成を定義する。射 f と射 g について cod f = dom g のとき、すなわち f: A -> B, g: B -> C のときf と g の合成を定義する。集合の圏 Set の場合、射 f と 射 g の合成写像 f . g を射 f と射 g の合成射と考える。このとき写像の性質から、f : A -> B, g : B -> C, k : C -> D について、

k . (g . f) = (k . g) . f

という結合法則が成りたつ。

圏の場合全ての対象には恒等射という特別な射が定義される。集合の圏 Set の場合対象 A の恒等射は対象 A の各要素にその要素自身を対応させる恒等写像である。このとき、恒等射 1A : A -> A について、つぎのような単位元律が成立する。つまり f : E -> A, g : A -> B について、

f = 1A . f かつ g = g . 1A

である。1A が A の恒等写像として定義されている時上の等式が成り立つのは容易に分かる。

このように、集合を対象とし、集合から集合への写像を射とし、合成写像と恒等射をもち、射の合成について結合法則と単位元律を持つ圏 Set を作ることができた。圏を作るためのこれらの条件が揃えば、どのような数学的対象からも圏創りだして圏というものとしてひとくくりに論じることができるようになる。

たとえば、1個の集合 A も離散圏というタイプの圏である。このとき離散圏の対象は集合 A の要素であり、射は各要素への恒等写像 1a : a |-> a である。したがって、dom f = cod g となるような一組の射 f と g は対象自身への射以外は存在しないので異なる対象にわたる合成射は存在しない、しかし、各対象 a について合成射 1a . 1a は存在し、合成射の結合法則と単位元律をみたしているので、この離散圏もまた圏の条件を満たしている。

こうして、圏をつくることで、様々な数学的対象を圏というコンテナにパッケージして、それらの構造の共通点を調べることができるようになる。
[PR]
by tnomura9 | 2014-10-09 08:09 | 圏論 | Comments(0)

圏論とは何か

圏論について少し分かり始めてきたら、自分の過去記事の内容が気に入らなくなってきた。そこで、手を入れていたら操作ミスでひとつは記事が消失し、ひとつは記事の日付が変わってしまった。ブログの性質上過去記事に手をいれるのはやめた方がいいかもしれない。

圏とは何か

そこで、何となく分かり始めてきた圏論の意味をまとめてみる事にする。まず、圏論とは何かと一言で言うと、それは演算を持った有向グラフの性質を調べる学問という事だ。有向グラフというのは、対象とその対象の間の関係性を示す射という2つの要素から構成されるネットワークの固まりのことだ。そういうと、画面の上に丸が散らばっていてそれらがたくさんの一方向の矢印でつなげられている所を想像するかもしれないが、まさに、その通りのものだ。

対象と対象の間に張られる矢印は、ひとつだけでなくても良い。集合と集合の間の写像が幾とおりも考えられるように、同じ対象の対の間の射は複数存在する事ができるし、逆方向の射も考える事ができる。また、対象と対象の間には射が張られている場合もあるし、何の射も張られていないものがあるという状態が混在してもいい。

圏論で扱う有向グラフの便利なところは、この対象と射のネットワークの中に様々な数学的構造物を入れ込むことができるということだ。例えば、集合を対象とし集合と集合の間の写像を射とする集合の対象と写像の射のネットワークからなる有向グラフを考える事ができる。また、データタイプを対象とし関数を射とする、Haskell のプログラムも有向グラフになる。

圏とは、このような有向グラフに恒等射と射の合成という射の演算が定義されているものをいう。有向グラフだけでは自由すぎて数学的構造の記述をするには力不足だが、有向グラフに恒等射と射の合成が導入される事によって、いままで、集合などを使って記述されていた数学的構造の細部の性質について、かなり細かい所まで圏論の言葉で記述する事ができるようになる。また、圏論が語っているのはこのような演算のある有向グラフ(圏)の性質なので、圏の中に閉じ込められたどのような数学的構造の性質も共通に圏論の言葉で論じる事ができる。

上に述べた圏の演算は射の合成についての結合性と単位元律という2つの公理を満たす必要がある。結合性とは、f : a -> b, g : b -> c, h : c ->d という射があったとき次の射の合成に関する等式が常に成り立つ事である。

h ◦ (g ◦ f) = (h ◦ g) ◦ f

また、単位元律とは射 f : a -> b, g : b -> c があるとき、恒等射 1b との合成についてどんな f と g についても次の等式が成り立つことである。

1b ◦ f = f かつ g ◦ 1b = g

圏とはこのように、対象と射からなるネットワークで、恒等射と射の合成という演算を持ち、それらが結合性と単位元律という2つの公理を満たすものである。圏を定義する構造の制約が少ないので、様々な数学的構造物を圏という枠組みの中に納める事ができる。したがって、一見あまり関係のなさそうな数学的構造物どうしも圏論の中で統一的に論じる事ができる。

external の立場

このように圏論では数学的構造物を圏の対象と射の中に埋め込む事ができるが、さらに、埋め込まれた数学的対象の詳細は圏論の議論では完全に隠蔽されてしまう。例えば集合の圏では対象は集合で、射は写像だが、対象である集合の要素を取り出す方法は基本的にはない。例えば集合の恒等射像のように要素が特定できないと定義すらできないように見えるものも、任意の f : a -> b と g : b -> c について、

1b ◦ f = f かつ g ◦ 1b = g

となるような射 1b として定義される。ここには要素という概念は一切使われないが、それゆえに対象が集合でない場合でも恒等射を定義する事ができる。このように対象の内部構造に言及しない立場を external な立場であるという。

内部の詳細が見えないのは対象だけではない。射もその内部構造を窺うことができない。上の恒等射の定義を見れば分かるように、射の定義も他の射との関係性で定義されるので、その定義からは恒等射が集合の要素をそれ自身に対応させる写像だという見方をすることはできない。射の特性はその内部の計算ではなく、他の射との関係だけで定義されるからだ。対象だけでなく射もその内部構造が隠蔽されてしまうのだ。

このように数学的対象の詳細を圏の対象と射に隠蔽してしまう事によって、圏論ではその数学的対象の詳細に影響されずに圏となった数学的対象の構造に焦点を当てて論じる事ができるようになる。つまりその数学的構造の詳細は捨象され、その構造のみが圏というネットワークに抽象される。

可換

上に述べたように、数学的対象は圏として抽象化されることによって、その詳細は完全に隠蔽されるが、それだけでは単に詳細の隠蔽を行っただけだ。集合の写像の全射や単射のような写像の性質についての表現性がなければ単なる意味のない抽象化になってしまう。

そこで、集合に見られるような表現力を実現するために、圏論では可換 (commutative) という概念を用いる。

可換とは、出発点の対象 (domain) と終点の対象 (codomain) が同じで、経路の異なる2つの合成射が同じ射であるということだ。例えば f : a -> b, g : b -> c, k : a -> c という3つの射があるとき、a -> b -> c という経路の合成射 g ◦ f が a -> c の射 k と全く同じ振る舞いをするときにこの2つは「可換である」と言う事にする。つまり、

g ◦ f = k

だ。2つの射や合成射が可換であるということは、単に始点と終点の対象が同じという事だけでは不十分だ。その2つの射の振る舞いが全く一致しなくてはならない。つまり集合の圏を例にとると、2つの合成射について、始点である定義域が全く一致し、終点の集合への定義域の集合の要素の像が全く一致しなくてはならない。可換の条件はかなり厳しい。

この「可換」の概念が圏論にあることによって、圏は集合と同じような表現力を持つ事ができるようになる。たとえば集合の写像の単射に相当するエピ射はつぎのように定義される。
射 h : a -> b がエピ (epi) であるとは、任意の2つの射 g1, g2 : b -> c について等式 g1 ◦ h = g2 ◦ h から g1 = g2 が従うことである。
このように演算の定義された有向グラフである圏に「可換」の概念をとりいれることで、圏は集合と写像の場合と同じような豊かな表現力を獲得することになる。

圏論の目的は数学的対象の詳細を捨象して、圏として抽象化する事によって様々な数学的対象の構造の共通点に光をあてることである。このとき、圏の表現力は射の「可換」という概念によって集合と写像の場合に匹敵するものになる。

プログラマの立場からは数学的対象とはあまり縁がない。しかし、Haskell のプログラムが圏であること、圏がオプジェクと指向プログラムにも見られるプログラムの詳細の隠蔽であることを考えると、圏論の考え方がプログラミングにも導入できるのではないかと思える。実際 IO モナドなどは圏論のモナドの考え方を導入している。プログラミングをするのに圏論を知らないといけないと考えるとちょっと引いてしまうが、プログラマの立場から圏論を見ることができるようになれば、圏論という視点からプログラムを設計することができるようになるかもしれない。
[PR]
by tnomura9 | 2014-10-02 00:50 | 圏論 | Comments(0)

圏論は面白い(3) メタ圏

モナドへの近道・Haskell からの寄道』へ戻ろう。『基礎知識の準備』セクションの定義2はメタ圏の定義だ。メタ圏とは、
メタ圏 (metacategory) は演算が定義されたメタグラフである.
ということだ。前回の記事で述べたメタグラフに演算が持ち込まれたものだ。

したがって、メタ圏はメタグラフの性質を全部持ち、つまり、対象や射や dom や cod や ソースやターゲットなどの性質をすべて持ち、さらにそれに演算という新しい性質を持つことになる。

それでは、「演算」とは何だろうか。Wikipediaでは、
n 項算法(エヌこうさんぽう)とは、最も広義には、集合 A の直積集合 An の部分集合 D から A への写像 f のことをいい、D をこの算法の定義域という。
という定義になっている。

つまり、Aという集合の要素のタブル(a1, a2, ... , an) から同じ集合Aの要素 ah への写像を n 項演算という。ただし、後でみるように圏論では二項演算だけを考えるといいようだ。つまり、集合Aの要素のペア (a1, a2) から集合 A の要素 a3 への写像 (a1, a2) -> a3 を考えるといいということだ。集合Aの要素のペアから集合Aの要素への写像は (a1, a2) -> a3 だけではないから、演算 op はそれらが集まったものである。op の型を Haskell 風に記述すると、op :: A a => (a, a) -> a となる。

それではメタ圏の演算とはどんなものだろうか。上の定義を見るかぎりは、演算の引き数のタプルの要素と演算によって写像される像は同じ集合の要素だった。しかし、メタグラフは対象と射という性格の異なるものから構成されているので同じ集合の要素として扱うわけにはいかない。

実際、メタグラフにおける演算には次のように、対象に定義される恒等射と、射と射の合成という2種類の演算がある。
各対象には演算 id が定義されており,これは対象 a を受け取りその対象をソースとし,かつターゲットとするような恒等射 (identity arrow)ida = 1a を返す関数である.射と射の間には合成演算 ◦ が定義されており,射の対⟨f, g⟩ に対して合成 f ◦ g は dom(f ◦ g) = domf, cod(f ◦ g) = codg を満たす.

また、メタ圏の演算が満たすべき条件として次の2つが上げてある。
結合律 (associative low) 次のような任意の 3 つの射 a --(f)--> b --(g)--> c --(k)--> d が与えられたとき,次の等式が常に成り立つ
k ◦ (g ◦ f) = (k ◦ g) ◦ f.
単位元律 (unit low) 任意の射 a --(f)--> b と b --(g)--> c について恒等射 1b との合成は次を与える
1b ◦ f = f かつ, g ◦ 1b = g.

ここで、注意しておかなければいけないのは、射の演算のイメージだ。射というと集合の写像を思い浮かべるので射の合成を写像の合成として捉えがちだが、射の演算は必ずしも写像の合成である必要はない。たとえば f : a -> [a] という射と g: b -> [2b] という射の演算 op を op f g -> (c -> [f(c) + g(c)]) で定義しよう。この op は関数の合成を使って定義したものではないが、射の演算になっている。 射の合成がかならずしも写像の合成にならなくてもいいという発想はKleisli 圏を理解するのに重要になる。

ghci で関数の合成にならない射の演算を定義してみた。

Prelude> let f x = [x]
Prelude> let g x = [2 * x]
Prelude> let h x = [x^2]
Prelude> let op f g x = [head $ f x + head $ g x]
Prelude> (g `op` h) 3
[15]
Prelude> (f `op` g) 3
[9]
Prelude> (f `op` h) 3
[12]
[PR]
by tnomura9 | 2014-10-01 22:48 | 圏論 | Comments(0)

自由群と随伴関手

やっと、自由群が随伴関手の例であることを確認できる所まで来た。まず 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)