プログラミング/圏論入門 の履歴(No.51)

目次†

Reference†

• https://otamusan.github.io/CategoryTheoryIntro/CategoryTheoryIntro.pdf

写像を表す２つの矢印†

• $f:A\to B$ と書くと、これは $f$ は $a\in A$ を受け取って $f(a)\in B$ を返す写像という意味
• $f:a\mapsto 3a$ と書くと、$f$ は $a$ という値を受け取ったら $3a$ という値を返す写像という意味

この形が微妙に違う２つの矢印の使い分けに注意しよう。

「クラス」 について†

圏論では『「要素の集まり」ではあるけれど「集合」とは呼べないもの』を扱うことがある。

これは、ラッセルの逆説として有名な話で「自分自身を含まない集合をすべて集めたもの $R$」を集合であるとすると矛盾が生じる、というようなのが関係している。

• $R$ が自分自身を含まないなら、$R$ は $R$ に含まれるはず？？？
• $R$ が自分自身を含むなら $R$ は $R$ に含まれないはず？？？

どちらも矛盾する。

これは何でもかんでも「要素の集まり」を「集合」と言ってしまうとまずいことが起きうる、ということを示している。

そこで「集合」よりも広い意味で「要素の集まり」と言いたいときの用語として、数学的な専門用語である「クラス(class)」が使われる。これ、数学的に定義をしっかりしようとすると結構ややこしいのだが、基本事項として「クラス」は「集合」と「要素の集まりだが集合とはみなせないもの（真のクラス）」の両方を含む概念。集合はクラスである一方、クラスではあるが集合ではないもの（真のクラスと呼ばれる）が存在する。

以下に出てくる「クラス」という用語は多くの場合「集合のようなもの」という程度の理解でしばらくは読み進められるはず。

有向グラフ†

圏の対象と射を次のような有向グラフで表すとイメージしやすい。

「黒丸」で表されたのが「対象」で、対象同士をつなぐ「矢印」で表されたのが「射」。

ここには $O=\set{A,B,C}$ で３つの「対象」が存在する。

$\mathrm{Hom}(A,B)=\set{d, e}$ が $A$ から $B$ へ向かう矢印の集合と考えると、

• $\mathrm{Hom}(A,A)=\set{a}$
• $\mathrm{Hom}(B,B)=\set{b}$
• $\mathrm{Hom}(C,C)=\set{c}$
• $\mathrm{Hom}(A,B)=\set{d, e}$
• $\mathrm{Hom}(B,A)=\set{}$
• $\mathrm{Hom}(B,C)=\set{f}$
• $\mathrm{Hom}(C,B)=\set{}$
• $\mathrm{Hom}(A,C)=\set{g,h}$
• $\mathrm{Hom}(C,A)=\set{}$

である。

射が向きを持つこと、ある対象から同じ対象へ戻る射 (例：$a,b,c$) が許されること、に注意せよ。

ただし、任意の有効グラフが圏を構成するわけではない。

射（矢印）が下で述べる公理を満たすときはじめて圏になる。

Set 圏 = すべての集合とすべての写像が作る圏†

始めて圏論を学ぶ際には、「射」の実体として「写像」を思い浮かべると理解しやすい。

写像 $f:A\to B$ は任意の $x\in A$ に対して $f(x)\in B$ となる値を計算するための規則（関数）であった。
$A$は始域、$B$は終域と呼ばれる。

上で射とされた $a,b,c,\dots,h$ がそれぞれ個別の写像であり、
$A,B,C$ はそれらの始域や終域となるクラス（集合）であると考える。

これは実際、かなりメジャーな圏の構成である。

特に、$O$ を「すべての集合を集めたクラス」とし（これは真のクラスになる）、
$\mathrm{Hom}$ を２つの集合の間に考え得る「すべての可能な写像の集合」（こちらは集合になる）
とする圏には Set 圏という名前がついていて、圏の代表例として良く参照される。

Set において圏の公理は以下のように解釈される。

• 射の合成可能性： 写像 $f:A\to B,\ g:B\to C$ を合成すると $g\circ f:A\to C$ が得られる
• 射の合成の結合則： 写像の合成は結合則を満たす
• 射の合成の単位元： 「恒等写像 $x\mapsto x$」をほかの写像と合成しても写像を変化させない

特に１番目と３番目の公理については Set が「考え得るすべての写像」を含んでいる、 という前提からすぐに従う。

ただし、

1. 全ての集合を含んでいること
2. すべての可能な写像を含んでいること

の２つは非常に強い条件なので、これらを緩めて作った「適当な集合＋適当な写像の圏」や「その他の一般の圏」では Set で成り立つ定理がなりたたない場合も多いことに注意が必要である。
（テキストが暗黙に Set を仮定していることがしばしばあったりするので）

射の合成とその公理†

射の合成は、
任意の $f\in\mathrm{Hom}(A,B),g\in\mathrm{Hom}(B,C)$ の順序対 $(f,g)$ を
ある $h\in\mathrm{Hom}(A,C)$ と結び付ける写像である： $(f,g)\mapsto h=g\circ f$

これは圏が射の合成に対して閉じていることを言っている

　　→ $f:A\to B,\ g:B\to C$ があるならそれらを合成した $g\circ f: A\to C$ が圏の中に必ず存在する

圏の公理はこの「合成」に対して以下の２つを要求する：

1. 射の合成に結合則が成り立つ
   　　→ 任意の $f:A\to B,\ g:B\to C,\ h:C\to D$ に対して
   　　$(h\circ g)\circ f=h\circ (g\circ f)$ が常に成り立つ
   　　ここから括弧なしの $h\circ g\circ f$ が一意に定義される
   &uml( (C)->(D):h (A)->(B):f (B)->(C):g B->D:h◦g A->C:g◦f );
   
   
2. 任意の対象 $A$ が恒等射（射の単位元）$1_A$ を持つ
   　　→ 恒等射は任意の $f:A\to B,g:C\to A$ に対して $f=f\circ 1_A, g=1_A\circ g$ を満たす
   &uml( (C)->(A):1◦g (A)-->(B):f◦1 (A)->(B):f A->A:1 C->A:g );

したがって、上の図の系が圏であるためには、

• $a=1_A$
• $b=1_B$
• $c=1_C$
• $g=f\circ d$ または $h=f\circ d$
• $g=f\circ e$ または $h=f\circ e$

であることが要求される。

このような記述で出てくる等号 "=" は、集合の要素としての「同一性」を意味する。

• $h=g\circ f$ は、「射の合成」という写像が「$(f,g)$ のペア」を、圏の中に存在する「$h$ という射そのもの」に移すこと、を表す。
• $(h\circ g)\circ f=h\circ (g\circ f)$ はどちらの経路で合成しても、合成結果が同じ射に重なること。
• $f=f\circ 1_A, g=1_A\circ g$ も、合成結果が自分自身そのものであること。

を表す。「計算結果が等しい」ではなく「移された先が同一」であることを当然と思えると良い。

圏を有向グラフのように表すと、合成は「矢印の継ぎ足し」としてイメージされるが、
合成先の $\mathrm{Hom}(A,C)$ が複数の射を持つ場合には、そのうちどちらに移されるか、
つまり、$g=f\circ d$ なのか $h=f\circ d$ なのか、ということまでがきっちりと定義されていることと
その定義の上で、合成の結合法則と単位射の存在が保証されていることの意味を正しく思い浮かべる必要がある。

対象の内部構造に踏み込まず、射の性質のみで公理化する†

恒等射が「要素を変更しない」のような要素レベルの言葉ではなく、
「別の射と合成したときに変化させない」のように射レベルの言葉で定義されていることに注意せよ。

このように圏論では対象の内部構造に踏み込まず、あくまで射と合成の関係のみを議論する。

圏論における「恒等射」は要素を変え得る†

そして、要素レベルの定義と、射レベルの定義とが
決定的に異なる結果を生む場合があることにも注意が必要だ。

最も顕著な例として、唯一の対象 $A$ へ出入りする射が恒等射 $e$ しかない非常に小さな圏を考える。 $$ \mathcal C(\set{A}, \set{\mathrm{Hom}(A,A)=\set{e}\, }) $$ このとき上の３つの公理は実質的に「恒等射が冪等であること $e\circ e=e$」しか求めない。

1. $e\circ e=e$ であれば圏は合成に対して閉じている
2. $(e\circ e)\circ e=e\circ (e\circ e)=e$ は結合則を満たす
3. 任意の $f:A\to B$ や $g:B\to A$ というのが $e$ しかないので恒等性も $e\circ e=e$ しか要求しない

恒等射に「要素を変えない」という要請が与えられないのだ。

例えば 「ゼロを掛ける」 や 「何らかの射影」 のような写像は冪等だ。
つまり実際にはそのような「要素を変化させる射」が「恒等射」とみなされうるのである。

他の射との合成で「本当は恒等でない」という事実が「ばれない」限り、それは恒等と見なされる。

射の合成のみで議論を進める圏論ではこういうケースがそこここに出てくることに注意せよ。

繰り返しになるが、圏論は対象の中身が何であるか、射の実体は何であるか、 とは切り離して、あくまで射の合成のみを扱う代数なのである。

「恒等射」はその名前に反して「合成の単位元」であることしか要求されていないことに注意せよ。

恒等写像は対象あたり高々１つしか存在しない†

「射と合成の関係のみを議論する」だけでも色々なことが分かる、という例として、

上記の射の合成の公理から、
ある対象 $A$ の上の恒等写像は高々１つだけであることを導こう。

$1_A:A\to A,1'_A:A\to A$ がどちらも $A$ の恒等写像であるとする。
このとき $1_A=1_A\circ 1'_A=1'_A$ であるから両者は一致する。

始対象†

Q: ある圏に始対象 $0$ があったとして、そこからある１つの対象 $A$ に対する一意な射　$f:0\to A$ を取り除いてしまったら $0$ はそれだけで始対象ではなくなるのか？

A: 定義上はそのとおりだが、「その射だけを取り除く」というわけにいかない場合が多いのため、そこには注意が必要だ。
$g: B\to A$ のような射が存在する場合には、$0\to B\to A$ の合成経路が存在するため、$f$ のみを取り除くことができない。$0$ および $A$ 自身以外から $A$ への射が一切存在しないときに限って $f$ を取り除くことができる。

そして、始対象の定義は「任意の対象に対して」一意な射を持つことなので、そのような射が１つでも欠落してしまえば始対象の資格を失う。

&uml( (0)-->(A):取り除けない (0)-->(B) B->A ); &uml( (始対象じゃない)-[dotted]->(A):取り除いた (始対象じゃない)-->(B) (始対象じゃない)-->(C) (始対象じゃない)-->(D) );

終対象は情報を媒介しない†

終対象へ入る射は、任意の射の後ろに合成した際の結果が定数になるという著しい性質を持つ。

終対象を 1 と書いて、これを見てみよう。

任意の対象 $A,B$ と $f,g: A\to B$
終対象への一意な射 $!_A: A\to 1,!_B: B\to 1$ を考える。

$f,g$ と $!_B$ とを合成した $!_B\circ f$ と $!_B\circ g$ はどちらも $A\to 1$ の射であるが、
$1$ が終対象であるなら $\mathrm{Hom}(A,1)$ は一意な射 $!_A$ しか含まないから、 $$!_B\circ f=\,!_B\circ g=\,!_A$$ でなければならない。

