米田の補題にまつわるあれこれを具体例を通して整理してみる ～ universal element

圏論

米田の補題と表現可能関手の関係は？

前回の記事では表現可能関手と米田の補題に関する例を紹介した。前回は初めに表現可能関手を導入しておきながら、その後の米田の補題では「実は表現可能関手は補題の主張に登場しません」という、一見するとわけが分からない説明をしていた。正直、ここは執筆時点での私の理解度の低さもあり、説明の流れがいまいちだったと反省している。

確かに米田の補題の主張に表現可能関手は登場しないが、 H^Aとか H_Aのようにそれを匂わせる要素は登場している。実際、両者は全くの無関係ではない。本稿では米田の補題と表現可能関手が関わりを持つ事例としてuniversal elementというものについて例を用いながら説明する。

Universal element

まずはuniversal element の定義を本[1]から引用する。

Universal element
Let \mathcal{A} be a locally small category and X: \mathcal{A}^\mathrm{op} \to \mathbf{Set}. Then a representation of X consists of an object A \in \mathcal{A} together with an element u \in X(A) such that:
\begin{equation} \begin{split} &\text{for each } B \in \mathcal{A} \text{ and } x \in X(B), \\ &\text{there is a unique map } \bar{x}: B \to A \\ &\text{such that } (X\bar{x})(u) = x. \end{split} \tag{4.6} \end{equation} ・・・中略・・・
An element u satisfying condition (4.6) is sometimes called a universal element of X.

上記の関係を図に描くと以下のようになる。

Universal element

つまり、反変関手 Xに対してあるすごい要素 u \in X(A)があって、 B \in \mathcal{A}, x \in X(B)に対して射 \bar{x}: B \to Aが一意に定まって、 uを経由しつつ \bar{x}から xへ至る道があるという感じである。このように射が一意に定まるというのは普遍性そのものであり、 uは普遍性を導き出してくれるものなのでuniversalの名を冠しているのだろう。

ここで、前回の記事で紹介した表現可能関手の定義を見てみよう。この定義の後半には Xの表現（representation）について説明されていた。おさらいすると、表現可能関手 Xについて Xの表現とは対象 A \in \mathcal{A}と自然同型 \alpha: H_A \Rightarrow Xの組のことであった。

本節の冒頭で紹介したuniversal elementの定義の前半部分では、 Xの表現は組 (A, u)によっても決まると言っている。これはつまり、条件(4.6)を満たす uと一対一に対応する自然同型 \alphaにがあって、組 (A, u)と組 (A, \alpha)のいずれを考えても実質同じだということである。以下ではそのことについて説明しよう（全体的に[1]を参考にした）。

まず、米田の補題より元 u \in X(A)に対して一対一に対応する自然変換 \tilde{u}: H_A \Rightarrow Xが存在する（これが先ほどまで \alphaと呼んでいたものに相当するが、説明の都合により記号を変える）。この uに対して条件(4.6)が成り立つことと \tilde{u}が自然同型であることが同値であると言えればよい。

そのために、まず B \in \mathcal{A}について \tilde{u}_B : H_A(B) = \mathcal{A}(B, A) \to X(B)という写像を以下のように定義しよう。

\begin{equation} \tilde{u}_B(f) = (X(f))(u) \in X(B) \end{equation}

このような射の族 \tilde{u} = (\tilde{u}_B)_{B\in \mathcal{A}}は Bについて自然であることが示せる（詳細は本[1]などを参照）。つまり、 \tilde{u}_Bを B成分とするような自然変換 \tilde{u}を考えることができる。

この \tilde{\quad}という写像は前回紹介した \hat{\quad}の逆写像になっており、 \hat{\tilde{u}} = uを満たす。

\tilde{u}が自然同型であるということは全ての B \in \mathcal{A}成分について \tilde{u}_Bが全単射であることと同値である。さらにこれは全ての Bと x \in X(B)について \tilde{u}_B(\bar{x}) = xとなるような \bar{x} \in \mathcal{A}(B, A)が一意に存在することと同値である。 \tilde{u}_B(\bar{x}) = (X \bar{x})(u)なので、これは結局条件(4.6)そのものである。以上により \tilde{u}が自然同型であることと条件(4.6)が成り立つことは同値である。

ここまでuniversal elementの性質について説明したが、本質的には米田の補題によって自然変換 \tilde{u}と uが対応するからこそ、 X(A)の元である uだけで反変関手 Xの表現が決まってしまうのだと言えよう。

共変バージョン

この後の例で使うためにuniversal elementに関するcorollaryの共変バージョンも本[1]から引用しておく。

Universal element（共変バージョン）
Let \mathcal{A} be a locally small category and X: \mathcal{A} \to \mathbf{Set}. Then a representation of X consists of an object A \in \mathcal{A} together with an element u \in X(A) such that:
\begin{equation} \begin{split} &\text{for each } B \in \mathcal{A} \text{ and } x \in X(B), \\ &\text{there is a unique map } \bar{x}: A \to B \\ &\text{such that } (X\bar{x})(u) = x. \end{split} \tag{4.7} \end{equation}

表現可能関手とuniversal elementの関係

私は本[1]を読んでいて一つ釈然としないことがあった。それは、4.3節でuniversal elementについて説明している中で一度も"representable"とか"representable functor"という言葉が出てこないことである。例の中には出てくるのだが、理論的な説明をしているところにはこれらの言葉が出てこない。一方、"representation"という言葉は出てくる。

圏論素人である自分からすると、結局representation（表現）が定まっているということは表現可能関手だと思ってよいのか？とか、あるいは同じことだがuniversal elementがあれば表現可能関手だと言ってよいのか？とかが初め良く分からなかった。

今の自分の理解としては、これらの問いへの答えはYESだと考えている。というのも、表現というのは対象 A \in \mathcal{A}とuniversal element uの組なわけだが、これは Aと自然同型 \tilde{u}: H_A \Rightarrow Xの組と一対一に対応する。そして \tilde{u}が自然同型ということは関手 Xは定義により表現可能関手になるからである。逆に、表現可能関手に対して表現 (A, \alpha)が存在することは定義より明らかである。そのため、 Xがuniversal elementを持つことと表現可能関手であることは同値であると言える、と思う。

本[1]にはこれらについて明示的に書かれていなかったので、一応ここで自分の理解を示しておいた。

例

前回の記事の例においてuniversal elementがどうなるのかを考えてみよう。

共変バージョンの例

前回と同じく体 k上の線形空間の圏 {\bf Vect}_kに対する忘却関手 U : {\bf Vect}_k \to {\bf Set}を考える。 u \in U(k)を0でない元とする。また、写像 \tilde{u}_V: \mathbf{Vect}_k(k, V) \to U(V)を以下のように定義する。

\begin{equation} \tilde{u}_V(f) = (Uf)(u) \end{equation}

ベクトル空間 Vと x \in U(V)を任意に選んだとき、 \tilde{u}_V(f) = xとなるような線形写像 f \in \mathbf{Vect}_k(k, V)が一意に定まれば uはuniversal elementだと言える。そこで、 \mathbf{x} \in V, x = U(\mathbf{x})に対して f_\mathbf{x}: k \to Vを以下のように定義する。

\begin{equation} f_\mathbf{x}(\lambda) = \frac{\lambda}{u'} \mathbf{x} \end{equation}

ただし、 u' \in k, u = U(u')であるとする。 f_\mathbf{x}を \tilde{u}_V(f)に代入すると以下のようになる。

