bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

デカルト閉圏(理論)

錦織圭が世界の4強に肉薄するような強さを発揮してくれているためだと思うが、テニスの実況中継が格段と増えた。このため、居ながらにして、一流の選手たちが見せてくれる華麗なプレーを楽しむことができる。

この数か月、南ヨーロッパでの戦いが続いている。いずれも、球足の遅いクレーコートで行われている。ストロークが長く続き、一流選手だけが持つ、優雅と言えるほどに洗練されたプレイを楽しむことができる。特に、ジョコビッチがコートの端から端まで駆け抜けて、最後に強烈なショットを打ち込んだ時の、彼の姿勢はとても美しい。長い足を巧みに使って、ベースラインと平行に、脛を地面と直角に、腿を地面と平行に折り曲げた軸足の姿は、神のなせる業のようにさえ思える。

随分と前のことになるが、ジミー・コナーズ(米国)とビョルン・ボルグ(スウェーデン)の試合は、いつも、長いストローク合戦になった。見ている方にも、次にどこへ、どのようなボールを打ったらよいのかを考えさせてくれる機会を与えてくれた。コナーズはフラットで打つため球速は早いのだがネットすれすれにボールが通過していく。このため、見ている方もひやひやとする。これに対して、ボルグはドライブで打つため、ネットのかなり高い地点を越えてゆく。このため、とても安定感がある。どちらを応援するかは、プレイングスタイルの好みによるのだろうが、危険を冒してでも挑戦していくコナーズのほうが好きだった。

この後、ジョン・マッケンロー(米国)が出てきて、サーブアンドボレーの時代へと変わり、ゲームは淡白化し、見る楽しみが消えてきたが、錦織圭が活躍していることもあって、この1,2年、またテニスが面白くなってきた。

最近の人工知能の研究がどのようになっているかを調べているときに、Yoky Matsuoka(松岡陽子)さんという方が活躍していることを知った。彼女は、バークレイを卒業した後、MITで、ロボット工学で有名なブルックス教授(彼はオーストラリアのアデレードの出身なので、サバティカルアデレード大学に滞在しているときに何度かお目にかかった)のもとで博士の学位を授与されたそうである。半身不随の人のために手のリハビリロボットの開発で、最近では、人間の行動を学習し温度の調整を行うサーモスタットの開発などで活躍している。

興味がわいてきたので、彼女のことをもう少し詳しく調べたところ、ジュニア時代はプロテニスプレーヤーを目指していたとのことである。けがのために断念したそうだが、その後の進路変更が鮮やかである。スポーツを目指している若い人は、生活がスポーツだけになってしまうため、スポーツがダメになった時の転換がとても難しい。しかし、彼女は、Two Track Mindの中で語っているのだが、小学生のころから、学校を終わった後、16時から21時までテニスをし、21時から24時までを勉強に費やしている。とてもまねできないのだが、スポーツ推薦で大学に入ってくる学生の現状を考えると、少しは彼女を見習って欲しいと思うのだが、要求のし過ぎだろうか。

1.指数対象

圏\(\mathcal C\)において、対象\(A\)から対象\(B\)への射の全ての集合を\({\rm Hom}_{\mathcal C}(A,B)\)と表した。
f:id:bitterharvest:20150527113931p:plain

\({\rm Hom}_{\mathcal C}(A,B)\)で考えることの利点は、圏\(\mathcal C\)の構造が\({\rm Hom}_{\mathcal C}(A,B)\)に写し取られることにある。いくつかの具体圏について観察する(この部分は中村晃一さんの圏論勉強会第4回の資料を参考にした)。

圏\(\mathcal C\)を集合の圏\({\bf Sets}\)とし、対象\(A\)を自然数の集合\(\mathbb{N}\)、対象\(B\)を実数の集合\(\mathbb{R}\)とする。この時、(任意の)射は次のように作ることができる。実数の集合の中から、適当に実数を取り出し続ける。これを、\(b_0,b_1,...\)とする。次に、自然数\(i\)を実数\(b_i\)に対応させる。これを求める射とする。
f:id:bitterharvest:20150527115907p:plain

上記のように考えると、射の集合\({\rm Hom}_{\bf Sets}({\mathbb N}, {\mathbb R})\)の要素は、任意の無限の実数列と一対一に対応することとなる。