&uml( (A)->(B):f (A)->(B):g (B)->(1):" !B" (A)->(1):" !A" );

元がどんな $f,g$ であったとしても、そこに $!_B$ を継ぎ足すと「区別がつかなくなってしまう」のだ。

Set の $1=\set{()}$ では、$f:A\to 1$ は任意の $a\in A$ を唯一の値 $()$ に映すしかなく、もと値 $a$ がどんな値であったかという情報が失われる、という構造だった。

話を一般の圏に戻せば、射や対象の「中」で何が起きているかを見ずとも、
終対象という構造だけから、$1$ を経由する射の合成結果が
（$1$ に入るまでの部分を $!$ に書き換えることができるため）
$1$ 以前の合成の情報を失うことを結論できるのである。

$$ \begin{aligned} &A\underbrace{ \xrightarrow{f_1} B\xrightarrow{f_2} C\xrightarrow{!_C}}_{!_A} 1\xrightarrow{f_3} D\xrightarrow{f_4} E\\[5mm] =\,&A \hspace{11mm} \xrightarrow{!_A} \hspace{11mm} 1\xrightarrow{f_3} D\xrightarrow{f_4} E\\ \end{aligned} $$

零対象の例†

例えばベクトル空間を対象とし、線形変換を射とする圏において、

• ゼロ次元空間 $\set{0}$ から任意の線形空間への線形変換は $0\mapsto 0$ の1種類しかない
• 任意の線形空間からゼロ次元空間 $\set{0}$ への線形変換は $v\mapsto 0$ (すべてを $0$ に移す) の1種類しかない
  したがってゼロ次元空間 $\set{0}$ は零対象である

このように零対象が意味を持つ圏では、ゼロ元あるいは単位元のみからなる集合が零対象になることが多い。

このとき、任意の $A\to 0\to B$ のような写像は元の $A$ にあった情報を捨てて $B$ のゼロ元に移るという顕著な性質を持つ。

Set の時と異なり、始対象から任意の対象への射は「空射」ではなく、$0$ 元を $0$ 元に移すという実在する射であることにも注意しよう。

始対象・終対象は存在するなら同型を除いて一意である†

言い換えると、始対象同士・終対象同士はお互い同型ということ。

なぜなら、
例えば $0,0'$がどちらも始対象であれば、

• $a:0\to 0'$
• $b:0'\to 0$
• $c:0\to 0$
• $d:0'\to 0'$

としてそれぞれの Hom に一意な射が存在するから、

• $b\circ a:0\to 0$ は $c$ に等しく、
• $a\circ b:0'\to 0'$ は $d$ に等しく、
• さらにどちらも恒等射に等しい。

すなわち $a,b$ は互いに逆射である。

&uml( (0)-->(0'):a (0')-->(0):b (0)->(0):c = 1 = b◦a (0')->(0'):d = 1 = a◦b );

で、実はまだ「対象同士の同型」の概念を定義していなかったのであるが、
「逆射を持つ対象を同型と呼ぶ」というのが次の話。

定理：同型な対象は、周囲の対象と必ず同じ本数の射で結ばれている†

$A,B$ が同型であり、その同型写像を $f:A\to B, f^{-1}:B\to A$ としよう。

ある $C$ に対して、

• $g:C\to A$ が存在するなら、それに対応して $f\circ g:C\to B$ が必ず存在する
• $h:A\to C$ が存在するなら、それに対応して $h\circ f^{-1}:B\to C$ が必ず存在する

このように、「同型であること」と「射の合成が常に可能であること」との組み合わせにより、
同型な対象は圏の中に「とてもよく似た構造」を持つことになる。

&uml( (A)-r-->(B):f (B)-l-->(A):f^-1 (A)--->(C) (A)-->(C) (B)-->(C) (B)-->(C) (C)-u->A (C)-u->B (A)--->(D) (A)--->(D) (B)--->(D) (B)--->(D) );

もう少しちゃんと書くなら、全単射

• $f\circ -:\mathrm{Hom}(C,A)\to\mathrm{Hom}(C,B)$
• $-\circ f^{-1}:\mathrm{Hom}(A,C)\to\mathrm{Hom}(B,C)$

により

• $\mathrm{Hom}(C,A)$ と $\mathrm{Hom}(C,B)$
• $\mathrm{Hom}(B,C)$ と $\mathrm{Hom}(A,C)$

の間に上への一対一対応が生まれる、ということ。

例えば、 $f\circ -:\mathrm{Hom}(C,A)\to\mathrm{Hom}(C,B)$ が全単射であることは次のように示される。

単射性： 任意の $g,g'\in \mathrm{Hom}(B,C)$ に対して $f\circ g=f\circ g'$ であるとすると、両辺に左から $f^{-1}$ をかけて、 $$ \begin{aligned} &f^{-1}\circ f\circ g=1_A\circ g=g\\ =\,&f^{-1}\circ f\circ g'=1_A\circ g'=g' \end{aligned} $$ すなわち $g=g'$ であるから単射。

全射性: 任意の $h\in\mathrm{Hom}(C,B)$ に対して $f^{-1}\circ h\in\mathrm{Hom}(C,A)$ が存在し、 $$f\circ (f^{-1}\circ h)=1_B\circ h=h$$ を満たすから全射。

その実体は？†

そこで仮定される

• すべての集合から唯一の射が伸びる終対象 $1$
• そこから任意の元を生成する定数写像

これらの「実体」は何なのか？

そんなものを持つなんて、まれなケースじゃないの？

と考え始めると悩むことになるのだが、

• $1$ の唯一の元は null あるいは概念的な「無」を表す
• $1\to A$ は無から任意の要素を作るコンストラクタ
• $A\to 1$ は任意の要素を無に帰すデストラクタ

と思えば、現実世界の集合＆写像を圏の世界に写し取る際に、
「個々の要素を手に取る」「それを捨てる」という「概念」あるいは「操作」自体を
圏に持ち込んだのが $1$ である、と理解できるはずだ。

集合では「個々の要素について議論可能」という概念そのもの、ということ。

そしてそれを持ち込む理由は、通常なら対象の中身に踏み込めない圏論に 「個々の要素について議論可能」という能力を付加するためだ。

圏論はあくまで射のみを議論し、対象の内部構造には踏み込まない、という建前を崩さないまま、 集合の元をこっそり射に写し取っておくことで、実は集合の元を直接あつかう、 という圏論の本性がここに出る。

well-pointed や separator の概念との違い†

圏論には well-pointed や separator という概念があって、
これは $\mathrm{Hom}(1,A)$ が「異なる射を区別するのに十分なだけの生成射」を含む
を意味する。

これと上の、「$A$の要素をすべて生成可能」とは異なる概念なので注意しよう。

現実世界に存在する「具体圏」に、任意の集合からデストラクタが向かう先である「終対象 $\set{\text{無}}$と、コンストラクタ $\mathrm{Hom}(\set{\text{無}},A)$ を加えて、 要素そのものをいじれる圏を構成する手法については、 入門的な文章においてあまりしっかり説明されないにもかかわらず、 暗に仮定した話をしてしまうようなことも見受けられるみたい？

以下ではそういう圏を「コンストラクタ付きの圏」などと言うことにする。

圏論を実世界と対応させるときには非常に大事な部分なはずなので見落とさないようにしたい。

積 (product) $A\times B$†

対象$A,B$の**積**とは、下記の公理を満たす3点セット $(A\times B,p,q)$ のこと。

• 対象 $A\times B$ = $A,B$ の直積$(A,B)$の集合をイメージ
• 射 $p:A\times B \to A$ （第1射影） = $(A,B)$ から $A$ を取り出す射影をイメージ
• 射 $q: A\times B \to B$ （第2射影） = $(A,B)$ から $B$ を取り出す射影をイメージ

公理：
任意の対象$C$と、任意の射の組 $f: C\to A$、$g: C\to B$ に対して、
ただ1本の射 $h: C \to A\times B$ が存在して、
$p\circ h = f$ かつ $q\circ h = g$ を満たす。

$f,g$ を決めれば１つ決まるこの $h$ は $h=\langle f,g\rangle$ あるいは $p,q$ を明示して $h=\langle f,g\rangle_{p,q}$ と書かれる。

公理は $h$ が存在することと、それが一意であることの２つを要求している。

このうち一意性については $h=\langle p\circ h,q\circ h\rangle_{p,q}$ とも書ける($\because p\circ h = f, q\circ h = g$) ことに注目しよう。まず、$A\times B$ に入る任意の射 $h$ に対して、それと $p,q$ とを合成すれば $f=p\circ h,g=q\circ h$ を作ることは必ずできる。それらに積の公理を適用すると、対応する射は始めに仮定した $h$ のみであり、他には存在しない、と読み下せると良い。

考えているストーリーは以下のようなもの：

• 要素 $\gamma\in C$ を入力として $f,g$ により $\alpha=f(\gamma)\in A,g(\gamma)\in B$ を得る
• それらをまとめて一旦 $\big(f(\gamma),g(\gamma)\big)\in A\times B$ に入れておく
• $f,g$ した後まとめる演算が $h:\gamma\mapsto\big(f(\gamma),g(\gamma)\big)$
• $\big(f(\gamma),g(\gamma)\big)\in A\times B$ から $p:(\alpha,\beta)\mapsto\alpha,$ $q:(\alpha,\beta)\mapsto\beta$ により $A,B$ の元を取り出すと $f,g$ を再現できる

そこからどうして上の公理が出てくるのか？
$C,f,g$ を仮定すると唯一の$h$が決まる、というのはどういうことか？

公理が言っているのは $A\times B$ からの取り出し方法 $p,q$ が与えられているとき、
正しく取り出せるような入れ方 $h$ が１つだけ存在する、ということ

これにより「取り出したもの $p(\cdot),q(\cdot)$」から
「入れたもの $\big(f(\gamma),g(\gamma)\big)$」を再現できるという事実を保証するのである。

この条件が「任意の」$(C,f,g)$ に対して成立する、というのは重要である。
これは $(A\times B,p,q)$ だけでなく圏自体に対する強い制約になる。
$h$ が圏に含まれないような $(C,f,g)$ があってはならない。

余積 (coproduct) $A+B$†

余積は積と双対関係にある構造である。互いに双対関係にあるペア、と言う意味で co- の接頭辞がつく。この定義は積の定義の矢印方向および合成順序をひっくり返して得られる。

対象$A,B$の**余積**とは、下記の公理を満たす3点セット $(A+B,p,q)$ のこと。

• 対象 $A+B$
• 射 $p:A\to A+B$ （第1射影）
• 射 $q: B\to A+B$ （第2射影）

公理：
任意の対象$C$と、任意の射の組 $f: A\to C$、$g: B\to C$ に対して、
ただ1本の射 $h: A+B\to C$ が存在して、~ $h\circ p = f$ かつ $h\circ q = g$ を満たす。

この $h$ を $h=[f,g]_{p,q}$ と書く。

&uml( (C)-->(AxB):〈f,g〉 (AxB)-r->(B):q (AxB)-l->(A):p C-->A:f C-->B:g ); &uml( (C)<--(A+B):" [f,g]" (A+B)<-r-(B):q (A+B)<-l-(A):p C<--A:f C<--B:g );

積と余積とデータ構造†

