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

概要†

前から気にはなっていたのだけれど、こちらにフリーの日本語テキストがあると聞いて読み始めました。

https://ktgw0316.github.io/milewski-ctfp-markdown/

→ 全然理解できなかったので、いろいろと調べながら分かった範囲をまとめようとしています

準備： 「クラス」 について†

圏論では『「要素の集まり」ではあるけれど「集合」とは呼べないもの』を扱うことがある。これは、ラッセルの逆説として有名な話、「自分自身を含まない集合をすべて集めたもの $R$」を集合であるとすると矛盾が生じる。という事実と関連している。

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

どちらも矛盾する。

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

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

以下に出てくる「クラス」という用語は多くの場合「集合」に置き換えられるけど、そうでない場合があるので念のため「クラス」と書いている、という程度の理解でしばらくは読み進められるはず。

圏(category)の定義†

圏 $\mathcal C(O, \mathrm{hom}(\cdot,\cdot))$ と書くとそれは以下を意味する。

• $O$ は対象(object)と呼ばれる要素のクラス（集まり）
• 任意の２つの対象 $A, B\in O$ を順序付きで取り出すと、そこに「射(morphism)」のクラス（集まり） $\mathrm{hom}(A,B)$ が付随する
• さらにこの「射」に対して下で述べる公理が成り立つ

と言ってもなんだかわからないのだが、
「対象」同士を結ぶ「矢印」をイメージするのが分かりやすい。

この図では黒丸が「対象」、矢印が「射」を表す。

ここには $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$) が許されること、に注意せよ。

同じ図を $\mathrm{hom}(\cdot,\cdot)$ の中身を入れ替えて、$\mathrm{hom}'(B, A)=\set{d, e}$ のように、$B,A$ の順で $A$ から $B$ への矢印の集合を表すと定義しなおして新たな圏を構成しても構わない。$\mathrm{hom}(\cdot,\cdot)$ に与える対象の順番が、射の何の方向を決めるか(矢印の方向か、その逆方向か、など)は $\mathrm{hom}(\cdot,\cdot)$ の定義次第である。

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

写像 $f:A\to B$ は任意の $x\in A$ に対して $f(x)\in B$ となる値を計算する規則（関数）であった。このとき$A$は始域、$B$は終域と呼ばれる。上で射とされた $a,b,c,\dots,h$ がそれぞれ個別の写像であり、$A,B,C$ はそれらの始域や終域となるクラス（集合）であると考える。これは実際、かなりメジャーな圏の構成である。

特殊な対象、空写像†