\begin{equation} \begin{aligned} (Uf_\mathbf{x})(u) &= U(f_\mathbf{x}(u')) \\ &= U(\mathbf{x}) \\ &= x \end{aligned} \end{equation}

次に f_\mathbf{x}(u') = \mathbf{x}を満たすような f_\mathbf{x}の一意性を示す。線形写像 gについて g(u') = \mathbf{x}と仮定すると以下の式が成り立つ。

\begin{equation} \begin{aligned} g(\lambda) &= \frac{\lambda}{u'} g(u') \\ &= \frac{\lambda}{u'} \mathbf{x} \\ &= \frac{\lambda}{u'} f_\mathbf{x}(u') \\ &= f_\mathbf{x}(\lambda) \end{aligned} \end{equation}

よって g=f_\mathbf{x}となるので f_\mathbf{x}は一意に定まる。以上により u \in U(k)はuniversal elementだと言える。この事実より明らかだが、一般にuniversal elementは1つだけ存在するとは限らない。

ところで、なぜ u \ne 0である必要があったのだろうか？試しに \tilde{0}の V成分を考えてみると、 \tilde{0}_V = (Uf)(0) = U(f(0)) = U(\mathbf{0}) = 0となり、 \tilde{0}が自然同型にならない。よって U(k)の元のうち0だけはuniversal elementにならない。

反変バージョンの例

前回と同じく集合に対する冪集合を返す関手 \mathcal{P}: {\bf Set}^\mathrm{op} \to {\bf Set}を考える。 U \in \mathcal{P}(\mathbf{2})とし、写像 \tilde{U}_S: \mathbf{Set}(S, \mathbf{2}) \to \mathcal{P}(S)を以下のように定義する。

\begin{equation} \tilde{U}_S(f) = (\mathcal{P}f)(U) \end{equation}

集合 Sと X \in \mathcal{P}(S)を任意に選んだとき、 \tilde{U}_S(f) = Xとなるような写像 f \in \mathbf{Set}(S, \mathbf{2})が一意に定まれば Uはuniversal elementだと言える。 Uの候補としては \emptyset, \{0\}, \{1\}, \mathbf{2}の4つがある。それぞれについて考えてみよう。

U=\{0\}のとき、 X \in \mathcal{P}(S)に対して f_X: S \to \mathbf{2}を以下のように定義する。

\begin{equation} f_X(s) = \begin{cases} 0 & (s \in X) \\ 1 & (s \notin X) \end{cases} \end{equation}

f_Xを \tilde{U}_S(f)に代入すると以下のようになる。

\begin{equation} \begin{aligned} (\mathcal{P}f_X)(\{0\}) &= f_X^{-1}(\{0\}) \\ &= X \end{aligned} \end{equation}

次に f_Xの一意性についてだが、これはほぼ自明なので割愛する。

以上により \{0\} \in \mathcal{P}(\mathbf{2})はuniversal elementだと言える。

同様に、 U = \{1\}の場合は以下のような f_Xに対してのみ (\mathcal{P}f_X)(\{1\}) = Xが成り立つ。

\begin{equation} f_X(s) = \begin{cases} 1 & (s \in X) \\ 0 & (s \notin X) \end{cases} \end{equation}

よって \{1\} \in \mathcal{P}(\mathbf{2})もuniversal elementである。

一方、 \emptysetおよび \mathbf{2}はuniversal elementではない。試しに U=\emptysetおよび U=\mathbf{2}に対してそれぞれ \tilde{U}_S(f)を計算してみると、 fに関わらず以下のような結果になる。

\begin{equation} \begin{aligned} (\mathcal{P}f)(\emptyset) &= f^{−1}(\emptyset) \\ &=\emptyset \\ (\mathcal{P}f)(\mathbf{2}) &= f^{−1}(\mathbf{2}) \\ &=S \\ \end{aligned} \end{equation}

これより任意の Xに対して \tilde{U}_S(f) = Xとなるような fをどう足掻いても構成できないので、 \emptysetおよび \mathbf{2}はuniversal elementではない。

まとめ

本稿では表現可能関手に関する重要な概念であるuniversal elementについて説明した。その中で米田の補題が重要な役割を担っていることについて言及した。最後にuniversal elementの例を2つ紹介した。

米田の補題にまつわる諸概念は初見だと本当に頭がこんがらがって全然理解できず、根気よく考えることが必要だった。しかし、良く分からないことを分かるまで考えてみるのは非常に楽しい。

今回も勉強の過程でChatGPTをたくさん使ったが、AIなしではかなり厳しかったと思う。数学の初歩的な事項を独学するには本当に良い時代になった（研究レベルで使い物になるのかはよく知らないが）。

参考

[1] [1612.09375] Basic Category Theory

米田の補題にまつわるあれこれを具体例を通して整理してみる ～ 表現可能関手と米田の補題

圏論

米田の補題が分かりたい

最近、圏論の勉強が進んでついに米田の補題まで辿り着いた。何を隠そうこれまで圏論を勉強してきた目標は米田の補題を理解することだったので、ここは是非ともちゃんと理解したい。しかし、数年前に勉強したときもそうだったが、米田の補題は何を言っているのかさっぱり分からない。そもそも前提となる表現可能関手が難しいし、関連して登場する米田埋め込みとかuniversal elementとかも何がしたいのかよく分からない。

前回はそれで挫折してしまったのだが、今回は随伴までの内容を多少まじめに勉強したこと、およびChatGPTが使える世の中になったことで、多少なりとも米田の補題が言わんとすることが分かってきた。そこで、いくつかの具体例を通して、米田の補題とそれにまつわる様々な概念がどのように繋がっており、それぞれどのような意味を持つのかを考えてみる。

例によって一つの記事に書き切るのは書くのも読むのも厳しいと思われるので、本稿では表現可能関手と米田の補題に絞って話をする。それに付随するいくつかの概念については次回以降に書きたいと思う。

理論的な話

表現可能関手

話の出発点は表現可能関手である。定義を[1]から引用する。

表現可能関手（共変バージョン）
Let \mathcal{A} be a locally small category. A functor X: \mathcal{A} \to {\bf Set} is representable if X \cong H^A for some A \in \mathcal{A}. A representation of X is a choice of an object A \in \mathcal{A} and an isomorphism between H^A and X.

ただし、 H^Aは関手で、 H^A = \mathcal{A}(A,−): \mathcal{A} \to {\bf Set}である。本[1]の記法に慣れていないと分かりづらいが、locally smallな圏 \mathcal{A}に対して \mathcal{A}(A,B)と書いたときには対象 A, B \in \mathcal{A}の間の射 A \to Bの集合を意味する。'−'はここが変数になっていることを意味する。つまり、 H^Aに入力として \mathcal{A}の対象 Bを与えると、出力として \mathcal{A}(A,B)という集合が得られるということである。

H^Aは関手なので射がどうなるのかも気にしておく必要がある。 \mathcal{A}の射 g: B \to B'が入力として与えられたとき、 H^A(g): \mathcal{A}(A,B) \to \mathcal{A}(A,B')は全ての射 p: A \to Bに対して p \to g \circ pという射を与える。以下に図を示す。

関手 H^A

ここまで説明したのは共変関手となるような表現可能関手である。これとは別に反変関手となるような表現可能関手も存在する。反変バージョンの定義を[1]から引用する。

表現可能関手（反変バージョン）
Let \mathcal{A} be a locally small category. A functor X: \mathcal{A}^\mathrm{op} \to {\bf Set} is representable if X \cong H_A for some A \in \mathcal{A}. A representation of X is a choice of an object A \in \mathcal{A} and an isomorphism between H_A and X.

H_Aは共変バージョンの定義に出てくる H^Aと似たような関手だが、反変関手であるという点に注意が必要である。すなわち、 \mathcal{A}の射 g: B' \to B（共変の場合とは逆向き）が入力として与えられたとき、 H_A(g): \mathcal{A}(B, A) \to \mathcal{A}(B', A)は全ての射 p: B \to Aに対して p \to p \circ gという射を与える。以下に図を示す。

関手 H_A

米田の補題

米田の補題を本[1]から引用する。

米田の補題
Let \mathcal{A} be a locally small category. Then
\displaystyle{ [\mathcal{A}^\mathrm{op}, {\bf Set} ](H_A, X) \cong X(A) }
naturally in A \in \mathcal{A} and X \in [\mathcal{A}^\mathrm{op}, {\bf Set} ].

この定義も本[1]の記法に慣れていないと理解しづらいので補足しておく。まず、 [\mathcal{A}^\mathrm{op}, {\bf Set} ]は関手圏を表す。この関手圏における射 H_A \to X全体の集合が [\mathcal{A}^\mathrm{op}, {\bf Set} ](H_A, X)である。関手圏の射とは自然変換のことであるから、これは要するに H_Aから Xへの自然変換全体の集合を意味する。Wikipedia[2]なんかを見ると \mathop {\mathrm {Nat} } (H_{A},F)\cong F(A)みたいに書かれていたりするが、同じことである。

見ての通り本[1]に書かれている米田の補題は H_Aを用いて書かれており、いわば反変バージョンであると言えるが、 H^Aを用いても同じような主張が成り立つらしい[2]。

話の流れ的に大変ややこしいのだが、補題の主張に出てくる Xは必ずしも表現可能関手である必要はない。

証明のアウトライン

この場で米田の補題の完全な証明をするつもりはない。それについては本[1]が素晴らしいのでそちらを見て頂ければと思う。しかし、この後に説明する例を理解する上で証明が全く頭に入っていないと辛い部分があるのと、シンプルに面白い話があるので、ざっくりアウトラインだけ述べておく。まず、自然変換 \alpha \in [\mathcal{A}^\mathrm{op}, {\bf Set} ](H_A, X)について、これに対応する X(A)の元を得るための写像を作ってやる（これを米田写像というらしい[2]）。それが全単射であることを示す。その後、 A, Xに関する自然性条件をコツコツと調べればよい。

前半の全単射性の証明についてもう少し説明する。まず、 \alphaに対して \hat{\alpha} = \alpha_A(1_A)と定める。 \alpha_Aは \alphaの A成分であり、 H_A(A) \to X(A)という写像になる。定義より H_A(A) = \mathcal{A}(A, A)であり、 1_A \in \mathcal{A}(A, A)なので確かに \hat{\alpha} \in X(A)となっている。

この後は^の逆向きの写像を構成して全単射性を示していく流れになるわけだが、ここで面白いのが \hat{\alpha}が 1_Aの値だけで決まるということである。あたかも 1_Aが「 \alpha全体の代表です」みたいな顔をして右向きの写像を定義しているわけだが、これがちゃんと全単射になるから驚きである。こういうところに圏論の面白さが詰まっているように（個人的には）感じる。

具体例

ではいよいよ具体例を見ていこう。共変バージョンと反変バージョンでそれぞれ微妙に違った面白さがあるので、どちらの例も取り上げる。

なお、米田の補題に登場する関手 Xは必ずしも表現可能関手である必要はないのだが、次の記事へのつなぎとして表現可能関手だと都合がよい。というわけで、ここでは Xが表現可能関手であるような例を紹介する。

共変バージョンの例

体 k上の線形空間の圏 {\bf Vect}_kに対する忘却関手 U : {\bf Vect}_k \to {\bf Set}を考える。まずは Uが共変バージョンの表現可能関手であることを示す。

線形空間 V \in {\bf Vect}_kについて線形写像 \phi: k \to Vを考える。 \phiは kのいろいろな値を取るので、それぞれに対して行き先がどうなるかを決めてやらないと写像として定まらないように思える。しかし、 \phiの線形性より任意の \lambda \in kに対して \phi(\lambda) = \lambda \phi(1)\; (1 \in k)となるので、実は \phi(1)の行き先さえ決まれば \phiは定まる。 \phi(1)の行き先としては Vの任意の元を取れるので、このような線形写像全体の集合と Vの元は一対一に対応する。これより {\bf Vect}_k(k, V) \cong U(V)となる。

しかもこれは Vについて自然になる。 \alpha: {\bf Vect}_k(k, −) \to Uの V成分を \alpha_V: \phi \mapsto U(\phi)(1)\;(1 \in U(k))と定める。このとき、任意の V, W \in {\bf Vect}_kおよび f: V \to Wについて以下の可換図式が成り立つ。

\displaystyle{ \require{amscd} \begin{CD} {\bf Vect}_k(k, V) @>{\bf Vect}_k(k, f)>> {\bf Vect}_k(k, W) \\ @V\alpha_{V}VV @VV\alpha_{W}V \\ U(V) @>>U(f)> U(W) \end{CD} }

実際、右回り・左回りのパスにおける写像を合成して \phi \in {\bf Vect}_k(k, V)に適用するとそれぞれ以下のように一致することが分かる。

\begin{align} \alpha_{W} \circ {\bf Vect}_k(k, f)(\phi) &= \alpha_{W} \circ f \circ \phi \\ &= U(f \circ \phi)(1) \\ U(f) \circ \alpha_{V}(\phi) &= U(f) \circ U(\phi)(1) \\ &= U(f \circ \phi)(1) \end{align}

以上の議論により U \cong H^kなので Uは表現可能関手である。

忘却関手 Uに対して体 kを渡すのは型が合っていないのではないか？と思われるかもしれないが、ここでは kは体であり、かつ k上の一次線形空間でもあると考えて記号を乱用している。
ここでの議論では kと U(k)を厳密に区別した。しかし、 kを線形空間として扱っているか集合として扱っているかは文脈で大体わかるので U(k)のことを kと書いてしまっても良かったかもしれない。このあたりの流儀は良く分かっていない。と言いつつ、1だけは kの元だったり U(k)の元だったりをあまり区別なく書いている。これも1と U(1)のように書き分けても良かったが、まあ分かるだろうということでサボっている。

続いて、米田の補題が成り立っている様子を観察してみよう。（本稿では明に説明していないが）米田の補題の共変バージョンより以下の同型が成り立つ。

\displaystyle{ [{\bf Vect}_k, {\bf Set} ](H^k, U) \cong U(k) }

左辺の自然変換の一つである \alphaの k成分は \alpha_k: \phi \mapsto U(\phi)(1)\;(\phi \in {\bf Vect}_k(k, k))である。証明のアウトラインで述べたように、 \hat{\alpha} = \alpha_k(1_k)とすればこれは U(k)の元である。よって \alpha_kの式に \phi=1_kを代入して得られる \alpha_k(1_k) = U(1_k)(1) = 1が \alphaに対応する U(k)の元である。

少々ややこしいが、1は kとか U(k)の元を表しており、 1_kは対象 kの恒等射である。両者は指しているものが全然違うので注意されたい。

さて、米田の補題より [{\bf Vect}_k, {\bf Set} ](H^k, U)という自然変換の集合は U(k)と一対一に対応するわけだから、他にもたくさんの自然変換が存在するはずである。これには \alphaの代わりに \alpha^{(s)}\;(s \in k)を考えればよい。これの k成分は \alpha^{(s)}_k: \phi \mapsto U(\phi)(s)と定める（ちなみに \alpha^{(1)}_k = \alpha_kである）。すると先ほどと同様の議論により \alpha^{(s)}_k(1_k) = U(1_k)(s) = U(s)が \alpha^{(s)}に対応する U(k)の元となる。

反変バージョンの例

集合に対する冪集合を返す関手 \mathcal{P}: {\bf Set}^\mathrm{op} \to {\bf Set}を考える。この関手によって射がどのように移されるかを理解するのがなかなか難しいのだが、端的に言うと {\bf Set}の射 g: A' \to Aに対して (\mathcal{P}(g))(U)=g^{−1}(U)\;(U \in \mathcal{P}(A))と定めればよい。これは \mathcal{P}(A) \to \mathcal{P}(A')という射になっている。

