圏論勉強会
第5回

@ワークスアプリケーションズ

謝辞

この勉強会の企画，会場設備の提供をして頂きました
㈱ ワークスアプリケーションズ様
にこの場をお借りして御礼申し上げます。

この会について

• 圏論(category theory)を題材にいろんなことを学びます。
• 分かり易さを重視して初歩的な例を多用します。
• 関数型言語の経験がある方がより楽しめると思います。資料中では主にHaskellを使います。
• 中高生も数人見ているらしいのでプログラミングと関係が浅い内容も取り上げます。
• この資料はhttp://nineties.github.com/category-seminarに置いてあります。

第5回: 様々な射

第5回の内容

前回は射によって考える事の重要性を話しましたが,今回は射の持つ様々な性質について説明していきます。射は関数概念の一般化とも考えられるので,集合・関数に関係する話も紹介します。

同型射

同型の定義

$f: A\rightarrow B$に対して,$g: B\rightarrow A$が存在し,

$ g\circ f = 1_A\qquad f\circ g = 1_B$

が成り立つならば$f$を同型射(isomorphism)と呼ぶ。
また,圏$\mathbf{C}$において$A$と$B$の間に同型射が存在するならば,$\mathbf{C}$において$A$は$B$と同型(isomorphic)であると言い, $$ A \cong B$$ と表す。

逆射

同型射とは

同型射$f: A\rightarrow B$の存在,つまり $$ A \cong B $$ である事はその圏に於いて$A$と$B$が本質的に同じものである事を表していると解釈出来ます。

これまで何となく$\cong$を使いましたが,ちゃんと見ていく事にします。

函手は同型性を保つ

函手は同型性を保つ

つまり,以下の様な事が言えます。

$\mathbf{C}$で同型$\Leftrightarrow\mathbf{C}^{\mathrm{op}}$で同型

定義の対称性から明らかですが,$\mathbf{C}$での同型射は双対圏$\mathbf{C}^{\mathrm{op}}$における同型射に移ります。

よって反変函手$F:\mathbf{C}^{\mathrm{op}}\rightarrow \mathbf{D}$も同型性を保ちます。 $$A\cong B\Rightarrow F(A)\cong F(B)$$

同型射$f: A\leftrightarrows B : f^{-1}$が存在する場合には,「$f$を左から合成する事」が同型射 $$\mathrm{Hom}(X,A) \rightarrow \mathrm{Hom}(X,B)$$ を与え,「$f^{-1}$を右から合成する事」が同型射 $$\mathrm{Hom}(A,Y) \rightarrow \mathrm{Hom}(B,Y)$$ を与えます。

すると$A\cong B$の時,$A$の周りの射を$B$の周りに移しても図式の可換性がそのまま保たれます。

$A$,$B$の周りの射はただ一対一に対応するだけでなく,それらに成り立つ等式(可換図式)も一対一に対応している事になります。

同型ならば区別出来ない

直感的に言うと,圏論の言葉のみを用いた場合
「$A\cong B$のとき$A$に関して成り立つ事は$B$に関しても成り立つ。逆も然り。」
という事になります。

逆に言うと同型である対象$A$と$B$をそれらが満たす性質のみによって区別する事は出来ないという事になります。

「同型ならば区別出来ない」の例

同値関係

同型は同値関係

圏$\mathbf{C}$における同型$\cong$は$\mathbf{C}$の対象の集合上の同値関係になっています。つまり

が成り立ちます。

証明は練習問題としますが,ついでに以下の公式を得ます。

【証明の概略】
反射律は任意の$A$について$1_A$が同型射である事,対称律は$f$が同型射ならば逆射$f^{-1}$も同型射である事,推移律は$f,g$が下図のような同型射ならば$f^{-1}\circ g^{-1}$が逆射となる事を示せば良いです。そして逆射の一意性より上の公式が示されます。

モノイドにおける同型

モノイド$(M, \cdot)$を圏とみなした時の同型射は$e$を単位元として $$ x\cdot y = y\cdot x = e $$ を満たす$x,y\in M$,つまり可逆元(invertivle element)の事です。

例えば$(\mathbb{R}, \times)$の同型射は$0$以外の全ての実数です。
「関数」や「準同型」以外の同型射の例となります。

半順序集合における同型

半順序集合$(A, \leqq)$においては $$ x\leqq y,\ y\leqq x\ \Rightarrow\ x = y$$ だったので,$(A, \leqq)$を圏とみなした場合,任意の対象$x$についてそれと同型なのは$x$自身のみとなります。

