bitterharvest’s diary

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

Haskellで学ぶ圏論・ウォームアップ編 基点付集合

1.不動点

丸い円盤が机の上に置かれていたとする。この丸い円盤は、回転したり、移動したり、縮めたりと自由に操作できるものとする。但し、この操作を行っているときは、元の円盤からはみ出すことは許されないとする。例えば、下図のように、円盤を楕円盤に変えたとする。
f:id:bitterharvest:20150227133645p:plain

この時、円盤のある点\(x\)が楕円盤のどの点\(y\)に移動したかを求めることができる。そして、これらの点の中で、全く移動していない点が一つあるということを、Browerの不動点定理は教えてくれる。

証明の概略は以下のとおりである。最初の円盤を\(X\)とする。回転したり、移動したり、縮めたりして得られた楕円盤を\(Y\)とする。円盤から楕円盤に変えたときの操作を\(f\)とすると、\(f: X \rightarrow Y\)である。この時、はみ出してはいけないという条件から\( X \supset Y\)である。このことから、元の円盤の中で楕円盤の領域内の点(\( x_0 \subset X\))は、楕円盤の中(\( x_0 \subset Y\))にある。

次に、先ほどと同一の操作(適応する関数\(f\)が同じ)をこの楕円盤にもう一度施す。そこで得られた新たな盤を\(Y'\)とする。即ち、\(f: Y \rightarrow Y'\)とする。この時、\(f \circ f: X \rightarrow Y'\)であるので、\( X \supset Y \supset Y' \)である。この時、元の円盤の中でこの新しい盤の領域の中にある点(\( x_0 \subset X\))は、新しい盤の中(\( x_0 \subset Y'\))にある。

この操作を無限に続けていくと、円盤は最後は一つの点(\(z\))になる。この結果、円盤の全ての点はこの点(\(z\))となる。一方、一つの点(\(z\))と重なっている円盤上の元々の点(\(x_0\))は、一つの点になった中に含まれる(\(x_0 \subset z \))ので、この点が、不動点となる。

2.代表者

新しい季節が始まると、町内会の役員を決めたり、父母会の役員を決めたり、委員会の役員を決めたりと煩わしいことが多くなる。感情的な問題はさておいて、役員とそうでない人の社会的な関係を論理的に表すことを考える。圏論では下図のように表すことができる。
f:id:bitterharvest:20150227142257p:plain

上の図で、\(X\)は町内会のメンバーの集まりである。また、\(x_0\)は町内会長である。\(Y\)はメンバーの住所であり、\(y_0\)は町内会長の住所である。\(f:X \rightarrow Y\)はそれぞれのメンバーに対してその人の住所を与える関数である。

町内会のメンバーの集まりはこれまで見てきた集合と同じであるが、この集合は町内会長という特別な要素がある。このような特別な要素を数学では基点と呼び、基点を持つ集合を基点付集合(pointed set)という。基点付集合を表現するときは、その集合の終対象(ここでは1と表す)から、集合の基点への写像で表す。

ところで、今説明した基点付集合と先ほど説明した不動点の話は全く異なる分野の話だが、それにもかかわらず、数学的な構造はとても良く似ている(不動点のほうにも終対象を設けてやり、不動点への写像を付加すると同じになる)。

基点付集合になるものはこの他にもたくさんあるので、基点付集合の構造を考えることは重要である。

3.基点付集合の構造

基点付集合の圏の構成を考えることにする。普通の集合の圏は次のように表していた。
(1)対象:集合\(X\), \(Y\), \(Z\),..
(2)射:写像\(f\), \(g\), \(h\),..
(3)ドメインとコドメイン:\(f:X \rightarrow Y\), \(g: Y \rightarrow Z\), \(h: Z \rightarrow \ \),..
(4)恒等射:\(id_X : X \rightarrow X\), \(id_Y : Y \rightarrow Y\), \(id_Z : Z \rightarrow Z\),...
(5)合成:\(g \circ f\), \(h \circ g\),...

基点付集合の圏はその構成を次のように表す。
(1)対象:写像\(x_0:1 \rightarrow X\)、写像\(y_0:1 \rightarrow Y\)
(2)射:写像\(x_0\)から写像\(y_0\)への写像\(f \circ\)(但し、\(f:X \rightarrow Y\)である。また、\(f \circ (x_0) = f \circ x_0\))
(3)ドメインとコドメインドメインは\(x_0:1 \rightarrow X\)、コドメインは\(y_0:1 \rightarrow Y\)
(4)恒等射:写像\(x_0\)から写像\(x_0\)への写像\(1_X \circ\)、写像\(y_0\)から写像\(y_0\)への写像\(1_Y \circ\)
(5)合成:\(f \circ 1_X \circ \), \(1_Y \circ f \circ \)など

この圏の構成は、集合の圏の構成とはずいぶん異なる。集合の圏では対象は集合であったが、基点付集合では対象は写像である(集合間の写像は複数個存在するので、一般的に扱うときは写像の集合となるが、ここでは、それぞれ一つずつしかないので、取りあえず、写像としておく)。また、集合の圏では射は写像であったが、基点付集合では射は写像間の写像である。基底付集合は、これまで説明してきた対象と射に対する概念を、抽象度をもう一レベル上げた世界へと誘っているように思える。

4.始対象と終対象

先の記事で、始対象の説明をした。それは次のようになっていた。一つの対象をすべての対象に写像するような射が丁度一つ存在するとき、写像する側の対象を始対象と呼ぶ。

この定義に従うと、始対象は、二つの対象\(x_0:1 \rightarrow X\)と\(y_0:1 \rightarrow Y\)に同時に写像するような丁度一つの射をもつ対象を探すことで求まる。ここで、対象は二つしかないので、まず、対象\(x_0:1 \rightarrow X\)について考えてみる。この対象から二つの対象へ写像する射が丁度一つあれば、この対象は始対象となる。

残念ながら、対象\(x_0:1 \rightarrow X\)からは、自身への恒等射\(1_X \circ\)と\(y_0:1 \rightarrow Y\)への射\(f \circ\)の二つがあるように見える。しかし、\(y_0:1 \rightarrow Y\)は不動点への写像であるため、別の不動点への写像\(x_0:1 \rightarrow X\)を決めた瞬間に一意的に定まる。このため、この二つの写像は別々の写像ではなく、一つの写像と見たほうが素直である。実際、この二つの写像は(証明は省くが)同型な写像である。従って、この圏では\(x_0:1 \rightarrow X\)と\(y_0:1 \rightarrow Y\)の二つの対象が始対象となり、これらは同型であるということになる。

終対象は、集合を下図のようにどんどん縮めていくことで求められるので、\(X\)から\(1\)への写像が終対象となる(同様に\(Y\)から\(1\)への写像も終対象であるが、これは同型である)。
f:id:bitterharvest:20150301062318p:plain

終対象と始対象の関係を図示すると次のようになる。
f:id:bitterharvest:20150301055644p:plain

5.Haskellでの実現

それでは、代表者を例にしてHaskellで実現することを試みる。以下のプログラムで、\(x_0\)はpointedMemberで、\(y_0\)はpointedAddressで、\(f \circ\)はresidenceMapで実現した。

module PointedSet where

data Member a = Name a deriving (Eq, Show, Read)
data Address a = Place a deriving (Eq, Show, Read)
data One = FixedMember | FixedAddress deriving (Eq, Show, Read)     -- x0 | y0

pointedMember :: One -> Member String
pointedMember x 
  | x == FixedMember  = Name "John"                                 -- x0: 1 -> X
  | otherwise = error "not the fixed point"

pointedAddress :: One -> Address String
pointedAddress x 
  | x == FixedAddress = Place "Berkeley"                            -- y0: 1 -> Y
  | otherwise = error "not the fixed point"

residence :: Member String -> Address String                        -- f: X -> Y
residence x
  | x == Name "John" = Place "Berkeley"
  | x == Name "Betty" = Place "Berkeley"
  | x == Name "Tom" = Place "Stanford"
  | x == Name "Mike" = Place "San Jose"
  | x == Name "Peter" = Place "Los Angeles"
  | x == Name "Jacky" = Place "Los Angele"
  | x == Name "Rose" = Place "Los Angele"
  | otherwise = error "not a member"

residenceMap :: (One -> Member String) -> (One -> Address String)   -- f. : x0 -> y0
residenceMap f = (residence . f) 

実行してみる。まず、対象、射が正しくできているかを検査する。

Prelude> :load "PointedSet.hs"
[1 of 1] Compiling PointedSet       ( PointedSet.hs, interpreted )
Ok, modules loaded: PointedSet.
*PointedSet> :t pointedMember
pointedMember :: One -> Member String
*PointedSet> :t pointedAddress
pointedAddress :: One -> Address String
*PointedSet> :t residence
residence :: Member String -> Address String
*PointedSet> :t residenceMap
residenceMap :: (One -> Member String) -> One -> Address String

それでは値を入れて実際に実行してみる。

*PointedSet> pointedMember FixedMember
Name "John"
*PointedSet> residenceMap pointedMember FixedMember
Place "Berkeley"
*PointedSet> pointedAddress FixedAddress
Place "Berkeley"

6.余談

基点付集合は、代数学幾何学を統合したホモトピーの世界へと誘ってくれるので重要な概念である。

また、ここでの不動点の話は連続系の話であり、代表者の話は離散系の話である。Haskellでプログラミングするときは、どうしても離散系が対象となるが、連続系も重要な対象分野である。なお、不動点の話で出てきたような空間を扱うときは、通常は、位相空間を扱う。このとき、対象は開集合で、射は連続写像となる。

代表者のところで出てきた、メンバーと住所の関係についても一言触れておく。メンバーの中には家族と一緒に住んでいる人もいるはずである。このような場合には、複数人のメンバーが同じ住所を有することとなる。従って、住所からメンバーへの写像を作成しようとすると、家族の中の代表者、例えば、世帯主への写像を与えることになる。

そこで、住所からメンバーに写像して、さらに、そこから、住所に写像して戻ってくる場合を考える。図で表すと次のようになる。
f:id:bitterharvest:20150301070649p:plain
上の図で、\(f\)と\(1_Y\)(同じ住所に写像する恒等射)とが与えられている。求めるのは、\(s\)である。前の記事にこの図と似たものがあった。前の記事では、\(s\)の決定は選択的な問題とされていた。ここでも、\(s\)は家族の中の代表者を決めるため、選択的な問題であることが分かる(写像\(s\)はセクションと呼ばれる)。

次に、住所とメンバーを逆にしてみる。下図のようになる。
f:id:bitterharvest:20150301070835p:plain
上の図で、\(f\)と\(1_X\)(同じメンバーに写像する恒等射)とが与えられている。求めるのは、\(r\)である。前の記事にこの図と似たものがあった。前の記事では、\(r\)の決定は決定的な問題とされていた。しかし、同じ住所を持つ人が複数人いるために、\(r\)を一意に決めることができない。そこで、世帯主が割り当てられたと仮定する。この時、\(r \circ f\)を実行すると出力は世帯主となるので、入力が世帯主でない場合には、本人とは一致しない。このため、\(1_X\)を満足することができなくなる。従って、この問題に対しては解がないことになる(写像\(r\)はリトラクションと呼ばれる)。

しかし、上記の問題は、世帯主については成り立っている。今、\(e = r \circ f\)とすると、\(e \circ e = e\)を満足していることがわかる(一回ぐるっと回しても、二回ぐるっと回しても世帯主が返ってくる)。このように、\(e \circ e = e\)が成り立つとき、冪等性(idemopotence)があるという。