次に、圏\(\mathcal C\)を順序集合の圏\({\bf Pos}\)とし、\(A,B\)は、上と同じように、自然数の集合と実数の集合とする。射も上記と同じように決めるが、但し、任意の自然数\(i,j\)に対する写像\(b_i,b_j\)は、\(i < j\)の時、\(b_i < b_j\)を満足するものとする
f:id:bitterharvest:20150527141534p:plain
このように考えると、射の集合\({\rm Hom}_{\bf Sets}({\mathbb N}, {\mathbb R})\)の要素は、任意の無限の単調増加実数列と一対一に対応することとなる。

さらに、圏\(\mathcal C\)をモノイド圏\({\bf Pos}\)とし、\(A,B\)は、それぞれ、加法を伴う自然数の集合と乗算を伴う実数の集合とする。準同型写像\(f_a \in {\rm Hom}_{\bf Sets}({\mathbb N}, {\mathbb R})\)を考えることにする。但し、\(a\)は整数とする。即ち、\(a \in {\mathbb Z}\)である。

単位元単位元写像されるので、\(0 \in {\mathbb N}\)は\(1 \in {\mathbb Z}\)に写像される。
ここで、\(1 \in {\mathbb N}\)は\(a \in {\mathbb Z}\)に写像されたとする。この時、\(n \in {\mathbb N}\)は、\(f_a (n)=f(1+1...)=f_a (1) \times f_a (1)..=a \times a...=a^n\)に写像される。
f:id:bitterharvest:20150527144631p:plain
従って、\({\rm Hom}_{\bf Sets}({\mathbb N}, {\mathbb R}) = \{...,f_{-1},f_0,f_1,f_2,f_3,...\} \cong {\mathbb Z}\)となる。

これまで見てきたように、\({\rm Hom}_{\mathcal C}(A,B)\)は、対象\(A\)から\(B\)への全ての射の集まりであるが、ここには、都合の良いことに、圏\({\mathcal C}\)の対象と同じ構造が組み込まれている。

そこで、対象\(A\)から\(B\)へのすべての射の集まりを、圏\({\mathcal C}\)の構造を表すものとして、利用したくなる。このために表れた概念が指数対象である。これは次のように定義される。

指数対象の定義:

1) \({\mathcal C}\)を任意の二対象の積を持つ圏とするとする。即ち、任意の対象\(A,B \in {\mathcal C}\)に対して、\(A \times B \in {\mathcal C}\)である。

2) \({\mathcal C}\)の対象と射の組\((B^A, \epsilon)\)が\(A\)から\(B\)への指数対象であるとは、任意の対象\(X\)と任意の射\(f:X \times A \rightarrow B\)に対して
\begin{eqnarray}
\epsilon \circ (\tilde{f} \times 1_A) = f
\end{eqnarray}
を満たす\( \tilde{f} \times 1_A \)がただ一つ存在することである。

3) \( \epsilon : B^A \times A \rightarrow B\)を評価射と呼ぶ。
f:id:bitterharvest:20150528092445p:plain
指数対象は、定義を見ただけでは、とっつきにくいかもしれない。しかし、Haskellを使っている人であれば、指数対象をあらゆる場面で利用している。

上の定義で、\(f\)を\(\tilde{f}\)に変換することをカリー化という。逆に、\(\tilde{f}\)を\(f\)に変換することを非カリー化という。

Haskellでの加算(+)は、モナイド圏\(\bf{Mon}\)での二項演算である。いま、(+)の型シグネチャを観察すると次のようになっている。

Prelude> :t (+)
(+) :: Num a => a -> a -> a

Numというクラスの属す型aのインスタンスを入力し、さらに別のインスタンスを入力し、最後に計算結果を出力するとなっている。2引数を受け取り、計算結果を出力しているように読めるのだが、実はそうではない。この説明は、実はサボっている。Haskellではカッコをなるべく省こうとするが、この記述でもカッコは省かれている。カッコをしっかりつけると次のようになる。

Prelude> :t (+)
(+) :: Num a => a -> (a -> a)