• タプルやレコードは複数のデータ型の直積であり、圏論の積の構造を持つ
• タグ付きユニオン型（discriminated union、例えば`{tag:"A",value:A}|{tag:"B",value:B}`）は複数のデータ型の直和であり、圏論の余積の構造を持つ
  • TypeScriptの素朴なユニオン型`A|B`は、AとBの構造が重なっていると由来の判別ができなくなる場合があり、その場合は余積にならない点に注意が必要
  • python なら値自体が型情報を持っているからそれ単体で直和が表現される

このあたりのデータ構造は比較的単純だが、リストやツリーでは再帰的に型が定義され、単純な積や余積には見られない構造を持つ。これらを議論する準備として、以下では関手や不動点について学ぶ。

Cat 圏†

関手を圏から圏への射であると捉え、圏と関手が作る構造を扱うのが Cat 圏の考え方である。

Cat 圏の定義：

• 対象は 任意の「小さな」圏
• 射は ２つの圏を結ぶことが可能なすべての関手

関手 $\mathcal F:\mathcal C\to\mathcal D$ と $\mathcal G:\mathcal D\to\mathcal E$ の合成 $\mathcal G\circ\mathcal F$ は、$\mathcal C$ を $\mathcal F$ で移して作られる部分圏 $\mathcal F(\mathcal C)\in \mathcal D$ をさらに $\mathcal G$ で移して $\mathcal G(\mathcal F(\mathcal C))$ を作る関手と考えればよい。この変換が関手となることはほぼ自明だろう。

Catの対象が任意の「小さな」圏と書かれているのは、ここを「任意の圏」としてしまうと、Cat自体が圏なので、自分を含む圏になってしまい、話がややこしくなるためだ。ここからはみ出す話はここではしない。大きな圏を含む場合は CAT と大文字で書かれるらしい。

同型関手†

関手 $\mathcal F:\mathcal C\to \mathcal C'$ が逆関手 $\mathcal F^{-1}:\mathcal C'\to \mathcal C$ を持つ、
すなわち $\mathcal F\circ \mathcal F^{-1}$ や $\mathcal F^{-1}\circ \mathcal F$ が恒等写像になるように $\mathcal F^{-1}$ を構成できるとき、
関手 $\mathcal F$ は同型関手であり、２つの圏 $\mathcal C$ と $\mathcal C'$ は同型である、と言う。

逆関手が存在する条件は、通常の写像と同様に関手$\mathcal F$が全単射であること、
すなわち $\mathcal F_o,\mathcal F_m$ がどちらも全単射であることと同値である。
(どちらも集合から集合への写像であることに注意せよ)

このうち射の写像$\mathcal F_m$については特別に、

写像 $\mathcal F_m$ が $\mathrm{Hom}(A,B)\to \mathrm{Hom}'(\mathcal F_o(A),\mathcal F_o (B))$ の写像として

• 単射であることを 忠実
• 全射であることを 充満

というように 忠実 および 充満 の語が定義されている。
「充満忠実な関手 $\mathcal F$」とは、その射に対する写像 $\mathcal F_m$ が全単射であることと同値である。

関手$\mathcal F$が全体として全単射であるためには充満忠実に加えて対象の写像 $\mathcal F_o$ が全単射である必要があるから、以下が同値となる。

（関手$\mathcal F$が同型関手) = （関手$\mathcal F$が逆写像を持つ) =
(関手$\mathcal F$が全単射) = (充満忠実 = $\mathcal F_m$ が全単射) + ($\mathcal F_o$ が全単射)

関手は対象の同型性も保つ†

関手が射の合成と恒等射を保つことから、対象の同型性をも保つことが導かれる。

「同型な対象」とは両者の間に射と逆射のペアが定義された２つの対象のことであった。
集合を対象とする圏なら、集合の要素の間に全単射による一対一対応がある状況を思い浮かべると良い。

同型な対象 $A\cong B$ の間の同型写像を $f,f^{-1}$ とすると、
$f\circ f^{-1}=1$ および $f^{-1}\circ f=1$ の関係が関手 $\mathcal F$ により保存されるため、

移された先において $\mathcal F(A)$ と $\mathcal F(B)$ とが互いに逆射の関係にある同型写像 $\mathcal F(f), \mathcal F(f^{-1})$ により結ばれることになる。

これは $\mathcal F(A)\cong \mathcal F(B)$ を表す。

自己関手†

圏を自分自身の上へ移す関手のこと。 $$ \mathcal F: C\to C $$

自己関手を思い浮かべると、関手が「新しい圏を生成するもの」ではなく、
「既存の圏の中に元の圏を写した像を見つけるもの」であることを理解しやすい。

$C$ の像 $\mathcal F(C)$ は $C$ の上の部分圏になる。

つまり、自分を自己関手 $\mathcal F$ で移した像 $\mathcal F(C)$ は、
あくまで「元々自分が持っていた構造の一部」なのだ。

これは一般の関手でも同じだ。
関手には必ず「終域」が決まっている。
関手で圏を写した像は、必ず終域となる圏が「もともと持っている構造の一部（部分圏）」なのだ。

具体例：リスト関手†

例えば、プログラム上の型を対象として、関数を射とする圏において、型 $A,B$ と射 $f:A\to B$ があるとしよう。

リスト関手$\mathcal F$ は任意の型をその型を要素とするリストに変換し、任意の射をリストを受け取り、個々の要素に射を適用して結果のリストを返す射に変換する。

• $\mathcal F_o(A)=\mathrm{List}\langle A\rangle$
• $\mathcal F_o(B)=\mathrm{List}\langle B\rangle$
• $\mathcal F_m(f)=(\mathrm{list}: \mathrm{List}\langle A\rangle)=>\mathrm{list.map}(f)$
• $\mathcal F_m(1_A)=1_{\mathrm{List}\langle A\rangle}$
• $\mathcal F_m(1_B)=1_{\mathrm{List}\langle B\rangle}$

みたいな。

このリスト関手 $\mathcal F$ は確かに任意の $A,B,f$ からなる小さな部分圏を $\mathrm{List}\langle A\rangle, \mathrm{List}\langle B\rangle, \mathcal F_m(f)$ からなる別の圏構造へその構造を保ったまま移す写像になっている。

圏が十分に広い範囲の射を含むケースにおいて、
この関手は忠実である: $f\ne g$ に対して $\mathcal F_m(f)\ne \mathcal F_m(g)$ が成り立つ
この関手は充満ではない： 各要素に同一の関数を当てはめる以外のずっと多くの射、例えば要素の入れ替えなどが考えられ、$\mathcal F_m(f)$ はそれらを覆いつくさない。

忠実性や充満性は圏がどういう射を含んでいるか次第であることには注意が必要だ。そもそも $f\ne g$ となるような射が存在しないなら $\mathcal F_m$ をどう定義したところで忠実。リスト間に適用可能な関数が map しか与えられていないなら充満になりうる。

準備：積圏†

２つの圏$\mathcal{C}$と$\mathcal{D}$から、新しい圏$\mathcal{C}\times\mathcal{D}$（積圏）を以下のように作る。

• 対象：$\mathcal{C}$の対象$c$と$\mathcal{D}$の対象$d$のペア $(c,d)$
• 射：$(c,d)\to(c',d')$は、$\mathcal{C}$の射$f\colon c\to c'$と$\mathcal{D}$の射$g\colon d\to d'$のペア$(f,g)$
• 合成：成分ごとに合成する。$(f',g')\circ(f,g)=(f'\circ f,\ g'\circ g)$
• 恒等射：$(c,d)$の恒等射は$(1_{\mathcal C},1_{\mathcal D})$

2つの圏を「横に並べて、対象も射もペアにしただけ」のもの。

双関手†

双関手は２つの圏から１つの圏への写像であるが、
つまり積圏を始域とする通常の関手とみなすこともできる。

$\mathcal C\times \mathcal D\to \mathcal E$

積の双関手†

分かりやすい例は積の双関手。
この場合には $\mathcal C=\mathcal D=\mathcal E$ として、
任意の対象 $A,C$ とその間の射 $f:A\to C$
任意の対象 $B,D$ とその間の射 $g:B\to D$^ を考える。

さらにこの圏が $A\times B$ および $C\times D$ の積構造を含んでいるとして次のような絵を描くと、ここから下記の形の「積の双関手」を抽出できる。

$\mathcal F_o(A,B)=A\times B$
$\mathcal F_o(C,D)=C\times D$
$\mathcal F_m(f,g)=(a, b)\mapsto(f(a), g(b))$ これは $(A\times B)\to(C\times D)$ の写像

積構造 $A\times B$ および $C\times D$ には $A,B,C,D$ との間の射の存在が含まれているため、始めに $\mathcal C=\mathcal D=\mathcal E$ を仮定したのであった。

積の双関手は $\mathcal C\to\mathcal C\times\mathcal C\to\mathcal C$ のように、自己関手となる。
積構造を含む圏 $\mathcal C$ に存在する構造を浮き彫りにしたものとみなせる。

余積の双関手†

同様に余積の双関手も作れる。
$\mathcal F_o(A,B)=A+B$
$\mathcal F_o(C,D)=C+D$
$\mathcal F_m(f,g)=A\text{の元なら} f \text{を、} B\text{の元なら} g \text{を適用}$ これは $(A+B)\to(C+D)$
これも余積の構造に付随して初めから存在する構造に名前を付けたものとみなせる。

これら積の双関手や余積の双関手の後ろに通常の（単項の）関手をつなぐことで、バラエティ豊かな一般の双関手を構成可能である。

反変関手・共変関手†

関手の $\mathcal F_m$ が射の向きをすべて逆転させるとき、反変関手という
今まで考えていた射の向きを保つ普通の関手は 共変関手という

$\mathcal C$ の反変関手による変換は $\mathcal C^{\mathrm{op}}$ の共変関手による変換と見做せる

プロ関手†

第1引数 $\mathcal C$ に反変、第2引数 $\mathcal D$ に共変な、Set圏を終域とする双関手をプロ関手という $$\mathcal C^{\mathrm{op}}\times\mathcal D\to\mathrm{Set}$$ なぜこんなものを考えるのか？

元々やりたいのは、

• $\mathcal C$ の射 $f_{ab}:A\to B$
• $\mathcal D$ の射 $f_{cd}:C\to D$

を元にして、

$f_{bc}:B\to C$ の前後に $f_{ab},f_{cd}$ を継ぎ足して $f_{ad}:A\to D$ に変換する射を生成するようなこと $$f_{bc}\mapsto f_{cd}\circ f_{bc}\circ f_{ab}=f_{ad}$$ $f_{cd}\circ f_{bc}\circ f_{ab}$ の接続により $A\to B\to C\to D$ として正しく計算可能になる。

この接続の演算は対象「$B\to C$ の任意の関数」から「対象 $A\to D$ の任意の関数」への射である。

これを 対象のペア $(B,C)$ から対象のペア $(A,D)$ への射 $(f_{ab}^{\mathrm{op}}, f_{cd})$ から生成する関手を考えているのだ。

変換先で必要となる情報が、正しく変換元から与えられていることを確認できる。

プロ関手で片側のみ双対をとる必要が生まれるのは、$(A,C), (B,D)$ ではなく、$A,B$ をひっくり返した $(B,C),(A,D)$ のペアを作りたいから、であることが分かるはずだ。