証明の圏における同型

$P$,$Q$を論理式とした時$P\cong Q$であるとは $$ \begin{aligned} & P\ \Rightarrow\ Q \\ & Q\ \Rightarrow\ P \end{aligned} $$ の証明が共に存在する事となります。つまり証明の圏における同型とは同値(equivalence)の事です。

$\mathbf{Sets}$における同型

まず準備として単射・全射の定義の確認をします。

単射

単射は異なる$A$の要素を異なる$B$の要素に移します。

全射

全射はその行き先(値域)が$B$全体を網羅します。

全単射

全単射は要素の一対一対応を与えます。

$\mathbf{Sets}$における同型射とは全単射の事です。

【同型射ならば全単射である事の証明】
$f,f^{-1}$が同型射とその逆射$f: A\leftrightarrows B: f^{-1}$であるとすると $$f(x_1) = f(x_2)\Rightarrow f^{-1}\circ f(x_1) = f^{-1}\circ f(x_2)\Rightarrow 1_A(x_1) = 1_A(x_2)\Rightarrow x_1 = x_2$$ なので$f$は単射。また任意の$y \in B$に対して$x = f^{-1}(y) \in A$が存在し, $$ f(x) = f\circ f^{-1}(y) = 1_B(y) = y $$ を満たすので$f$は全射。従って$f$は全単射である。
【全単射ならば同型射である事の証明】
$f: A\rightarrow B$が全単射であるとすると,任意の$y\in B$について$f(x) = y$を満たす$x$が存在する。ここで$f(x_1) = y,\,f(x_2) = y$であるとすると$f(x_1)=f(x_2)$であるから$f$の単射性より$x_1 = x_2$となる。すなわち任意の$y\in B$について$f(x) = y$を満たす$x$が唯一つ存在するので,この対応$g: y=f(x)\mapsto x$は関数である。このとき任意の$x \in A$について$g(f(x)) = x$となるから$g\circ f = 1_A$。また任意の$y = f(x) \in B$について$f(g(y)) = f(x) = y$となるから$f\circ g = 1_B$。従って$f$は同型射である。 □

集合のサイズを測る

有限集合$A$,$B$の要素数が等しい事を「全単射$f: A\rightarrow B$が存在する事」として定義するのは自然です。

集合の濃度

ゲオルグ・カントール(1845-1918)はこの考え方を無限集合にも一般化して「射で集合のサイズを測る」方法を確立しました。

例えば$f(x) = 2x$が自然数から$0$以上の偶数への全単射となるので $$|\text{自然数の集合}|=|\text{$0$以上の偶数の集合}|$$ となります。

カントールの定理

$A$が無限集合の場合には$\mathcal{P}(A)$も無限集合となりますが,$A$と$\mathcal{P}(A)$の濃度が異なるという事をこの定理は言っています。今回濃度の大小の話はしていませんが,カントールは無限集合にもサイズの大小があるという事を発見したわけです。

カントールの対角線論法

【証明】
全射$f: A\rightarrow\mathcal{P}(A)$が存在したと仮定して $$ X = \{x\in A | x\not\in f(x)\} $$ とする。ここで$X$の要素は全て$A$の要素要素だから$X$は$A$の部分集合の一つであるから,$f$の全射性より $$ X = f(x) $$ を満たす$x \in A$が存在する。すると$x \in X=f(x)$ならば$x \not\in X$,$x \not\in X=f(x)$ならば$x \in X$であるから$x\in X\Leftrightarrow x\not\in X$となり矛盾。従ってこのような全射$f$は存在しない。□

単純に面白いということもありますが,「集合論」は数学の土台ですのでこういった基本的な事実は知っておきましょう。

また,対角線論法は計算機科学の重要な定理の証明にも使用されます。 圏論による一般化と併せて後の回に扱う予定です。

レトラクト

$$ g\circ f = 1_A,\ f\circ g= 1_B$$ が「共に」成り立つ事が同型の定義でした。この条件を弱めるとセクション・レトラクションが定義されます。

レトラクト

レトラクトとは

直感的に説明すると$A$が$B$のレトラクトであるということは$B$が$A$を取り出せる形で含んでいるという事を表しています。これによって様々な状況が説明されます。

函手はレトラクトを保つ

レトラクトは等式(可換図式)によって定義される事に注意しましょう。従って任意の函手$F: \mathbf{C}\rightarrow\mathbf{D}$はレトラクトを保ちます。

$\mathbf{Sets}$におけるレトラクト