これは、正確に読むと次のようになる。aのインスタンスを一つ読み込み(指数対象の定義での\(X\)の部分)、それに対応した関数(指数対象の定義での\(B^A\)の部分)を取り出す。その関数は、aの別のインスタンスを読み込み、計算結果を出力するようになっているので、これを評価する(指数対象の定義での\(\epsilon\)の部分)。従って、最初のインスタンスに対して関数を対応付けている。即ち、カリー化を行っている。これは、他のHaskellの関数についてもいえることである。

もし、JavaやCのように、どうしても、2引数を同時に受け取って加算を行いたい場合にはタプルを用いる。例えば、2引数を受け取りその加算を行う関数がaddであったとするなら、次のようにする。

Prelude> add (3,5)
8

2.デカルト閉圏

指数対象を利用したデカルト閉圏(Cartesian closed category)を定義する。

圏\({\mathcal C}\)が次の二つの条件を満足するとき、\({\mathcal C}\)をデカルト閉圏という。
1) 任意の有限個の対象の積が存在する。つまり、終対象と任意の二対象の積が存在する。
2) 任意の対象\(A,B\)について\(B^A\)が存在する

2.1 デカルト閉圏での法則\(A^1=A\)

デカルト閉圏では、任意の対象\(A\)について、\(A^1=A\)が成り立つ。

デカルト閉園では、終対象1が存在するので、任意の対象\(X\)と任意の射\(f:X \times 1 \rightarrow A\)に対して、\(\pi_1 \circ (\tilde{f} \times 1_1)=f\)を満たす\(\tilde{f}:X \rightarrow A\)がただ一つ存在することを証明すればよい(下図で評価射は\(\epsilon\)ではなく、\(\pi_1\)になっている。その理由は後でわかる)。
f:id:bitterharvest:20150529061737p:plain
上記の式で、本来は\(A^1\)が来るべきところを、\(A\)に代えてある。従って、もし、ただ一つ存在することを証明できれば、\(A^1=A\)を証明したことになる。

2.2 \(A^1=A\)の証明

先ほどの可換図式をよく見ると、圏論での積になっているので、積の様子がよく分かるように図を書き直すと次のようになる。
f:id:bitterharvest:20150528215535p:plain
証明は、\(\pi_1 \circ (\tilde{f} \times 1_1)=f\)を満たす\(\tilde{f}\)を求めればよい。そこで、\(\pi_1:A \times 1 \rightarrow A \)は、二つの対象の積の左側を返していることを考慮すると、\(\tilde{f} \times 1_1 = <\tilde{f} \circ \pi_1, !_{X \times 1}>\)を得る。ここで、
\begin{eqnarray}
(\tilde{f} \circ \pi_1) (X \times 1) & = & \tilde{f} (X) \\
& = & A
\end{eqnarray}
である。
また、また、\(!_{X \times 1}\)は対象\(X \times 1 \)から終対象1への唯一の射とする。従って、
\begin{eqnarray}
!_{X \times 1}(X \times 1) = 1
\end{eqnarray}
である。また、\(< g,h >\)は、任意の対象\(B\)に対して、\(< g,h >(B) = g(B) \times h(A)\)を与えるものとする。
従って、\(< \tilde{f} \circ \pi_1, !_{X \times 1} > (X \times 1) \)は\(A \times 1\)となる。

そこで、\(\pi_1 \circ (\tilde{f} \times 1_1)=f\)に\(\tilde{f} \times 1_1 = <\tilde{f} \circ \pi_1, !_{X \times 1}>\)の式を代入すると、
\begin{eqnarray}
\pi_1 \circ (\tilde{f} \times 1_1) & = & f \\
\pi_1 \circ <\tilde{f} \circ \pi_1, !_{X \times 1}> & = & f
\end{eqnarray}

\(\pi_1\)が積となっている二つの対象の左側を返すことを考えると、\(\tilde{f} \circ \pi_1=f\)を得る。そこで、左辺を次のように変形する。

\begin{eqnarray}
(\tilde{f} \circ \pi_1 \circ < 1_{X \times 1}, !_{X \times 1} >) (X \times 1) = \tilde{f} (X \times 1)
\end{eqnarray}
なので、
\begin{eqnarray}
\tilde{f} (X \times 1) = (f \circ < 1_{X \times 1}, !_{X \times 1} >) (X \times 1)
\end{eqnarray}
となる。
従って、
\begin{eqnarray}
\tilde{f} = f \circ < 1_{X \times 1}, !_{X \times 1} >
\end{eqnarray}
を得る。これで、\(\tilde{f}\)を求めることができたので、\(A^1\)が\(A\)であることが証明された。
f:id:bitterharvest:20150530083042p:plain

