圏論(Category Theory)についての覚書: 圏論の基礎を整理する(2): 圏論の基礎概念をおおざっぱにまとめる - 疑念は探究の動機であり、探究の唯一の目的は信念の確定である。

こんにちは。今回は圏論の基礎概念をおおざっぱに書きたいと思います。前回の記事はこちらから

f:id:yoheiwatanabe0606:20170915222624p:plain

圏論には大きく分けると次の3つのパートがあると思われます。

第I部: 圏・CCC・トポス

第II部: 関手・自然変換・イクィバレンス・米田の補題

第III部: 随伴・モナド

今回は第I部の圏について書きたいと思います。

第I部: Categories
圏(Categories)の定義と例
- 圏の定義
- 圏の例
圏の特別な概念

圏論において決定的に重要なのは「自然変換(Natural Transformations)」である。それを理解するためには関手(Functors)を理解しなければならず、関手を理解するためには圏(Categories)を理解しなくてはならない。関手とは圏と圏との写像である。ここまではそれほど難しくないし、それほど突飛なものでもない。しかし圏論はこれで終わらない。圏論では次に自然変換を定義するのだが、それは関手と関手の写像である。要は自然変換とは圏の間の写像間の写像である。

写像を関数(Fuctions)とみなして、それを「関係」や「はたらき」と解釈するならば、 自然変換とは関係の関係であると言うことができる。

随伴(Adjunctions, Adjoints)とは自然変換の特別なものである。それは数学のいたるところにみられる。これはいくつかの同値な定義がある。

モナドとは自己関手 $T:\textbf{C}\to\textbf{C}$ と2つの自然変換 $\eta: 1_{\textbf{C}}\to T$ と $\mu: TT\to T$ が或る性質を満たす組み $(T, \eta, \mu)$ である。随伴があるならばモナドがあり、モナドがあるならば随伴を満たす別の圏がある。それはEilenberg-Moore圏と言われる。

第I部: Categories

圏(Categories)の定義と例

圏の定義

圏は対象と呼ばれるものと射と呼ばれるものが或る性質を満たす数学的抽象物である。

f:id:yoheiwatanabe0606:20170916163647p:plain

圏の例

圏にはさまざまな例がある。

0: 対象も射もひとつもない圏

1: ただ1つの対象と恒等射のみの圏

Set(集合の圏): 対象は集合で、射は関数

Grp(群の圏): 対象は群で、射は準同型写像

Top(位相空間の圏): 対象は位相空間で、射は連続写像

Stone(ストーン空間の圏): 対象はストーン空間で、射は連続写像

Boole(ブール代数の圏): 対象はブール代数で、射はブール保存写像

FDVeckk(体kの有限次元ベクトル空間の圏):対象は体kの有限次元ベクトル空間で、射は線形写像

Pre(プレオーダー集合の圏): 対象はプレオーダー集合 $(P, \leq_P)$ で、射は順序保存写像である。つまり、2つのプレオーダー集合を $(P,\leq_P),\,(Q,\leq_Q)$ として、順序保存写像 $f:P\to Q$ とは任意の $p_1\leq_Pp_2\in P$ に対して、 $f(p_1)\leq_Qf(p_2) \in Q$ が成り立つ写像である。

Pos(ポセットの圏): 対象はポセットつまり順序集合で、射は順序保存写像である。

Mon(モノイドの圏): 対象はモノイドで、射はモノイド保存写像である。モノイドとは集合 $M$ と二項関係　 $\circ_M: M\times M\to M$ と $M$ の特別な元 $1_M$ のあつまり $(M, \circ_M, 1_M)$ で、これは結合法則を満たし $1_M$ が単位元である。モノイド保存写像　 $\varphi: (M, \circ_M, 1_M)\to (N, \circ_N, 1_N)$ とは $\varphi(x\circ_M y) = \varphi(x)\circ_N\varphi(y)$ と $\varphi(1_M) = 1_N$ が成り立つことである。

決定的に重要なのは、プレセット $(P, \leq_P)$ やモノイド $(M, \circ, 1)$ それ自体も圏であるということである。つまり、プレセットは対象がその元で、射がただ1つの圏であり、モノイドはただ1つの対象で、その射がモノイドの元である圏である。

ほかにも、圏の射は必ずしも関数や何かしらの構造を保つ写像とは限らないという例を理解すること。

また与えられた圏から新しい圏を構成することも重要である。例えば、双対圏 $\textbf{C}^{\textrm{op}}$ やプロダクト・カテゴリー(Product categories) $\textbf{C}\times\textbf{C}$ やスライス・カテゴリー(Slice categories) $(A\downarrow \textbf{C})$ である。