$\mathbf{Sets}$において,$r\circ s=1_A$であるならば$s$は単射,$r$は全射となります。この事実は後で一般化された形で見ます。

全射$r: B\rightarrow A$によって$B$の要素は($A$の要素と同じ数だけの)空でない互いに素な集合に類別(classify)されます。

全射$r$のセクションが$s$が存在するならば,$s$は$r$によって類別された各集合から一つずつ元を選択する事に相当します。

ここで$e = s\circ r : B\rightarrow B$とおくと$e$は$r$によって類別された各集合の元を,$s$によって選択された元に移す関数となります。

この操作は一度やれば何度やっても変わりませんから $$e\circ e = e$$ が成り立ちます。この性質については後で説明します。

射$r: B\rightarrow A$のセクションが存在する事は以下と同値。

任意の対象$X$と射$f: X\rightarrow A$について下図が可換となるような射$g: X\rightarrow B$が存在する。

【前者$\Rightarrow$後者の証明】
$r:B\rightarrow A$のセクション$s:A\rightarrow B$が存在するならば$g = s\circ f$とおくと $$r\circ g = r\circ s\circ f = 1_A\circ f = f$$ が成り立つ。
【後者$\Rightarrow$前者の証明】
$X = A$,$f=1_A$の場合を考えると$g$が$r$のセクションである。

同様に射$s: A\rightarrow B$のレトラクションが存在する事は以下と同値。

任意の対象$X$と射$f: A\rightarrow X$について下図が可換となるような射$g: B\rightarrow X$が存在する。

証明は練習問題とします。

モノ射・エピ射

$A$が$B$のレトラクトであるということは$B$が$A$を取り出せる形で含んでいる事を表していると説明しました。

しかし,次に説明するように取り出せないけど$B$が$A$を含んでいるという状況があります。

位相空間と連続写像からなる圏を考えます。$D^2$を円板,$S^1$をその縁とすると確かに$D^2$は$S^1$を含んでいます。

しかし$D^2$に穴を開けずに$S^1$に変形する事は出来ないので,$S^1$は$D^2$のレトラクトになっていません。

(直感的な意味での)「$A$が$B$の一部であるという事」ををレトラクトによって定義するのは条件が強すぎるという事が判ります。

セクション・レトラクションの条件を緩めて,単射・全射の圏論による一般化を考えます。

$f: A\rightarrow B$がレトラクション$r: B\rightarrow A$を持つという事は $$ r\circ f = 1_A$$ が成り立つ事でした。この事は$f$を左から消す事が出来る事を表しています。セクションについても同様です。

$A\rightarrow B$へのモノ射・エピ射とはセクション・レトラクションと同様の性質を$B\rightarrow A$の向きの射の存在に依らずに定義したものと言えます。

モノ射

射$m: A\rightarrow B$がモノ射(monomorphism)であるとは,任意の対象$X$と射$f,g: X\rightarrow A$について $$ m\circ f = m\circ g \ \Rightarrow\ f = g $$ が成り立つ事である。
$m$がモノ射である事をモニックであるとも言い,記号では$m: A\rightarrowtail B$と表す。

$\mathbf{Sets}$におけるモノ射とは単射の事です。

【モノ射ならば単射である事の証明】
$f: A\rightarrow B$がモノ射であるとする。$x_1,x_2 \in A$が$x_1\neq x_2$であるとする。$x_1,x_2$に対応する定数関数$\overline{x_1},\overline{x_2}: 1\rightarrow A$を考えると,$\overline{x_1}\neq \overline{x_2}$となり$f$がモノ射であるから$f\circ \overline{x_1} \neq f\circ \overline{x_2}$となる。すなわち,これに$1$の元を代入すれば$f(x_1)\neq f(x_2)$となる。 対偶を取れば任意の$x_1,x_2\in A$について $f(x_1) = f(x_2) \ \Rightarrow\ x_1 = x_2$ となるので$f$は単射である。
【単射ならばモノ射である事の証明】
$f: A\rightarrow B$が単射であるとする。関数$g,h:X\rightarrow A$が$g \neq h$ならばある$x\in X$が存在して$g(x)\neq h(x)$となる。すると$f$が単射であることより$f(g(x)) \neq f(h(x))$であるから$f\circ g \neq f\circ h$となる。対偶を取れば $f\circ g = f\circ h \ \Rightarrow\ g = h$ となるので$f$はモノ射である。□

エピ射

射$e: A\rightarrow B$がエピ射(epimorphism)であるとは,任意の対象$X$と射$f,g: B\rightarrow X$について $$ f\circ e = g\circ e \ \Rightarrow\ f = g $$ が成り立つ事である。
$e$がエピ射である事をエピックであるとも言い,$e: A\twoheadrightarrow B$と表す。