2.3 デカルト閉圏での法則\(C^{B \times A}=C^{B^A}\)

これも先ほどと同様に証明できるが、証明は先ほどにもまして複雑である。そこで、米田の原理を用いると容易に証明することができる(米田の原理は米田の補題から導くことができる)。


米田の原理:
圏\( {\mathcal C} \)の二つの対象\(A,B\)において、任意の対象\(X\)に対して自然同型\({\rm Hom}_{\mathcal C}(X,A) \cong {\rm Hom}_{\mathcal C}(X,B)\)が存在するならば、\(A \cong B \)である。

カリー化と積の結合律を利用して、

\begin{eqnarray}
{\rm Hom}_{\mathcal C}(X, C^{(B \times A)}) & \cong & {\rm Hom}_{\mathcal A}(X \times (B \times A), C) \\
& \cong & {\rm Hom}_{\mathcal C}((X \times A) \times B, C) \\
& \cong & {\rm Hom}_{\mathcal C}(X \times A, C^B) \\
& \cong & {\rm Hom}_{\mathcal C}(X, {(C^B)}^A)
\end{eqnarray}
と導けるので、\(C^{(B \times A)} \cong {(C^B)}^A \)となる。
f:id:bitterharvest:20150530085419p:plain
f:id:bitterharvest:20150530083158p:plain

2.4 その他の法則

デカルト閉圏は上記のほかに次のような法則を有する。
\begin{eqnarray}
1^A & \cong & 1 \\
{(B \times C)}^A & \cong & B^A \times C^A \\
A \times B + A \times C & \cong & A \times (B + C)
\end{eqnarray}

これらの法則も、米田の原理を用いて証明できる。即ち、
\begin{eqnarray}
{\rm Hom}_{\mathcal C}(X, 1^A) & \cong & {\rm Hom}_{\mathcal C}(X \times A, 1) \\
& \cong & 1
\end{eqnarray}
より、\(1^A \cong 1 \)となる。
f:id:bitterharvest:20150530084423p:plain

また、
\begin{eqnarray}
{\rm Hom}_{\mathcal C}(X, {(B \times C)}^A ) & \cong & {\rm Hom}_{\mathcal C}(X \times A, B \times C) \\
& \cong & {\rm Hom}_{\mathcal C}(X \times A, B) \times {\rm Hom}_{\mathcal C}(X \times A, C) \\
& \cong & {\rm Hom}_{\mathcal C}(X, B^A) \times {\rm Hom}_{\mathcal C}(X, C^A) \\
& \cong & {\rm Hom}_{\mathcal C}(X, B^A \times C^A) \\
\end{eqnarray}
より、\({(B \times C)}^A \cong B^A \times C^A\)となる。

米田の原理は双対性を用いると、次のようにも言える。
圏\( {\mathcal C} \)の二つの対象\(A,B\)において、任意の対象\(X\)に対して自然同型\({\rm Hom}_{\mathcal C}(A,X) \cong {\rm Hom}_{\mathcal C}(B,X)\)が存在するならば、\(A \cong B \)である。
また、デカルト閉圏において、始対象と任意の対象について余積が存在するとき、分配的であるという。そこで、デカルト閉圏が分配的であったとすると、次のことがいえる。
\begin{eqnarray}
{\rm Hom}_{\mathcal C}(A \times B + A \times C, X) & \cong & {\rm Hom}_{\mathcal C}(A \times B, X) \times {\rm Hom}_{\mathcal C}(A \times C, X)\\
& \cong & {\rm Hom}_{\mathcal C}(B, X^A) \times {\rm Hom}_{\mathcal C}(C, X^A) \\
& \cong & {\rm Hom}_{\mathcal C}(B + C, X^A) \\
& \cong & {\rm Hom}_{\mathcal C}(A \times (B + C), X) \\
\end{eqnarray}
より、\(A \times B + A \times C \cong A \times (B + C)\)となる。

次の記事では、デカルト閉圏を応用した例を説明する。