射 $f: A\to B$ が同型写像であるとは、ある射 $g:B\to A$ が存在して、 $g\circ f = 1_A$ と $f\circ g = 1_B$ が成り立つ。対象 $A$ が対象 $B$ と同型であるとは $A$ から $B$ への同型写像が存在することであり、 $A\cong B$ と書く。

部分圏

圏の特別な概念

圏論において重要な概念に「ユニバーサル・マッピング・プロパティ」(Universal Mapping Property)というものがある*1。これは「ある条件を満たす任意の数学的抽象物に対して、ある特別な性質を満たす唯一の射が存在すること」を意味する。

特別な対象(objects)

終対象(Terminal ojbects) ・始対象(Initial objects)

終対象 $T$ とは、任意の対象 $X$ に対して、ただ1つの射 $!_X: X\to T$ が存在する。

始対象とは、終対象の双対的な概念である、つまり圏 $\textbf{C}$ の始対象 $I$ とは双対圏 $\textbf{C}^{\textrm{op}}$ の終対象である。

$\textbf{Set}$ において終対象はシングルトン $\{*\}$ であり、始対象は空集合 $\emptyset$ である。

また、ブール代数 *2それ自体をひとつの圏とみなすと、終対象は最大元1であり、始対象は最小元0である。

もしも終対象が存在するならばそれはただ1つしか存在しない。つまりもし2つの終対象 $T_1, T_2$ があるならば、 $T_1$ は $T_2$ と(キャノニカル)同型である。 $T_1\cong T_2$ 。これは始対象も同様である。

積(Products)・双対積(Coproducts)

$A$ と $B$ を対象とする。対象 $P$ が $A$ と $B$ の積であるとは、2つの射の組み $A\overset{p_A}{\leftarrow}P\overset{p_B}{\rightarrow}B$ が存在して、次の性質を満たすものである。任意の対象 $X$ と任意のペア $(f: X\to A, g: X\to B)$ に対して、ある射 $h: X\to P$ がただ1つ存在して、 $f = p_A\circ h$ と $g = p_B\circ h$ が成り立つ。

$A$ と $B$ の積 $P$ はただ1つしか存在しない。したがって $P$ を $A\times B$ と書ける。

双対積は積の双対である。

$\textbf{Set}$ において積はカルテジアンプロダクトである。

ブール代数 $B$ を1つの圏とみなすと $a,b\in B$ に対して、 $a$ と $b$ の積は $a$ と $b$ の下限(infimum) $a\land b$ であり、 $a$ と $b$ の双対積は $a$ と $b$ の上限(supremum) $a\lor b$ である。

Exercise 1: $A\cong 1\times A$

Exercise 2: $A\times B\cong B\times A$

Exercise 3: $A\times(B\times C)\cong (A\times B)\times C$

イクアライザー(Equalizers)・コイクアライザー (Coequalizers)

射 $A\overset{f}{\underset{g}{\rightrightarrows}}B$ とする。 $f$ と $g$ のイクアライザーとは対象 $E$ と射 $e:E\to A$ を持ち、それは次の性質を満たす。 $f\circ e = g\circ e$ であり、任意の対象 $X$ と任意の射 $h:X\to A$ に対して、 $f\circ h = g\circ h$ ならば、 $h = e\circ k$ となるただ1つの射 $k: X\to E$ が存在する。

コイクアライザーはイクアライザーの双対的な概念である。

Exercise 1: イクアライザーはモノモルフィズムである。

プルバック(Pullbacks)・コプルバック(Copullbacks)

射 $A\overset{f}{\rightarrow}C\overset{g}{\leftarrow}B$ とする。 $f$ と $g$ のプルバックとは、ある対象 $P$ と射 $A\overset{p_1}{\leftarrow}P\overset{p_2}{\rightarrow}B$ が存在して、次の性質を満たす。 $f\circ p_1 = g\circ p_2$ であり、さらに任意の対象 $X$ と任意の射 $h:X\to A, k:X\to B$ のペアに対して、 $f\circ h = g\circ k$ ならば、 $h = p_1\circ l$ と $k = p_2\circ l$ が成り立つ射 $l:X\to P$ がただ1つ存在する。

f:id:yoheiwatanabe0606:20170919013546p:plain

コプルバックはプルバックの双対的な概念である。

いくつかの定理がある。

プルバックは重要である。

特別な射(arrows)