\mathcal{P}が反変バージョンの表現可能関手であることを示す。集合 Aとその部分集合 Uについて写像 \chi_U​: A \to {\bf 2} = \{0, 1\}を以下のように定義する。

\displaystyle{ \chi_U(x) = \begin{cases} 1 & x \in U \\ 0 & x \notin U \end{cases} }

これは Aの各要素が Uに含まれるかどうかを表す関数となっている。このような関数は Aの部分集合それぞれに対して定めることができる。つまり、 \mathcal{P}(A) \cong {\bf Set}​(A, {\bf 2})=H_{\bf 2}(A)となる。

しかもこれは Aについて自然になる。 \alpha: {\bf Set}(−, {\bf 2}) \to \mathcal{P}の A成分を \alpha_A: \phi \mapsto \phi^{-1}(\{1\})と定める。このとき、任意の A, B \in {\bf Set}および f: B \to Aについて以下の可換図式が成り立つ。

\displaystyle{ \require{amscd} \begin{CD} {\bf Set}(A, {\bf 2}) @>{\bf Set}(f, {\bf 2})>> {\bf Set}(B, {\bf 2}) \\ @V\alpha_{A}VV @VV\alpha_{B}V \\ \mathcal{P}(A) @>>\mathcal{P}(f)> \mathcal{P}(B) \end{CD} }

実際、右回り・左回りのパスにおける写像を合成して \phi \in {\bf Set}(A, {\bf 2})に適用するとそれぞれ以下のように一致することが分かる。

\begin{align} \alpha_{B} \circ {\bf Set}_k(f, {\bf 2})(\phi) &= \alpha_{B} \circ \phi \circ f \\ &= (\phi \circ f)^{-1}(\{1\}) \\ \mathcal{P}(f) \circ \alpha_{A}(\phi) &= \mathcal{P}(f) \circ \phi^{-1}(\{1\}) \\ &= f^{-1}(\phi^{-1}(\{1\})) \\ &= (\phi \circ f)^{-1}(\{1\}) \end{align}

以上の議論により \mathcal{P} \cong H_{\bf 2}なので \mathcal{P}は表現可能関手である。

続いて、米田の補題が成り立っている様子を観察してみよう。米田の補題より以下の同型が成り立つ。

\displaystyle{ [{\bf Set}^\mathrm{op}, {\bf Set} ](H_{\bf 2}, \mathcal{P}) \cong \mathcal{P}({\bf 2}) }

左辺の自然変換の一つである \alphaの {\bf 2}成分は \alpha_{\bf 2}: \phi \mapsto \phi^{-1}(\{1\})\;(\phi \in {\bf Set}^\mathrm{op}({\bf 2}, {\bf 2}))である。証明のアウトラインで述べたように、 \hat{\alpha} = \alpha_{\bf 2}(1_{\bf 2})とすればこれは \mathcal{P}({\bf 2})の元である。よって \alpha_{\bf 2}の式に \phi=1_{\bf 2}を代入して得られる \alpha_{\bf 2}(1_{\bf 2}) = 1_{\bf 2}^{-1}(\{1\}) = \{1\}が \alphaに対応する \mathcal{P}({\bf 2})の元である。

