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

目次†

有向グラフ†

圏をイメージするには「対象」同士を結ぶ「矢印」を描くと分かりやすい。

この図では黒丸が「対象」、矢印が「射」を表す。
いわゆる「有向グラフ」になっている。

ここには $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 で成り立つ定理がなりたたない場合も多いので注意が必要である。
（テキストが暗黙に Set を仮定していることがしばしばあったりするので）

Set では「射の合成」は「写像の合成」のことである。

圏論は、個々の写像が始域の個々の要素を終域のどの要素へ移すか、
という「対象の具体的な内部構造」に立ち入らないまま、
「射の合成演算」と「射の同値関係」のみから圏の構造を議論する。

射と合成の公理†

射の合成の公理を式で表しておく：

1. 射（写像）は常に合成可能である（圏は射の合成に対して閉じている）
   　　→ $f:A\to B,\ g:B\to C$ があるならそれを合成した $g\circ f: A\to C$ も必ず圏に含まれる
   
   
2. 射の合成に結合則が成り立つ
   　　→ 任意の $f:A\to B,\ g:B\to C,\ h:C\to D$ に対して
   　　$(h\circ g)\circ f=h\circ (g\circ f)$ が常に成り立つ
   
   
3. 任意の対象が恒等射（射の単位元）$1$ を持つ
   　　→ 各対象ごとに、任意の $f:A\to B$ に対して、$f=f\circ 1_A=1_B\circ f$
   　　を満たす写像 $1_A:A\to A,\ 1_B:B\to B$ が必ず存在する（恒等射の定義も兼ねている）
   
   
4. 射の同値関係
   　　→ すぐ上で射の比較が出てきたように、個々の Hom 内で射に同値関係が定義されていることも暗に要求される
   　　→ 異なる Hom に属する射は比較できない、ということにも注意しよう

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

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

であることが要求される（$g,h$ は逆でもいい）。

一般の有向グラフは「合成に対して閉じていること」や「恒等写像が存在すること」を満たさないため、
そのままでは圏にはならない。この２つの要請は圏の性質を強く縛るものになっている。

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

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

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

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

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

最も顕著な例として、唯一の対象 $A$ へ出入りする射が恒等射 $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$ への射が一切存在しないときに限って $f$ を取り除くことができる。始対象の定義は「任意の対象に対して」一意な射を持つことなので、そのような射が１つでも欠落してしまえば始対象の資格を失う。

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

終対象の一般化された元、つまり、終対象へ入る射は、任意の射のと合成結果が定数になるという著しい性質を持つ。

終対象を 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$$ でなければならない。

元がどんな $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$ のゼロ元に移るという顕著な性質を持つ。

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

$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$ が必ず存在する

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

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

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

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

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

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

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

一般化された元、プローブ対象、錐†

一般化された元、という語は上で紹介した。

$\mathrm{Hom}(C,A)$ は $C$ をプローブとした $A$ の一般化された元。

今はプローブ対象 $C$ を変えながら、複数の対象の一般化された元、 $\mathrm{Hom}(C,A), \mathrm{Hom}(C,B)$ を同時に考えている。

このようにプローブ対象から各対象へ一般化された元が伸びる構造は「錐(cone)」と呼ばれる。

要素の言葉で考えれば、$c\in C$ が写像により $A,B$ に移された先の値同士の関係を考えていることになる。

異なる $C$ を頂点とする錐の間の関係を考える手法は今後も良く出てくることになる。

余積構造を持つ写像 = 直和†

$\mathcal C$ での積が $\mathcal C^{\mathrm{op}}$ で余積に見える、というのはその通りであるが、それとは別に
$\mathcal C$ 内に余積構造を持つ写像を構成することも可能である。

$\alpha\in A,\beta\in B$ のとき、特殊な元 $\mathrm{null}$ を使って、
$D=A+B$ を $\set{(\alpha,\mathrm{null})}\cup\set{(\mathrm{null},\beta)}$ と定義し、
$p:\alpha\mapsto (\alpha,\mathrm{null})$
$q:\beta\mapsto (\mathrm{null},\beta)$
とする。

$h$ を、

• $A+B$ の元が $\alpha$ のみ含んでいるか、$\beta$ のみ含んでいるかを判別
• その結果をもとに適切に $f$ または $g$ を適用
• $f(\alpha)$ または $g(\beta)$ を返す

とすれば、$h\circ p=f,\ h\circ q=g$ が成り立つ。

$A,B$ の元をごちゃまぜに $A+B$ に突っ込んだところから、
それらを適切に分離して $A$ または $B$ の元を取り出す方法が一意に定まる、
というのが余積の構造であると読み取ることができる。

圏における積が対象の直積に相当するのに対して、
圏における余積は対象の直和に相当する。

同型関手†

関手 $\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))$ の写像として

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

というように 忠実 および 充満 の語が定義されている。
「充満忠実な関手 $\mathccal 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 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'$ を含む) とが同値である、と呼ぶ。
（こう定義することで「同値」が対称律を持つようになる）

自己関手†

圏を自分自身の上へ移す関手のこと。 $$ \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 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})$ から生成する関手を考えているのだ。

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

プロ関手で片側のみ双対をとる必要が生まれたのは、$(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} $$ この変換が 直積の作成と、圏に存在するいくつかの射との合成によって構成されていることを確認せよ。

• $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)$ が全単射であることの証明†

全射性：
$\Phi$ が全射であることを証明するため、任意の $k\in\mathrm{Hom}(A,B)$ に対して $\Phi(h)=k$ を満たする $h$ が存在することを確かめよう。

$k$ から、$g=k\circ p:1\times A\to B$ を作る。$k,p$ とも実在の射であるから、その合成である $g$ も圏に含まれる。
関数対象の公理で $Z=1$ と置き、評価射をこの $g$ に取ると、$\mathrm{eval}\circ(h\times\mathrm{id})=g$ を満たす $h\colon 1\to(A\Rightarrow B)$ がただ１つ存在する。
この $h$ に対して $\Phi(h)=k$ となることを確かめられる。

単射性：
今見た $k$ から $h$ が一意に決まるという事実から、
$\Phi(h_1)=\Phi(h_2)=k$ から $h_1=h_2$ を導が導かれる。
これは $\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{𝑒𝑣𝑎𝑙}\circ (h\times 1_A)(z,a)\\ &=\mathrm{𝑒𝑣𝑎𝑙}\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)$$

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