プロ関手はこれを一般化した、
$\mathcal C^{\mathrm{op}}\times\mathcal D\to\mathrm{Set}$ の形を満たす変換のことなので、
以下の形をテンプレートとすると理解しやすい。

Hom関手†

圏 $\mathcal C(O, \mathrm{Hom})$ から射の集合 hom を取り出す関手で、これは $\mathcal C$ 同士の間のプロ関手になる。 $$\mathcal C^{\mathrm{op}}\times\mathcal C\to \mathrm{Set}$$ 上の表を使うと関手の変換は以下のように理解できる。

プロ関手の説明で「こういうことがしたい」とかいていたものそのままが Hom 関手と思ってOK。

実はこれまで $\mathrm{Hom}(A,B)$ と書いていたものは
元の圏の対象 $A,B$ を Hom 関手で移した対象そのものだったのだ。

その意味するところ†

関数対象$A\Rightarrow B$とは、対象 $A,B$ を含む圏に存在する１つの対象であって、対象$A$から$B$への射の集合そのものであるか、あるいは対象$A$から$B$への射と一対一に対応する要素(個々の射に付けたラベルのようなもの)を集めた集合、であることを想定して作られた存在だ（実際には微妙に異なる形になることもある）。 特定の圏が実際にそういうものを含むかどうか、あるいはそれがどのように射と対応するか、あたりも含めて以下で説明する。

まず、Set圏はすべての集合を対象として含む圏だった。
任意の集合間の写像を集めた hom は集合になるから、
Set圏の任意の hom はそれ自身Set圏に対象として存在する。
だからこれをそのまま関数対象見做せる。

一方、その他の圏では hom 集合自体が対象として存在する保証がないため、関数対象は射自身を集めたものではなく、射と一対一に対応するラベルを集めた集合であっても構わない。

公理化の方針†

以下ではこの「関数対象」に普遍的な公理（要素に言及せず射の性質のみで記述された公理）を与える。実のところ、そのような圏論的な定義は関数対象$A\Rightarrow B$ の内部構造に踏み込まないので、その要素が何であるかという上記のような話は本質的ではなくなる。

またこの公理は「圏の中に関数対象を作り出そう」とするものではない。すでに圏の全体像は決まっているものとして、その圏の個々の対象に対して、その対象が「関数対象$A\Rightarrow B$ と見做せるものであるかどうか」を判別する手段を与えるものである。

この公理、かなり複雑なので順を追って説明する。

公理の実体†

考える関数（射）の始域を $A$、終域を $B$ として、これらは圏に含まれるとする。

関数対象の候補を $Z$ とすると、関数に始域$A$の値を与えて評価し、終域$B$の値を得る手順は、具体的な関数(のラベル) $z\in Z$ と、そこに与える引数 $a\in A$ を受け取って、そこから返り値 $b\in B$ を計算して返すことに相当する。

関数対象の公理ではこの手順を $Z\times A$ から $B$ への射（評価射と呼ばれる） $g:Z\times A\to B$ と同一視するため、そもそも圏に積 $Z\times A$ が含まれないような $Z$ は始めから関数対象の候補から外してしまう。（ある対象が関数対象と見做せるかどうか、という文脈だったことを思い出そう）

一般には関数対象は単なるラベルなので、その評価射 $g$ とセットで初めて演算の内容が定義される。そこで以下では候補探しは $Z,g$ をセットで考える。

$Z\times A$ が存在し、評価射の候補 $g:Z\times A\to B$ が存在すれば、$Z,g$ は関数対象とその評価射の候補になる。そして、ある特定の候補が圏に含まれる任意の候補を下記の意味で「過不足なく生成可能」であるとき、それこそが関数対象$A\Rightarrow B$ および評価射 $\mathrm{eval}$ であるとするのがこの公理である。そのような候補は複数あっても構わないが、それらはすべて同型となるため、関数対象$A\Rightarrow B$は同型を除いて一意に決定される。逆にそのような候補がないとき、その圏には関数対象$A\Rightarrow B$は存在しない。

関数対象とその評価射の候補 $Z',g'$ が別の候補 $Z,g$ から「過不足なく生成可能」とは、
$$g'=g\circ(h\times 1_A)$$ を成り立たせる $$h:Z'\to Z$$ が 「ただ一つだけ」 存在すること、として定義される。

これだけだと難しいので、以下では集合の言葉を使って解釈しよう。

$g'=g\circ(h\times 1_A)$ の意味†

