プログラミング/圏論入門 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• プログラミング/圏論入門 へ行く。
• プログラミング/圏論入門 の差分を削除

#author("2026-07-12T09:51:44+00:00","default:administrator","administrator")
#author("2026-07-12T10:50:25+00:00","default:administrator","administrator")
[[公開メモ]]
&katex();

* 概要 [#j3474b48]

圏論はプログラミングにおける様々な概念の数学的なバックグラウンドを与えるということで、
前から気にはなっていたのだけれど、こちらにフリーの日本語テキストがあると聞いて読み始めました。

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

で、全然理解できなかったので、いろいろと調べながら分かった範囲をまとめようとしています~
(上のリンク先、それだけで独学するにはあまり向いていないかも？？？)

** 目次 [#bc12a31d]

#contents

* 準備： 「クラス」 について [#o1df991c]

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

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

どちらも矛盾する。

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

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

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

* 圏とは：合成演算を備えた射のクラス（あつまり） [#u20d4f6c]

圏は「射」とその「合成」演算が生み出す構造を扱う代数である。

-- 「合成」したものが必ず圏に含まれること
-- 「合成」が結合法則を満たすこと
-- 「合成」の「単位元」が存在すること

が保証された「射」のクラス(あつまり)のことを圏とよぶ。

「射」は「対象」と呼ばれるものをつなぐ形で定義される。

* 圏(category)の定義 [#f2491c65]

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

- $O$ は対象(object)と呼ばれるものを集めたクラス（集まり）
- 任意の２つの対象 $A, B\in O$ を順序付きで取り出すと、そこに「射(morphism)」のクラス（集まり） $\mathrm{Hom}(A,B)$ が付随する
- ２つの「射」の間の「合成」という演算に対して上で述べた公理が満たされる

と言ってもなんだかわからないのだが、、、

** 有向グラフ [#sf6d286a]

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

&ref(Pasted image 20260706223759.png,,66%);

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

ここには $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 圏 = すべての集合とすべての写像が作る圏 [#nd2feee4]

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

写像 $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$ が得られる → 射の合成可能性
- 写像の合成は結合則を満たす → 射の合成の結合則
- 恒等写像の存在 → 射の合成の単位元(ほかの射も合成しても射を変化させない射)になる

ただし、
+ 全ての集合を含んでいること
+ すべての可能な写像を含んでいること

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

** 射の合成とその公理 [#h40cf4fd]

射の合成は、~
任意の $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$ が圏の中に必ず存在する

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

+ 射の合成に結合則が成り立つ~
　　→ 任意の $f:A\to B,\ g:B\to C,\ h:C\to D$ に対して~
　　$(h\circ g)\circ f=h\circ (g\circ f)$ が常に成り立つ~
~
+ 任意の対象 $A$ が恒等射（射の単位元）$1_A$ を持つ~
　　→ 恒等射は任意の $f:A\to B,g:C\to A$ に対して $f=f\circ 1_A, g=1_A\circ 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$

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

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

** 対象の内部構造に踏み込まず、射の性質のみで公理化する [#b856129f]

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

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

** 圏論における「恒等射」は要素を変え得る [#ic10cba8]

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

最も顕著な例として、唯一の対象 $A$ へ出入りする射が恒等射 $e$ しかない非常に小さな圏を考える。~
このとき上の３つの公理は実質的に「恒等射が冪等であること $e\circ e=e$」しか求めない。~
+ $e\circ e=e$ であれば閉じている
+ $(e\circ e)\circ e=e\circ (e\circ e)=e$ は結合則を満たす
+ 任意の $f:A\to B$ や $g:B\to A$ というのが $e$ しかないので恒等性も $e\circ e=e$ しか要求しない

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

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

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

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

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

「恒等射」はその名前に反して「合成の単位元」であることしか保証されていないのだ。

** 恒等写像は対象あたり高々１つしか存在しない [#fb7888ad]

射の合成の話をする、の例として、

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

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


* 一般化された元 [#x44b3fd1]

大事なことなので繰り返すが、~
圏論では対象の内部構造に踏み込まず、対象同士をつなぐ射の合成だけを扱う。

その文脈において~
$Z\to A$ の射自体を~
「$Z$ をプローブとして観察した $A$ の一般化された元」と呼ぶことがある。

なぜ「$A$ へ入る射」を「$A$ の元」であるかのように呼ぶのか？

対象 $Z,A$ が離散集合であり、それらを結ぶ射が集合間の写像であるとすると、その気持ちを理解しやすい。

$f:Z\to A$ という写像は個々の $z\in Z$ をどの $a\in A$ に対応させるかを定めたテーブルと同一視できる。~
実現可能な独立な写像の数は $\#A^{\#Z}$ 個であり、そのうち実在するものだけを集めたのが $\mathrm{Hom}(Z,A)$ だ。

$f$ を 「$f$ による $Z$ の像 $f(Z)\in A$ から要素を $\#Z$ 個取り出して並べたリスト」 と同一視すると、~
$\#Z=1$ であれば、その唯一の $z\in Z$ が移された先の１個の要素 $a=f(z)$ からなるリスト $[a]$ になるから、個々の射 $f$ を対応する $A$ の元 $a=f(z)$ とすなおに同一視できる。

一方 $\#Z>1$ では射は $A$ の元そのものではなくリストに対応するので、これを「一般化された元」と呼ぶ。

これが「一般化された元」というときの気持ちだ。

* 特殊な対象、空写像 [#pad62574]

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

$A$ を任意の対象(Set圏なので集合)とすると、

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

$f:A\to\set{}$ は $A=\set{}$ であれば空写像であるが、$A\ne\set{}$ では呼び出せるのに「返せる値が存在しない」となってしまう。そのような写像は存在しえない。つまり $A\ne \set{}$ のとき $\mathrm{Hom}(A,\set{})$ は必ず空集合になる。（$A=\set{}$ なら空写像のみを含む）

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

$f:\set{()}\to A$ は与えられる要素が $()$ に固定されているので、$A$ のどの要素を返すか、だけで写像が定義されるから、$\#A$ 個の独立な写像が存在し、それらは $A$ の元と一対一対応する。

圏論ではこういった特殊な対象を普遍的に扱うために、**始対象**、**終対象**という言葉を使う。

* 始対象0、終対象1、零対象0 [#p1000317]

''始対象''$0$とは、任意の対象 $A$ に対して、$f:0\to A$ となる射がただ1つだけ存在する対象のこと。~
Set圏では $\set{}$ が始対象になる。

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

''零対象''とは、始対象かつ終対象であるような対象のこと。~
このとき $0=1$ であるが、名前のせいもあって $0$ で表現されることが多い。~
Set圏には零対象は存在しない。

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

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

このように、Set 圏（すべての集合とその間のありとあらゆる可能な写像を含む）で成り立つ話が他の圏で成り立たないことはよくあるので、どういう圏について考えているか、を常に意識しながら話を追うことが重要になる。

** 始対象 [#u7bcbb52]

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

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

** 終対象は情報を媒介しない [#j5c67afa]

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

終対象を 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}
$$

** 零対象 [#wc387951]

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

例えばベクトル空間を対象とし、線形変換を射とする圏において、~
- ゼロ次元空間 $\set{0}$ から任意の線形空間への線形変換は $0\mapsto 0$ の1種類しかない
- 任意の線形空間からゼロ次元空間 $\set{0}$ への線形変換は $v\mapsto 0$ (すべてを $0$ に移す) の1種類しかない~
したがってゼロ次元空間 $\set{0}$ は零対象である

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

*** 始対象・終対象は存在するなら同型を除いて一意である [#bda42614]

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

なぜなら、~
例えば $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$ は互いに逆射である。

逆射を持つ対象を同型と呼ぶ、と言う話が次。

* 対象の同型性 = 逆射の存在 [#i91d7851]

２つの射 $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}$ が必ずしも圏に含まれないため 素朴には同一視はできないことに注意が必要である。

$A$ と $B$ が同型であることを $A\cong B$ と書くことにする。

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

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

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

* 「集合の元」に一対一対応する「射」 [#n8043daa]

一般化された元のところで、集合と写像の圏においては 

$\#Z=1$ となる集合 $Z=\set{z}$ に対して、~
任意の $f:Z->A$ は $a=f(z)\in A$ という定数写像であるから、~
その定数である特定の $A$ の要素 $a$ と同一視できる、と述べた。

Set 圏は対象間に「考え得るあらゆる写像」を射として含むため、
- $\#Z=1$ となる集合はすべて終対象になる
- $\#Z=1$ のとき $\mathrm{Hom}(Z,A)$ は $A$ の全ての元に一対一に対応する射を含む

通常、圏論では「対象の中身に踏み込まず射の合成のみに注目する」のであるが、~
Set 圏では「対象の要素」に一対一対応する射 $\mathrm{Hom}(1,A)$ があるので、~
集合の要素の演算を間接的に圏論に取り込める。

例えば、$a\in \mathrm{Hom}(1,A)$ とすれば、これはあくまで「$a$ を返す定数写像」であるが~
任意の $f:A\to B$ に対して $f\circ a\in \mathrm{Hom}(1,B)$ は $f(a)\in B$ に対応する定数写像になるから、~
$f(a)$ の計算を射の合成 $f\circ a$ で再現していることになる。

集合の元から元への計算をすべてそのまま、射の合成として表せるのだ。

これは非常に便利な性質であるため、Set でない一般の集合＋写像の圏でも、~
終状態 $1$ の存在と、任意の $A$ の要素を生成する定数写像が $\mathrm{Hom}(1,A)$ 
に含まれることを仮定する場合が多い。

そこで仮定される~
- すべての集合から唯一の射が伸びる終状態 $1$
- そこから任意の元を生成する定数写像

これらの「実体」は何なのか？~
そんなものを持つなんてまれなケースじゃないの？~
と考え始めると悩むことになるのだが、

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

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

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

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

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

** well-pointed や separator の概念との違い [#g619e17c]

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

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

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

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

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

* 単射、全射、全単射 [#lcb320f8]

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

$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$ となる射が存在せず、公理が実質何のチェックも行わないためだ。

当然、こういう「実際には何のチェックもされていない全単射」は「逆射の存在」を保証しない。~
圏論では「全単射」と「逆射の存在」とがまったく別の概念となることに注意を払おう。

* 双対性 [#sfe5617e]

|用語     |定義                                  |
| 始対象$0$ | 任意の対象 $A$ に対して、$f:0\to A$ となる射がただ1つ |
| 終対象$1$ | 任意の対象 $A$ に対して、$f:A\to 1$ となる射がただ1つ |
のように並べてみると、これらの定義は矢印の方向が逆なだけでそっくりな形をしている。

この類似性は双対性（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$ の写像の集合であるとしよう、と言っている。対象であったり、写像であったりといった実体は同じまま、射の向きを写像の向きと反対方向に取ると定義するだけ。

もともと圏論の「射」は抽象的な概念であるから、~
写像 $f:A\to B$ を表す「射の向き」を写像の「終域 $B$ から始域 $A$ への向きに取る」~
と定めたとしても、それはそれで写像の世界を圏に写し取る正しい手段になるのだ。

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

圏論で１つ定理を証明すると、その双対も自動的に証明されるのは便利な性質である。

* 積 (product) [#td84fd18]

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

&ref(Pasted image 20260707083253.png,,66%);

考えているストーリーは以下のようなもの：
- 要素 $\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)$があってはならない。

ここまでの議論は $A,B,A\times B$ の元について直接考える代わりに、~
$C$ からそれぞれの対象に元を生成する射$f,g,h$に基づいたものになっていた。

** 一般化された元、プローブ対象、錐 [#q8192344]

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

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

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

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

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

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

* 余積 (coproduct) [#af650fdd]

余積は積と双対関係にある構造である。互いに双対関係にあるペア、と言う意味で 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$ に対して、~
''ただ1本の射'' $h: D\to C$ が存在して、~ 
$h\circ p = f$ かつ $h\circ q = g$ を満たす。

|積 $D$                                                                                              |余積 $D$                                                                                               |
| $p:D\to A$&br();$q:D\to B$&br();$f:C\to A$&br();$g:C\to B$&br();$h:C\to D$&br();$p\circ h=f$&br();$q\circ h=g$ | $p:A\to D$&br();$q:B\to D$&br();$f: A\to C$&br();$g: B\to C$&br();$h:D\to C$&br();$h\circ p=f$&br();$h\circ q=g$ |

** 余積構造を持つ写像 = 直和 [#c42e028d]

$\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$ の元を取り出す方法が一意に定まる、~
というのが余積の構造であると読み取ることができる。

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

* 積と余積とデータ構造 [#b0fab2ac]

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

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

* 関手 (functor) [#v90de57e]

関手はある圏 $\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)}
$$

&ref(Pasted image 20260707140611.png,,66%);

関手は $\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$ の情報は何も残らないが、このようなものも関手の一つであるとされる。

射に関手を適用して、終域となる圏の上の射を得ることをしばしば「持ち上げる(lift)」と表現するようだ。~
例：「$f$ を $\mathcal F$ で持ち上げて $g$ を得る」

** 同型関手 [#ad059c90]

関手 $\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$ が全単射)

** 関手は対象の同型性も保つ [#iedb145e]

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

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

同型な対象 $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)$ を表す。


** 同値関手 [#kf804a23]

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

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

例題として、$\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'$ を含む) とが同値である、と呼ぶ。~
（こう定義することで「同値」が対称律を持つようになる）

** 自己関手 [#z27acddc]

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

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

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

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

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

関手が「新たな圏を生成するもの」でないことは肝に銘じよう。

** 具体例：リスト関手 [#ic9a5854]

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

&ref(Pasted image 20260707150259.png,,66%);

リスト関手$\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 しか与えられていないなら充満になりうる。

* 双関手 [#j040bfef]

上で見た関手は $\mathcal C$ から $\mathcal C'$ への写像、つまり１つの圏から１つの圏への写像。

双関手は２つの圏から１つの圏への関手であるのだが、説明のまえに準備をしよう。

** 準備：積圏 [#j6087304]

２つの圏$\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つの圏を「横に並べて、対象も射もペアにしただけ」のもの。

** 双関手 [#waeb8b89]

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

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

** 積の双関手 [#kfc274c9]

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

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

&ref(Pasted image 20260707201127.png,,66%);

$\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$ を仮定したのであった。このように、積の双関手は圏が積構造を含む際に初めから存在した構造を浮き彫りにしたものとみなせる。

** 余積の双関手 [#m7fa1582]

同様に余積の双関手も作れる。~
$\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)$ ~
これも余積の構造に付随して初めから存在する構造に名前を付けたものとみなせる。~

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

** 反変関手・共変関手 [#kf959ce8]

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

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

** プロ関手 [#leef0fc6]

第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)$」                     | →   | 対象「$B\to C$ の任意の関数」                             |
| 対象「ペア $(A,D)$」                     | →   | 対象「$A\to D$ の任意の関数」                             |
| 射 $(f_{ab}^{\mathrm{op}}, f_{cd})$ | →   | 「$B\to C$ の任意の関数」から「$A\to D$ の任意の関数」への射&br();$g\mapsto f_{cd}\circ g\circ f_{ab}$  (関数の変換) |

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

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

~

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

| 関手の変換元                             |     | 関手の変換先                                          |
| 対象「ペア $(B,C)$」                     | →   | 目的に応じて変換したもの                             |
| 対象「ペア $(A,D)$」                     | →   | 目的に応じて変換したもの                             |
| 射 $(f_{ab}^{\mathrm{op}}, f_{cd})$ | →   | 目的に応じて変換したもの |

** Hom関手 [#u1eb7932]

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

| 関手の変換元                             |     | 関手の変換先                                                                |
| 対象「ペア $(B,C)$」                     | →   | $B\to C$ の射の集合 $\mathrm{Hom}(B,C)$                                    |
| 対象「ペア $(A,D)$」                     | →   | $A\to D$ の射の集合 $\mathrm{Hom}(A,D)$                                    |
| 射 $(f_{ab}^{\mathrm{op}}, f_{cd})$ | →   | 射 $g\mapsto f_{cd}\circ g\circ f_{ab}$&br();$B\to C$ から $A\to D$ への射の変換 |

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

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

* 関数対象 [#n92f661d]

** その意味するところ [#se14a313]

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

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

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

** 公理化の方針 [#q8178a6f]

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

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

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

** 公理の実体 [#c7667153]

考える関数（射）の始域を $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)$ の意味 [#s97afa05]

等号で結ばれた２つの射に $(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'$ を過不足なく生成可能と言うのか？

** 過不足なく生成可能 [#oaebf641]

上の条件を成り立たせる $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$ から「過不足なく生成可能」の意味である。

** すべての候補を過不足なく生成可能 [#j1374aed]

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

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

** 追加で必要な条件 [#o6cf3251]

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

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

> 上記の公理により、$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$ の存在を追加 [#ke39707e]

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

*** 補題: $1\times A$ は $A$ と同型である [#dee09b12]

$1 \times A$ は積なので、積の公理のプローブ対象として $A$ を取ると、~
$f:A\to A$ を恒等射, $g:A\to 1$ を終対象への一意な射として、~
$p:1\times A\to 1, q:1\times A\to A$ に対して $f=p\circ c,g=q\circ c$ を満たす~
唯一の $c:A\to 1\times A$ が存在することが出てくる。

このうち $f=p\circ c$ は $f$ が恒等射であるから、$p$ と $c$ が互いに逆射であること示す。~
$p:1\times A\to A$　が逆射を持つから $1\times A$ は $A$ と同型である。

** 証明したい内容 [#d004614c]

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

$\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)$ の導入 [#l039a72e]

具体的な $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)$ が全単射であることの証明 [#f3827259]

全射性：~
$\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)
$$
** 実集合との対応 [#h71c69a0]

圏論が示すのはあくまで、
$$\#\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$ のコンストラクタを二段階に
分解したときに必要になる積として、自然に導入される。

** カリー化 [#l02f7fab]

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

例えば 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) [#n86bc69d]

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

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

** デカルト閉圏 と 整数算術 [#n8167cfe]

上で $\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)$$

（これはあくまで説明を簡単にするための仮定であって、デカルト閉圏そのものに要求されるものではない）
*** 積と冪の関係 [#z1ac8fb9]

積を任意に繰り返せるとき、同型の意味で結合則を満たすため、
$$
A\times B\times C\cong(A\times B)\times C\cong A\times (B\times C)
$$
を同型を除き一意に定義可能。~
この対象の元は $(a,b,c)$ のようなタプルと思えばいい。

ここから同じ対象の自然数に対する冪が作れる。
$$
A^n\cong\underbrace{A\times A\times\dots\times A}_{n\text{回}}
$$
こちらは同じ集合の要素のタプル $(a_1,a_2,\dots,a_n)$

この自然数による冪と、対象 $B$ による冪 $A^B$ とが似た表記になっているのは偶然ではない。

$A^B=B\Rightarrow A$ を $\mathrm{Hom}(B,A)$ と同一視できるとき、その元は $B\to A$ の写像だ。

一般化された元のところで述べたように、$A,B$ が有限集合の時、これは $B$ の要素のそれぞれを
どの $A$ の要素に変換するかという変換表： $A$ の要素を $\#B$ 個並べたもの と同一視できる。

したがって $A^B$ は $A^{\#B} = \underbrace{A\times A\times\dots\times A}_{\#B\,\text{個}}$ 
の部分集合と「同一視」できる。（これは対象の同型とかじゃなく、集合としての一対一関係）

つまり、概念的には $A^B \subset A^{\#B}$ みたいなこと。

$\#(A^B)=\#(A^{\#B})$ つまり、$\mathrm{Hom}(B,A)$ が考え得るすべての射を含んでいるときには、~
$A^B\cong A^{\#B}$ つまり両者が実際に同型になるらしいのだが、その証明はもう少し進まないと難しい？

*** 終対象 $1$、始対象 $0$ との積 [#v18fb8ac]

先に $1\times A\cong A$ を証明したが、同様に $A\times 1\cong A$ であり、~
終対象 $1$ は積に対する単位元になる。

だから一般に $1^A\cong 1$

これは $A\Rightarrow 1\cong 1$ であり、任意の $A$ から終対象 $1$ への写像、
デストラクタがただ１つ存在する、という主張と解釈できる。

一般の圏では始対象 $0$ と任意の対象 $A$ の積に特別な性質を見いだせないが、

始対象 $0$ を持つデカルト閉圏では $A\times 0\cong 0\times A\cong 0$ が言える。

というのも、カリー化の等式から、
$$
\mathrm{Hom}(0\times A,B)\cong \mathrm{Hom}(0,A\Rightarrow B)
$$
であるが、この右辺は始対象から $A\Rightarrow B$ への唯一の射であるから、~
左辺がこれと一対一なのは、~
任意の $B$ に対して $0\times A$ からただ１つの射が飛ぶこと、~
つまり、$0\times A$ が始対象であること、~
つまり、$0$ と同型であること、を表している。

ここに一般に $A\times B\cong B\times A$ であることを加えると、
$A\times 0\cong 0\times A\cong 0$ が出る。

要素が存在しない型とのタプルには要素が存在しない、と読める。
*** 始対象 $0$ による $A^0\cong 1$ [#f8ab859a]

これは $A$ の要素が一つも入っていない $()$ からなる集合が $1=\set{()}$ 
と読める。

$0$ が数字のゼロでなく始対象のとき、~
$A^0\cong(0\Rightarrow A)\cong1$  となることは、カリー化の式
$$
\#\mathrm{Hom}(Z\times 0,A)= \#\mathrm{Hom}(Z,0\Rightarrow A)
$$
から出る。左辺は $Z\times 0\cong 0$ より始対象から $B$ への唯一の射を持つから、
右辺より任意の対象 $Z$ から $0\Rightarrow A$ へ唯一の射が存在すること、すなわち $0\Rightarrow A=A^0$ が始対象であること、したがって $1$ と同型であることが言える。

*** 終対象 $1$ による $A^1\cong A$ [#p5bf8578]

$(1\Rightarrow A)=A^1\cong A$ は $A$ の元とコンストラクタ $1\Rightarrow A$ の元との一対一対応を表す。

証明はかなり大変。~
実際に逆射を作って $A\cong(1\Rightarrow A)$ を確認する。

(1) $u: A\to (1\Rightarrow A)$ を定義:

与えられた $a\in A$ に対応するコンストラクタ $\hat a:1\Rightarrow A$ を返す。~
$1\Rightarrow A$ の評価射を $\mathrm{eval}:(1\Rightarrow A)\times 1\to A$ とし、~
これらを使った積 $A\times 1$ の左取り出し射 $p_{A\times 1}\colon A\times 1\to A$ のカリー化を考えると、
$$
p_{A\times 1}=\mathrm{eval}\circ(u\times 1_1)
$$を満たす一意な $u\colon A\to(1\Rightarrow A)$ が関数対象の公理から得られる。

(2) $v: (1\Rightarrow A)\to A$ を定義:

コンストラクタ $\hat a:1\Rightarrow A$ が与えられたら対応する $a$ を返す。~
恒等射 $1_{1\Rightarrow A}$ と終対象への射 $!_{1\Rightarrow A}$ を使って $(\hat a, 1)$ を作り~
$\mathrm{eval}$ に与えればいい。
$$
v=\mathrm{eval}\,\circ\langle1_{1\Rightarrow A},!_{1\Rightarrow A}\rangle
$$
ここで $\langle1_{1\Rightarrow A},!_{1\Rightarrow A}\rangle_{A\times 1}$ は積の取り出し写像により $1_{1\Rightarrow A},!_{1\Rightarrow A}$ を再現可能な $(1\Rightarrow A)\times 1$ を作る唯一の射(積の公理により存在が保証される)。

(3) $v\circ u=1_A$ を示す

$$
v\circ u=\mathrm{eval}\,\circ\langle1_{1\Rightarrow A},!_{1\Rightarrow A}\rangle\circ u
$$
ここで、
$$
\begin{aligned}
\langle1_{1\Rightarrow A},!_{1\Rightarrow A}\rangle\circ u
&=\langle u,!_A\rangle\\
&=(u\times 1_1)\circ\langle 1_A,!_A\rangle
\end{aligned}
$$
と書き換えられるから、
$$
v\circ u=p_{A\times 1}\circ\langle 1_A,!_A\rangle=1_A
$$
積を作って左側を取り出す演算で $1_A$ が取り出される。

(4) $u\circ v=1_{1\Rightarrow A}$ を示す

$$
u\circ v=u\circ \mathrm{eval}\,\circ\langle1_{1\Rightarrow A},!_{1\Rightarrow A}\rangle
$$
関数対象の公理により $\mathrm{eval}\colon (1\Rightarrow A)\times1\to A$ 自身をカリー化して
$$
\mathrm{eval}=\mathrm{eval}\circ(x\times 1_1)
$$
と表すような $x:(1\Rightarrow A)\to(1\Rightarrow A)$ がただ１つ存在することが保証される。

つまり $1_{1\Rightarrow A}$ と $u\circ v$ とがどちらも $x$ として有効であるなら両者は等しいことになる。
$$
\mathrm{eval}\circ(1_{1\Rightarrow A}\times 1_1)
=\mathrm{eval}\circ1_{(1\Rightarrow A)\times 1}=\mathrm{eval}
$$
の方は簡単で、$u\circ v$ についても、
$$
\begin{aligned}
&\mathrm{eval}\circ((u\circ v)\times 1_1)\\
=&\,\mathrm{eval}\circ (u\times1_1)\circ(v\times 1_1)\\
=&\,p_{A\times 1}\circ(v\times 1_1)\\
=&\,v\circ p_{(1\Rightarrow A)\times 1}\\
=&\,\mathrm{eval}\,\circ\langle1_{1\Rightarrow A},!_{1\Rightarrow A}\rangle\circ p_{(1\Rightarrow A)\times 1}\\
=&\,\mathrm{eval}\,\circ1_{A\times 1}\\
=&\,\mathrm{eval}
\end{aligned}
$$
途中、$\langle1_{1\Rightarrow A},!_{1\Rightarrow A}\rangle\circ p_{(1\Rightarrow A)\times 1}$ が $p_{(1\Rightarrow A)\times 1}$ により $(1\Rightarrow A)\times 1$ の左側を取り出した後、再び右側に $1$ を添える写像になっているため $1_{(1\Rightarrow A)\times 1}$ に等しいことを使った。

逆射を持つ写像 $u$ で結ばれるため $(1\Rightarrow A)=A^1\cong A$

PukiWiki 1.5.4 © 2001-2022 PukiWiki Development Team. Powered by PHP 8.2.31. HTML convert time: 0.016 sec.
Also based on Bootstrap, Start Bootstrap - SB Admin 2, highlight.js, Google fonts, Google recaptcha, Google chart, Bitly.