$\mathbf{Sets}$におけるエピ射とは全射の事です。

【エピ射なら全射である事の証明】
$f: A\rightarrow B$がエピ射でありかつ全射でないとすると,ある$b \in B$について$b = f(x)$を満たす$x \in A$が存在しない。ここで関数$g,h: B\rightarrow \{0,1\}$を$g(x) = 0$ $$ h(x) = \left\{\begin{array}{cl} 0 & (x \neq b) \\ 1 & (x = b) \end{array}\right. $$ によって定義すると,$g \neq h$であるのに$g\circ f = h\circ f$となる。これは$f$がエピ射である事に矛盾するので,$f$は全射である。
【全射ならばエピ射である事の証明】
$f: A\rightarrow B$が全射であるとする。関数$g,h:B\rightarrow X$が$g \neq h$であるとするとある$y \in B$が存在し$g(y) \neq h(y)$である。ここで$f$は全射であるから$y = f(x)$を満たす$x$が存在し$g(f(x)) \neq h(f(x))$となる。従って$g\circ f \neq h\circ f$であるから対偶をとって $$ g\circ f = h\circ f \ \Rightarrow\ g = h$$ すなわち$f$はエピ射である。□

同型射・セクション・レトラクションとの関係

以下の事実が言えます。証明は簡単なので練習問題とします。

• 同型射はモニックかつエピック
• $f$がレトラクションを持つならば$f$はモニック
• $f$がセクションを持つならば$f$はエピック

モニックかつエピック $\not\Rightarrow$ 同型射

今見たようにモノ射は単射の一般化,エピ射は全射の一般化と言えます。

しかし,射$f$がモニックかつエピックであっても同型射であるとは限りません。

モニックかつエピックだが同型射でない例

$\mathbf{Mon}$における準同型 $$ f: (\mathbb{N}, +) \rightarrow (\mathbb{Z}, +)$$ を$f(x) = x$によって定義します。これは明らかに同型射ではありませんが,モニックかつエピックです。$g: (\mathbb{Z},+)\rightarrow (M,\cdot )$があったとすると,$g(-n)$は必ず$g(n)$の逆源に移ります。従って$\mathbb{Z}$の$n \geqq 0$の部分のみによって$g$全体が定まるという事になります。

証明はAwodeyのテキストのExample 2.5にあります。時間があれば,当日説明します。

モノ射とエピ射は双対

$f$が$\mathbf{C}$におけるモノ射ならば,$\mathbf{C}^{\mathrm{op}}$においてはエピ射となります。逆も然りです。すると一方の性質から他方の性質を自動的に得る事が出来ます。

例えば$f: A\rightarrowtail B$, $g: B\rightarrowtail C$ならば$g\circ f: A\rightarrowtail C$となる事が示せます(練習問題)。
すると双対性により$f: A\twoheadrightarrow B$, $g: B\twoheadrightarrow C$ならば$g\circ f: A\twoheadrightarrow C$事も自動的に言えます。

冪等射

冪等射

分裂冪等射

先ほど述べた様にセクションとレトラクション$s: A\rightarrow B: r,\ r\circ s=1_A$を用いて $$ e = s\circ r $$ と定義すると $$ e\circ e = s\circ r\circ s\circ r = s\circ 1_A\circ r = s\circ r = e$$ なので$e$は冪等射となります。

このようにセクションとレトラクションで表される冪等射を分裂冪等射(split idempotent)と言います。

プログラミングの文脈での冪等性

列と連結からなるモノイドにおいて$[e]$が冪等射であるとします。すると, $$ \begin{aligned} & [a,b,\cdots,x,e,e,e,e,e,y,\cdots] \\ = &[a,b,\cdots,x,e,y,\cdots] \end{aligned} $$ です。これをプログラムの命令の列だと思うと,$e$は連続して実行しても一回だけ実行しても同じ命令を表します。

例えば「ボタンを連打しても一回押しても同じ処理」、「同じ変数への同じ値の書き込み」などです。

この様にある種の冗長性(redundancy)を扱う場面で冪等性が登場する事があります。

第5回はここで終わります

お疲れ様でした。
関数によって類別や選択,包含関係などの２つの集合の関係が表現される事を見ました。 圏論では全てを射で考えるので,このような射の解釈に親しむ事がとても大切です。

次回は積・余積などを始めとする普遍的な対象について,その構成方法について説明をします。