等号で結ばれた２つの射に $(z',a)\in Z'\times A$ を与えると、$$g'(z',a)=g\circ(h\times 1_A)\,(z',a)$$ となる。

• 左辺は $g'$ がそのまま $z'\in Z'$ を使って $a\in A$ を評価する射
• 右辺は $(h(z'),a)$ に変換してから $g$ に渡すという合成射
  つまり $g$ が $z=h(z')$ で $a$ を評価する射

これら２つが等しいという主張。
言い換えれば、$z$ と $h(z')$ が同じ関数を表すということ。

なぜこの条件を $Z,g$ が $Z',g'$ を過不足なく生成可能と言うのか？

過不足なく生成可能†

上の条件を成り立たせる $h$ の存在は、
任意の $z'\in Z'$ に対してそれと一致する関数 $h(z')$ が $Z$ に含まれていることを意味する

そして、そのような $h$ が複数存在するとしたら、
ある $z'\in Z'$ に一致する関数 $h_1(z'), h_2(z'), \dots$ が２つ以上 $Z$ に含まれており、そのうちどれ対応させてもよい、ということになる。すなわち $Z$ 内に同じ関数が複数含まれていることに対応する。

だから、そのような $h$ が「ただ１つ存在する」という主張は任意の $z'\in Z'$ に対して、それと一致する関数が $Z$ にただ一つ含まれている、と読み替えられて、これが候補 $Z',g'$ が別の候補 $Z,g$ から「過不足なく生成可能」の意味である。

すべての候補を過不足なく生成可能†

すべての候補を「過不足なく生成可能」な $Z,g$ が見つかったならそれらを $A\Rightarrow B,\mathrm{eval}$ と書き、関数対象とその評価射と呼ぶ。

上記の公理により、$A\Rightarrow B$ には圏が持つ任意の $Z\times A$ と、$\mathrm{Hom}(Z\times A,B)$ に含まれる任意の評価射の組み合わせで表現しうるすべての$A\to B$関数から、重複を取り除いたうえですべて１つずつ含まれていることが保証される。

追加で必要な条件†

ここまで来て何なのだが、実はここまでの議論には致命的な欠陥がある。

すぐ上で次のように書いた。

上記の公理により、$A\Rightarrow B$ には圏が持つ任意の $Z\times A$ と、$\mathrm{Hom}(Z\times A,B)$ に含まれる任意の評価射の組み合わせで表現しうるすべての$A\to B$関数から、重複を取り除いたうえですべて１つずつ含まれていることが保証される。

上記公理が $A\Rightarrow B,\mathrm{eval}$ に保証するのは本当にこれだけなのだ。

何が欠けているかと言うと、「候補たちが表現していた関数」 が 「実際の$\mathrm{Hom}(A,B)$と対応しているかどうか」 について一切言及されていないということ。

これは本当に致命的で、一生懸命 $A\Rightarrow B$ に集めて回った射は実際の$\mathrm{Hom}(A,B)$とは関係なく、たまたま候補たちが表現していた関数だった！

この致命的問題を回避するには、上記の公理に
「圏が終対象 $1$ およびその積 $1\times A$ を含むこと」という新たな仮定を加えればいい。

そうすることで関数対象 $A\Rightarrow B$ が（集合論を扱う圏論の言葉の上で）正しく $\mathrm{Hom}(A,B)$ と一対一に対応し、その射を評価射 $\mathrm{eval}$ により再現できるようになる。

（集合論を扱う圏論の言葉の上で）という注釈については下記証明を参照。

終対象 $1$ およびその積 $1\times A$ の存在を追加†

圏が終対象 $1$ とその積 $1\times A$ を含んでいる、という追加の仮定を入れることで、 関数対象 $A\Rightarrow B$ が（集合論を扱う圏論の言葉の上で）正しく $\mathrm{Hom}(A,B)$ と一対一対応することを示そう。

証明したい内容†

ここで本当に示されるのは、

$\mathrm{Hom}(1,A\Rightarrow B)$ と $\mathrm{Hom}(A,B)$ との間の一対一対応である。

つまり、ある $f:A\to B$ にはそれと一対一に対応する $h:1\to (A\Rightarrow B)$ が存在する というのがこの定理。

本来ほしかったのは $f:A\to B$ と $A\Rightarrow B$ の元との1対1対応であるが、 コンストラクタ付きの圏であれば $h$ は $A\Rightarrow B$ のコンストラクタであるから、 結果的に $A\Rightarrow B$ の元と一対一対応する、という話。

$\Phi(h)$ の導入†

具体的な $h$ と $f$ との結びつきは、以下の変換により媒介される。 $$ f=\Phi(h)=\mathrm{eval}\circ(h\times 1_A)\circ p^{-1} $$

&uml( usecase "(A=>B)xA" as ABxA

(1xA)-->(A):p (1xA)<==(A) #line:red :p^-1 (1xA)->(1):! A->1:! ABxA-->(A=>B):q' ABxA-->A:p' A==>(B) #line:green :f ABxA==>B #line:red :eval 1=>(A=>B) #line:blue :h (1xA)=>(ABxA) #line:red :hx1 );

この変換が 直積の作成と、圏に存在するいくつかの射との合成によって構成されていることを確認せよ。

• $p^{-1}:A\to1\times A$ はすぐ上で出てきた $p:1\times A\to A$ の逆射
• $1_A:A\to A$ は $A$ の恒等射
• $\mathrm{eval}:((A\Rightarrow B)\times A)\to B$ は $A\Rightarrow B$ の評価射

つまり任意の $h:1\to (A\Rightarrow B)$ に対してこの関数を評価可能である。

射 $f$ の形を確認しておくと、 $$ f:A \xrightarrow{p^{-1}}1\times A \xrightarrow{(h\times 1_A)}(A\Rightarrow B)\times A \xrightarrow{\mathrm{eval}} B $$ つまり、 $$ f:A\to B $$ である。

この $\Phi(h)$ が $A\Rightarrow B$ の１つの要素に対応するコンストラクタ $h$ を、 その要素に対応する実在関数 $f:A\to B$ に変換していることを読み取ってほしい。

以下では $\Phi(h)$ が全単射であることを示すことで、 $A\Rightarrow B$ と $\mathrm{Hom}(A,B)$ との1対1対応を証明する。

$\Phi(h)$ が全単射であることの証明†

$p$ が逆射を持つ、すなわち $1\times A\cong A$ であるから、任意の $f\in\mathrm{Hom}(A,B)$ と $f\circ p\in\mathrm{Hom}(1\times A,B)$ とが一対一に対応する。

$1\times A$ を関数対象の公理で $Z=1$ と置いたものと捉え、評価射をこの $g$ に取ると、 $\mathrm{eval}\circ(h\times\mathrm{id})=f\circ p$ を満たす $h: 1\to(A\Rightarrow B)$ はただ１つだけ存在する。

この $h$ に対して $\Phi(h)=f$ となるから、$\Phi(h)$ は全射である。

また $\mathrm{eval}\circ(h\times\mathrm{id})=f\circ p$ を満たす $h$ すなわち $\Phi(h)=f$ を満たす $h$ はただ一つであるから $\Phi(h)$ は単射である。

つまり $\Phi(h)$ は全単射（一対一写像）であり、
$\mathrm{Hom}(1,A\Rightarrow B)$ の元と $\mathrm{Hom}(A,B)$の元の間の一対一対応を与える。

集合間の一対一対応は濃度の一致と同値なので、

$$ \#\mathrm{Hom}(1,A\Rightarrow B)=\#\mathrm{Hom}(A,B) $$

実集合との対応†

圏論が示すのはあくまで、 $$\#\mathrm{Hom}(1,A\Rightarrow B)=\#\mathrm{Hom}(A,B)$$ である(両者の間の一対一対応 = 要素の数(濃度)が等しいこと)。

これを現実世界に当てはめるには、追加で圏がコンストラクタを持つこと（対象の「要素」を自由に操作可能であること）の仮定が必要になる。

上でも述べたが、このとき $\mathrm{Hom}(1,A\Rightarrow B)$ と $A\Rightarrow B$ との一対一対応が生まれ、ようやく $\mathrm{Hom}(A,B)$ と $A\Rightarrow B$ とが一対一に対応することが言える。

逆に、圏にコンストラクタ・デストラクタがあることを先に要求すれば、
上で入れた仮定のうち $1$ の存在は自動的に満たされ、
もう1つの $1\times A$ の存在も、 $$ \begin{aligned} &\mathrm{null}\in 1\\ \to&(\mathrm{null}, a)\in 1\times A\\ \to&(x, a)\in (A\Rightarrow B)\times A\\ \end{aligned} $$ という $(A\Rightarrow B)\times A$ のコンストラクタを二段階に 分解したときに必要になる積として、自然に導入される。

カリー化†

複数の引数を持つ関数にあらかじめいくつかパラメータを渡してしまい、 残った引数だけの関数にする手順をカリー化と呼ぶ。

例えば TypeScript を使って

LANG:ts
function g(z: Z, a: A): B {
  // 実装
  throw new Error("not implemented");
}

function h(z: Z): (a: A) => B {
  return (a) => g(z, a);
}

のように書くと、$h(z)$ は $g(z,a)$ をパラメータ $z$ でカリー化した $A\to B$ の関数を返す。

両者の間に成り立つ g(z,a)=h(z)(a) は、g と h とが一対一に対応することを表す。

圏論でこれを次のように表す。

• $g:Z\times A\to B$
• $h:Z\to(A\Rightarrow B)$

関数対象では１つ目の式を関数ラベル$Z$と$A$を受け取って$B$を返すと読んだが、
ここではそれを一般化して任意のパラメータ$Z$と$A$から$B$を求めると読む。

２つ目は、$h$ が返す値は本来なら $A\to B$ であるが、
一般には $hom(A,B)$ 自体は圏論の対象ではないため、
$A\Rightarrow B$ に存在するその「表現」を返すとしている。

$g$ と $h$ との関係は $A\Rightarrow B$ の評価射を $\mathrm{eval}$ として、 $$ g=\mathrm{𝑒𝑣𝑎𝑙}\circ (h\times 1_A) $$ となる。このとき、 $$ \begin{aligned} g(z,a) &=\mathrm{eval}\circ (h\times 1_A)(z,a)\\ &=\mathrm{eval}\circ (h(z),a)\\ \end{aligned} $$ となって、$h$ から $g$ を決める手段が得られる。

そして、関数対象の公理により $A\Rightarrow B,\mathrm{eval}$ は $Z,g$ を生成可能である。
言い換えると、そのような $g$ を指定することで $h$ が唯一決まることを保証した。

ここから $g$ から $h$ を決める手段も得られるから、両者は一対一対応にする。

すなわち $\mathrm{Hom}(Z\times A,B)$ と $\mathrm{Hom}(Z,A\Rightarrow B)$ とが一対一対応することが、 関数対象の公理から導かれるのである。

集合間の一対一対応は濃度の一致と同義なので、

$$ \#\mathrm{Hom}(Z\times A,B)=\#\mathrm{Hom}(Z,A\Rightarrow B) $$

冪(べき exponential)†

関数対象 $A\Rightarrow B$ はしばしば $B^A$ と書かれ、冪、あるいは指数対象とも呼ばれる。

なぜ？ という疑問は当然なので、それを次節以降で説明する。

デカルト閉圏 と 整数算術†

上で $\mathrm{Hom}(1,A\Rightarrow B)$ と $\mathrm{Hom}(A, B)$ の一対一対応を導く際に $1,1\times A$ の存在を仮定した。

ここにさらに条件を重ねて、

• 終対象 $1$
• 任意の対象のペアの積 $A\times B$
• 対象の任意のペアの冪 $B^A$

の存在を仮定した圏を、デカルト閉圏と呼ぶ。（ここでの 積 = デカルト積 という対応）

これは「積や冪に対して閉じた圏」を構成したものである。

コンストラクタの存在を仮定しないとその意味を理解するのにいろいろ注意が必要になるので、 以下では コンストラクタ の存在も仮定しよう。

つまり、任意の対象 $A$ に対して、

$$A\cong\mathrm{Hom}(1,A)$$

（これはあくまで説明を簡単にするための仮定であって、デカルト閉圏そのものに要求されるものではない）

自然変換の演算規則†

$\alpha:\mathcal F\to\mathcal G$ の自然変換と $f:X\to Y$ に対して次式が成り立つ $$\alpha_Y\circ \mathcal F(f)=\mathcal G(f)\circ \alpha_X$$

この形は頻出するのでスルッと出てくるようにしておきたい。

自然変換の例†

例として挙げられていたのが $\mathrm{safeHead}$ という関数。

前提となるのは２つの関手。

１つは型 $A$ の要素 $a_1,a_2,a_3,\dots$ を含むリスト型 $\mathrm{List}(A)$ で、その値は $[a_1,a_2,a_3,\dots]$ みたいなもの（上で再帰的な定義になりそうなことに言及したが、実はまだこれを数学的に定義する準備が揃っていない）。

もう１つは $A$ の要素があるか、ないか、が分からないという意図を伝える $\mathrm{Maybe}(A)$ 型。この元は $A$ の要素 $a$ から、その $a$ を含むコンテナを作成する射 $\mathrm{Just}(a)$ により作られるもの (元自体も $\mathrm{Just}(a)$ と書き表す) と、$A$ の要素がないことを表す定数 $\mathrm{Nothing}$ からなる。（必ず存在チェックを挟むことを強制するため、$A$ の値そのままではなく、取り出すひと手間を加えた $\mathrm{Just}(a)$ になっていることに注意）

$\mathrm{safeHead}$ は $A$ を型パラメータとして、

• 型 $A$ の要素を持つリスト型 $\mathrm{List}(A)$ の値 $[a_1,a_2,\dots]$ を受け取る
• リストの「先頭の項目」を取り出して $\mathrm{Maybe}(A)$ 型の値を返す
  • 通常は先頭に対応する型 $A$ の値 $a_1$ を $\mathrm{Just}$ でラップした値 $\mathrm{Just}(a_1)$ を返す
  • リストが空 $[\ ]$ であるなら $\mathrm{Nothing}$ を返す

引数は $\mathrm{List}(A)$ だが、返り値は $\mathrm{Maybe}(A)$ なので、 $$ \mathrm{safeHead}: \mathrm{List}(A)\to \mathrm{Maybe}(A) $$ これを、

• $A \to \mathrm{List}(A)$ を 関手 $\mathcal F$
• $A\to\mathrm{Maybe}(A)$ を 関手 $\mathcal G$
• $\mathrm{safeHead}: \mathrm{List}(A)\to \mathrm{Maybe}(A)$ を $\mathcal F$ から $\mathcal G$ への自然変換

と見る。

これが任意の関数 $f:A\to B$ に対して自然になるのは、

• $\mathcal F(f): \mathrm{List}(A)\to\mathrm{List}(B)$ を例えば $\mathrm{map}$ として、すべての要素に $f$ を適用した結果をリストにして返す
• $\mathcal G(f): \mathrm{Maybe}(A)\to\mathrm{Maybe}(B)$ を $\mathrm{Nothing}$ なら $\mathrm{Nothing}$、そうでなければ $f$ を適用して返す

とすれば、

• $\mathrm{safeHead}\circ \mathcal F(f)$ は リストに f を適用してから先頭を取り出す
• $\mathcal G(f)\circ\mathrm{safeHead}$ は先頭を取り出してから $f$ を適用

となって、どちらも答えは同じになる、という主張。

実際、この $\mathrm{safeHead}$ のように型 $A$ が実際に何であるかにまるっきり依存しない形で書かかれる関数（パラメトリック多相関数）は、内部の処理で型 $A$ の「値」に触ることができない（何者かを知らないから触れない）ため、自然性を破ることができない、と書かれていた。

何を言っているかというと、上で $\alpha_X$ と書いていたものは、一般には $X$ それぞれに対して $\mathrm{Hom}(\mathcal F(A),\mathcal G(A))$ の任意の射を選んだものだったが、それら一連の射がすべて、型 $X$ をパラメータ化したある「テンプレート関数」で表記できるなら、それは自動的に、任意の射 $f:A\to B$ を考えた際の自然な変換になるということ。

「型 $X$ をパラメータ化した、射を生成するテンプレート関数」というのは圏論の外の枠組みなので、これを議論に含めるには 第二階多相ラムダ計算 を行うための System F と呼ばれる体系を考えるのが一般的で、そこから得られる結論がこれなのだそうだ・・・がここでは踏み込まない。

この議論が、$A\Rightarrow B$ と $\mathrm{Hom}(A,B)$ とを同一視したものになっていることに注意せよ。これはこの手の議論が常に「コンストラクタ付きのデカルト閉圏」を仮定したものになっており、$A\Rightarrow B$ と $\mathrm{Hom}(1,A\Rightarrow B)$ とを同一視していることによっている。$A\Rightarrow B\cong\mathrm{Hom}(1,A\Rightarrow B)\cong\mathrm{Hom}(A,B)$ ということ。

また、$\mathrm{Nothing}$ を $\mathrm{Maybe}(A)$ の元を作成するコンストラクタ（$1\to\mathrm{Maybe}(A)$ の射）とみなしたり、実際にその射により生成される元そのもの $\mathrm{Nothing}\in\mathrm{Maybe}(A)$ とみなしたり、コンストラクタと生成される元との同一視がここでも行われていること、そもそも $\mathrm{Nothing}_A\in\mathrm{Maybe}(A)$ と $\mathrm{Nothing}_B\in\mathrm{Maybe}(B)$ は数学的には別物なのに、Haskell はこれらを同一視していること、にも注意を払おう。

反変関手の自然変換†

$A$ を型パラメータとする。

• 型 $A$ の値を与えると $\mathrm{bool}$ 値を返す関数 $f: F\Rightarrow\mathrm{bool}$ を受け取って、
• $f$ の戻り値を "T" または "F" の文字列にして返す関数 $\alpha_A$ を考えると
  この関数は $\alpha_A:(A\Rightarrow\mathrm{bool})\Rightarrow(A\Rightarrow\mathrm{string})$

この状況を関手で考えると、

• $\mathcal F(A) = A\Rightarrow\mathrm{bool}$
• $\mathcal G(A) = A\Rightarrow\mathrm{string}$ と書きたくなるところだけれど、関数の引数となる対象は反変にする必要があるため、
• $\mathcal F(A^{\mathrm{op}}) = A\Rightarrow\mathrm{bool}$
• $\mathcal G(A^{\mathrm{op}}) = A\Rightarrow\mathrm{string}$ と考える必要がある。

話を簡単にするため $A\Rightarrow\mathrm{bool}$　を $A\to\mathrm{bool}$ と同一視すると（矢印が $\Rightarrow$ から $\to$ になった）、Hom 関手はプロ関手だから第一引数 (引数側の型) は反変になる。という話。

その理由を思い出すために、$f_A\in\mathcal F(A)=A\to\mathrm{bool}$ から $f_B\in\mathcal F(B)=B\to \mathrm{bool}$ を作る射を構成するのに $f:A\to B$ ではなく $g:B\to A$ が必要なこと。 $$ f_B=f_A\circ g $$ 共変のままでは $\mathcal F(A)\to\mathcal F(B)$ を $A\to B$ から作らなければならないが、反変 $\mathcal F(A^{op})\to\mathcal F(B^{op})$ ならば矢印の向きを逆にした $B\to A$ から作ればいい。

これが、型から関数を作る関手が引数型に対して反変である理由であった。

これを反映して、2つの反変関手の間の多相関数は、反対圏から関手を見たときに自然変換となる。
$f:B\to A$ とすると、これは $\mathrm{Hom}(A^{\mathrm{op}},B^{\mathrm{op}})$ のメンバーであるから、

• $\mathcal F(A^{\mathrm{op}}) = A\Rightarrow\mathrm{bool},\ \mathcal F(B^{\mathrm{op}})= B\Rightarrow\mathrm{bool}$
• $\mathcal G(A^{\mathrm{op}}) = A\Rightarrow\mathrm{string},\ \mathcal G(B^{\mathrm{op}})= B\Rightarrow\mathrm{string}$
• $\mathcal F(f): \mathcal F(B^{\mathrm{op}})\to \mathcal F(A^{\mathrm{op}})$
• $\mathcal G(f): \mathcal G(B^{\mathrm{op}})\to \mathcal G(A^{\mathrm{op}})$
• $\alpha_A: \mathcal F(A^{\mathrm{op}})\to\mathcal F(A^{\mathrm{op}})$
• $\alpha_B: \mathcal F(B^{\mathrm{op}})\to\mathcal G(B^{\mathrm{op}})$ $$ \alpha_A\circ\mathcal F(f)=\mathcal G(f)\circ \alpha_B $$

自然同型†

すべての成分が逆射を持つような自然変換で結ばれた２つの関手は自然同型であるという。

これらの逆射を集めたものは逆向きの自然変換になるから、自然同型は対称律を満たす。

なぜなら、$\alpha$ が自然性を満たし、 $$\alpha_Y\circ \mathcal F(f)=\mathcal G(f)\circ \alpha_X$$ なおかつ $\alpha^{-1}$ を持つならば、両辺に左から $\alpha_Y^{-1}$、右から $\alpha_X^{-1}$ を掛けることで、 $$\alpha_Y^{-1}\circ\big(\alpha_Y\circ \mathcal F(f)\big)\circ\alpha_X^{-1}=\alpha_Y^{-1}\circ\big(\mathcal G(f)\circ \alpha_X\big)\circ\alpha_X^{-1}$$ $$\mathcal F(f)\circ\alpha_X^{-1}=\alpha_Y^{-1}\circ\mathcal G(f)$$ として $\alpha^{-1}$ の自然性が導かれる。

圏の階層構造†

ここまでの話を振り返ると圏が階層構造を作っていることに気づく。

1. 例えば集合を対象とし、集合間の写像を射とする、オリジナルの圏があり
2. 次にそれらの圏を対象として、その間の関手を射とする圏を考えた (Cat 圏)
3. さらに、関手を対象として、その間の自然変換を射とする圏を考えた（関手圏）

3. で見た $\mathcal C$ から $\mathcal D$ への関手圏 $[\mathcal C, \mathcal D]$ は、Cat の $\mathrm{Hom}(\mathcal C,\mathcal D)$ に含まれる射を対象として、その間の自然変換を考える圏構造であったことを認識しよう。

Cat 圏の持つこのような性質を公理化した構造は 2-圏 と呼ばれる。

Cat圏の性質†

2-圏の話を広げる前に Cat に特有な話を２つ見ておこう。

• 関手圏が Cat の関数対象そのものになること
• Cat がデカルト閉圏となること

2-圏 (2-category)†

Cat はその Hom 集合の中に圏の構造を持っており、そこでの２種類の射はある種の「自然性」の条件を満たしていた。 Cat のこの性質を公理化したのが 2-圏 の概念である。

2-圏 $\mathcal K$ は次の内容で構成される：

• 対象 $C,D,E\in\mathrm{Ob}(\mathcal K)$
• 対象の順序対ごとに通常の射の集合 $f,g,h\in\mathrm{Hom}_{\mathcal C}(C,D)$ が存在
  この射を 1-射 (1-morphism) と呼ぶ
• 対象と1-射が通常の圏をなす
  • 1-射の合成 $f:C\to D,g:D\to E$ に対して $g\circ f: C\to E$ が存在
  • 1-射の結合律 $(f\circ g)\circ h=f\circ(g\circ h)$ が常に成り立つ
  • 1-射の恒等射 対象 $D$ ごとに、任意の $f:C\to D,g:D\to E$ に対して $1_D\circ f=f$, $g\circ 1_D=g$ を満たす $1_D:D\to D$ が存在。
• 対象の順序対ごとに、1-射 を対象とし、その間の射を持つ hom 圏 $\mathcal K(C,D)$ が存在
  • ここでの射を 2-射 (2-morphism) と呼ぶ ($\alpha,\beta,\gamma,\dots$)
  • 2-射の合成 $\alpha:f\Rightarrow g,\ \beta:g\Rightarrow h$ に対して $\beta\cdot \alpha: f\Rightarrow h$ が存在
    これは垂直合成と呼ばれ、ドット $\cdot$ で書かれる
    また2-射の始域と終域は $\Rightarrow$ で結ばれる
  • 2-射の結合律 $(\alpha\cdot\beta)\cdot\gamma=\alpha\cdot(\beta\cdot\gamma)$ が常に成り立つ
  • 2-射の恒等射 1-射 $g$ ごとに、任意の $\alpha:f\Rightarrow g,\beta:g\Rightarrow h$ に対して $1_g\cdot\alpha=\alpha$, $\beta\cdot1_g=\beta$ を満たす $1_g:g\Rightarrow g$ が存在。
• 1-射の合成と2-射の水平合成が１つの双関手の形で書ける（以下に詳述）。

1-射 $f:C\to D,\ g:D\to E$ の合成 $g\circ f:C\to E$ と、
2-射 $f,f':C\to D,\ g,g':D\to E$ の間を結ぶ $\alpha:f\Rightarrow f',\ \beta: g\Rightarrow g'$ の水平合成 $\beta\circ\alpha:g\circ f\Rightarrow g'\circ f'$ とが、
１つの双関手 $\circ_{C,D,E}$ （合成関手）と見做せる形で定義される。 $$ \circ_{C,D,E}:\mathcal K(D,E)\times\mathcal K(C,D)\to\mathcal K(C,E) $$ これは何を言っているのか？

この関手は、

• 対象である1-射の組を1-射に移す移し方 $(g,f)\mapsto g\circ f$
• 射である2-射の組を2-射に移す移し方 $(\beta,\alpha)\mapsto \beta\circ \alpha$

の２つを与えるものであるが、その組み合わせが関手となるためには、関手の適用が2-射に対する垂直合成および恒等射を保存する必要がある。すなわち、垂直合成してから水平合成しても、水平合成してから垂直合成しても、結果が変わらないこと（垂直合成と水平合成が満たした相互交換法則）、 $$ (\beta'\cdot\beta)\circ(\alpha'\cdot\alpha)= (\beta'\circ\alpha')\cdot(\beta\circ\alpha) $$ 恒等射を恒等射に移すこと、 $$ 1_g\circ1_f=1_{g\circ f} $$ がその条件となる。

Cat の垂直合成と水平合成が満たした「相互交換法則」こそが 2-圏 の中核をなしていると読み取ればよい。

この 2-射 の公理から、Cat が持つ興味深い性質の多くが導かれる。

関手を部分圏のコンストラクタとして使う†

圏 $\mathcal C$ における積 $A\times B,p,q$ とは、対象 $A,B,A\times B$ と射 $p:(A\times B)\to A,\ q:(A\times B)\to B$ により構成される構造を持っていた。

上で「集合の元」と、「終対象からその元への射」とを同一視したように、

注目する圏の構造（ここでは積）を構成する部分圏を、
自明と見做せる最小限の構造を持つ圏からそれらを生成する関手と同一視することを考える。

積の構造であれば、２つの独立な対象 $a,b$ と、それらの恒等射 $1_a,1_b$ からなる $n=2$ の離散圏 ($n$ 個の対象とその恒等射のみからなる圏) を $\mathrm{Disc}(2)$ と書いて、これを生成関手の始域とする。

関手 $\mathcal F:\mathrm{Disc}(2)\to\mathcal C$ を $a\mapsto A,b\mapsto B,1_a\mapsto 1_A,1_b\mapsto 1_B$ として定義すれば、これは $\mathrm{Disc}(2)$ から $A,B$ を含む最小の部分圏を生成する関手となる。

また、$\Delta_{A\times B}:\mathrm{Disc}(2)\to\mathcal C$ を $a\mapsto A\times B,b\mapsto A\times B,1_a\mapsto 1_{A\times B},1_b\mapsto 1_{A\times B}$ は $\mathrm{Disc}(2)$ に含まれた２つの対象 $a,b$ を１つの対象 $A\times B$ につぶす生成関手となる。

添字圏、図式†

このような時、元となる小さな圏のことは添字圏 (index category) と呼ぶ。
生成された圏の対象や射に意味付けをする（添え字を付ける）圏であることがその由来である。

また、添字圏から生成される $\set{A,B}$ や $\set{A\times B}$ のような部分圏と、それを生成する関手はしばしば同一視され、どちらも「図式 (diagram)」と呼ばれる。

生成された対象同士をつなぐ射は自然変換とみなせる†

$A,B$ と $A\times B$ とを１つの $\mathrm{Disc}(2)$ から生成したことにより、これらの間をつなぐ射 $p,q$ を、$\Delta_{A\times B}$ から $\mathcal F$ への１つの自然変換 $\alpha$ の成分とみなせるようになる。 $$\alpha:\Delta_{A\times B}\Rightarrow\mathcal F, \alpha_A=p,\ \alpha_B=q$$ というのも、始域を離散圏 $\mathrm{Disc}(n)$ とした生成関手では、圏に存在する射がすべて恒等射となるために「自然性の条件」は射に対する追加の条件を生まないのである。すなわち、離散圏を始域とする関手では終域同士を結ぶ任意の射を自然変換とみなせる。

同様に、積の公理に使う任意の対象 $Z$ とそこから $A,B$ へ伸びる $f:Z\to A,g:Z\to B$ も、 $\Delta_{Z}$ から $\mathcal F$ への自然変換が対応する。 $$\beta:\Delta_{Z}\Rightarrow\mathcal F, \beta_A=f,\beta_B=g$$

錐と頂点†

この $\Delta_{A\times B}$ や $\Delta_{Z}$ のように、$\mathrm{Disc}(n)$ を唯一の対象 $A\times B$ あるいは $Z$ へ集めたときの $A\times B$ や $Z$ のこと（対象を１つしか持たない図式）を「頂点」と呼ぶ。

そして、$\mathrm{Disc}(n)$ を対象の数を変化させないように移した先、上の例では $A,B$ からなる部分圏を $n$ 角形の底面とみなし、頂点 $Z$ からこの $n$ 角形の頂点への自然変換を考えた際の全体の構造は、その概念的な形状から「錐」と呼ばれる。

１つの「錐」が $f=\beta_A,g=\beta_B$ のように頂点 $\Delta_Z$ から底面 $\mathcal F$ へ広がる１つの自然変換 $\beta:\Delta_Z\to\mathcal F$ を可視化した概念であることを正しく認識せよ。

すなわち、錐 = 自然変換 である。

錐の圏†

$Z,f,g$ を決めるごとに錐 (自然変換) が１つ決まることになるが、これらの錐は圏をなす。

$Z,f,g$ から $Z',f',g'$ への射は $m:Z\to Z'$ という $\mathcal C$ に存在する射であって、 $$ f=f'\circ m, g=g'\circ m $$ を満たすものである。

• $m:Z\to Z',m':Z'\to Z''$ のとき $m'\circ m:Z\to Z' '$ がこの圏の射になることは明らか
• $m$ はもともと $\mathcal C$ の射であるから結合則を満たす
• $m=1_Z$ が恒等射

２つの錐に対応する自然変換を $\beta,\beta'$ とし、上で定義した自然変換と 1-射 との合成の記号を用いれば、 $$\beta=\beta'\circ m$$ である。

底面となる図式を $\mathcal F$ として、この錐の圏は $\mathrm{Cone}(\mathcal F)$ と表記される。

錐の圏の終対象†

積 $A\times B,p,q$ あるいはそれに対応する自然変換 $\alpha:\ \alpha_A=p,\alpha_B=q$ は上記の錐の圏の対象の１つである。

積の公理は任意の $Z,f,g$ に対して $f=p\circ h,g=q\circ h$ を満たす $h:Z\to A\times B$ がただ１つだけ存在することを要求しているため、$A\times B$ は錐の圏の終対象になる。(任意の $\beta$ から $\alpha$ へ入る射 $-\circ h$ がただ１つ存在する)

積の公理 を「錐の圏において $A\times B,p,q$ が終対象である」という条件に読み替えられたことを認識せよ。

普遍錐†

錐の圏の終対象は「普遍錐」と呼ばれることがある。
同じような意味で $A\times B$ が持つ普遍性、とか、$A\times B$ を普遍的な方法で定義する、のような用語の使われ方をされる。
これはすべての錐に対して唯一の射を持つという普遍性を表しているのだと思われる。

極限 $\varprojlim\mathcal F$†

普遍錐は、

底面を表す図式を $\mathcal F$ として、「$\mathcal F$ の極限」と呼ばれ、$\lim \mathcal F$ あるいは $\varprojlim \mathcal F$ と書かれたりもする。

（この $\lim \mathcal F$ が普遍錐ではなく、その頂点となる対象 $A\times B$ の意味で使われるときもあるので、そこは文脈によって読み替えると良い）

これを極限と呼ぶ気持ちは完全には理解できていないのだけれど、錐の圏に含まれる $A\times B,p,q$ 以外の錐から見ると、他の錐から飛んでくる射の数は必ずしも1ではなく、0だったり、複数あったりする。入ってくる射の数の最小値はゼロ以上、最大値は１以上（自分からの恒等射があるため）となるが、この最小と最大が１で一致するところが終対象＝極限、と思うと、不足と重複で両側から挟んでぴったり一致するところ、という感覚で「極限」という気持ちがまあわからなくもないか、と現時点では個人的に納得している。米田の補題や表現可能性などの話を理解してから戻ってくるとまた見えるものは違うのかもしれない・・・らしい。

$\varprojlim \mathcal F$ の左向き矢印は、頂点から $\mathcal F$ へ「入ってくる射」について考えていることを表している。

余極限 $\varinjlim \mathcal F$†

極限の双対である「余極限」は逆向きの $\varinjlim \mathcal F$ で表される。

積の双対が余積なので、余積の構造は余極限で表される。

12章は情報量が多いので、これまでの議論とのつながりを意識しながら骨格を整理します。

ここまでを振り返る†

$A\times B$ の構造は以下のように整理される

• 添字圏 $\mathcal I=\mathrm{Disc}(2)$ (２つの対象のみを含む離散圏)
• 図式 $\mathcal F:\ \mathcal I\to\mathcal C$ ($A,B$ の生成関手)
• 図式 $D=\mathcal F(\mathcal I)$ ($A,B$ のみからなる部分圏)
• 任意の頂点 $Z$ とその生成関手 $\Delta_Z$ (すべてを１つの対象に集める)
• $Z$ を頂点とする錐
  • $\Delta_Z$ から $\mathcal F$ への自然変換 $\alpha$ のこと （$f=\alpha_A,\ g=\alpha_B$）
  • １つの $Z$ に対して $\alpha$ の取り方は複数ありうる
  • 異なる $Z,Z',Z'{}',\dots$ も含めていろいろ作れる
• 図式 $\mathcal F$ を底面とする錐の圏 $\mathrm{Cone}(\mathcal F)$
  • 対象=自然変換 $\alpha$、射= $m:Z\to Z'$ との積 $-\circ m$
• その終対象 $\varprojlim\mathcal F$ ($A\times B,p,q$ に対応する自然変換)

この話を、別の角度から眺めてみたい。

１つの $Z$ を頂点とする部分圏†

錐の圏 $\mathrm{Cone}(\mathcal F)$ の中で、ある１つの $Z$ を頂点とする錐のみを集めると部分圏を作る。(１つの $Z$ に対して、$\Delta_Z$ から $\mathcal F$ への自然変換 $\alpha:\Delta_Z\to\mathcal F$ （$f=\alpha_A,\ g=\alpha_B$） は複数存在しうることに注意せよ)

この部分圏に含まれる対象（自然変換）の集合を、 $$ \mathrm{Nat}(\Delta_Z,\mathcal F) $$ と書く。Nat は natural の意味である。

Nat の圏への反変関手†

異なる $Z$ に対して異なる $\mathrm{Nat}$ を生じるため、それらの $\mathrm{Nat}$ を対象とする圏を考える。その間の射 $f_m$ は $m:Z'\to Z$ を用いて、 $$ f_m\big(\alpha\in\mathrm{Nat}(\Delta_Z,\mathcal F)\big)=\alpha\circ m\in \mathrm{Nat}(\Delta_{Z'},\mathcal F) $$ と定義する。$\alpha$ の個々の成分が添え字を $i\in \mathrm{Ob}(\mathrm{Disc}(2))$ として $$ \begin{aligned} &\alpha_i: Z\to \mathcal F(i)\\ &\alpha_i\circ m: Z'\to \mathcal F(i) \end{aligned} $$ となることを確認せよ。また、このように作られた $\alpha\circ m$ は離散圏を添字とする図式においては自動的に自然変換になる。したがって、これで正しく $f_m:\mathrm{Nat}(\Delta_Z,\mathcal F)\to \mathrm{Nat}(\Delta_{Z'},\mathcal F)$ が得られることになる。

元々 $Z,m$ は圏 $\mathcal C$ の対象と射であるから、 $$ \begin{aligned} &Z\mapsto \mathrm{Nat}(\Delta_Z,\mathcal F)\\ &m\mapsto f_m \end{aligned} $$ が圏 $\mathcal C$ から Nat の作る圏への関手となる・・・かと思いきや、$m$ の方向と $f_m$ の方向が逆になるので、これは反変関手、すなわち $\mathcal C^{\mathrm{op}}$ から Nat の作る圏への関手となる。

上記の意味での関手を対象側の変換で代表させて $$ \mathrm{Nat}(\Delta_-,\mathcal F) $$ と略記する。これには射の変換が付随していることを忘れないようにしよう。

Hom 圏への反変関手†

圏 $\mathcal C$ の Hom 関手の右側を $A\times B$ に固定(カリー化)した関手を考える。 $$ \mathrm{Hom}_{\mathcal C}(-,A\times B) $$ これも反変関手になるから、$Z,Z'$ および $f:Z'\to Z$ を移した先は、 $$ {}-\circ f: \mathrm{Hom}_{\mathcal C}(Z,A\times B)\to\mathrm{Hom}_{\mathcal C}(Z',A\times B) $$ すなわち $g: Z\to A\times B$ に対して、 $$ g\mapsto g\circ f\hspace{5mm} \text{(これは $Z'\to A\times B$ になる)} $$ である。

前層(presheaf)†

圏 $\mathcal C$ の前層とは $\mathcal C^{\mathrm{op}}\to\mathrm{Set}$ となるような関手のことである。

その意味で、上記の２つの関手はどちらも前層である。

• $\mathrm{Nat}(\Delta_-,\mathcal F)$
• $\mathrm{Hom}_{\mathcal C}(-,A\times B)$

元々、前層という語は圏論とは関係なく位相空間において使われた言葉であった。この位相空間における前層の概念を、位相空間の上の開集合とその包含関係が作る圏を経由して、一般の圏にアナロジーとして取り込んだのが、圏論における前層とのことで、ここで前層という言葉が意味するところを考えても実りはないらしい。

前層の圏 $\mathrm{PSh}(\mathcal C)$†

圏 $\mathcal C$ 上の前層 $\mathcal C\to\mathrm{Set}$ は、自然変換を射として圏をなす。

この圏を $\mathrm{PSh}(\mathcal C)$ と表す。

表現可能前層†

圏 $\mathcal C$ のある前層 $\mathcal F:\mathcal C^{\mathrm{op}}\to\mathrm{Set}$ が、圏 $\mathcal C$ の何らかの対象 $X$ に対する前層 $\mathrm{Hom}_{\mathcal C}(-,X)$ と自然同型であるとき、その前層は $X$ により表現される、といい、このような $\mathcal F$ を表現可能前層と呼ぶ。 $$\mathcal F\cong\mathrm{Hom}_{\mathcal C}(-,X)$$

余前層 (copresheaf)†

前層の双対として、反変ではなく共変な関手 $\mathcal C\to \mathrm{Set}$ は余前層と呼ばれる。

同様に、表現可能余前層の考え方もできて、その場合の表現は余前層 $\mathrm{Hom}_{\mathcal C}(X,-)$ との自然同型として定義される。

圏 $\mathcal C$ のある余前層 $\mathcal F:\mathcal C\to\mathrm{Set}$ が $X$ で表現されるとは次の同型自然変換が存在すること。 $$\mathcal F\cong\mathrm{Hom}_{\mathcal C}(X, -)$$

積の場合†

実は $A\times B$ の公理から、 $$\mathrm{Nat}(\Delta_-,\mathcal F)\cong \mathrm{Hom}_{\mathcal C}(-,A\times B)$$ を示すことができる。 すなわち、$A\times B$ は $\mathrm{Nat}(\Delta_-,\mathcal F)$ の表現だという話。

そして、ここが真に重要な部分↓
逆に、$A\times B$ が $\mathrm{Nat}(\Delta_-,\mathcal F)$ の表現であるという前提から積の公理を導くことができる。

同型自然写像 $\theta$ の存在は、ある $Z$ を固定した際に $\mathrm{Nat}(\Delta_Z,\mathcal F)$ の要素と $\mathrm{Hom}_{\mathcal C}(Z,A\times B)$ の要素との間に一対一の対応を付ける。

その対応こそが、$\alpha\in\mathrm{Nat}(\Delta_Z,\mathcal F)$ が与える $Z,f=\alpha_A,\ g=\alpha_B$ の組に、ただ１つの $h\in\mathrm{Hom}_{\mathcal C}(Z,A\times B)$ が対応させるものである。

この $Z$ に $A\times B$ を入れると、 $$\mathrm{Nat}(\Delta_{A\times B},\mathcal F)\cong \mathrm{Hom}_{\mathcal C}(A\times B,A\times B)$$ が出るが、特に右辺の Hom に含まれる $1_{A\times B}$ に対応する Nat の元を $\pi$ とすると、これが $A\times B$ からの取り出し射を与え $\alpha=\pi\circ h$ を満たすため、ここまでで積の公理が導かれることになる。

$\alpha=\pi\circ h$ は、同型自然変換 $\theta$ につての次のダイアグラムの自然性から導かれる。 $$ \begin{matrix} \mathrm{Nat}&&&\mathrm{Hom}&\\\hline \pi&\xleftrightarrow{\theta}&&1_{A\times B}\\[3mm] {}-\circ h\downarrow\hspace{12mm}&&&h\downarrow\ \ \\[3mm] \alpha&\xleftrightarrow{\theta}&&h\\ \end{matrix} $$ （Nat 関手による $h$ の像が $-\circ h$ であることに注意せよ）

左上の $1_{A\times B}$ から $\alpha$ への経路を考えると、
右回り: $1_{A\times B}$ から $\alpha$ に対応する $h$ への射は $h$ 左回り： すると $1_{A\times B}$ に対応する $\pi$ から $\alpha$ への射は Nat により $h$ を変換したものであるべきで、それは $-\circ h$

すなわち、$\alpha=\pi\circ h$ が得られる。

ここまでに見たストーリーの骨子はすぐ後で米田の補題として現れる。

補題の意味とその証明†

実は自然変換を、その変換がちゃんと自然性を持つように構成しようとすると、非常に自由度が限られていて、どこか一点の変換先を決めるだけで全体が決まってしまうようなことが起きる、というのが米田の補題の肝の部分になる。

$\alpha\in\mathrm{Nat}(\mathrm{Hom}_{\mathcal C}(-,X),\mathcal F)$ という自然変換の自由度について考える。

$\alpha$ の自然性を使うと、任意の $f:X'\to X$ に対して次の四辺形が書けて、 $$ \begin{matrix} \mathrm{Hom}_{\mathcal C}(X,X)&\xrightarrow{\alpha_X}&\mathcal F(X)\\ {}-\circ f\downarrow&&\mathcal F(f)\downarrow\hspace{12mm}\\ \mathrm{Hom}_{\mathcal C}(X',X)&\xrightarrow{\alpha_{X'}}&\mathcal F(X')\\ \end{matrix} $$ 左上に $1_X$ を与えると、右回り $\mathcal F(f)\circ \alpha_X(1_X)$、左回り $\alpha_{X'}(1_X\circ f)$　だから、 $$ \alpha_{X'}(f)=\mathcal F(f)\big(\alpha_X(1_X)\big) $$ が得られる。

これは著しい結果と言える。というのも、始めに $\alpha$ の $X$ 成分 $\alpha_X$ が $1_X$ を移す先 $\alpha_X(1_X)=\pi \in \mathcal F(X)$ を固定したならば($\mathcal F$ は前層なので $\mathcal F(X)$ は集合、$\pi$ はその元である)、任意の $X'$ に対する $\alpha_{X'}$ が完全に決まってしまうのだ（$X'=X$ のケースを含め、任意の $f:X'\to X$ を移す先が決まってしまう）。 $$ \alpha_{X'}(f)=\mathcal F(f)\big(\pi\big) $$ この、 $$\pi \in \mathcal F(X)\hspace{5mm}\xleftrightarrow{\hspace{5mm}\alpha_X(1_X)\ =\ \pi\hspace{5mm}}\hspace{5mm}\alpha=\set{\alpha_{X'}}:\mathrm{Hom}_{\mathcal C}(X',X)\to\mathcal F(X')$$ という一対一対応を関手の言葉ですっきり述べたのが米田の補題であると認識しよう。

