斜めの線を使わない圏論(1) - エレファント・コンピューティング調査報告

先日圏論の説明をしようとしましたが、ここでは可換図式の斜めの線が書けないらしいので可換図式を書くのがけっこう難しいです。そこで図を使わずに数式の変形だけで説明できないのか考えていきたいと思います。

圏の定義から(Wikipediaに従って)説明していきたいと思うのですが、しかしながら圏の定義とかを数式の変形で説明するのは難しいので、とりあえず自由群の説明あたりまでは普通に説明していきたいと思います。その説明に到達するまでけっこうあります。群よりモノイドの方が簡単なのでまずは自由モノイドについて説明します。

自由モノイド

集合 $X$ の生成する自由モノイドは、 $X$ の要素の有限個の列を元とし、列の連結を演算とするものとなります。長さ $0$ の列が単位元となります。これを(集合としては) $X^*$ と書くことにします。列の連結の演算を $\cdot$ と書くことにすます。 $x_i$ 、 $y_j$ が $X$ の元のとき
$(x_1 x_2 \cdots x_m) \cdot (y_1 y_2 \cdots y_n) = x_1 x_2 \cdots x_m \cdot y_1 y_2 \cdots y_n$
となります。紛らわしくない場合は $\cdot$ は省略します。このようにすると $(X^*, \cdot)$ はモノイドとなります。

モノイド $(M, \cdot)$ を単に $M$ と書くこともあります。

集合 $X$ をモノイド $M$ の部分集合とします。 $X$ を含む $M$ の部分モノイドの中で最小のものが存在します。これを $X$ が生成する部分モノイドと呼び $\langle X \rangle$ と書くことにします。 $\langle X \rangle$ は $M$ のすべての部分モノイドの共通部分となります。 $\langle X \rangle$ は集合としては $x_1 x_2 \cdots x_m$ という元全体の集合となります(各 $x_i$ は $X$ の元で単位元を含む)。

集合 $X$ をモノイド $M$ の部分集合とするとモノイドの準同型 $\varphi: X^* \to M$ が存在します。これは $X^*$ の元 $x_1 x_2 \cdots x_m$ を $M$ の元 $x_1 x_2 \cdots x_m$ に写すものとなります。 $\varphi(X^*) = \langle X \rangle$ となります。

モノイド $M$ の台集合(モノイド $(M, \cdot)$ の $M$ )に対する $M^*$ と上記の $\varphi$ に対して $\varphi( M^{*}) = \langle M \rangle = M$ となります。この $\varphi$ を $\varepsilon_M$ と書くことにします。

集合 $X$ からモノイド $M$ への写像 $f: X \to M$ に対して写像 $f^*: X^* \to M$ を $X^*$ の元 $x_1 x_2 \cdots x_m$ を $M$ の元 $f(x_1) f(x_2) \cdots f(x_m)$ に写すものとすると、 $f^*$ はモノイドの準同型となります。

集合 $X$ から集合 $Y$ への写像 $f: X \to Y$ に対して写像 $f^*: X^* \to Y^*$ を上記のものと同様のものとすると、 $f^*$ はモノイドの準同型となります。

随伴関手と自由モノイド

(Wikipedia「随伴関手」の「自由群」の項による)
関手 $F : \mathbf{Mon} \gets \mathbf{Set}$ は集合 $X$ に $X^*$ 、写像 $f$ に $f^*$ を対応させる関手とします(自由関手)。関手 $G : \mathbf{Mon} \to \mathbf{Set}$ はモノイドにその台集合、モノイドの準同型にそれを集合の間の写像と見たものを対応させる関手とします(忘却関手)。

モノイド $M$ に対して $G(M)$ と上記の $\varepsilon_M$ の組は $F$ から $M$ への普遍射となります。すなわち、 $X$ を集合、 $\psi: X^* \to M$ をモノイドの準同型とするとき、上記の議論と同様 $G(\psi)$ を $X$ に制限した写像を $g: X \to G(M)$ とすると、 $\psi = \varepsilon_M \circ g^*$ が成り立ちます。これは $X^*$ の元 $x_1 x_2 \cdots x_m$ を $M$ の元 $g(x_1) g(x_2) \cdots g(x_m) = \psi(x_1) \psi(x_2) \cdots \psi(x_m)$ に写す写像となります。

$\require{AMScd} \begin{CD} F(X) = X^* @> \psi >> M \\ @V F(g) = g^* VV @| \\ F(G(M)) = G(M)^* @>> \varepsilon_M > M \end{CD}$

集合 $X$ に対して $\eta_X : X \to G(F(X)) = G(X^*)$ を $x$ に $x$ を対応させる写像とすると、 $X^* = F(X)$ と $\eta_X$ の組 $(X^*, \eta_X)$ は $X$ から $G$ への普遍射となります。すなわち、 $M$ をモノイド、 $f: X \to G(M)$ を集合の間の写像とするとき、 $f = G(f^*) \circ \eta_X$ が成り立ちます。

$\require{AMScd} \begin{CD} X @> \eta_X >> G(F(X)) = G(X^*) \\ @| @VV G(f^*) V \\ X @>> f > G(M) \end{CD}$

以下に示すように $F$ は $G$ の左随伴となります。

余単位-単位随伴

(この項が数式の変形で書けそうなのでWikipediaにはいろいろあるのですがこの項だけ書くことにします。)

$\varepsilon _{X}$ はモノイド $FGX$ からモノイド $X$ へのモノイドの準同型で $x_1 x_2 \cdots x_m$ を $x_1 x_2 \cdots x_m$ に写すものとなります。
写像 $\eta _{Y}$ は集合 $Y$ を集合 $GFY$ の部分集合と見たときの包含写像となります。