空集合 $\set{}$ や、１つの要素だけ(その要素を $()$ と書く） を含む集合 $\set{()}$ は圏論の「対象」として顕著な性質を持つ。

$A$ を任意の対象として写像の言葉で考えると、

$f:\set{}\to A$ は写像に与えるべき値が存在しないため「呼び出し不可能な写像」となる
圏論ではこれを「空写像」と呼び、そのような写像がただ１つだけ存在しうる、と数える。
（存在しないのではなく、存在するが呼び出せない、と考える）

$f:A\to\set{}$ は $A=\set{}$ であれば空写像であるが、$A\ne\set{}$ では呼び出せるのに返せる値が存在しない、となってしまうため、そのような写像は存在しない。つまり $\mathrm{hom}(A,\set{})$ は必ず空集合になる。

$f:A\to\set{()}$ は返せる値が1つしかないので、「任意の $a\in A$ に対して $()$ を返す」 という１つの写像だけを作りうる。

$f:\set{()}\to A$ は与えられる要素が $()$ に固定されているので、$A$ のどの要素を返すか、だけで写像が定義されるから、$\#A$ 個の写像を作りうる。

圏論ではこういったケースを対象や写像の中身に踏み込まずに扱うため、**始対象**、**終対象**という言葉を使う。

始対象、終対象†

始対象$I$とは、任意の対象 $A$ に対して、$f:I\to A$ となる射がただ1つだけ存在する対象のこと。
上の $\set{}$ は始対象の候補になる。

終対象$T$とは、任意の対象 $A$ に対して、$f:A\to T$ となる射がただ1つだけ存在する対象のこと。
上の $\set{()}$ は終対象の候補になる。

Q: ある圏に始対象$I$があったとして、そこからある対象 $A$ に対する一意な射　$f:I\to A$ を取り除いてしまったら $I$ は始対象ではなくなるのか？
A: 定義上はそのとおりだが、取り除けない場合があるのでそこには注意が必要。
$g: B\to A$ のような射が存在する場合には、$I\to B\to A$ の合成経路が存在するため、$f$ のみを取り除くことができない。$I$ 以外の対象から$A$への射が一切存在しないときに限って$f$を取り除くことができる。始対象の定義は任意の対象に対して一意な射を持つことなので、そのような射が欠落してしまえば始対象の資格を失う。

上の図の例では始対象も終対象も存在しない。

上の図から $e,h$ を取り除くと、$A$が始対象、$C$ が終対象となる。
この時、$A$ や $C$ は必ずしも空集合や１要素集合でなくともよく、それぞれのペアに定義される一意な射も空写像や定数写像である必要もない。

始対象・終対象は存在するなら同型を除いて一意である。
なぜなら、例えば $I,I'$がどちらも始対象であれば$a:I\to I'$、$b:I'\to I$、$c:I\to I$、$d:I'\to I'$ にはそれぞれに一意な射であるから $b\circ a:I\to I, a\circ b:I'\to I'$ はそれぞれ $c,d$ に等しく、さらに恒等射に等しい。すなわち $a,b$ は互いに逆射である。

逆射と同型の関係を次に述べる。

同型な対象†

対象 $A,B$ が $a:A\to B,b: B\to A$ を持ち、$a\circ b=1_B$ かつ $b\circ a=1_A$ を満たすとき $a,b$ は互いに逆射であると言い($a^{-1}=b, b^{-1}=a$)、逆射を持つ射を同型射と言い、同型射で結ばれる $A,B$ は同型であると言う。

同型射は一対一写像(全単射)のようなものと思えばいいが、一般の圏では対象は必ずしも集合ではなく射は必ずしも写像ではないし、対象が集合であり、$a$ が一対一写像であったとしても、その逆写像 $a^{-1}$ が必ずしも圏に含まれないことに注意が必要である。

単射、全射、全単射†

圏論ではこれらの概念も、「個別要素がどこに写像されるか」に踏み込まずに定義される。

$f:A\to B$ として、

$f$ が単射とは: 任意の対象 $C$ と $g, h: C\to A$ に対して、$g\ne h⇒f\circ g\ne f\circ h$

• 通常、写像の用語で単射とは、「入力が異なれば出力が異なる」という性質のことである
• 圏論ではそれを、前置する写像が異なれば、合成写像が異なる、と言い換えている
• 両者は一見すると似ているものの、実はこの違いは大きくい
• 写像として単射ではなく、複数の要素が同じ出力を生じる場合であっても、ちょうどそこを踏み分けるような $g\ne h$ が圏内に存在しなければ、圏論的には単射と呼ばれることになるのである。

$f$ が全射とは: 任意の対象 $C$ と $g, h: B\to C$ に対して、$g\ne h⇒g\circ f\ne h\circ f$

• 写像用語で全射とは、出力が終域すべてをカバーする、というようなことである
• それを、後置する写像が異なれば、合成写像が異なる、と言い換えている
• 終域の中で出力がカバーしない範囲があれば、そこでだけ異なる値を取るような異なる $g,h$ に対して、合成射が等しくなってしまうことを思い浮かべれば意味を理解しやすい
• とはいえこちらも、もし終域にカバーしない範囲があったとしても、それを見分けられる射 $g,h$ が存在しなければ全射と見なされるため、写像としての全射とは同一視できない

$f$ が全単射とは： 全射かつ単射であること。

写像としての全射・単射と、圏論における全射・単射が大きく異なることを示す極端な例として、任意の対象間に高々１つしか射が定義されていない「細い圏(thin category)」では、すべての射がその内容に寄らず自動的に全単射となる。$g\ne h$ となる射が存在しないためだ。

圏論では全単射と「逆射の存在」とがまったく別の概念として存在することにも注意を払おう。

双対性†

のように並べてみると、これらの定義は矢印の方向が逆なだけでそっくりな形をしている。

この類似性は双対性（duality）と言い表される。

圏 $\mathcal C(O,\mathrm{hom})$ の射の向きだけをすべてひっくり返した反対圏 (opposite category) $\mathcal C^{\mathrm{op}}(O,\mathrm{hom}')$ を作ることを考える(双対圏 dual category とも呼ばれる)。これは例えば$A\to B$ の写像の向きを反転させて$B\to A$ の写像を考えよう、というようなことを言っているのではなく、$\mathrm{hom}(A,B)$ が $A\to B$ の写像の集合だったのに対して、$\mathcal C^{\mathrm{op}}$ では $\mathrm{hom}'(B,A)$ が $A\to B$ の写像の集合であるとしよう、と言っている。対象であったり、写像で合ったりと言った実体は同じまま、射として見る際に写像の始域と終域と、射の始域と終域とを逆向きに対応させる、というだけのこと。

すると、元の圏における始対象・終対象は反対圏では逆に終対象と始対象になる。このように矢印の向きだけを入れ替えたときに対応するペアを一般に双対(dual)と呼ぶ。$\mathcal C$ と $\mathcal C^{\mathrm{op}}$ は双対（双対圏）であり、始対象の定義と終対象の定義も双対の関係にある。

積 (product)†

対象$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$ を満たす。

要素 $\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)$ に対して $h$ が必ず１つ存在しなければならないということ。これは $(A\times B,p,q)$ だけでなく圏自体に対する強い制約になっている。$h$ が欠損するような$(C,f,g)$があってはならない。

ここまでの議論は $A,B,A\times B$ の元について直接考える代わりに、$C$ からそれぞれの対象に元を生成する射$f,g,h$に基づいたものになっていた。この $C$ のように興味範囲の対象に元を供給する源となる対象は「プローブ対象(probing object)」と呼ばれ、元を生成する射 $f,g,h$ 自体のことを「一般化された元(generalized element)」と呼ぶ。個々の元そのものを考える代わりに、プローブ対象から各対象へ一般化された元が伸びる構造（「錐(cone)」と呼ばれる）で代用するのは圏論の標準的な手法となっている。

プローブ対象$C$を一般化された元$f$で移した像$f(C)$が、飛び先の対象の中で有効な元の範囲となることからも分かる通り、「圏全体に含まれるいずれの射」からも生成されない元は、圏論では存在しないものとみなされることになる。これは全射・単射の議論でも出てきた話だった。

また、ここまでの話は対象が集合で、射がその間を結ぶ写像であるという前提での議論になっていたが、上記の積やプローブ対象、一般化された元、錐などの概念は、より一般的な圏では異なる意味を持つことになる。

余積 (coproduct)†

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

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

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

公理：
任意の対象$C$と、任意の射の組 $f: A\to C$、$g: B\to C$ に対して、

積と余積とデータ構造†

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

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

関手 (functor)†

関手はある圏 $\mathcal C(O, \mathrm{hom})$ と別の圏 $\mathcal C'(O', \mathrm{hom}')$ との間の写像のペア $\mathcal F=(\mathcal F_o,\mathcal F_m)$ で、

$\mathcal F_o:O\to O'$ → 対象を対象に移す
$\mathcal F_m:\mathrm{hom}(A,B)\to \mathrm{hom}'(\mathcal F_m(A),\mathcal F_m(B))$ ただし $A,B\in O$ → 射を射に移す

$\mathcal C$ 全体を $\mathcal F$ で変換した構造がそのまま $\mathcal C'$ 上で部分圏 $\mathcal F(\mathcal C)$ を作り、さらに合成と恒等射を保つもの。

$$ \mathcal F_m(g\circ f)=\mathcal F_m(g)\circ \mathcal F_m(f),\ \mathcal F_m(1_A)=\mathcal 1_{F_m(A)} $$

関手は $\mathcal C$ と $\mathcal C'$ とをつなぐ写像になるが、これは必ずしも $\mathcal C$ と $\mathcal C'$ とが、あるいは $\mathcal C$ と $\mathcal F(\mathcal C)$ とが同型であることを意味しない。$\mathcal F$ が全射でなければ $\mathcal F(\mathcal C) \subsetneqq \mathcal C'$ であるし、$\mathcal F$ が単射でなければ $\mathcal C$ の構造の一部は $\mathcal F(\mathcal C)$ の中で「つぶれて」しまう。

例えば $\mathcal F_o$ がすべての $A_i\in O$ を特定の $X\in O'$ に移す定数写像であり、$\mathcal F_m$ がすべての $f\in\mathcal C$ を $X$ 上の恒等射 $1_X$ に移す定数写像であったとすれば、$\mathcal C$ の対象と射の関係は（大幅につぶれてしまうものの）部分圏 $\mathcal F(\mathcal C)$ の中に対応関係を保ったまま埋め込まれる。この例は「定数関手」と呼ばれる最も小さな部分圏を生む関手であり、 $\mathcal F(\mathcal C)$ には $\mathcal C$ の情報はほとんど何も残らないが、このようなものも関手の一つであるとされる。

双関手†

上で見た関手は $\mathcal C$ から $\mathcal C'$ への写像であった
双関手は２つの圏から１つの圏への写像 $\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 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)$
これも余積の構造に付随して初めから存在する構造に名前を付けたものとみなせる。

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