実際、ここまででほぼ証明も済んでいる。
$\alpha$ に自然性を要求したことにより

1. $\pi$ を選ぶと $\alpha_{X'}(f)=\mathcal F(f)\circ \pi$ により $\alpha$ が決まり
2. $\alpha$ を決めると $\pi=a_X(1_X)$ が決まる

という全単射が得られた。
あとはこれが自然変換になっていることを示せばよい。

成分が $\Phi_X: \alpha\mapsto \alpha_X(1_X)$ で与えられる変換 $\Phi$ の自然性を確認しよう。

任意の $f:X'\to X$ に対して、 $$ \begin{matrix} \mathrm{Nat}(\mathrm{Hom}_{\mathcal C}(-,X),\mathcal F)&\xrightarrow{\Phi_X}&\mathcal F(X)\\ {}-\cdot f\downarrow&&\mathcal F(f)\downarrow\hspace{12mm}\\ \mathrm{Nat}(\mathrm{Hom}_{\mathcal C}(-,X'),\mathcal F)&\xrightarrow{\Phi_{X'}}&\mathcal F(X')\\ \end{matrix} $$ 左上に $\alpha$ を与えたとすると、
右回り： $\mathcal F(f)\circ\Phi_X(\alpha)=\mathcal F(f)\circ\alpha_X(1_X)$
左回り：$\Phi_{X'}(\alpha\cdot f)=(\alpha\cdot f)_{X'}(1_{X'})=\alpha_{X'}(f)$

ここに上記の $\alpha$ の自然性を入れると両者は等しくなり $\Phi$ の自然性が示された。

余米田の補題 (co-Yoneda lemma)†

米田の補題は前層 $\mathcal F:\mathcal C^{\mathrm{op}}\to\mathrm{Set}$ に関する次の定理だった。 $$ \mathrm{Nat}(\mathrm{Hom}_{\mathcal C}(-',-),\mathcal F(-'))\cong\mathcal F(-) $$

その双対が余米田の補題 $$ \mathrm{Nat}(\mathrm{Hom}_{\mathcal C}(-,-'),\mathcal F(-'))\cong\mathcal F(-) $$ こちらは余前層 $\mathcal F:\mathcal C\to\mathrm{Set}$ についての定理になっている。

（ここでの $-$ と $-'$ を使い分ける記法は標準的ではないので注意せよ。便利なので今後はやらせたいところだ。）

圏の同型(isomorphism)†

&uml( (C)-->(D): R (D)-->(C): L (C)<-(C):I_C (D)<-(D):I_D );

• $\mathcal R:\mathcal C\to\mathcal D$
• $\mathcal L:\mathcal D\to\mathcal C$

これらが互いに逆射であるとする。

• $\mathcal L\circ \mathcal R=\mathcal I_C$
• $\mathcal R\circ \mathcal L=\mathcal I_D$

このとき２つの圏 $\mathcal C,\mathcal D$ は同型であるといい、 $$\mathcal C\cong\mathcal D$$ と書く。

圏の同値(equivalence)†

上で関手が対象の同型関係を保つことを見た。

そのため、圏が同型な対象が複数含むときに、圏の「同型」を少し緩めた「同値」という概念が役に立つことになる。

部分圏が同型な対象を複数含むとき、関手がそのどれを、相手のどれに対応付けるか、には任意性がある。

例題として、$\mathcal C$ が含む $A,B,C$ が互いに同型な対象であるとしよう。
これらをそれぞれ $\mathcal C'$ が含む $A',B',C'$ に対応させて同型関手になるならそれらも同型であるから、

$A\mapsto A', B\mapsto B', C\mapsto C'$ と対応付ける代わりに、
$A\mapsto B', B\mapsto C', C\mapsto A'$ と対応付けても同型な関手を作ることが可能ということ。

それをさらに進めて、
$A\mapsto A', B\mapsto A', C\mapsto A'$ のようにつぶしてしまっても本質的な構造は保たれるから、
こういう「同型よりも少し緩い対応付けの取れる圏同士」を「同値」と呼ぼう、という話。

逆に、
$\mathcal C$ には $A$ しかないが、
$\mathcal C'$ は $A$ に対応する $A'$ と同型な $B',C'$ も含むとする。

このとき、
$\mathcal C$ から $\mathcal C'$ へ延びる関手は $A\mapsto A'$ だけで、$B',C'$ に対応付けるための対象が不足するが、このときも同型を代表して $A'$ に対応付けられていれば $\mathcal C$ と $\mathcal C'$ 全体 ($B',C'$ を含む) とが同値である、と呼ぶ。
（こう定義することで「同値」が対称律を持つようになる）

随伴(adjoint)†

自然同型は逆射を持つ自然変換により結ばれるということであった。

だから、たとえば同値関係に現れた $\mathcal L\circ \mathcal R\cong \mathcal I_C$ は、

• $\mathcal L\circ \mathcal R\to \mathcal I_C$
• $\mathcal L\circ \mathcal R\leftarrow \mathcal I_C$

の２つの自然変換が存在して互いに逆であるという条件。

随伴はこの条件をさらに緩和して、

• $\eta:\mathcal I_D\to\mathcal R\circ \mathcal L$
• $\varepsilon:\mathcal L\circ \mathcal R\to \mathcal I_C$

の２つの一方向の自然変換が存在し、 次の三角恒等式が成り立つことだけを要求する。

• $\varepsilon_{C}\circ\mathcal L(\eta_D)=1_C$
• $\mathcal R(\varepsilon_{C})\circ\eta_{D'}=1_{D'}$

これらも一方向だけなので、逆射であることを要求しているわけではないことに注意しよう。

&uml( rectangle "Category D" {

 usecase (D)
 usecase (D')
 usecase (D'')

} rectangle "Category C" {

 usecase (C)
 usecase (C')

} (D)-->(D') #blue :" η_D " (D)-left-->(C):" L" (C)-right-->(D'):" R " (C')-up->(C) #red :ε_C (C)->(C') #blue :L(η_D) (D')->(C'): "L " C-up->C:1_C (D')-->(D'):1_D' (C')-down-->(D''):" R" (D')-->(D'') #yellowgreen : " η_D' " (D'')-up->(D') #red : " R(ε_C)" );

このとき、

• $\eta$ は随伴の単位 (unit) と呼ばれ、
• $\varepsilon$ は余単位 (counit) と呼ばれ、
• 関手 $\mathcal L$ は関手 $\mathcal R$ に対する左随伴 (left adjoint) と呼ばれる。

随伴関係は、 $$\mathcal L\dashv\mathcal R$$ と書かれる。