さて、米田の補題より [{\bf Set}^\mathrm{op}, {\bf Set} ](H_{\bf 2}, \mathcal{P})という自然変換の集合は \mathcal{P}({\bf 2})と一対一に対応するわけだから、 \alpha以外に \emptyset, \{0\}, {\bf 2} \in \mathcal{P}({\bf 2})と対応する自然変換が存在するはずである。これには \alphaの代わりに \alpha^{(U)}を考えればよい。これの {\bf 2}成分は \alpha^{(U)}_{\bf 2}: \phi \mapsto \phi^{-1}(U)\;(U \in \mathcal{P}({\bf 2}))と定める（ちなみに \alpha^{(\{1\})}_{\bf 2} = \alpha_{\bf 2}である）。すると先ほどと同様の議論により \alpha^{(U)}_{\bf 2}(1_{\bf 2}) = 1_{\bf 2}^{-1}(U) = Uが \alpha^{(U)}に対応する \mathcal{P}({\bf 2})の元となる。

まとめ

本稿では米田の補題にまつわる話題として、表現可能関手および米田の補題について具体例を用いながら説明した。米田の補題は初見だと本当に何が言いたいのかさっぱり分からなかったが、例をいじくりまわしているうちに少しずつ感覚が掴めてきたように思う。

長年の目標であった米田の補題そのものについてはひとまず理解できたので、この世に対する未練がまた一つなくなった。あとは孫の顔さえ見られれば成仏できるかもしれない（何十年後になるか分からないが）。

参考

[1] [1612.09375] Basic Category Theory
[2] 米田の補題 - Wikipedia

戦略の組み合わせに制約がある場合のナッシュ均衡について考えてみた

ゲーム理論

ここのところ圏論に関してシリーズものっぽい感じで記事を書いているが、それとは関係ない話題でネタを思いついたので書いてみる。

ある日の授業参観にて

先日、子どもの授業参観があった。うきうきで有給休暇を取って出席したのだが、そのときの授業が算数だった。そこで以下のようなゲームを題材にした授業が行われた。

  • 2人のプレイヤーがじゃんけんをし、結果に応じて以下のように得点が与えられる。
    • グーで勝利: 1点
    • チョキで勝利: 2点
    • パーで勝利: 3点
    • 敗北: 0点
  • あいこの場合は勝敗が決まるまで何度でもやり直す。
  • あいこの場合には適宜やり直して勝敗が決まるところまでを1回と数え、このような試行を10回繰り返す。10回の試行で得た得点の総和が大きい方のプレイヤーが勝者となる。

これを見た瞬間、私はいかにもゲーム理論っぽい問題設定だなと思った。つまり、何か理論的に最適な戦略があるのではないかと考えた。ところが、私はゲーム理論をまじめに勉強したことがなく、すぐには答えが分からなかった。

そこで、ひとまず初歩の初歩を動画[1]やweb上の資料[2]などで勉強し、この問題に対する解を考えてみることにした。その結果、このじゃんけんゲームについていろいろと悩むポイントがあったので、それについて書いてみようと思う。

当然だが、子どもの算数の授業では別にゲーム理論の話はされていなかった。

知りたいことを言語化してみる

知りたいことをざっくり述べると、先ほど説明したゲームにおいて各プレイヤーがどのような戦略を取るのがよいか？ということである。恐らく特定の手だけ出すというのはあまりよくないだろう。また、グー・チョキ・パーそれぞれで勝利したときの得点が異なる以上、それぞれを等確率で出すというのも違う気がする。もっと最適な確率分布というのがありそうだ。

このように各行動を確率的に取るような戦略のことをゲーム理論では混合戦略と呼ぶらしい。ちなみに、特定の行動を確率1で選ぶような戦略のことは純粋戦略というようだ。

考えるべきは「よい戦略」とは何か？ということである。これにはパレート最適とナッシュ均衡という概念が関わってきそうである。さしあたり、自分の勉強の進み具合の都合上、本稿ではこのじゃんけんゲームにおける混合戦略のナッシュ均衡を求めることを目指す。

ナッシュ均衡

ナッシュ均衡の定義は調べるといろいろ出てくるが、個人的に一番しっくりきたものをWikipedia[3]より引用する。

ナッシュ均衡 (Nash equilibrium)
Formally, let S_{i} be the set of all possible strategies for player i, where i=1,\ldots ,N. Let s^{*}=(s_{i}^{*},s_{-i}^{*}) be a strategy profile, a set consisting of one strategy for each player, where s_{-i}^{*} denotes the N-1 strategies of all the players except i. Let u_{i}(s_{i},s_{-i}^{*}) be player i's payoff as a function of the strategies. The strategy profile s^{*} is a Nash equilibrium if
\displaystyle{ u_{i}(s_{i}^{*},s_{-i}^{*})\geq u_{i}(s_{i},s_{-i}^{*})\ {\text{for all}}\ s_{i}\in S_{i}. }

要するに、どのプレイヤーが単独で戦略を変えてもそれ以上自身の利得を上げることができないような状態がナッシュ均衡であると言える。

ちなみにこれは純粋戦略に対するナッシュ均衡の定義である。混合戦略の場合は若干異なる形をしているが、根底にある考え方は同じである。詳細が気になる方は[4][5]などに定義があるので見てみるとよいだろう。

純粋戦略のナッシュ均衡が存在しないことの確認

話を先ほどのじゃんけんゲームに戻す。2人のプレイヤーをそれぞれA, Bと呼ぶことにする。まずはA, Bの利得表を書いてみよう。これは以下のようになる。

A\B グー チョキ パー
グー N/A (1, 0) (0, 3)
チョキ (0, 1) N/A (2, 0)
パー (3, 0) (0, 2) N/A

カッコ内の左側の数字がAの利得、右側がBの利得を表している。あいこになる箇所はN/Aとしている。

これを用いて純粋戦略のナッシュ均衡が存在しないことを確認してみよう。全パターン考えるのは大変なので、例えばBがグーを出すという純粋戦略を取るケースを考える。このとき、Aの最適な戦略はパーを出すことである。Aとしてはそれでよいわけだが、Bはこの状況でチョキを出す戦略に変更すれば現状より利得が大きくなる。つまり、(A, B) = (パー・グー) はナッシュ均衡ではない。

他のパターンも同様に確かめられるので、今考えているゲームに純粋戦略のナッシュ均衡は存在しない。

戦略の制約が生み出すおかしな状況

以上の議論により混合戦略を取るしかないことは分かった。これで準備ができたので本題に入っていこう。

まず、Aがグー・チョキ・パーを出す確率をそれぞれ p, q, 1-p-qとする。Bについてはそれぞれ r, s, 1-r-sとする。ここまでの議論により p, q, r, sにはそれぞれ以下のような制約が付く。