モノイドの準同型 $f: X \to X'$ と $x_1, x_2, \cdots , x_m \in X$ に対して
$(f \circ \varepsilon_{X})(x_1 x_2 \cdots x_m) = f(x_1) f(x_2) \cdots f(x_m)$ 、
$(\varepsilon_{X'} \circ F(G(f)))(x_1 x_2 \cdots x_m) = f(x_1) f(x_2) \cdots f(x_m)$
が成り立つので以下の図式は可換となり $\varepsilon$ は自然変換となります。
$\begin{CD} F(G(X)) @> F(G(f)) >> F(G(X')) \\ @V \varepsilon_{X} VV @VV \varepsilon_{X'} V \\ 1_\mathbf{Mon}(X)=X @>> 1_\mathbf{Mon}(f)=f > 1_\mathbf{Mon}(X')=X' \end{CD}$

集合の間の写像 $g: Y \to Y'$ と $y \in Y$ に対して
$(G(F(g)) \circ \eta_{Y})(y) = g(y)$ 、
$(\eta_{Y'} \circ g)(y) = g(y)$
が成り立つので以下の図式は可換となり $\eta$ は自然変換となります。
$\begin{CD} 1_\mathbf{Set}(Y)=Y @> 1_\mathbf{Set}(g)=g >> 1_\mathbf{Set}(Y')=Y' \\ @V \eta_{Y} VV @VV \eta_{Y'} V \\ G(F(Y)) @>> G(F(g)) > G(F(Y')) \end{CD}$

余単位-単位随伴 $(\varepsilon ,\eta ):F\dashv G$ であることは以下のことからわかります。

$1_{F}=\varepsilon F\circ F\eta$

$1_{F}=\varepsilon F\circ F\eta$ というのは各集合 $Y$ に対して、合成
$FY{\xrightarrow {F(\eta _{Y})}}FGFY{\xrightarrow {\varepsilon _{FY}}}FY$
が恒等射であるということなので、これは $\varepsilon _{FY} \circ F(\eta _{Y})$ がモノイド $FY$ の恒等写像であるということを示せばよいということになります。 $GFY$ は自由モノイド $F(Y) = Y^*$ の台集合であり、 $FGFY$ は $Y^*$ の台集合から生成される自由モノイドとなります。射 $F(\eta _{Y})$ は $FY$ から $FGFY$ へのモノイドの単射準同型であり、 $FY$ を $FGFY$ の部分集合を見たときの包含写像となります。射 $\varepsilon _{FY}$ は $FGFY$ から $FY$ へのモノイドの準同型であり、 $x_1 x_2 \cdots x_m$ を $x_1 x_2 \cdots x_m$ に写すものとなり(各 $x_i$ は $FY$ の元)、これを $FY$ に制限したものは恒等写像となります。したがって $\varepsilon _{FY} \circ F(\eta _{Y})$ は恒等写像となります。

$1_{G}=G\varepsilon \circ \eta G$

$1_{G}=G\varepsilon \circ \eta G$ というのは各モノイド $X$ に対して、合成
$GX{\xrightarrow {\eta _{GX}}}GFGX{\xrightarrow {G(\varepsilon _{X})}}GX$
が恒等射であるということなので、これは $G(\varepsilon _{X}) \circ \eta _{GX}$ が集合 $GX$ の恒等写像であるということを示せばよいということになります。 $GFGX$ は $FGX$ の台集合であり、写像 $\eta _{GX}$ は集合 $GX$ を集合 $GFGX$ の部分集合と見たときの包含写像となります。 $FGX$ はモノイド $X$ の台集合で生成された自由モノイドであり、 $\varepsilon _{X}$ はモノイド $FGX$ からモノイド $X$ へのモノイドの準同型で $x_1 x_2 \cdots x_m$ を $x_1 x_2 \cdots x_m$ に写すものとなります。 $G(\varepsilon _{X})$ は $\varepsilon _{X}$ を集合の間の写像と見た集合 $GFGX$ から集合 $GX$ への写像で、 $GX$ を $GFGX$ の部分集合と考えると $G(\varepsilon _{X})$ を $GX$ に制限したものは恒等写像となります。したがって $G(\varepsilon _{X}) \circ \eta _{GX}$ は恒等写像となります。

この項は数式の変形でできそうなので今後考えていきたいと思います。自由関手の方は普通の言葉で説明できそうなのですが、忘却関手の方は言葉で書くとわかりにくいのでこのようなものは数式で書いた方が良いと考えられます。

問題

写像 $f: X \to X^*$ に対して $f^{*}$ を $n$ 個合成したモノイドの準同型 $f^{*n}: X^* \to X^*$ が定義できます。 $x \in X$ に対して $x \in X^*$ の元の可算個の列 $e(f, x)$ を $e(f, x) = (x, f^*(x), f^{*2}(x), f^{*3}(x), \cdots)$ と定義します。 $x \in X^*$ の元の可算個の列全体の集合を $X^{**}$ と書くことにします。 $X^{**}$ の部分集合 $f^{**} = \{ e(f, x) | x \in X \}$ を定義します。

この「逆像」を考えます。 $Y \subseteq X^*$ に対して $g(Y) = (f^*)^{-1}(Y) = \{ x \in X^* | f^*(x) \in Y \}$ と定義します。 $g$ を $n$ 個合成した写像を $g^n$ とします。 $x \in X^*$ の部分集合の可算個の列 $g^*(Y)$ を $g^*(Y) = ( Y, g(Y), g^2(Y), g^3(Y), \cdots )$ とおきます。