同型(Isomorphisms)・セクション(Sections)・リトラクション(Retractions)

$A\overset{r}{\underset{s}{\rightleftarrows}}B$ が $r\circ s = 1_B$ を満たしているとする。このとき、 $s$ をセクションと言い、 $r$ をリトラクションと言う。さらにセクション $s$ がリトラクションでもあるとき、つまり、 $s\circ r = 1_A$ であるとき、 $s$ はアイソモルフィズム(同型写像)であると言う。

セクションはスプリット・モニックとも言い、リトラクションはスプリット・エピックとも言う。つまり、セクションならばモノモルフィズムであり、リトラクションならばエピモルフィズムである。したがって、アイソモルフィズム(同型写像)はバイモルフィズムである。

モノ(Mononorphisms)・エピ(Epimorphisms)・バイモルフィズム(Bimorphisms)

射 $f:A\to B$ とする。 $f$ がモノモルフィズムであるとは任意の対象 $C$ と任意の射のペア $C\overset{g}{\underset{g}{\rightrightarrows}}A$ に対して、 $f\circ g = f\circ h$ ならば、 $g = h$ が成り立つことである。

エピはモノの双対的な概念である。バイモルフィズムとはモノかつエピであることである。

$\textbf{Set}$ においてはアイソモルフィズムとバイモルフィズムは同じである。つまりモノはセクションでもあり、エピはリトラクションでもある。

しかし一般的な圏においてはそうとは限らない。

特別な圏

一般的な圏よりもより豊かな圏がある。いくつかある中で論理学やコンピューター・サイエンスにおいて重要なのはCartesian Closed Categoryとトポス(Topos)である。

CCC(Cartesian Closed Categories)

エクスポネンシャル(Exponentials)

$A$ と $B$ を或る圏 $\textbf{C}$ の対象とする。 $A$ による $B$ のエクスポネンシャルとは、或る対象 $I$ と或る射 $e:I\times A\to B$ が存在していて、それは次の性質を満たす。任意の対象 $C$ と任意の射 $f: C\times A\to B$ に対して、射 $\bar{f}: C\to I$ がただ1つ存在して、 $f = e\circ \bar{f}\times 1_A$ が成り立つ。

エクスポネンシャルは同型写像の限りでただ1つである。 $I = B^A$ と書き、 $e = \textrm{ev}_{A,B}: B^A\times A\to B$ と書く。

$A$ による $B$ のエクスポネンシャルは次のようにも言える。つまり、それはコンマ圏 $(\overline{\,\,\,\,\,}\times A)\Rightarrow B$ の終対象である。

エクスポネンシャルにはその名の通りExponentialの性質を満たしている。つまり、

(1): $A^X\times A^Y\cong A^{X + Y}$ ( $a^x\times a^y = a^{x+y}$ )

$A^0\cong 1$ ( $a^0 = 1$ )

(2): $(A^X)^Y\cong A^{X\times Y}$ ( $(a^x)^y = a^{x\times y}$ )

$A^1\cong A$ ( $a^1 = a$ )

(3): $(A\times B)^X\cong A^X\times B^X$ ( $(a\times b)^x = a^x\times b^x$ )

$1^X\cong 1$ ( $1^x = 1$ )

圏 $\textbf{C}$ がCartesian Closed Category(CCC)であるとは、すべての有限積とエクスポネンシャルをもつ圏のことである。ここでは終対象 $1$ も含まれている。

$\textbf{Set}$ において、 $B^A = \{ g:A\to B\}$ および $\textrm{ev}_{A,B}(a, g) = g(a)$ 。ここで $\textrm{ev}_{A,B}: A\times B^A\to B$ であり、 $g\in B^A$ である。

ブール代数はCCCである。 $b^a:= \lnot a\lor b$ と定義すれば、 $b^a$ はエクスポネンシャルである。つまり任意の元 $c\in B$ と射 $c\land a\leq b$ に対して、 $c\leq b^a$ と $b^a\land a\leq b$ が成り立つ。

λ-calculi

λ計算はCCCの応用例である。まだ詳しい中身は勉強していない。

トポス(Toposes)

トポスはCCCよりも条件が強い圏である。

サブオブジェクト・クラシファイヤー(Subobject-classifiers)

終対象 $1$ をもつ圏 $\textbf{C}$ を考える。 $\textbf{C}$ のサブオブジェクト・クラシファイヤーであるとは、圏 $\textbf{C}$ の対象 $\Omega$ と射 $\textrm{true}: 1\to \Omega$ のあつまりであり、次の性質を満たす。