\left\{ \, \begin{aligned} & 0 \le p < 1 \\ & 0 \le q < 1 \\ & 0 \le 1-p-q < 1 \\ & 0 \le r < 1 \\ & 0 \le s < 1 \\ & 0 \le 1-r-s < 1 \end{aligned} \right.

これを用いてAの期待利得を計算してみよう。[2]によるとナッシュ均衡ではAが各（純粋）戦略を選んだ場合の期待利得が同じになるらしいので、その性質を利用して r, sが求まるようだ。

試しにAがグーだけを出すという戦略を取ったときのAの期待利得について考えてみる。Bもグーを出すとあいこになってしまうので、Bはチョキかパーを出すしかない。ここが曲者で、今回は許されない戦略の組み合わせ（つまりあいこの場合）があるので、チョキとパーを出す確率をそのまま使うとおかしなことになる。というのも、Bが取れる選択肢はチョキを出すかパーを出すかしかないのだが、それぞれの確率を単純に足すと s + (1-r-s) = 1-rとなってしまい、和が1にならない。

では、これらを適当に正規化したらどうだろうか？つまり、Aがグーを出すときにはBはチョキ・パーをそれぞれ \frac{s}{1-r}, \frac{1-r-s}{1-r}の確率で出すと考えるのである。これは何となく正しそうな気がする。少なくとも取り得る戦略の確率の総和は1になった。

この調子でAがチョキだけを出すという戦略を取ったときのAの期待利得を計算してみる。このときBはグー・パーのいずれかを出すことになる。先ほどと同様に正規化してみると、それぞれの手を出す確率は \frac{r}{1-s}, \frac{1-r-s}{1-s}となる。ここで、よく見るとパーを出す確率が先ほどと異なる。先ほどとは正規化の仕方が違うので当然といえば当然なのだが、本来Bがパーを出す確率は 1-r-sなわけで、状況によって確率が変わってしまうのはなんとなく不安に駆られる。本当にこの調子で続けて正しくナッシュ均衡を求めることができるのだろうか？

愚直に計算してみる

こういう場合はふわっとした知識には頼らず、絶対に正しいと思えることを積み重ねて考えてみる。すなわち、Aの利得を愚直に計算してみることにする。そのためには利得表の各セルの事象が起こる確率をそれぞれ求める必要がある。この際、あいこは許されないという制約から利得表全体での正規化を考える必要がある。つまり、適当な正規化のための関数 N(p, q, r, s)を用いて、各事象の確率は以下のように書ける（記載が面倒なので Nの引数部分は省略した）。

A\B グー チョキ パー
グー N/A ps/N p(1-r-s)/N
チョキ qr/N N/A q(1-r-s)/N
パー (1-p-q)r/N (1-p-q)s/N N/A

ただし、 N \ne 0とする。というのも、 N=0だと無限にあいこになり続けてゲームが一生終わらないためである。

このように正規化を行うことの妥当性について補足する。じゃんけんをしてあいこになった場合はじゃんけんをやり直すことになるが、いつかは決着がつくことになる。決着がつくという条件のもとで各事象が起こる条件付き確率を考えると、これは結局正規化した確率を求めることと同じになる。

これだと説明がふわふわしすぎているかもしれないので、例えばA, Bがそれぞれ最終的にグー・チョキを出して決着がつく場合の確率を考えてみる。あいこになる確率を Mとおくと、自然数 nに対して n回目までに(A, B) = (グー・チョキ) で決着がつく確率は以下のようになる。

\displaystyle{ \sum_{i=1}^{n} M^{i-1} ps }

M < 1に注意して上式の n \to \inftyでの極限を求めると \frac{ps}{1-M}となる。ここで N=1-Mとすれば先ほどの正規化した式が得られる。他のケースも同様である。

続いてAの期待利得を計算してみよう。これは以下のようになる。

\begin{align} & 1 \cdot \frac{ps}{N} + 2 \cdot \frac{q(1-r-s)}{N} + 3 \cdot \frac{(1-p-q)r}{N} \\ =& \frac{1}{N}(p \cdot s + q \cdot 2(1-r-s) + (1-p-q) \cdot 3r) \end{align}

この式のカッコ内の形はAがグー・チョキ・パーを出す確率と何らかの値の線形和になっている。つまり、 s, 2(1-r-s), 3rの大小関係によってAの最適な戦略が変わってくる。ところが、これらのうち特定の1つが他の2つより大きくなることは許されない。なぜならそのときAは自身の期待利得を大きくするために特定の手だけを出すことができてしまうからである。それは p, qの制約に違反する。

よってナッシュ均衡に至るためにはこれら3つの値は等しくなるか、あるいは2つが等しくなり、かつ1つは他の2つよりも小さくなる必要がある。以下で、それぞれのケースについて考えてみよう。

s = 2(1-r-s) = 3rのとき

このとき以下の連立方程式が成り立つ。

\left\{ \, \begin{aligned} & s = 2(1-r-s) \\ & s = 3r \end{aligned} \right.

これを解くと (r, s) = (2/11, 6/11)となる。さらに 1-r-s = 3/11となる。よってBはグー・チョキ・パーをそれぞれ2/11, 6/11, 3/11の確率で出せばナッシュ均衡になることが分かった。ゲームの性質上、AとBを入れ替えても同様の議論が成り立つ。

Aの期待利得について考えていたらいつの間にかBのナッシュ均衡における戦略が求まってしまったのはなんだかキツネにつままれたような気分になるが、まあそういうものなのだろう。[5]のP.10を見ていると期待利得の式をどう捉えるかという視点の問題という気もするが、ここは私自身あまり咀嚼できていない。

s, 2(1-r-s), 3rのいずれか2つが一致し、かつ1つは他の2つよりも小さくなる

これは厳密にはさらに3パターンに分けられるが、面倒なので1パターンだけ確認してみる（じゃんけんの性質上、どうせこのパターンはナッシュ均衡にならなさそうだという直観があるためサボる）。

例えば s = 3r > 2(1-r-s)のときを考えてみよう。これをうまく整理すると r > 2/11, s > 6/11が得られる。

このときAはチョキを出すモチベーションがなくなる。つまり q = 0となる。すると、Bとしてはパーを高確率で出す戦略に移行すれば期待利得を上げられる。極端な話、 r=s=0という戦略に変更すればよい（厳密にはBの期待利得の式を求めて確認すべきだが、ほぼ明らかだろう）。B単独のでの戦略変更によってBの期待利得が上がるため、これはナッシュ均衡ではない。

最初にやろうとした計算は本当にダメだったのか？

さて、ナッシュ均衡が無事に求まったわけだが、最初にやろうとしていた計算が本当にダメだったのか？は気になるところである。実際に計算して正しい値が出てくるか確認してみよう。

Aがグーを出すときBはチョキ・パーをそれぞれ \frac{s}{1-r}, \frac{1-r-s}{1-r}の確率で出す。するとAの期待利得は以下のようになる。

\displaystyle{ 1 \cdot \frac{s}{1-r} + 0 \cdot \frac{1-r-s}{1-r} = \frac{s}{1-r} }

同様にAがチョキ・パーを出すときのAの期待利得を計算すると、それぞれ以下のようになる。

\begin{align} & 0 \cdot \frac{r}{1-s} + 2 \cdot \frac{1-r-s}{1-s} = \frac{2(1-r-s)}{1-s} \\ & 3 \cdot \frac{r}{r+s} + 0 \cdot \frac{s}{r+s} = \frac{3r}{r+s} \end{align}

ナッシュ均衡ではこれらがそれぞれ等しくなるという言説が今の状況でも正しいと信じることにすると、以下の連立方程式を解けばよいはずである。

\left\{ \, \begin{aligned} & \frac{s}{1-r} = \frac{2(1-r-s)}{1-s} \\ & \frac{s}{1-r} = \frac{3r}{r+s} \end{aligned} \right.

これを解くのは非常に骨が折れるのでこっそり数値計算した結果だけ述べておくと、少なくとも (r, s) = (2/11, 6/11)はこの連立方程式の解にはならない。つまりこの解法は誤りである。

ちなみにここまで書いてみて分かったことだが、ここでやった計算において変に正規化などせず普通に s = 2(1-r-s) = 3rを解けば解が得られる。結局、正規化を行とか列ごとにやるのが間違いであり、利得表全体で確率を正規化した上で方程式からは正規化係数を取り払ったと考えれば正規化しないのと同じになるというわけである。

まだ分かっていないこと

今回は戦略の組み合わせに制約があるようなケースを考えたが、これは現実に即して考えるとなんだか変な感じがする。というのも、A, Bがどちらも超頑固者で「私はパーしか出しません」と言い張ってしまうと、このゲームは永久に終了しないことになる。また、1回の試行の中であいこが繰り返されると手をあれこれ変える必要があり、時間発展的な要素が入ってくることになる。このようなものをゲーム理論の枠組みに無理やり押し込めたのは果たして適切だったのかはよく分からなかった。

ゲーム理論で扱う内容としては他にもいくつか種類があるようなので、もしかすると他のフレームワークを使うとすっきりと理解できるかもしれない。が、今の自分の知識量だとこのあたりが限界だった。

まとめ

本稿では戦略の組み合わせに制約がある場合のナッシュ均衡について私が考えたことについて述べた。戦略の組み合わせに制約がある場合、やや考え方に注意は必要なものの、通常の場合と同様にナッシュ均衡を求められることが分かった。

今度子どもの担任の先生にお会いする機会があればぜひこの結果を披露したいところだが、変な人だと思われそうなのでやめておく。

参考

[1] youtube.com
[2] 混合戦略ナッシュ均衡の求め方 - NABENAVI.net
[3] Nash equilibrium - Wikipedia
[4] https://ocw.mit.edu/courses/17-810-game-theory-spring-2021/mit17_810s21_lec3.pdf
[5] https://felixmunozgarcia.com/wp-content/uploads/2017/08/slides_61.pdf

圏に関する初歩的な概念を小さな例で理解する ～ 圏同値と随伴の関係

圏論

前回の記事ではunitとcounitについて説明した。ここで本[1]の内容から一歩踏み出して圏同値と随伴の関係について整理してみたいと思う。

圏同値と随伴の微妙な関係性

前々回の記事で圏同値なら随伴になるという話をした。しかし、これは言い方がややいい加減であった。正確には、圏 \mathcal{A}, \mathcal{B}に対して関手 F: \mathcal{A} \to \mathcal{B}, G: \mathcal{B} \to \mathcal{A}および自然同型 \eta:1_{\mathcal{A}} \to G \circ F, \epsilon: F \circ G \to 1_{\mathcal{B}}が圏同値を与えるとき、 Fは Gの左随伴となる。これは本[1]のExercise 2.3.10そのものであり、公式の解答はないものの解答を公開している方がいる[2]ので、詳しくはそちらが参考になるだろう。

ここで一つ言及しておきたいことがある。それは圏同値を考えるときに登場した \eta, \epsilonが必ずしも随伴のunit, counitになるとは限らないということである。これは圏同値と随伴では求められる条件が微妙に違っており、必ずしも圏同値における \eta, \epsilonがtirangle identityを満たすとは限らないということらしい[1]。

このことを確かめる例を見てみよう。以下のような状況を考える。

圏同値を与える自然同型がunit, counitにならない例

上図の関係を式で書くと以下のようになる。

\begin{align} F(a) &= b' \\ F(a') &= b \\ F(f) &= s \\ F(g) &= r \\ G(b) &= a' \\ G(b') &= a \\ G(r) &= g \\ G(s) &= f \\ \end{align}

ただし、射 f, g, r, sはいずれも同型射であり、それぞれの逆射は自分自身であるとする。例えば f^{-1} = fである。

ここで、自然変換 \eta: 1_{\mathcal{A}} \to GFおよび \epsilon: FG \to 1_{\mathcal{B}}を以下のように定める。

\begin{align} \eta_a &= f \\ \eta_{a'} &= g \\ \epsilon_b &= 1_b \\ \epsilon_{b'} &= 1_{b'} \end{align}

f, g, r, sは定義より同型射であるため、 \eta, \epsilonはいずれも自然同型である。

では、この \eta, \epsilonに対してtriangle identityが成り立つかどうかを確認してみよう。これについて考えるために以前の記事で示したtriangle identityの図を再掲する[1]。

triangle identity

例えば aに着目すると、左側の可換図式において上側のルートを通る合成射は以下のようになる。

\begin{align} \epsilon_{F(a)} \circ F(\eta_a) &= \epsilon_{b'} \circ F(f) \\ &= 1_{b'} \circ s \\ &= s \end{align}

これは可換図式の下側のルートを通る射 1_{F(a)} = 1_{b'}と一致していない。つまり、triangle identityが成り立っていないことが分かる。

圏同値かつtriangle identityが成り立つような \eta, \epsilonは存在しないのか？

圏同値を与える自然変換がunit, counitになっていないというのはなんとも美しくない。何とかして \eta, \epsilonをうまく定めて (F, G, \eta, \epsilon)が圏同値を与えつつ \eta, \epsilonがtriangle identityを満たすようにできないものだろうか？

実はこれは可能である。ざっくり言うと F, G, \etaを適当に選んだ後に \epsilonをうまく定めればこういうことが成り立つらしい。これについての証明は[3][4]などが詳しいが、可換図式やstring diagramとかいうやつを用いた証明になっており、正しそうな気はするもののいまいち分かった気持ちになれなかった。

そこで、以下では証明[4]をベースにしつつ式変形による愚直な証明を試みる。

以下に示す証明は私がほぼ自力で考えたものである。私の数学力を考えると誤りを含んでいる可能性があるので、無条件に信用せず注意深く見て欲しい。

圏同値であることの証明

まず、圏 \mathcal{A}, \mathcal{B}の間に関手 F: \mathcal{A} \to \mathcal{B}および G: \mathcal{B} \to \mathcal{A}があり、これらについて以下のような自然同型の組があるとする。

\begin{align} \eta: & 1_{\mathcal{A}} \to GF \\ \xi: & FG \to 1_{\mathcal{B}} \end{align}

つまり、 \mathcal{A} \simeq \mathcal{B}である。ここで、自然変換 \epsilonを以下のように定める。

\displaystyle{ \epsilon = \xi \circ (F\eta^{−1}G) \circ (FG \xi^{−1}) }

このとき、 (F, G, \eta, \epsilon)が \mathcal{A}, \mathcal{B}の圏同値を与えつつ \eta, \epsilonがtriangle identityを満たすことを示す。

まず、 \epsilonの定義に含まれる自然変換がいずれも自然同型であることから \epsilonも自然同型となる。また、 \epsilonを構成する自然変換はそれぞれ以下のようになっている。

\begin{align} FG \xi^{−1}: & FG \to FGFG \\ F\eta^{−1}G: & FG FG\to FG \\ \xi: & FG \to 1_{\mathcal{B}} \end{align}

よって \epsilonは FG \to 1_{\mathcal{B}}という自然同型である。これより (F, G, \eta, \epsilon)は \mathcal{A}, \mathcal{B}の圏同値を与える。

Triangle identityを満たすことの証明

続いて \eta, \epsilonがtriangle identityを満たすことを示す。Triangle identityは2つの式から成るが、片方を示せばもう片方も同様に示せる。というわけで、ここでは以下の式が成り立つことだけを示す。

\displaystyle{ \epsilon F \circ F \eta=1_F }

対象 A \in \mathcal{A}について上式の A成分は以下のようになる。

\begin{align} (\epsilon F \circ F \eta)_{A} &= (1_F)_A \\ (\epsilon F)_A \circ (F \eta)_{A} &= 1_{F(A)} \\ \epsilon_{F(A)} \circ F(\eta_A) &= 1_{F(A)} \end{align}

Aは任意なのでこの式を示せば元の式が示せたことになる。

\epsilon_{F(A)}を定義から計算すると以下のようになる。

\begin{align} \epsilon_{F(A)} &= (\xi \circ (F\eta^{−1}G) \circ (FG\xi^{−1}))_{F(A)} \\ &= \xi_{F(A)} \circ (F\eta^{−1}G)_{F(A)} \circ (FG\xi^{−1})_{F(A)} \\ &= \xi_{F(A)} \circ F \left(\eta_{GF(A)}^{−1} \right) \circ FG \left(\xi_{F(A)}^{−1} \right) \end{align}

よって以下の式が成り立つ。

\begin{align} \epsilon_{F(A)} \circ F(\eta_A) &= \xi_{F(A)} \circ F \left(\eta_{GF(A)}^{−1} \right) \circ FG \left(\xi_{F(A)}^{−1} \right) \circ F(\eta_A) \\ &= \xi_{F(A)} \circ F \left(\eta_{GF(A)}^{−1} \right) \circ F\left(G \left(\xi_{F(A)}^{−1} \right) \circ \eta_A \right) \end{align}

ここで、最後の式の末尾にある G \left(\xi_{F(A)}^{−1} \right) \circ \eta_Aに着目する。 \xi_{F(A)}^{−1} \in \mathcal{B}[F(A), FGF(A)]であるが、 Fが忠実充満な関手であること（これについては本[1]のexercise 1.3.32などを参照）から F(f) = \xi_{F(A)}^{−1}となるような f \in \mathcal{A}[A, GF(A)]がただ一つ存在する。これを用いると先ほどの式は GF(f) \circ \eta_Aと書ける。

さらに \etaの自然性より A, GF(A)について以下の可換図式が成り立つ。

\displaystyle{ \require{amscd} \begin{CD} A @>f>> GF(A) \\ @V\eta_AVV @VV\eta_{GF(A)}V \\ GF(A) @>>GF(f)> GFGF(A) \end{CD} }

よって以下の式が成り立つ。

\displaystyle{ GF(f) \circ \eta_A = \eta_{GF(A)} \circ f }

これを元の式に代入して式変形していくと以下のようになる。

\begin{align} \xi_{F(A)} \circ F \left(\eta_{GF(A)}^{−1} \right) \circ F(\eta_{GF(A)} \circ f) &= \xi_{F(A)} \circ F \left(\eta_{GF(A)}^{−1} \right) \circ F(\eta_{GF(A)}) \circ F(f) \\ &= \xi_{F(A)} \circ F \left(\eta_{GF(A)}^{−1} \circ \eta_{GF(A)} \right) \circ F(f) \\ &= \xi_{F(A)} \circ F(f) \\ &= \xi_{F(A)} \circ \xi_{F(A)}^{−1} \\ &= 1_{F(A)} \end{align}

以上により \epsilon F \circ F \eta=1_Fであることが示された。

圏同値を与える自然変換がunit, counitにもなるように変換する例

大変な証明が終わったところで、最初に示した例に戻って実際に圏同値を与えつつunit, counitになるような自然変換が得られることを確かめてみよう。先ほどの例で \epsilonと書いていた自然変換を \xiとし、改めて以下の自然変換を \epsilonとして定義し直す。

\displaystyle{ \epsilon = \xi \circ (F\eta^{−1}G) \circ (FG \xi^{−1}) }

\xi（旧 \epsilon）は以下のように定義されていたのであった。

\begin{align} \xi_b &= 1_b \\ \xi_{b'} &= 1_{b'} \end{align}

これは a, a'を用いて以下のように書ける。

\begin{align} \xi_{F(a')} &= 1_b \\ \xi_{F(a)} &= 1_{b'} \end{align}

よって \epsilonの F(a)成分は以下のように求められる。

\begin{align} \epsilon_{F(a)} &= \xi_{F(a)} \circ (F\eta^{−1}G)_{F(a)} \circ (FG\xi^{−1})_{F(a)} \\ &= 1_{b'} \circ F\left(\eta^{−1}_{GF(a)}\right) \circ FG(1_{b'}) \\ &= 1_{b'} \circ F(f) \circ FG(1_{b'}) \\ &= s \end{align}

同様に F(a')成分は以下のように求められる。

\begin{align} \epsilon_{F(a')} &= \xi_{F(a')} \circ (F\eta^{−1}G)_{F(a')} \circ (FG\xi^{−1})_{F(a')} \\ &= 1_{b} \circ F\left(\eta^{−1}_{GF(a')}\right) \circ FG(1_{b}) \\ &= 1_{b} \circ F(g) \circ FG(1_{b}) \\ &= r \end{align}

これを用いると aについて以下の式が成り立つ。

\begin{align} \epsilon_{F(a)} \circ F(\eta_a) &= s \circ s \\ &= 1_{b'} \end{align}

同様に a'について以下の式が成り立つ。

\begin{align} \epsilon_{F(a')} \circ F(\eta_{a'}) &= r \circ r \\ &= 1_{b} \end{align}

よって一つ目のtriangle identityは満たされることが分かった。もう一方も示す必要があるが、私にはそこまで確かめるパワーがないので成り立っているものと信じることにする。

まとめ

本稿では圏同値と随伴の関係性について述べた。ざっくり言うと圏同値なら随伴となるが、圏同値を与える2つの自然同型が必ずしも随伴のunit, counitにならないこと、および適切な変形を行うことでこのずれを解消できることについて説明した。

実用的には可換図式やstring diagramで考えた方が圧倒的に便利なのだろうが、式変形ゴリ押しでの証明を試みたことでまた一段と理解が深まった気がする。

参考

[1] [1612.09375] Basic Category Theory
[2] Solutions to Basic Category Theory, Tom Leinster, All Chapters – positron0802
[3] youtu.be
[4] adjoint equivalence in nLab

圏に関する初歩的な概念を小さな例で理解する ～ unitとcounit

圏論

前回の記事では随伴について例を用いて説明した。本稿では前回説明しきれなかった随伴に関連する話題として、unitとcounitについて例を用いながら考えてみる。

unitとcounit

Unitとcounitの定義を本[1]から引用する。

unitとcounit
For each A \in \mathcal{A}, we have a map
\displaystyle{ \left(A \overset{\eta_A}{\longrightarrow} GF(A) \right) = \overline{\left(F(A) \overset{1}{\longrightarrow} F(A) \right)}. }
Dually, for each B \in \mathcal{B}, we have a map
\displaystyle{ \left(FG(B) \overset{\epsilon_B}{\longrightarrow} B \right) = \overline{\left(G(B) \overset{1}{\longrightarrow} G(B) \right)}. }
(We have begun to omit brackets, writing GF(A) instead of G(F(A)), etc.) These define natural transformations
\displaystyle{ \eta: 1_{\mathcal{A}} \to G \circ F,\ \epsilon: F \circ G \to 1_{\mathcal{B}}, }
called the unit and counit of the adjunction, respectively.

要するにunit, counitとはそれぞれ F(A) \to F(A)および G(B) \to G(B)という恒等射を転置したものを集めてできる自然変換である。

triangle identity

Unitとcounitについてtriangle identity（三角恒等式？）という重要な可換図式が成り立つ。Triangle identityの説明を本[1]から引用する。

triangle identity
Given an adjunction F \dashv G with unit \eta and counit \epsilon, the triangles
commute.

はてなブログだと斜めの矢印を含んだ可換図式を描くのに苦労したので、諦めて本[1]の数式をキャプチャしたものを添付した。

可換図式の中に出てくる F\etaとか \eta Gといった記号の意味について補足する。これは自然変換のhorizontal composition（水平合成）というものの一種である。Horizontal compositionとは自然変換を横方向につなぐような合成のことである。詳しくは本[1]やalg-dさんの動画[2]を参照のこと。

前述の可換図式に登場する水平合成は合成する2つの自然変換のうち一方が恒等変換になっているようなケースである。例えば自然変換 \alpha: F \Rightarrow Gと 1: F' \Rightarrow F'を水平合成すると以下の図のようになる。

F' \alphaの図[1]

F' \alphaの成分は (F' \alpha)_A = F'(\alpha_A)\ (A \in \mathcal{A})となる。

同様に自然変換 1: F \Rightarrow Fと \alpha': F' \Rightarrow G'を水平合成すると以下の図のようになる。

\alpha' Fの図[1]

\alpha' Fの成分は (\alpha' F)_A = \alpha'_{F(A)}\ (A \in \mathcal{A})となる。

例

前回の記事で用いた図を見ながらunitとcounitがどうなるか確認してみよう。以下に図を再掲する。

随伴の例

\mathcal{A}の各対象について \etaの成分はそれぞれ以下のようになる。

\begin{align} \eta_{a} &= \overline{1_{F(a)}} = f \\ \eta_{a'} &= \overline{1_{F(a')}} = 1_{a'} \\ \eta_{a'} &= \overline{1_{F(a'')}} = 1_{a''} \end{align}

\mathcal{B}の各対象について \epsilonの成分はそれぞれ以下のようになる。

\begin{align} \epsilon_{b} &= \overline{1_{G(b)}} = 1_{b} \\ \epsilon_{b'} &= \overline{1_{G(b')}} = 1_{b'} \end{align}

Unitおよびcounitの各成分の中で \eta_{a}だけ非自明な射になっている。これはまるで aが a'に圧し潰されて \mathcal{A}と \mathcal{B}が同じ形になっているような印象を受ける（個人の感想であり、一般にこういう現象が起きるかは分からない）。

念のためtriangle identiyが成り立つことも確認してみよう。全ての対象について確認すると大変なので適当に aと b'をピックアップする。

まずは aについて、可換図式の上側のルートを通る合成射は以下のようになる。

\begin{align} \epsilon_{F(a)} \circ F(\eta_a) &= \epsilon_b \circ F(f) \\ &= 1_b \circ 1_b \\ &= 1_b \end{align}

これは確かに可換図式の下側のルートを通る射 1_{F(a)} = 1_bと一致している。

続いて b'について、可換図式の上側のルートを通る合成射は以下のようになる。

\begin{align} G(\epsilon_{b'}) \circ \eta_{G(b')} &= G(1_{b'}) \circ \eta_{a''} \\ &= 1_{a''} \circ 1_{a''} \\ &= 1_{a''} \end{align}

これは確かに可換図式の下側のルートを通る射 1_{G(b')} = 1_{a''}と一致している。

まとめ

本稿では圏の随伴に関連する重要な概念であるunitとcounitについて説明した。個人的には本稿を書くまで水平合成のところがなんだかよく分からないと思っていたので、書きながら理解できてよかった。

また、alg-dさんの動画は本当に助かったので大感謝である。初心者向けの動画シリーズもあるので興味のある方は見てみると良いだろう。

参考

[1] [1612.09375] Basic Category Theory
[2] youtu.be

圏に関する初歩的な概念を小さな例で理解する ～ 随伴

圏論

前回の記事では圏同値について例を用いて説明した。本稿ではその続きとして随伴について小さな例を用いて考えてみる。

随伴

随伴の定義を本[1]より引用する。

随伴
Let \mathcal{A} \overset{F}{\underset{G}{\rightleftarrows}} \mathcal{B} be categories and functors. We say that F is left adjoint to G, and G is right adjoint to F, and write F \dashv G, if
\begin{align} \mathcal{B}(F(A),B) \cong \mathcal{A}(A,G(B)) \tag{2.1} \end{align}
naturally in A \in \mathcal{A} and B \in \mathcal{B}. (・・・中略・・・) An adjunction between F and G is a choice of natural isomorphism (2.1).

ここで、"naturally in A \in \mathcal{A} and B \in \mathcal{B}"と書かれているところについて本[1]では定義の後に説明が続いている。丸ごと引用すると長くなるのでやめておくが、要するに以下の二式が成り立つということを言いたいらしい。

\begin{align} \overline{\left(F(A) \overset{g}{\longrightarrow} B \overset{q}{\longrightarrow} B' \right)} &= \left(A \overset{\bar{g}}{\longrightarrow} G(B) \overset{G(q)}{\longrightarrow} G(B') \right) \tag{1} \\ \overline{\left(A' \overset{p}{\longrightarrow} A \overset{f}{\longrightarrow} G(B) \right)} &= \left(F(A') \overset{F(p)}{\longrightarrow} F(A) \overset{\bar{f}}{\longrightarrow} B \right) \tag{2} \end{align}

ただし、上線は転置 (transpose) と呼ばれるもので、本[1]では以下のように説明されている。

転置 (transpose)
Given objects A \in \mathcal{A} and B \in \mathcal{B}, the correspondence (2.1) between maps F(A) \to B and A \to G(B) is denoted by a horizontal bar, in both directions:
\begin{align} \left(F(A) \overset{g}{\longrightarrow} B \right) &\mapsto \left(A \overset{\bar{g}}{\longrightarrow} G(B) \right) \\ \left(F(A) \overset{\bar{f}}{\longrightarrow} B \right) &↤ \left(A \overset{f}{\longrightarrow} G(B) \right) \end{align}
So \bar{\bar{f}} = f and \bar{\bar{g}} = g. We call \bar{f} the transpose of f, and similarly for g.

随伴の定義の中で"choice of natural isomorphism (2.1)"と書かれている部分があるが、実はここの意味が私は良く分かっていない。自然同型は関手圏の対象（つまり関手）の間の同型のことを意味するのであった。しかし、随伴の定義では射の集まりの間の同型に着目しているように見える。

本[1]を読み進めると4章で再度この定義に関して振り返っている箇所があるので、そのあたりまで理解しないとこのもやもやは晴れないのかもしれない。ひとまず本稿では2つの射の集まりの間に全単射が構成できて、かつ良い感じの性質を持っているというくらいに考えておく。

例

では例を見てみよう。以下のように圏 \mathcal{A}, \mathcal{B}の間に関手 F, Gが存在する状況を考える。

随伴の例

上図の関係を式で書くと以下のようになる。

\begin{eqnarray} F(a) &=& b \\ F(a') &=& b \\ F(a'') &=& b' \\ F(f) &=& 1_b \\ F(g) &=& r \\ G(b) &=& a' \\ G(b') &=& a'' \\ G(r) &=& g \end{eqnarray}

F \dashv Gであることの確認

前述の例において F \dashv Gとなっていることを随伴の定義に照らし合わせて確かめてみよう。初めに (a, b')という組について考える。 \mathcal{B}(F(a),b') = \{r \}、 \mathcal{A}(a, G(b')) = \{g \circ f \}なので、それぞれのただ一つの元が一対一に対応していると考えれば両者の間に全単射を構成することができる。つまり \bar{r} = g \circ fである。

式(1)(2)についても確認する。 b'から出ていく方向の射は 1_{b'}しかないので、式(1)の左辺と右辺はそれぞれ以下のパターンだけ考えればよい。

\begin{eqnarray} \overline{\left(F(a) \overset{r}{\longrightarrow} b' \overset{1_{b'}}{\longrightarrow} b' \right)} &=& \bar{r} \\ &=& g \circ f \\ \left(a \overset{\bar{r}}{\longrightarrow} G(b') \overset{G(1_{b'})}{\longrightarrow} G(b') \right) &=& 1_{a''} \circ \bar{r} \\ &=& g \circ f \\ \end{eqnarray}

この場合、左辺と右辺は一致しており、条件を満たしている。

次に、 aに入ってくる方向の射は 1_aしかないので、式(2)の左辺と右辺はそれぞれ以下のパターンだけ考えればよい。

\begin{eqnarray} \overline{\left(a \overset{1_a}{\longrightarrow} a \overset{g \circ f}{\longrightarrow} G(b') \right)} &=& \overline{g \circ f} \\ &=& r \\ \left(F(a) \overset{F(1_a)}{\longrightarrow} F(a) \overset{\overline{g \circ f}}{\longrightarrow} b' \right) &=& \overline{g \circ f} \circ 1_{b} \\ &=& r \end{eqnarray}

この場合、左辺と右辺は一致しており、条件を満たしている。

続いて (a', b')という組について考えてみよう。 \mathcal{B}(F(a'),b') = \{r \}、 \mathcal{A}(a', G(b')) = \{g \}なので、それぞれのただ一つの元が一対一に対応していると考えれば両者の間に全単射を構成することができる。つまり \bar{r} = gである。

b'から出ていく方向の射は 1_bしかないので、式(1)は (a, b')のケースと同じように成り立つ。 a'に入ってくる方向の射は 1_{a'}, fの2つがある。 1_{a'}は先ほどと同様に確かめれば成り立つことが分かるので、 fについて式(2)の両辺の値を確かめてみると以下のようになる。

\begin{eqnarray} \overline{\left(a \overset{f}{\longrightarrow} a' \overset{g}{\longrightarrow} G(b') \right)} &=& \overline{g \circ f} \\ &=& r \\ \left(F(a) \overset{F(f)}{\longrightarrow} F(a') \overset{\overline{g}}{\longrightarrow} b' \right) &=& \bar{g} \circ 1_b \\ &=& r \end{eqnarray}

左辺値の計算における二つ目の等号について補足する。着目していた組 (a', b')に対して aを手前にくっつけたので、 g \circ f \in \mathcal{A}(a, G(b'))と考えるべきである。それゆえ先ほど組 (a, b')のところで説明した通り \overline{g \circ f} = rとなる。

以上により左辺と右辺は一致しており、条件を満たしている。

この調子で全部の対象の組について調べていくのは紙面の都合でやめておくが、最後に (a, b)という組について考えてみよう。 \mathcal{B}(F(a),b) = \{1_b \}、 \mathcal{A}(a, G(b)) = \{f \}なので、それぞれのただ一つの元が一対一に対応していると考えれば両者の間に全単射を構成することができる。つまり \overline{1_b} = fである。

bから出ていく方向の射は 1_{b}, rの2つがある。 1_{b}は先ほどと同様に確かめれば成り立つことが分かるので、 rについて式(1)の両辺の値を確かめてみると以下のようになる。

\begin{eqnarray} \overline{\left(F(a) \overset{1_b}{\longrightarrow} b \overset{r}{\longrightarrow} b' \right)} &=& \bar{r} \\ &=& g \circ f \\ \left(a \overset{\overline{1_b}}{\longrightarrow} G(b) \overset{G(r)}{\longrightarrow} G(b') \right) &=& g \circ \overline{1_b} \\ &=& g \circ f \end{eqnarray}

左辺値の計算における二つ目の等号について補足する。着目していた組 (a, b)に対して b'を後ろにくっつけたので、 r \in \mathcal{B}(F(a), b')と考えるべきである。それゆえ先ほど組 (a, b')のところで説明した通り \bar{r} = g \circ fとなる。

以上により左辺と右辺は一致しており、条件を満たしている。

aに入ってくる方向の射は 1_aしかないので、式(2)は (a, b')のケースと同じように成り立つ。

以上、3つの対象の組について調べたが、他の組も同様に調べていけば F \dashv Gであることが分かる。

上記の説明を漫然と読んでいると \bar{g} = \overline{g \circ f} = rに思えてしまうかもしれない。しかしこれは微妙に正しくない。射の転置というのはどの対象のペアを考えているかによって意味が変わる点に注意が必要である。つまり、文脈なしに転置の記号が出てきてもそれは意味を成さない（ということに私は初め気付かず大変混乱した）。

G \dashv Fでないことの確認

実は逆向きの随伴は成り立たない。例えば組 (b, a)について考えてみると \mathcal{A}(G(b), a) = \emptyset、 \mathcal{B}(b, F(a)) = \{1_b\}なので両者の間に全単射を構成することができない。

随伴と圏同値の関係

随伴の定義を見ていると何となく互いに逆向きの関手のペアのような概念に思える。これはいかにも圏同値と関連がありそうである。というのも、圏同値の定義においても互いに逆向きっぽい2つの関手が関係するためである。実際、随伴と圏同値はどういう関係にあるのだろうか？

随伴なら圏同値か？

これは正しくない。例えば先ほど示した例において圏 \mathcal{A}, \mathcal{B}は圏同値ではない。例えば aに対して G(x) \cong aとなるような x \in \mathcal{B}は存在しない、つまり Gは本質的全射ではない。「 Gが悪いのであって、他のちゃんとした関手を選べば圏同値にできないんですか？」という疑問が湧くかもしれないが、 \mathcal{A}の対象が3つあり、かついずれも互いに同型でないのに対して、 \mathcal{B}の対象が2個しかないので、どんな関手を持ってこようと \mathcal{B} \to \mathcal{A}方向に対しては本質的全射になり得ない。

圏同値なら随伴か？

これは正しいらしい。が、本稿の内容だけを前提として証明するのは難しい。元気があればまた別の機会に説明したい。

まとめ

本稿では随伴について例を用いて説明した。また、随伴と圏同値の関連について少しだけ触れた。

随伴にはunitとcounitという大事な概念があるのだが、本稿ではそこまで説明しきれなかった。また、結局のところ随伴とは何なのかという直観的な理解はあまり得られなかったというのが正直な感想である。前者については時間ができたら記事を書きたいと思う。後者についてはいろいろと勉強していくうちに直観が養われていくと信じて頑張りたい。

参考

[1] [1612.09375] Basic Category Theory