エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

代数的構造による圏論(12)

随伴(3) 随伴の三角等式による定義

随伴の定義についても本に従って見ていきます。

随伴の三角等式による定義

定義 8.1 \mathcal{C} \mathcal{D} 間の関手  \mathcal{C} \xrightarrow{F} \mathcal{D} \mathcal{C} \xleftarrow{G} \mathcal{D} について、自然変換  FG \overset{\varepsilon}{\Longrightarrow} \mathrm{id}_\mathcal{D} \mathrm{id}_\mathcal{C} \overset{\eta}{\Longrightarrow} GF が存在してこれらが三角等式を満たすとき、すなわち  \require{AMScd} \begin{CD}
F @> 1_F >> F \\
@V Fη VV @| \\
FGF @>> εF > F
\end{CD} \begin{CD}
G @> ηG >> GFG \\
@| @VV Gε V \\
G @>> 1_G > G
\end{CD} を可換にするとき、四つ組  \langle F, G, \varepsilon, \eta \rangle を随伴関係と呼びます。

定義(圏の積) \mathcal{C} \mathcal{D} の積  \mathcal{C} \times \mathcal{D} とは、

  •  \mathcal{C} \times \mathcal{D} の対象は、 \mathcal{C} の対象  X \mathcal{D} の対象  Y の組  \langle X, Y \rangle
  •  \mathcal{C} \times \mathcal{D} の射は、 \mathcal{C} の射  X \xrightarrow{f} X' \mathcal{D} の射  Y \xrightarrow{g} Y' の組  \langle X, Y \rangle \xrightarrow{\langle f, g \rangle} \langle X', Y' \rangle

であるものと定義します(これは圏となります)。

定義 関手  \mathcal{C}^\mathrm{op} \times \mathcal{C} \xrightarrow{\mathrm{Hom}_\mathcal{C}(-, -)} \mathbf{Set}

  •  \mathcal{C}^\mathrm{op} \times \mathcal{D} の対象  \langle X, Y \rangle \mathrm{Hom}_\mathcal{C}(X, Y) を対応させる
  •  \mathcal{C} の射  A' \xrightarrow{a} A に対応する  \mathcal{C}^\mathrm{op} の射を  A \xrightarrow{a^\mathrm{op}} A' とすると、 \mathcal{C}^\mathrm{op} の射を  A \xrightarrow{a^\mathrm{op}} A' \mathcal{C} の射  B \xrightarrow{b} B' の組である  \mathcal{C}^\mathrm{op} \times \mathcal{C} の射  \langle A, B \rangle \xrightarrow{\langle a^\mathrm{op}, b \rangle} \langle A', B' \rangle に対応する  \mathbf{Set} の射  \mathrm{Hom}_\mathcal{C}(A, B) \xrightarrow{\mathrm{Hom}_\mathcal{C}(a^\mathrm{op}, b)} \mathrm{Hom}_\mathcal{C}(A,' B') を、
    •  A \xrightarrow{x} B A' \xrightarrow{a} A \xrightarrow{x} B \xrightarrow{b} B' に対応させるもの

と定義します(これは関手となります)。

定義 関手  \mathcal{C} \xrightarrow{F} \mathcal{D} に対応する関手  \mathcal{C}^\mathrm{op} \xrightarrow{F^\mathrm{op}} \mathcal{D}^\mathrm{op} F^\mathrm{op} として

  •  \mathcal{C}^\mathrm{op} \times \mathcal{D} \xrightarrow{F^\mathrm{op} \times \mathrm{id}_\mathcal{D}} \mathcal{D}^\mathrm{op} \times \mathcal{D} \xrightarrow{\mathrm{Hom}_\mathcal{D}(-, -)} \mathrm{Set} \mathrm{Hom}_\mathcal{D}(F(-), -)
  •  \mathcal{C}^\mathrm{op} \times \mathcal{D} \xrightarrow{\mathrm{id}_{\mathcal{C}^\mathrm{op}} \times G} \mathcal{C}^\mathrm{op} \times \mathcal{C} \xrightarrow{\mathrm{Hom}_\mathcal{C}(-, -)} \mathrm{Set} \mathrm{Hom}_\mathcal{C}(-, G(-))

と書きます。

定理 8.2 \mathcal{C} \mathcal{D} 間の関手  \mathcal{C} \xrightarrow{F} \mathcal{D} \mathcal{C} \xleftarrow{G} \mathcal{D} の定める随伴関係  \langle F, G, \varepsilon, \eta \rangle から自然同値  \mathrm{Hom}_\mathcal{D}(F(-), -) \implies \mathrm{Hom}_\mathcal{C}(-, G(-)) を構成することができます。

[証明]

  •  F(X) \xrightarrow{f} Y から  X \xrightarrow{\eta_X} GF(X) \xrightarrow{G(f)} G(Y) への対応を  \Phi_{\langle X, Y \rangle}
  •  X \xrightarrow{g} G(Y) から  F(X) \xrightarrow{F(g)} FG(Y) \xrightarrow{\varepsilon_Y} Y への対応を  \Psi_{\langle X, Y \rangle}

とおきます。

  •  \mathrm{Hom}_\mathcal{D}(F(-), -) \overset{\Phi}{\Longrightarrow} \mathrm{Hom}_\mathcal{C}(-, G(-)) (カリー化)
  •  \mathrm{Hom}_\mathcal{D}(F(-), -) \overset{\Psi}{\Longleftarrow} \mathrm{Hom}_\mathcal{C}(-, G(-)) (アンカリー化)

は以下の図式が可換図式となることから自然変換となります。

 X \xrightarrow{x} X' Y \xrightarrow{y} Y' に関する以下の図式を考えます。(図式1) \begin{CD}
\mathrm{Hom}_{\mathcal{D}}(F(X),Y) @> \Phi_{\langle X, Y \rangle} >> \mathrm{Hom}_{\mathcal{C}}(X,G(Y)) \\
@V \mathrm{Hom}_{\mathcal{D}}(F(x),y) VV @VV \mathrm{Hom}_{\mathcal{C}}(x,G(y)) V \\
\mathrm{Hom}_{\mathcal{D}}(F(X'),Y') @> \Phi_{\langle X', Y' \rangle} >> \mathrm{Hom}_{\mathcal{C}}(X',G(Y')) \\
\end{CD}

 F(X) \xrightarrow{f} Y をとると、 \eta が自然変換であることから  GF(x) \circ η_{X'} = η_{X} \circ x となるので \begin{eqnarray*}
\Phi_{\langle X', Y' \rangle} ( \mathrm{Hom}_{\mathcal{D}}(F(x),y) (f) )
& = & \Phi_{\langle X', Y' \rangle} ( y \circ f \circ F(x) ) \\
& = & G(y) \circ G(f) \circ GF(x) \circ η_{X'} \\
& = & G(y) \circ G(f) \circ η_{X} \circ x \\
& = & \mathrm{Hom}_{\mathcal{C}}(x,G(y)) ( G(f) \circ η_{X} ) \\
& = & \mathrm{Hom}_{\mathcal{C}}(x,G(y)) ( \Phi_{\langle X, Y \rangle}(f) ) \\
\end{eqnarray*} となって、(図式1)は可換図式となります。よって  \Phi は自然変換となります。

 X \xrightarrow{x} X' Y \xrightarrow{y} Y' に関する以下の図式を考えます。(図式2) \begin{CD}
\mathrm{Hom}_{\mathcal{D}}(F(X),Y) @< \Psi_{\langle X, Y \rangle} << \mathrm{Hom}_{\mathcal{C}}(X,G(Y)) \\
@V \mathrm{Hom}_{\mathcal{D}}(F(x),y) VV @VV \mathrm{Hom}_{\mathcal{C}}(x,G(y)) V \\
\mathrm{Hom}_{\mathcal{D}}(F(X'),Y') @< \Psi_{\langle X', Y' \rangle} << \mathrm{Hom}_{\mathcal{C}}(X',G(Y')) \\
\end{CD}

 X \xrightarrow{g} G(Y) をとると、 \varepsilon が自然変換であることから  ε_{Y'} \circ FG(y) = y \circ ε_{Y} となるので \begin{eqnarray*}
\Psi_{\langle X', Y' \rangle} ( \mathrm{Hom}_{\mathcal{c}}(x,G(y)) (g) )
& = & \Phi_{\langle X', Y' \rangle} ( G(y) \circ g \circ x ) \\
& = & ε_{Y'} \circ FG(y) \circ F(g) \circ F(x) \\
& = & y \circ ε_{Y} \circ F(g) \circ F(x) \\
& = & \mathrm{Hom}_{\mathcal{D}}(F(x),y) ( ε_{Y} \circ F(g) ) \\
& = & \mathrm{Hom}_{\mathcal{D}}(F(x),y) ( \Psi_{\langle X, Y \rangle}(g) ) \\
\end{eqnarray*} となって、(図式2)は可換図式となります。よって  \Psi は自然変換となります。

 (Fη)_X = F(η_X) (εF)_X = ε_{F(X)} なので三角等式を書き換えると(図式3) \begin{CD}
F(X) @> 1_{F(X)} >> F(X) \\
@V F(η_X) VV @VV 1_{F(X)} V \\
FGF(X) @>> ε_{F(X)} > F(X)
\end{CD} は可換図式となります。 F(X) \xrightarrow{f} Y をとると、 ε は自然変換なので(図式4) \begin{CD}
F(X) @> 1_{F(X)} >> F(X) \\
@V F(η_X) VV @VV 1_{F(X)} V \\
FGF(X) @>> ε_{F(X)} > F(X) \\
@V FG(f) VV @VV f V \\
F(X) @>> ε_{Y} > Y
\end{CD} は可換図式となります。よって \begin{eqnarray*}
\Psi_{\langle X, Y \rangle} ( \Phi_{\langle X, Y \rangle} (f) )
& = & \Psi_{\langle X, Y \rangle} ( G(f) \circ η_{X} ) \\
& = & ε_{Y} \circ FG(f) \circ F(η_{X}) \\
& = & f \\
\end{eqnarray*} となって、 \Psi \circ \Phi \mathrm{Hom}_{\mathcal{D}}(F(-), -) の恒等自然変換となります。

 (Gε)_Y = G(ε_Y) (ηG)_Y = η_{G(Y)} なので三角等式を書き換えると(図式5) \begin{CD}
G(Y) @> η_{G(Y)} >> GFG(Y) \\
@V 1_{G(Y)} VV @VV G(ε_Y) V \\
G(Y) @>> 1_{G(Y)} > G(Y)
\end{CD} は可換図式となります。 X \xrightarrow{g} G(Y) をとると、 η は自然変換なので(図式6) \begin{CD}
X @> η_{X} >> GF(X) \\
@V g VV @VV GF(g) V \\
G(Y) @> η_{G(Y)} >> GFG(Y) \\
@V 1_{G(Y)} VV @VV G(ε_Y) V \\
G(Y) @>> 1_{G(Y)} > G(Y)
\end{CD} は可換図式となります。よって \begin{eqnarray*}
\Phi_{\langle X, Y \rangle} ( \Psi_{\langle X, Y \rangle} (g) )
& = & \Phi_{\langle X, Y \rangle} ( ε_Y \circ F(g) ) \\
& = & G(ε_{Y}) \circ GF(g) \circ η_{X} \\
& = & g \\
\end{eqnarray*} となって、 \Phi \circ \Psi \mathrm{Hom}_{\mathcal{C}}(-, G(-)) の恒等自然変換となります。

よって  \Phi は自然同値となります。[証明終わり]

代数的構造による圏論(11)

随伴(2) 積関手と冪関手

自由マグマと自由モノイドの関係を使って、随伴(の一部)を説明することができると思ったのですが、まだできていないし、随伴の全体を説明することは難しいと思われるので、また「圏論の道案内 ~矢印でえがく数学の世界~」の「第8章 随伴 ①積と冪との間の関係」に従って説明していくことにします。

これ以降この本では可換モノイド、半環、行列などの話題が現れないようですが、これらについても調査していく予定です。

積関手

積を持つ圏  \mathcal{C} の対象  A に対して

  • 任意の対象  X に対して対象  A \times X
  • 任意の射  X \xrightarrow{f} Y に対して射  A \times X \xrightarrow{1_A \times f} A \times Y

を対応させるものは関手となります。この関手を  \mathcal{C} から  \mathcal{C} への積関手  A \times () と呼びます。

冪関手

積および冪を持つ圏  \mathcal{C} において、対象  X に対して評価射  A \times X^A \xrightarrow{\varepsilon_X} X は、任意の射  A \times Y \xrightarrow{h} X に対して 射  Y \xrightarrow{\tilde{h}} X^A で(可換図式1)  \require{AMScd} \begin{CD}
A \times Y @> h >> X \\
@V 1_A \times \tilde{h} VV @VV 1_X V \\
A \times X^A @>> \varepsilon_X > X
\end{CD} を可換にするものが一意的に存在するものとなります。 \tilde{h} h のカリー化または転置と呼び、ここでは  \mathrm{curry}(h) と書きます。

 X \xrightarrow{f} Y に対して、冪の普遍性(可換図式1)より  X^A \xrightarrow{u} Y^A で(可換図式2) \begin{CD}
A \times X^A @> \varepsilon_X >> X \\
@V 1_A \times u VV @VV f V \\
A \times Y^A @>> \varepsilon_Y > Y
\end{CD} を可換にするものが一意的に存在します。

この  u f^A と書くと、冪を持つ圏  \mathcal{C} の対象  A に対して

  • 任意の対象  X に対して対象  X^A
  • 任意の射  X \xrightarrow{f} Y に対して射  X^A \xrightarrow{f^A} Y^A

を対応させるものは関手となります。この関手を  \mathcal{C} から  \mathcal{C} への関手(冪関手)  ()^A と呼びます。

積関手と冪関手の関係 ( \varepsilon)

積関手を  F_A、冪関手を  G_A とすると、(可換図式2)は(可換図式3) \begin{CD}
F_A G_A (X) @> \varepsilon_X >> X \\
@V F_A G_A (f) VV @VV f V \\
F_A G_A (Y) @>> \varepsilon_Y > Y \\
\end{CD} となって、自然変換  F_A G_A \overset{\varepsilon}{\Longrightarrow} \mathrm{id}_\mathcal{C} を表すものとなります。

積関手と冪関手の関係 ( \eta)

対象  A X に対して冪の普遍性(可換図式1)より(可換図式4) \begin{CD}
A \times X @> 1_A \times 1_X >> A \times X \\
@V 1_A \times η_X VV @VV 1_A \times 1_X V \\
A \times (A \times X)^A @>> \varepsilon_{A \times X} > A \times X
\end{CD} を可換にする  X \xrightarrow{η_X} (A \times X)^A が一意的に存在します( η_X = \mathrm{curry}(1_A \times 1_X))。

 A \times X \xrightarrow{1_A \times f} A \times Y のカリー化  X \xrightarrow{g} (A \times Y)^A ( g = \mathrm{curry}(1_A \times f))が一意的に存在して(可換図式5) \begin{CD}
A \times X @> 1_A \times f >> A \times Y \\
@V 1_A \times g VV @VV 1_A \times 1_Y V \\
A \times (A \times Y)^A @>> \varepsilon_{A \times Y} > A \times Y
\end{CD} を可換にします。

以下の図式が可換図式となることを見ていきます。(図式6) \begin{CD}
X @> η_X >> (A \times X)^A \\
@V f VV @VV (1_A \times f)^A V \\
Y @>> η_Y > (A \times Y)^A \\
\end{CD}

(可換図式4)より以下の図式(可換図式7) \begin{CD}
A \times X @> 1_A \times f >> A \times Y \\
@V 1_A \times f VV @VV 1_A \times 1_Y V \\
A \times Y @> 1_A \times 1_Y >> A \times Y \\
@V 1_A \times η_Y VV @VV 1_A \times 1_Y V \\
A \times (A \times Y)^A @>> \varepsilon_{A \times Y} > A \times Y
\end{CD} は可換図式となります。(可換図式5)より  \eta_Y \circ f = \mathrm{curry}(1_A \times f) となります。

(可換図式4)、(可換図式2)より(可換図式8) \begin{CD}
A \times X @> 1_A \times 1_X >> A \times X \\
@V 1_A \times η_X VV @VV 1_A \times 1_X V \\
A \times (A \times X)^A @> \varepsilon_{A \times X} >> A \times X \\
@V 1_A \times (1_A \times f)^A VV @VV 1_A \times f V \\
A \times (A \times Y)^A @>> \varepsilon_{A \times Y} > A \times Y
\end{CD} は可換図式となります。(可換図式5)のより  (1_A \times f)^A \circ η_X = \mathrm{curry}(1_A \times f) となります。

よって(図式6)は可換図式となり(可換図式9) \begin{CD}
X @> η_X >> G_A F_A(X) \\
@V f VV @VV G_A F_A(f) V \\
Y @>> η_Y > G_A F_A(Y) \\
\end{CD} は可換図式となり、自然変換  \mathrm{id}_\mathcal{C} \overset{\eta}{\Longrightarrow} G_A F_A を表す可換図式となります。

三角等式

三角等式 ( F_AG_AF_A)

(可換図式4)を  F_A G_A を使って描くと(可換図式10) \begin{CD}
F_A(X) @> 1_{F_A(X)} >> F_A(X) \\
@V F_A(η_X) VV @VV 1_{F_A(X)} V \\
F_AG_AF_A(X) @>> \varepsilon_{F_A(X)} > F_A(X)
\end{CD} となります。

三角等式 ( G_AF_AG_A)

(可換図式10)で  X G_A(X) にすると(可換図式11) \begin{CD}
F_AG_A(X) @> 1_{F_AG_A(X)} >> F_AG_A(X) \\
@V F_A(η_{G_A(X)}) VV @VV 1_{F_AG_A(X)} V \\
F_AG_AF_AG_A(X) @>> \varepsilon_{F_AG_A(X)} > F_AG_A(X)
\end{CD} は可換図式となります。

(可換図式3)で  X \xrightarrow{f} Y F_A G_A (X) \xrightarrow{\varepsilon_X} X とすると(可換図式12) \begin{CD}
F_A G_A F_A G_A (X) @> \varepsilon_{F_A G_A (X)} >> F_A G_A (X) \\
@V F_A G_A (\varepsilon_X) VV @VV \varepsilon_X V \\
F_A G_A (X) @>> \varepsilon_X > X \\
\end{CD} は可換図式となります。

(可換図式11)と(可換図式12)より(可換図式13) \begin{CD}
F_AG_A(X) @> 1_{F_AG_A(X)} >> F_AG_A(X) \\
@V F_A(η_{G_A(X)}) VV @VV 1_{F_AG_A(X)} V \\
F_A G_A F_A G_A (X) @> \varepsilon_{F_A G_A (X)} >> F_A G_A (X) \\
@V F_A G_A (\varepsilon_X) VV @VV \varepsilon_X V \\
F_A G_A (X) @>> \varepsilon_X > X \\
\end{CD} は可換図式となって、 G_A (\varepsilon_X) \circ η_{G_A(X)} = \mathrm{curry}(\varepsilon_X) となります。

(可換図式3)の  X \xrightarrow{f} Y X \xrightarrow{1_{X}} X とすると(可換図式14)
\begin{CD}
F_A G_A (X) @> \varepsilon_X >> X \\
@V F_A(1_{G_A (X)}) VV @VV 1_X V \\
F_A G_A (X) @>> \varepsilon_X > X \\
\end{CD} は可換図式となって、 1_{G_A(X)} = \mathrm{curry}(\varepsilon_X) となります。

よって(可換図式15) \begin{CD}
G_A (X) @> η_{G_A(X)} >> G_A F_A G_A(X) \\
@V 1_{G_A (X)} VV @VV G_A (\varepsilon_X) V \\
G_A (X) @>> 1_{G_A (X)} > G(X) \\
\end{CD} は可換図式となります。

三角等式 (自然変換  \varepsilon, \eta)

関手  H と自然変換  t を合成した自然変換  Ht tH X 成分が

  •  (Ht)_X = H(t_X)
  •  (tH)_X = t_{H(X)}

であるものと定義します。\begin{CD}
F_A @> 1_{F_A} >> F_A \\
@V F_Aη VV @| \\
F_AG_AF_A @>> εF_A > F_A
\end{CD} \begin{CD}
G_A @> ηG_A >> G_AF_AG_A \\
@| @VV G_Aε V \\
G_A @>> 1_{G_A} > G_A
\end{CD} は自然変換の可換図式となります。

代数的構造による圏論(10)

随伴(1) 自由マグマ

まず基本になると思われる自由マグマから始めます。

マグマ

集合  M が二項演算  \cdot を持つとき  (M, \cdot) をマグマと呼びます。単に  M と表すこともあります。

部分マグマ

 (M, \cdot) をマグマとします。 X, Y \subseteq M に対して  X \cdot Y = \{ x \cdot y \mid x \in X, y \in Y \} と書くことにします。 X \subseteq M X \cdot X \subseteq X を満たすとき  X \cdot X への制限に関してマグマとなります。このような  X M の部分マグマと呼びます。 X M の部分マグマであるとき  X \le M と書くことにします。マグマ  M の部分マグマ全体の集合を  \mathfrak{S}(M) と書くことにします。

マグマの準同型

マグマ  (M. \cdot) からマグマ  (M', *) への写像  f: M \to M' が演算を保存するとき、すなわち

  •  f(x \cdot y) = f(x) * f(y)

を満たすとき、 f をマグマ  (M. \cdot) からマグマ  (M', *) へのマグマの準同型と呼びます。 f の像  f(M) M' の部分マグマとなります。 f全単射であるときマグマの同型と呼びます。マグマの同型  f: M \to M' が存在するとき  (M. \cdot) (M', *) は同型である(通常は演算を省略して  M M' は同型である)といい、 M \cong M' と書きます。

部分集合で生成された部分マグマ

 X をマグマ  M の部分集合とします。 N \subseteq M に対して、 N X を含む  M の部分マグマ( X \subseteq N \le M)であり、 X を含む  M の部分マグマの最小のもの、すなわち

  •  N' X を含む  M の部分マグマ( X \subseteq N' \le M)ならば  N \subseteq N'

であるとき、 N X で生成された  M の部分マグマと呼びます。マグマ  M X で生成された  M の部分マグマであるとき  M X で生成されたマグマと呼びます。

  • (MAG1)  N N' がどちらも  X で生成された  M の部分マグマならば  N = N' となります。

 X \subseteq M に対して  \overline{X} = \{ N \in \mathfrak{S}(M) \mid X \subseteq N \le M \} とおき、  \displaystyle X^+ = \bigcap \overline{X} とおきます。

任意の  N \in \overline{X} に対して  X \subseteq N となるので  X = \bigcap \{ X \mid N \in \overline{X} \} \subseteq \bigcap \{ N \mid N \in \overline{X} \} = X^+ が成り立ちます。また
\begin{eqnarray*}
X^+ \cdot X^+ & = & \left(\bigcap \overline{X}\right) \cdot \left(\bigcap \overline{X}\right) \\
& \subseteq & \bigcap \{ N \cdot N' \mid N, N' \in \overline{X} \} \\
& \subseteq & \bigcap \{ N \cdot N \mid N \in \overline{X} \} \\
& \subseteq & \bigcap \{ N \mid N \in \overline{X} \} = X^+ \\
\end{eqnarray*}
となります。よって  X \subseteq X^+ \le M が成り立ち、 X^+ X で生成された部分マグマとなります。

 X \subseteq M に対して、 X^{(\cdot)} = X \cup (X \cdot X) とおき、 X^{(\cdot)(n)}帰納的に
\begin{cases}
X^{(\cdot)(0)} = X \\
X^{(\cdot)(n+1)} = (X^{(\cdot)(n)})^{(\cdot)} \\
\end{cases}
と定義します。 \displaystyle X^{(\cdot)(*)} = \bigcup_{n \in \mathbb{N}} X^{(\cdot)(n)} とおくと、 X = X^{(\cdot)(0)} \subseteq X^{(\cdot)(*)} であり、
\begin{eqnarray*}
X^{(\cdot)(*)} \cdot X^{(\cdot)(*)} & = & \left( \bigcup_{n \in \mathbb{N}} X^{(\cdot)(n)} \right) \cdot \left( \bigcup_{n \in \mathbb{N}} X^{(\cdot)(n)} \right) \\
& \subseteq & \bigcup_{n \in \mathbb{N}} \bigcup_{n' \in \mathbb{N}} \left( X^{(\cdot)(n)} \cdot X^{(\cdot)(n')} \right) \\
& \subseteq & \bigcup_{n \in \mathbb{N}} \bigcup_{n' \in \mathbb{N}} X^{(\cdot)(n+n')} \\
& \subseteq & \bigcup_{n \in \mathbb{N}} X^{(\cdot)(n)} = X^{(\cdot)(*)} \\
\end{eqnarray*}
となります。よって  X \subseteq X^{(\cdot)(*)} \le M が成り立ち、 X^{(\cdot)(*)} X で生成された部分マグマとなります。

(MAG1)より  X^+ = X^{(\cdot)(*)} が成り立ちます。

自由マグマ

 M X で生成されたマグマ(または  X と集合として同値な集合で生成されたマグマ)で、任意のマグマ  M'写像  f: X \to M' に対して  f を拡張したマグマの準同型  f^*: M \to M' が一意的に存在するとき、 M X で生成された自由マグマと呼びます。 \eta: X \to M を包含写像とすると  f^* \circ \eta = f が成り立ちます。(以下は可換図式) \require{AMScd} \begin{CD}
X @> f >> M' \\
@V η VV @| \\
M @>> f^* > M'
\end{CD}

  • (MAG2)  M M' がどちらも  X で生成された自由マグマならば  M \cong M' となります。

(MAG3)  M X で生成された自由マグマ、 \eta: X \to M を包含写像 M' をマグマとします。

  • 写像  f: X \to M' に対して  f を拡張したマグマの準同型  f^*: M \to M' が一意的に存在します。 f^* = \varphi(f) とおきます。
  • マグマの準同型  g: M \to M' に対して  g X への制限写像  g|_X: X \to M' が一意的に存在します。 g|_X = \psi(g) とおきます。
  •  \psi(\varphi(f)) = f が成り立ちます。
  •  \varphi(\psi(g)) = g が成り立ちます。

集合  X に対して、 X に「  (」(開きかっこ)、「 )」(閉じかっこ)、「 *」(アスタリスク) という元をを付け加えた集合を  C_X とし、 C_X の元からなる有限個の列全体の集合を  S_X とします。すなわち、 S_X の元は、ある自然数  n が存在して  a_1 a_2 \cdots a_n という列で、各  a_i X の元であるか、開きかっこ、閉じかっこ、アスタリスクのどれかであるものとします。

 S_X に二項演算  \cdot: S_X \times S_X \to S_X \alpha \cdot \beta (\alpha * \beta) という列と定義すると  S_X はマグマとなります。 \iota: X \to S_X x \in X x という(長さ  1 の)列を対応させる写像とします。

 \eta(X) で生成された  S_X の部分マグマを  M_X とおきます。

 \displaystyle M_X = X^{(\cdot)(*)} = \bigcup_{n \in \mathbb{N}} X^{(\cdot)(n)} より  \alpha \in M_X に対してある自然数  n が存在して  \alpha \in X^{(\cdot)(n)} となります。このような最小の  n n_\alpha とおきます。

 n_\alpha > 0 のとき  \alpha = \beta \cdot \gamma となる  \beta, \gamma が存在します。 \alpha (\beta * \gamma) という列なのでこのような  \beta, \gamma は一意的に存在します。

よってマグマ  M'写像  f: X \to M' に対して  f^*: M_X \to M'
\begin{cases}
f^*(\alpha) = f(x) & (n_\alpha = 0, \alpha = \iota(x)) \\
f^*(\alpha) = f^*(\beta) \cdot f^*(\gamma) & (n_\alpha > 0, \alpha = \beta \cdot \gamma) \\
\end{cases}
と定義することができて、 n_\alpha > 0 のとき  f^*(\beta \cdot \gamma) = f^*(\beta) \cdot f^*(\gamma) が成り立つのでマグマの準同型となります。

また  n_\alpha = 0 のとき  f^*(\eta(x)) = f(x) が成り立つので  f^* \circ \eta = f が成り立ちます。

また、 g: M_X \to M' f を拡張したマグマの準同型とすると、任意の  \alpha \in M_X に対して  \alphaアスタリスクの個数に関する帰納法によって  g(\alpha) = f^*(\alpha) が成り立ちます。よって  M_X X で生成された自由マグマとなります。

集合の直積と直和との関係

集合  X, Y に対して、集合の直積  X \times Y、集合の直和  X + Y が一意的に決まるとします。

集合の直和を作る演算は可換かつ結合的とし、有限個の集合からなる集合  \mathcal{X} = \{ X_1, X_2, \cdots, X_m \} に対して  X_1 + X_2 + \cdots + X_m \bigsqcup \mathcal{X} と表します。 \mathcal{X} = \{ X_1, X_2, \cdots, X_m \} \mathcal{Y} = \{ Y_1, Y_2, \cdots, Y_n \} に対して  \mathcal{X} \cdot \mathcal{Y} = \{ X \times Y \mid X \in \mathcal{X}, Y \in \mathcal{Y} \} と定義します。

有限個の集合からなる集合  \mathcal{X} に対して、 \mathcal{X}^{(\cdot\cdot)} = \mathcal{X} \cup (\mathcal{X} \cdot \mathcal{X}) とおきます。集合  X に対して  X^{(\cdot\cdot)(n)}帰納的に
\begin{cases}
X^{(\cdot\cdot)(0)} = \{X\} \\
X^{(\cdot\cdot)(n+1)} = (X^{(\cdot\cdot)(n)})^{(\cdot\cdot)} \\
\end{cases}
と定義します。 \displaystyle X^{(\cdot\cdot)(*)} = \bigcup_{n \in \mathbb{N}} X^{(\cdot\cdot)(n)} とおくと、 X \in X^{(\cdot\cdot)(0)} \subseteq X^{(\cdot\cdot)(*)} であり、
\begin{eqnarray*}
X^{(\cdot\cdot)(*)} \cdot X^{(\cdot\cdot)(*)} & = & \left( \bigcup_{n \in \mathbb{N}} X^{(\cdot\cdot)(n)} \right) \cdot \left( \bigcup_{n \in \mathbb{N}} X^{(\cdot\cdot)(n)} \right) \\
& \subseteq & \bigcup_{n \in \mathbb{N}} \bigcup_{n' \in \mathbb{N}} \left( X^{(\cdot\cdot)(n)} \cdot X^{(\cdot\cdot)(n')} \right) \\
& \subseteq & \bigcup_{n \in \mathbb{N}} \bigcup_{n' \in \mathbb{N}} X^{(\cdot\cdot)(n+n')} \\
& \subseteq & \bigcup_{n \in \mathbb{N}} X^{(\cdot\cdot)(n)} = X^{(\cdot\cdot)(*)} \\
\end{eqnarray*}
となります。

 M^\times_X = \bigsqcup  X^{(\cdot\cdot)(*)} とおきます。 y \in Y \in X^{(\cdot\cdot)(*)} z \in Z \in X^{(\cdot\cdot)(*)} に対して  y z の組  \langle y, z \rangle \in Y \times Z \in X^{(\cdot\cdot)(*)} y \cdot z と定義すると、 (M^\times_X, \cdot) はマグマとなります。 M_X の元を  X の元で表したものを同じ形の  M^\times_X の元に対応させる写像はマグマの同型となるので、 (M^\times_X, \cdot) X で生成された自由マグマとなります。

随伴との関係

Wikipedia「随伴関手」の「自由群」の項を参考にします。ここの書き方に従って関手の記法を  FGX のように書くことがあります。

 \mathbf{Set} を集合の圏、 \mathbf{Mag} をマグマの圏とします。

関手  F : \mathbf{Mag} ← \mathbf{Set} は各集合  Y Y で生成された自由マグマを対応させるものとし、関手  G : \mathbf{Mag} → \mathbf{Set} はマグマ  X にその台集合を対応させる忘却関手とします。

集合  Y で生成された自由マグマ  FY とは、 GFY Y を含み( \eta_Y: Y \to GFY を包含写像とする)、任意のマグマ  X写像  g: Y \to GX に対してマグマの準同型  g^*: FY \to X が一意的に存在して、 G(g^*) \circ \eta_Y = g が成り立つというものでした。(可換図式1)
\begin{CD}
Y @> g >> GX \\
@V η_Y VV @| \\
GFY @>> G(g^*) > GX
\end{CD}

マグマの準同型  f: X \to X' に対して、 G(f): GX \to GX' f を集合の間の写像とみなしたものとすれば  G は関手となります。

集合の間の写像  g: Y \to Y' に対して、 F(g): FY \to FY' F(g) = (\eta_{Y'} \circ g)^* とすれば  F は関手となります。(可換図式2)
\begin{CD}
Y @> η_{Y'} \circ g >> GFY' \\
@V η_Y VV @| \\
GFY @>> G(η_{Y'} \circ g)^* > GFY'
\end{CD}
(可換図式2)より  1_Y: Y \to Y に対して
\begin{CD}
Y @> η_{Y} >> GFY \\
@V η_Y VV @| \\
GFY @>> G (1_{FY}) > GFY
\end{CD} は可換図式となり、自由マグマ  FY の普遍性( G (1_{FY}) の射の一意性)より  F (1_Y) = 1_{FY} = (\eta_{Y})^* となります。

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

余単位-単位随伴

(MAG3)より  \mathbf{Mag} の対象  X \mathbf{Set} の対象  Y に対して、 FY \xrightarrow{f} X Y に制限した  Y \xrightarrow{g} GX は一意的に存在し、 Y \xrightarrow{g} GX FY に拡張した  FY \xrightarrow{f} X は一意的に存在します。この対応
 \Phi_{Y,X}: \mathrm{Hom}_{\mathbf{Mag}}(FY,X) \to \mathrm{Hom}_{\mathbf{Set}}(Y,GX)
全単射となります。

マグマ  X に対して、 \varepsilon_{X}: FGX \to X \varepsilon_{X} = \Phi_{GX,X}^{-1}(1_{GX}) とおくと、以下の可換図式を満たします。(可換図式3)
\begin{CD}
GX @> 1_{GX} >> GX \\
@V η_{GX} VV @| \\
GFGX @>> G (\varepsilon_{X}) > GX
\end{CD}

 X \xrightarrow{f} X' とすると  \Phi_{GX,X'}^{-1}(G(f)) = ε_{X'} \circ FG(f) = f \circ ε_{X} となって(可換図式4)
\begin{CD}
FGX @> FG(f) >> FGX' \\
@V ε_{X} VV @VV ε_{X'} V \\
X @>> f > X'
\end{CD} は可換図式となり、 FG \overset{\varepsilon}{\Longrightarrow} 1_{\mathbf{Mag}} は自然変換となります。

集合  Y に対して、 Y \xrightarrow{\eta_Y} GFY \eta_{Y} = \Phi_{Y,FY}(1_{FY}) とおくと、以下の可換図式を満たします。(可換図式5)
\begin{CD}
FY @> F(η_{Y}) >> FGFY \\
@| @VV ε_{FY} V \\
FY @>> 1_{FY} > FY
\end{CD}

 Y \xrightarrow{g} Y' に対して、 \Phi_{Y,FY'}(F(g)) = η_{Y'} \circ g = GF(g) \circ η_{Y} となって(可換図式6)
\begin{CD}
Y @> g >> Y' \\
@V η_{Y} VV @VV η_{Y'} V \\
GFY @>> GF(g) > GFY'
\end{CD} は可換図式となり、 1_{\mathbf{Set}} \overset{\eta}{\Longrightarrow} GF は自然変換となります。

 FG \overset{\varepsilon}{\Longrightarrow} 1_{\mathbf{Mag}} を余単位、 1_{\mathbf{Set}} \overset{\eta}{\Longrightarrow} GF を単位と呼びます。

(可換図式5)、(可換図式3)より任意の  \mathbf{Mag} の対象  X \mathbf{Set} の対象  Y に対して \begin{eqnarray*}
1_{{FY}} &=& \varepsilon _{{FY}}\circ F(η_{Y}) \\
1_{{GX}} &=& G(\varepsilon _{X})\circ η_{{GX}}
\end{eqnarray*} が成り立ちます。よって余単位-単位恒等式 \begin{eqnarray*}
1_{F} &=& \varepsilon F\circ Fη \\
1_{G} &=& G\varepsilon \circ ηG
\end{eqnarray*} が成り立ちます。

[定義] \mathcal{C} \mathcal{D}、関手  F: \mathcal{C} \gets \mathcal{D} G: \mathcal{C} \to \mathcal{D}、 自然変換(余単位および単位)
\begin{aligned}
ε: & \ FG \to 1_{\mathcal{C}} \\
η: & \ 1_{\mathcal{D}} \to GF
\end{aligned}
が余単位-単位恒等式 \begin{eqnarray*}
1_{F} &=& \varepsilon F\circ Fη \\
1_{G} &=& G\varepsilon \circ ηG
\end{eqnarray*} を満たすとき、 F G の左随伴、 G F の右随伴と呼びます。この関係を  (\varepsilon ,\eta ):F \dashv G、または単に  F \dashv Gと書きます。

(三角等式) この等式を以下の可換図式で記述して三角等式と呼びます。(ただし三角形の図が描けないので四角形で描きますがこの等式自体を三角等式と呼ぶようなので問題はありません。) \begin{CD}
F @> 1_F >> F \\
@V Fη VV @| \\
FGF @>> εF > F
\end{CD} \begin{CD}
G @> ηG >> GFG \\
@| @VV Gε V \\
G @>> 1_G > G
\end{CD}

 F から  X への普遍射

 Y \mathbf{Set} の対象、 f : FY → X \mathbf{Mag} の射とすると、(可換図式5)、(可換図式4)より(可換図式7)
\begin{CD}
FY @> F(η_{Y}) >> FGFY @> FG(f) >> FGX \\
@| @VV ε_{FY} V @VV ε_{X} V \\
FY @>> 1_{FY} > FY @>> f > X
\end{CD}
は可換図式となります。よって  g = G(f) \circ η_{Y} とおくと  \varepsilon_{X} \circ F(g) = f となります。 g = \Phi_{Y,X}(f) となります。よって

  •  Y \mathbf{Set} の対象で  f : FY → X \mathbf{Mag} の射ならば、 \mathbf{Set} の射  g : Y → GX が一意的に存在して  \varepsilon_{X} \circ F(g) = f

が成り立ちます。よって  (GX,\varepsilon_{X}) F から  X への普遍射となります。

[定義] \mathcal{C} \mathcal{D}、関手  F: \mathcal{C} \gets \mathcal{D} が、任意の  \mathcal{C} の対象  X に対して  F から  X への普遍射が存在するとき、 F を左随伴関手と呼びます。

 \mathcal{C} の対象  X に対して  \mathcal{D} の対象  G_0X F から  X への普遍射  ε_X : FG_0X → X を決めます。関手  G: \mathcal{C} \to \mathcal{D} を、

  •  GX = G_0X
  •  \mathcal{C} の射  f : X → X' に対して  ε_{X'} \circ F(g) = f \circ  ε_X を満たす  g: GX \to GX' が一意的に存在します。この  g に対して  G(f) = g

と定義することができます。このとき  F G の左随伴であるといいます。

 Y から  G への普遍射

 X \mathbf{Mag} の対象、 g : GX \gets Y \mathbf{Set} の射とすると、(可換図式6)、(可換図式3)より(可換図式8)
\begin{CD}
Y @> g >> GX @> 1_{GX} >> GX \\
@V η_{Y} VV @VV η_{GX} V @| \\
GFY @>> GF(g) > GFGX @>> G (\varepsilon_{X}) > GX
\end{CD}
は可換図式となります。よって  f = \varepsilon_{X} \circ F(g) とおくと   G(f) \circ \eta_{Y} = g となります。 f = \Phi_{Y,X}^{-1}(g) となります。よって

  •  X \mathbf{Mag} の対象で  g : GX \gets Y \mathbf{Set} の射ならば、 \mathbf{Mag} の射  f : X \gets FY が一意的に存在して   G(f) \circ \eta_{Y} = g

が成り立ちます。よって  (FY,\eta_{Y}) Y から  G への普遍射となります。

[定義] \mathcal{C} \mathcal{D}、関手  G: \mathcal{C} \to \mathcal{D} が、任意の  \mathcal{D} の対象  Y に対して  Y から  G への普遍射が存在するとき、 G を右随伴関手と呼びます。

 \mathcal{D} の対象  Y に対して  \mathcal{C} の対象  F_0Y Y から  G への普遍射  η_Y : Y → GF_0Y を決めます。関手  F: \mathcal{C} \gets \mathcal{D} を、

  •  FY = F_0Y
  •  \mathcal{D} の射  g : Y → Y' に対して  G(f) \circ η_Y = η_{Y'} \circ g を満たす  f: FY \to FY' が一意的に存在します。この  f に対して  F(g) = f

と定義することができます。このとき、 G F の右随伴であるといいます。

Hom集合随伴

 \mathbf{Mag} の対象  X \mathbf{Set} の対象  Y \mathbf{Mag} の射  FY \xrightarrow{f} X \mathbf{Set} の射  Y \xrightarrow{g} GX \Phi_{Y,X}(f) = g を満たすとします。

(可換図式7)より任意の  \mathbf{Mag} の射  FY \xrightarrow{f} X に対して  \mathbf{Set} の射  Y \xrightarrow{g} GX が一意的に存在して以下の図式は可換図式となります。よって任意の  \mathbf{Set} の射  Y' \xrightarrow{y} Y に対して以下の図式を可換にする  Y' \to GX の射は一意的に存在します。(可換図式9)
\begin{CD}
FY' @> F(y) >> FY @> F(g) >> FGX \\
@. @| @VV ε_{X} V \\
@. FY @>> f > X
\end{CD}
よって  \Phi_{Y',X}(f \circ F(y)) = g \circ y が成り立ちます。このとき  \Phi_{Y,X} Y に関して自然であるといいます。これを \begin{equation*}
\cfrac{FY' \xrightarrow{F(y)} FY \xrightarrow{f} X}{Y' \xrightarrow[y]{} Y \xrightarrow[g]{} GX}
\end{equation*} と表します。

(可換図式8)より任意の  \mathbf{Set} の射  Y \xrightarrow{g} GX に対して  \mathbf{Mag} の射  FY \xrightarrow{f} X が一意的に存在して以下の図式は可換図式となります。よって任意の  \mathbf{Mag} の射  X \xrightarrow{x} X' に対して以下の図式を可換にする  FY \to X' の射は一意的に存在します。(可換図式10)
\begin{CD}
Y @> g >> GX \\
@VV η_{Y} V @| \\
GFY @>> G(f) > GX @>> G(x) > GX'
\end{CD}
よって  \Phi_{Y,X'}(x \circ f) = G(x) \circ g が成り立ちます。このとき  \Phi_{Y,X} X に関して自然であるといいます。これを \begin{equation*}
\cfrac{FY \xrightarrow{f} X \xrightarrow{x} X'}{Y \xrightarrow[g]{} GX \xrightarrow[G(x)]{} GX'}
\end{equation*} と表します。

[定義]  \Phi_{Y,X} Y に関して自然であり、 X に関して自然であるとき、 F G の左随伴であり  G F の右随伴であるといいます。この関係を  \Phi: F \dashv G、または単に  F\dashv G と書きます。

この対応によって  \Phi : \mathrm{Hom}_{\mathbf{Mag}}(F-,-) \to \mathrm{Hom}_{\mathbf{Set}}(-,G-) は自然同型となります。以下でこれを説明します。

 \mathbf{Mag} の対象  X に対して  \mathrm{Hom}_{\mathbf{Mag}}(F-,X)

  •  \mathbf{Set} の対象  Y \mathrm{Hom}_\mathbf{Mag}(FY, X) を対応させ、
  •  \mathbf{Set}の射  y: Y' \to Y \psi(y) = \mathrm{Hom}_\mathbf{Mag}(Fy, X): \mathrm{Hom}_\mathbf{Mag}(FY, X) \to \mathrm{Hom}_\mathbf{Mag}(FY', X) \psi(y)(f) = f \circ F(y) を対応させるもの

\begin{CD}
FY' @> \psi(y)(f) >> X \\
@V F(y) VV @| \\
FY @>> f > X
\end{CD} と定義すると、 Y'' \xrightarrow{y'} Y' \xrightarrow{y} Y に対して \begin{eqnarray*}
\psi(y \circ y')(f) & = & f \circ ( F(y \circ y') ) \\
& = & f \circ ( F(y) \circ F(y') ) \\
& = & ( f \circ F(y) ) \circ F(y') \\
& = & \psi(y') ( f \circ F(y) ) \\
& = & \psi(y') ( \psi(y) (f) ) \\
& = & (\psi(y') \circ \psi(y))(f)
\end{eqnarray*} となり、 \mathbf{Set} から  \mathbf{Set} への反変関手となります。

 \mathbf{Mag} の対象  X に対して  \mathrm{Hom}_{\mathbf{Set}}(-,GX)

  •  \mathbf{Set} の対象  Y \mathrm{Hom}_\mathbf{Set}(Y, GX) を対応させ、
  •  \mathbf{Set}の射  y: Y' \to Y \psi(y) = \mathrm{Hom}_\mathbf{Set}(y, GX): \mathrm{Hom}_\mathbf{Set}(Y, GX) \to \mathrm{Hom}_\mathbf{Set}(Y', GX) \psi(y)(g) = g \circ y を対応させるもの

\begin{CD}
Y' @> \psi(y)(g) >> GX \\
@V y VV @| \\
Y @>> g > GX
\end{CD} と定義すると、 Y'' \xrightarrow{y'} Y' \xrightarrow{y} Y に対して \begin{eqnarray*}
\psi(y \circ y')(g) & = & g \circ ( (y \circ y' ) \\
& = & ( g \circ y ) \circ y' \\
& = & \psi(y') ( g \circ y ) \\
& = & \psi(y') ( \psi(y) (g) ) \\
& = & (\psi(y') \circ \psi(y))(g)
\end{eqnarray*} となり、 \mathbf{Set} から  \mathbf{Set} への反変関手となります。

 \mathbf{Set} の対象  Y に対して  \mathrm{Hom}_{\mathbf{Mag}}(FY,-)

  •  \mathbf{Mag} の対象  X \mathrm{Hom}_\mathbf{Mag}(FY, X) を対応させ、
  •  \mathbf{Mag}の射  x: X \to X' \psi(x) = \mathrm{Hom}_\mathbf{Mag}(FY, x): \mathrm{Hom}_\mathbf{Mag}(FY, X) \to \mathrm{Hom}_\mathbf{Mag}(FY, X') \psi(x)(f) = x \circ f を対応させるもの

\begin{CD}
FY @> f >> X \\
@| @VV x V \\
FY @>> \psi(x)(f) > X'
\end{CD} と定義すると、 X \xrightarrow{x} X' \xrightarrow{x'} X'' に対して \begin{eqnarray*}
\psi(x' \circ x)(f) & = & (x' \circ x) \circ f \\
& = & x' \circ (x \circ f) \\
& = & x' \circ \psi(x)(f) \\
& = & \psi(x')( \psi(x)(f) ) \\
& = & (\psi(x') \circ \psi(x))(f) \\
\end{eqnarray*} となり、 \mathbf{Mag} から  \mathbf{Set} への共変関手となります。

 \mathbf{Set} の対象  Y に対して  \mathrm{Hom}_{\mathbf{Set}}(Y,G-)

  •  \mathbf{Mag} の対象  X \mathrm{Hom}_\mathbf{Set}(Y, GX) を対応させ、
  •  \mathbf{Mag}の射  x: X \to X' \psi(x) = \mathrm{Hom}_\mathbf{Set}(Y, Gx): \mathrm{Hom}_\mathbf{Set}(Y, GX) \to \mathrm{Hom}_\mathbf{Set}(Y, GX') \psi(x)(g) = G(x) \circ g を対応させるもの

\begin{CD}
Y @> g >> GX \\
@| @VV G(x) V \\
Y @>> \psi(x)(g) > GX'
\end{CD} と定義すると、 X \xrightarrow{x} X' \xrightarrow{x'} X'' に対して \begin{eqnarray*}
\psi(x' \circ x)(g) & = & G(x' \circ x) \circ g \\
& = & (G(x') \circ G(x)) \circ g \\
& = & G(x') \circ (G(x) \circ g) \\
& = & G(x') \circ \psi(x)(g) \\
& = & \psi(x')(\psi(x)(g)) \\
& = & (\psi(x') \circ \psi(x))(g) \\
\end{eqnarray*} となり、 \mathbf{Mag} から  \mathbf{Set} への共変関手となります。

これらの関手を組み合わせることによって  \mathrm{Hom}_{\mathbf{Mag}}(F-,-): \mathbf{Set}^\mathrm{op} \times \mathbf{Mag} \to \mathbf{Set} \mathrm{Hom}_{\mathbf{Set}}(-,G-): \mathbf{Set}^\mathrm{op} \times \mathbf{Mag} \to \mathbf{Set} は関手となります。

 \mathbf{Set} の対象  Y Y'、射  g: Y' \to Y \mathbf{Mag} の対象  X X'、射  f: X \to X' に対して(可換図式9)、(可換図式10)より  \Phi_{Y,X}: \mathrm{Hom}_{\mathbf{Mag}}(FY,X) \to \mathrm{Hom}_{\mathbf{Set}}(Y,GX) は可換図式
\begin{CD}
\mathrm{Hom}_{\mathbf{Mag}}(FY,X) @> \Phi_{Y,X} >> \mathrm{Hom}_{\mathbf{Set}}(Y,GX) \\
@V \mathrm{Hom}_{\mathbf{Mag}}(Fg,f) VV @VV \mathrm{Hom}_{\mathbf{Set}}(g,Gf) V \\
\mathrm{Hom}_{\mathbf{Mag}}(FY',X') @> \Phi_{Y',X'} >> \mathrm{Hom}_{\mathbf{Set}}(Y',GX') \\
\end{CD}
を満たすので  \Phi : \mathrm{Hom}_{\mathbf{Mag}}(F-,-) \to \mathrm{Hom}_{\mathbf{Set}}(-,G-) は自然変換となります。 \Phi_{Y,X}全単射なので  \Phi は自然同型(自然同値)となります。

[定義]  \Phi が自然同型であるとき、 F G の左随伴であり  G F の右随伴であるといいます。この関係を  \Phi: F \dashv G、または単に  F\dashv G と書きます。

代数的構造による圏論(9)

トポス(1)

この段階で数学的帰納法を使うことによって図式を使わずに説明することができるようになったと思うのですが、簡単にはいかないのでトポスについてもう少し調べてみたいと思います。

[4]、[5]、[6]、[7]の本を持っていたので少し読んでみようと思います。[4]、[5]は型理論の本でトポスに関する記述もあるようです。[7]はトポスの本のようです。[6]は圏論全般の本のようですがトポスに関する記述があります。ただ英語のトポスの本を読むのはたいへんなので、[2]、[3]の本を持っていたのでまずこれから読んで見たいと思います。

まずトポスの定義から見ていきます。

[1] 圏論の道案内 ~矢印でえがく数学の世界~

[1]のトポスの定義は以下のようになっています。

定義 7.2 (トポス) \mathcal{C} が CCC であり、部分対象分類子を持つとき、初等トポス(elementary topos)あるいは単にトポスと呼びます。ここで部分対象分類子(subobject classifier)とは  \mathcal{C} の射  1 \xrightarrow{t} \Omegaで、任意の単射  A \xrightarrow{m} B に対して射  B \xrightarrow{\chi_m} \Omega \require{AMScd} \begin{CD}
A @> !_A >> 1 \\
@V m VV @VV t V \\
B @>> \chi_m > \Omega
\end{CD} が引き戻しの図式となるようなものが一意に存在するものをいいます。このとき  \chi_m m の特性射(characteristic morphism)と呼びます。 t は真(True)とも呼ばれ、また True とも書かれます。そして  \Omega は真理値対象(truth value object)と呼ばれます。

[2] 圏論による論理学―高階論理とトポス

部分対象分類子の定義、以下の定義 1 (トポス)は[1]と同じです。

定義 1 (トポス) 圏が以下の条件 (1)~(4) を満たすときトポスと呼びます。

  • (1) 終対象が存在する。
  • (2) 任意の対象  A, B に対して積  A \times B が存在する。
  • (3) 任意の対象  A, B に対して冪  B^A が存在する。
  • (4) 部分対象分類子が存在する。

<1> 終対象、積、部分対象分類子が存在するなら、イコライザーが存在する。

[証明] A \overset{f}{\underset{g}{\rightrightarrows}} B とします。[1]で  \binom{f}{g} と書かれていた射をここでは  \langle f, g \rangle と書いています。 \Delta_B = \langle 1_B, 1_B \rangle とし  B \times B \xrightarrow{\delta_B} \Omega を図式(1) \begin{CD}
B @> !_B >> 1 \\
@V \Delta_B VV @VV t V \\
B \times B @>> \delta_B > \Omega
\end{CD} が引き戻しの図式となる射とします。 A \xrightarrow{\langle f, g \rangle} B \times B \xrightarrow{\delta_B} \Omega に対して図式(2) \begin{CD}
C @> !_C >> 1 \\
@V e VV @VV t V \\
A @>> \delta_B \circ \langle f, g \rangle > \Omega
\end{CD} が引き戻しの図式となる射  C \xrightarrow{e} A が存在します。*1

 X \xrightarrow{p} C とすると、図式(3) \begin{CD}
X @> !_X >> 1 \\
@V e \circ p VV @VV t V \\
A @>> \delta_B \circ \langle f, g \rangle > \Omega
\end{CD} は可換となります。図式(2)が引き戻しの図式であることから  e \circ p = e \circ u となる  X \xrightarrow{u} C が一意的に存在します。一意性より  e \circ p = e \circ u' ならば  u = u' となります。よって  e \circ p = e \circ q ならば  p = q となるので  e単射となります。*2

図式(4) \begin{CD}
C @> !_C >> 1 \\
@V \langle f, g \rangle \circ e VV @VV t V \\
B \times B @>> \delta_B > \Omega
\end{CD} が可換で図式(1)が引き戻しの図式であることから、 \langle f, g \rangle \circ e = \Delta_B \circ v を満たす  C \xrightarrow{v} B が一意的に存在します。よって  f \circ e = \pi_1 \circ \langle f, g \rangle \circ e = \pi_1 \circ \Delta_B \circ v = 1_B \circ v = v g \circ e = \pi_2 \circ \langle f, g \rangle \circ e = \pi_2 \circ \Delta_B \circ v = 1_B \circ v = v となり  f \circ e = g \circ e となります。

 D \xrightarrow{h} A f \circ h = g \circ h を満たすとします。 \langle f, g \rangle \circ h = \langle f \circ h, g \circ h \rangle = \langle f \circ h, f \circ h \rangle = \Delta_B \circ f \circ h となって、図式(5) \begin{CD}
D @> f \circ h >> B @> !_B >> 1 \\
@V h VV @V \Delta_B VV @VV t V \\
A @>> \langle f, g \rangle > B \times B @>> \delta_B > \Omega
\end{CD} は可換となります。図式(1)が引き戻しの図式であることから  D \xrightarrow{w} C が一意的に存在して  e \circ w = h となります。

よって  C \xrightarrow{e} A A \overset{f}{\underset{g}{\rightrightarrows}} Bイコライザーとなっています。】

<2> 積、イコライザーが存在するなら、引き戻しが存在する。
[証明] A \xrightarrow{f} C \xleftarrow{g} B とすると、イコライザーが存在することから \begin{CD}
X @> e >> A \times B \\
@V e VV @VV g \circ \pi_2 V \\
A \times B @>> f \circ \pi_1 > C
\end{CD} が可換となるイコライザー  X \xrightarrow{e} A が存在します。\begin{CD}
Y @> q >> B \\
@V p VV @VV g V \\
A @>> f > C
\end{CD} が可換とすると、\begin{CD}
Y @> \langle p, q \rangle >> A \times B \\
@V \langle p, q \rangle VV @VV g \circ \pi_2 V \\
A \times B @>> f \circ \pi_1 > C
\end{CD} は可換となり、 X \xrightarrow{e} Aイコライザーなので  Y \xrightarrow{u} X e \circ u = \langle p, q \rangle であるものが存在します。 \pi_1 \circ e \circ u = \pi_1 \circ \langle p, q \rangle = p \pi_2 \circ e \circ u = \pi_2 \circ \langle p, q \rangle = q となるので \begin{CD}
X @> \pi_2 \circ e >> B \\
@V \pi_1 \circ e VV @VV g V \\
A @>> f > C
\end{CD} は引き戻しの図式となります。】

<3> 定義 1 の (1)~(4) が成立するなら、始対象、直和、押し出しが存在する。この証明は省略されています。

定義 2 (トポス) 圏が以下の条件 (1)~(4) を満たすときトポスと呼びます。

  • (1) 終対象が存在する。
  • (2) 任意の射  A \to C \gets B に対して引き戻しが存在する。
  • (3) 任意の対象  A, B に対して冪  B^A が存在する。
  • (4) 部分対象分類子が存在する。

<4> 終対象と引き戻しが存在するなら、積が存在する。
[証明]【 図式(1) \begin{CD}
X @> g >> B \\
@V f VV @VVV \\
A @>>> 1
\end{CD} を引き戻しの図式とします。 A \xleftarrow{p} Y \xrightarrow{q} B とすると、
\begin{CD}
Y @> q >> B \\
@V p VV @VVV \\
A @>>> 1
\end{CD} は可換となります。図式(1)が引き戻しの図式であることから、 Y \xrightarrow{u} X f \circ u = p g \circ u = q であるものが存在します。よって  A \xleftarrow{f} X \xrightarrow{g} B は積の図式となります。】 

[3] 層・圏・トポス―現代的集合像を求めて

定義 (部分対象分類子) 部分対象分類子(subobject classifier)とは  \mathcal{C} の射  1 \xrightarrow{t} \Omegaで、以下の二つの条件を満たすものをいいます。

(1) 任意の  B \xrightarrow{f} \Omega に対して  A \xrightarrow{g} B で \begin{CD}
A @> !_A >> 1 \\
@V g VV @VV t V \\
B @>> f > \Omega
\end{CD} が引き戻しの図式となるようなものが存在する。

(2) 任意の単射  A \xrightarrow{m} B に対して射  B \xrightarrow{\chi_m} \Omega で \begin{CD}
A @> !_A >> 1 \\
@V m VV @VV t V \\
B @>> \chi_m > \Omega
\end{CD} が引き戻しの図式となるようなものが一意に存在する。

部分対象分類子の定義は[1]の定義に条件(1)が追加されたものです。

定義 (トポス) \mathcal{C} が CCC であり、部分対象分類子を持つとき、トポスと呼びます。

トポスの定義も同様に[1]の定義に条件(1)が追加されたものとなっています。

[4] Introduction to Higher-Order Categorical Logic

  • Part II Type theory and toposes
    • 3 The internal language of a topos

定義 (部分対象分類子) 部分対象分類子(subobject classifier)とは  \mathcal{C} の射  1 \xrightarrow{t} \Omegaで、以下の二つの条件を満たすものをいいます。

  • (1) 任意の  B \xrightarrow{f} \Omega に対して  B \xrightarrow{f} \Omega B \xrightarrow{!_B} 1 \xrightarrow{t} \Omegaイコライザー  A \xrightarrow{g} B が存在する
  • (2) [3]の(2)と同じ

トポスの定義では自然数対象を持つという条件が増えています。自然数対象の定義は[1]と同じです。

定義 3.1 (トポス) \mathcal{C} が CCC であり、部分対象分類子と自然数対象を持つとき、トポスと呼びます。

[5] Categories, Types, and Structures

  • 2 Constructions
    • 2.7 Subobject Classifiers and Topoi

定義 2.7.2 (トポス) [2]定義 2 と同じです。

[6] Computational Category Theory

  • 7 Toposes
    • 7.2 Toposes

定義 26 (トポス) 圏が以下の条件 (1)~(3) を満たすときトポスと呼びます。

  • (1) 有限図式に対する極限が存在する(有限完備)。有限図式に対する余極限が存在する(有限余完備)。
  • (2) 任意の対象  A, B に対して冪  B^A が存在する。
  • (3) 部分対象分類子が存在する。

[7] Sheaves in Geometry and Logic

  • IV. First Properties of Elementary Topoi
    • 1. Definition of a Topos

定義 (トポス) 圏が以下の条件 (1)~(4) を満たすときトポスと呼びます。

  • (1) 終対象が存在する。
  • (2) 任意の射  A \to C \gets B に対して引き戻しが存在する。
  • (3) 部分対象分類子が存在する。
  • (4) 任意の対象  B に対して、以下の条件を満たす対象  PB、射  B \times PB \xrightarrow{\in_B} \Omega が存在する:
    • 任意の射  B \times A \xrightarrow{f} \Omega に対して、以下の図式を可換にする射  A \xrightarrow{g} PB が一意的に存在する:

\begin{CD}
B \times A @> f >> \Omega \\
@V 1_B \times g VV @| \\
B \times PB @>> \in_B > \Omega
\end{CD}

*1:この理由は不明。引き戻しが存在すると仮定すると成り立ちますが、後で引き戻しの存在の証明に使われているのでそれでは意味がない。 集合の場合は  h = \delta_B \circ \langle f, g \rangle とおくと  C = h^{-1}(true) = \bigcup \{ X \mid X \subseteq A \ で図式が可換 \} となります。 集合のように書くと  C \xrightarrow{e} A = \{ X \xrightarrow{m} A \mid \ 単射で図式が可換 \} という射が存在すると仮定すれば成り立ちます。\begin{CD} X @> !_X >> 1 \\ @V m VV @VV t V \\ A @>> \delta_B \circ \langle f, g \rangle > \Omega \end{CD}

*2: e が最初から単射としたときはこの議論は不要。

中間報告(6)

このブログは、論理プログラミングに実行順序を指定する機能を追加するため、現在は主に数学的帰納法や可換モノイドについてプログラミング言語で記述する方法を調査しています。

前回の中間報告以降更新したもの

代数的構造による圏論 ← 斜めの線を使わない圏論

このブログでは普通の圏論の本に載っているような図式を書くことができないらしいので、「斜めの線を使わない圏論」では、自由生成モノイド、自由生成可換モノイド、自由生成半環などを構成するような方法で、極限、随伴などを説明することができないか検討していました。圏論の本に載っているような説明は私にはわかりにくいので、別の説明の方法があるかどうか考えていましたが、特に進展はありませんでした。

このシリーズでは、「圏論の道案内」を読みながら上記のような問題を考えていきます。

圏論の道案内」では自然変換を中心に説明されています。「第4章 自然変換」、その前の「第3章 関手」ではたぶん自然変換に関連した例が書かれていています。その前に「前順序」の説明があります。このあたりは何かの説明に使えるかもしれません。

続いて、この本では「コンマ圏」を使って「第5章 普遍性 ⑥射圏,そして一般射圏」で極限が説明されています。この本では「コンマ圏」のことを「一般射圏」と呼んでいます。

「エレファントな整数論」で写像から作られる前順序集合について調べているのですが、そのような議論をするには「第7章 圏論集合論」の「①トポス(topos)」、「②圏論集合論」まで読んだほうが良いようなので、そこまでは読みました。

今の段階で

  • 数学的帰納法の記述
  • 帰納的定義の記述
  • 可換モノイドに関する帰納法の記述
  • 外積の定義と計算
  • 連立一次方程式の順序に依存しない解法
  • 論理プログラミングとしての半環の標準化

を結合律を使った書き方で書く方法を考えることができると思われます。しかし、トポスの定義がまだよくわかっていないので、他の本も参考にして調べています。「直観主義論理」や「型理論」に関する本もあったので読んでみることにします。これは無限に動くプログラムの連携に使えるのではないかと思っています。

「論理プログラミングとしての半環の標準化」というのは論理プログラミングの実行を「選言標準形」のような形に変形することと考えた場合どうなるかというものです。結合律のような法則により自然数より少し一般的な全順序集合の合成と考えることができます。これはモナドが関連するかもしれないのでモナドのところまで読んでみます。今のところこの「変形」を説明する言葉がないので、まずそれを考えた後で次に進もうと思います。

エレファントな整数論

の説明のところまで終わった状況です。これらは定義から自動的に実行できるはずだが、実行順序によっては実行できないことがあり、それを記述するためのプログラミング言語の要素がないと考えられます。今後はこれらの記述方法について考えていきます。

前回の中間報告以降更新していないもの

エレファントな線形代数

連立一次方程式の解法や行列のランクなどを、行列を使わずに説明することを引き続き考えていきます。

エレファントな関数論

コーシーの積分定理の証明について調査中です。

群論の計算

数学的帰納法や可換モノイドの記述について調査した後、以下のような計算が簡単に書けるようになるかどうか調査する予定です。

  • 群の簡単な計算
  • 可解群の定義
  • 対称式の基本定理
  • ガロア理論の基本定理
  • 可解群と代数方程式の代数的解法の関係

保留中のシリーズ

以下の記事のシリーズは、他の案件で進展があるまで保留中です。

今後の予定

まだどのような形で数式の「変形」を書けば良いのかわかっていないので、まずそこから考えていきます。その後いろいろな数学の問題について考えて、プログラミング言語で表すことができるのかどうか考えていきます。

代数的構造による圏論(8)

第5章まで読めばろいろできると思われるのですが、数学的帰納法について考えるには第7章まで読んだほうが良いようなのでさらに引用していきます。そこまでは少し図式を描いていきます。

第6章 冪:プログラムの本質

①冪

定義 6.1 (冪) 積を持つ圏  \mathcal{C} の対象  A, B について、コンマ圏(一般射圏)  (A \times () \to B) の終対象を  A から  B への冪(exponential)と呼びます。

積を持つ圏  \mathcal{C} の対象  A に対して  \mathcal{C} から  \mathcal{C} への関手  A \times () は、

  • 任意の対象  X に対して対象  A \times X
  • 任意の射  X \xrightarrow{f} Y に対して射  A \times X \xrightarrow{1_A \times f} A \times Y

を対応させるものです。

対象  B は圏  \mathbf{1} から  \mathcal{C} への関手  \bar{B} と同一視します。 \bar{B}

  •  \mathbf{1} のただ一つの対象  X に対して対象  B
  •  \mathbf{1} のただ一つの射  1_X に対して射  1_B

を対応させるものとなります。自然変換  \bar{B} \overset{t}{\Longrightarrow} \bar{B} の成分  t_X

  • 対象  B に対して対象  B
  •  1_B に対して射  1_B

を対応させるものとなります。

すると  (A \times () \to B) の対象は  \mathcal{C} の対象  X を用いて  A \times X \to B と書ける射となります。終対象は射  A \times P \xrightarrow{p} B で、他に射  A \times X \xrightarrow{x} B があれば、射  X \xrightarrow{\tilde{x}}P \require{AMScd} \begin{CD}
A \times X @> x >> B \\
@V 1_A \times \tilde{x} VV @| \\
A \times P @>> p > B
\end{CD} を可換にするものが一意に存在するものとなります。このとき対象  P のことも冪と呼び、 B^A と書きます。また射  p は評価射(evalution morphism)と呼び、  \mathrm{eval} と書きます。

「二つの入力を持つ関数」 X \times Y \xrightarrow{f} Z を考えると、冪の普遍性から  X \xrightarrow{\tilde{f}} Z^Y で上の図式を可換にするもの、つまり  \mathrm{eval} \circ (1_X \times \tilde{f}) = f を満たすものが一意に存在します。このようなことを繰り返して「多変数関数」をただ一つの入力をもつ「一変数関数」の連鎖に変換することをカリー化(currying)と呼びます。また、カリー化された射を元の射に戻すことアンカリー化(uncurrying)と呼びます。

②CCC

定義 6.2 (CCC) 圏が

  • 終対象
  • 任意の対象  X, Y に対しての積  X \times Y
  • 任意の対象  X, Y に対しての冪  Y^X

を持つとき、カルテジアン閉圏(cartesian closed category)、略して CCC と呼びます。

定義 (点全射) A \xrightarrow{f} X が点全射であるとは、任意の  1 \xrightarrow{x} X に対して  1 \xrightarrow{a} A x = f \circ a なるものが存在することをいいます。

定義 (広義の点全射) A \times B \xrightarrow{g}X について、そのカリー化  B \xrightarrow{\tilde{g}} X^A が広義の点全射(weakly point-surjective)であるとは、任意の  A \xrightarrow{h} X に対して  1 \xrightarrow{b} B で、すべての  1 \xrightarrow{a} A に対して  g \circ \binom{a}{b} = h \circ a であるようなものが存在することをいいます。\begin{CD}
1 @> a >> A \\
@V \binom{a}{b} VV @VV h V \\
A \times B @>> g > X
\end{CD}

定理 6.3 (Lawvere の不動点定理) \mathcal{C} は CCC であるとします。射  A \times A \xrightarrow{f} X で、そのカリー化  A \xrightarrow{\tilde{f}} X^A が広義の点全射であるようなものが存在すれば、 X から  X 自身への任意の射  g について  1 \xrightarrow{x} X g \circ x = x となるものが存在します。このような射  1 \xrightarrow{x} X g不動点(fixed point)と呼びます。

[証明] \tilde{f} が広義の点全射だから、どんな射  A \xrightarrow{h} X に対しても射  1 \xrightarrow{b} A で任意の射  1 \xrightarrow{a} A に対して  f \circ \binom{a}{b} = h \circ a となるものが存在します。\begin{CD}
1 @> a >> A \\
@V \binom{a}{b} VV @VV h V \\
A \times A @>> f > X
\end{CD}  h として特に  A \xrightarrow{\Delta_A} A \times A \xrightarrow{f} X \xrightarrow{g} X ( \Delta_A = \binom{1_A}{1_A})をとれば  f \circ \binom{a}{b} = g \circ f \circ \Delta_A \circ a = g \circ f \circ \binom{1_A}{1_A} \circ a = g \circ f \circ \binom{a}{a} となるから、 a = b とすれば  f \circ \binom{b}{b} g不動点となります。】

 X としてちょうど二つの要素からなる集合  2 を考え、その二つの要素を True および False と呼びます。 A の部分集合は  A から  2 への写像と同一視することができます。

 A から  2^A へは単射はあるが全射は存在しません。(対角線論法)

[証明] A の各要素を、その要素のみからなる部分集合に対応させる写像単射となります。全射があったとします。 \mathbf{Set} では点全射全射は同じことだから、これは上の定理における  \tilde{f} となり、言い換えればそのアンカリー化が  f となります。すると、 2 から自身への任意の写像  g不動点を持つことになります。「否定」、つまり True と False を入れ替える  2 から  2 への写像を考えると、これは不動点を持たないので矛盾となります。よって全射は存在しません。】

第7章 圏論集合論

①トポス (topos)

定義 7.1 (単射全射) \mathcal{C} の射  X \xrightarrow{f} Y単射(monomorphism)であるとは、 Z \overset{g}{\underset{h}{\rightrightarrows}} X f \circ g = f \circ h なる任意の  g, h に対して  g = h であるときにいいます。 f は左簡約可能(left cancellable)とも呼びます。双対圏  \mathcal{C}^\mathrm{op} における単射 \mathcal{C}全射(epimorphism)と呼びます。

定義 7.2 (トポス) \mathcal{C} が CCC であり、部分対象分類子を持つとき、初等トポス(elementary topos)あるいは単にトポスと呼びます。ここで部分対象分類子(subobject classifier)とは  \mathcal{C} の射  1 \xrightarrow{t} \Omegaで、任意の単射  A \xrightarrow{m} B に対して射  B \xrightarrow{\chi_m} \Omega で \begin{CD}
A @> !_A >> 1 \\
@V m VV @VV t V \\
B @>> \chi_m > \Omega
\end{CD} が引き戻しの図式となるようなものが一意に存在するものをいいます。このとき  \chi_m m の特性射(characteristic morphism)と呼びます。 t は真(True)とも呼ばれ、また True とも書かれます。そして  \Omega は真理値対象(truth value object)と呼ばれます。

定理 7.3 トポスにおいて、単射かつ全射な射は同型射となります。

[証明]【 上の図式(図式(1))に  B \xrightarrow{!_B}1 を追加して図式(2) \begin{CD}
A @> m >> B @> !_B >> 1 \\
@| @. @VV t V \\
A @>> m > B @>> \chi_m > \Omega
\end{CD} とすると図式(1)が可換であることから図式(2)も可換となります。\begin{CD}
A' @> m' >> B @> !_B >> 1 \\
@| @. @VV t V \\
A' @>> m' > B @>> \chi_m > \Omega
\end{CD} が可換とすると、図式(1)が引き戻しの図式であることから、 A' \xrightarrow{u} A が一意的に存在して  m \circ u = m' を満たします。\begin{CD}
A' @> m' >> B \\
@V u VV @| \\
A @>> m > B
\end{CD}
 1_B単射なので図式 \begin{CD}
B @> !_B >> 1 \\
@V 1_B VV @VV t V \\
B @>> \chi_{1_B} > \Omega
\end{CD} は可換となります。 \chi_{1_B} \circ m = \chi_{1_B} \circ 1_B \circ m = t \circ {!_B} \circ m = t \circ {!_A} = \chi_{m} \circ m となって、 m全射(右簡約可能)ならば  \chi_{1_B} = \chi_{m} となります。よって \begin{CD}
B @> !_B >> 1 \\
@V 1_B VV @VV t V \\
B @>> \chi_{m} > \Omega
\end{CD} は可換となります。図式(1)が引き戻しの図式であることから  B \xrightarrow{u} A m \circ u = 1_B を満たすものが一意的に存在します。

 m \circ u \circ m = 1_B \circ m =  m = m \circ 1_A となり、 m単射(左簡約可能)なので  u \circ m = 1_A となります。よって  m は同型射となります。】

圏論集合論

定義 7.4 以下の条件を満たす圏を集合圏(category of sets)と呼び、 \mathbf{Set} と書きます。

  • 1.  \mathbf{Set} はトポスである。
  • 2.  \mathbf{Set}全射は切断を持つ。
  • 3.  \mathbf{Set} は well-pointed である。
  • 4.  \mathbf{Set}自然数対象を持つ。

 X \xrightarrow{f} Y の切断(section)とは、射  Y \xrightarrow{s} X f \circ s = 1_Y を満たすもののことを言います。条件 2 は選択公理(axiom of choice)と呼びます。

定義 7.5 終対象を持つ圏  \mathcal{C} が well-pointed であるとは。 1 が始対象でなく、 \mathcal{C} の任意の相異なる射  X \overset{f}{\underset{g}{\rightrightarrows}} Y に対して射  1 \xrightarrow{x} X f \circ x \ne g \circ x なるものが存在するときにいいます。

定義 7.6 終対象  1 を持つ圏   \mathcal{C} において、自然数対象(natural number object)とは対象  N、射  N \xrightarrow{s} N および  1 \xrightarrow{z} N の組  \langle N, s, z \rangle で、他の同様な組  \langle X, f, x \rangle に対して射  N \xrightarrow{u} X
\begin{CD}
1 @> z >> N @> s >> N \\
@| @VV u V @VV u V \\
1 @>> x > X @>> f > X \\
\end{CD}
を可換にするものが一意に存在するときにいいます。

代数的構造による圏論(7)

⑦極限,余極限の定義

続いて極限と積などの関係を見ていきます。

積・余積

 \mathcal{J} を対象が  a, b の二つで、射が恒等射だけの圏とします。 \mathcal{J} = \{a, b\} と書くことにします。

 \mathcal{J} 型の図式(圏  \mathcal{J} から圏  \mathcal{C} への関手)  D に対する極限( (\Delta \to D) の終対象)が存在するとします。 A = D(a) B = D(b) とおきます。

 D を圏  \mathbf{1} (対象を  \cdot とする)から  \mathrm{Fun}(\mathcal{J}, \mathcal{C}) への関手」と見たものを  D' とします。 (\Delta \to D) は、 \mathcal{C} の対象  X \mathbf{1} の(ただ一つの)対象  \cdot \mathrm{Fun}(\mathcal{J}, \mathcal{C}) の射  \Delta(X) \xrightarrow{p} D'(\cdot) = D からなる三つ組  \langle X, \cdot, p \rangle を対象として、 \langle X, \cdot, p \rangle から  \langle Y, \cdot, q \rangle への射としては、 \mathcal{C} の射  X \xrightarrow{u} Y \mathbf{1} の(ただ一つの)射  \cdot の組  \langle u, \cdot \rangle \require{AMScd}
\begin{CD}
\Delta(X) @> p >> D \\
@V \Delta(u) VV @| \\
\Delta(Y) @>> q > D
\end{CD}
を可換とする射からなる圏となります。各成分に対して
\begin{CD}
X @> p_j >> D(j) \\
@V u VV @| \\
Y @>> q_j > D(j)
\end{CD}
は可換となります。

自然変換  \Delta(X) \overset{p}{\Longrightarrow} D \ (: \mathcal{J} \to \mathcal{C}) は、 \mathcal{J} の対象  j に対して成分  p_j X = \Delta(X)(j) \xrightarrow{p_j} D(j) \ (\in \mathcal{C}) \mathcal{J} の射  j \xrightarrow{f} k に対して
\begin{CD}
X @> p_j >> D(j) \\
@| @VV D(f) V \\
X @>> p_k > D(k)
\end{CD}
を可換とするものとなります。これは  f が恒等射なので成り立ちます。

よって図式
\begin{CD}
A @< q_a << X @> q_b >> B \\
@| @VV u V @| \\
A @<< p_a < L @>> p_b > B
\end{CD}
が可換となるすべての射  u によって作られる射が  (\Delta \to D) の射となります。

 (\Delta \to D) の終対象  \langle L, \cdot, p \rangle は 任意の  \langle X, \cdot, q \rangle に対して  u: X \to L が存在して上記の図式が可換となるものとなります。よって  L (または  \langle L, p_a, p_b \rangle)は積  A \times B と同型となります。

余積は双対となります。

等化子(イコライザー)・余等化子

 \mathcal{J} を対象が  a, b の二つで、射が恒等射のほか、 a \xrightarrow{\alpha} b a \xrightarrow{\beta} b だけの圏とします。 \mathcal{J} = \{a, b; \ a \xrightarrow{\alpha} b, a \xrightarrow{\beta} b\} と書くことにします。

 \mathcal{J} 型の図式(圏  \mathcal{J} から圏  \mathcal{C} への関手)  D に対する極限( (\Delta \to D) の終対象)が存在するとします。 A = D(a) B = D(b) f = D(\alpha) g = D(\beta) とおきます。

自然変換  \Delta(X) \overset{p}{\Longrightarrow} D \ (: \mathcal{J} \to \mathcal{C}) は、 \mathcal{J} の対象  j に対して成分  p_j X = \Delta(X)(j) \xrightarrow{p_j} D(j) \ (\in \mathcal{C}) \mathcal{J} の射  j \xrightarrow{f} k に対して
\begin{CD}
X @> p_j >> D(j) \\
@| @VV D(f) V \\
X @>> p_k > D(k)
\end{CD}
を可換とするものとなります。これは
\begin{CD}
A @< p_a << X @> p_a >> A \\
@V f VV @| @VV g V \\
B @<< p_b < X @>> p_b > B
\end{CD}
を可換とするものとなります。よって
\begin{CD}
A @< p_a << X @> p_a >> A \\
@V f VV @VV p_b V @VV g V \\
B @= B @= B \\
\end{CD}
を可換とするものとなります。

よって上記の条件を満たす  \langle L, \cdot, p \rangle \langle X, \cdot, q \rangle に対して図式
\begin{CD}
A @< q_a << X @> q_b >> B \\
@| @VV u V @| \\
A @<< p_a < L @>> p_b > B
\end{CD}
が可換となるすべての射  u によって作られる射が  (\Delta \to D) の射となります。

 (\Delta \to D) の終対象  \langle L, \cdot, p \rangle は 任意の  \langle X, \cdot, q \rangle に対して  u: X \to L が存在して上記の図式が可換となるものとなります。

よって  L (または  \langle L, p_a, p_b \rangle)は  f g の等化子(以下の定義を参照)となります。

定義  A \xrightarrow{f} B A \xrightarrow{g} B に対して、対象  E と 射  E \xrightarrow{e} A f \circ e = g \circ e を満たすものであって、対象  X と 射  X \xrightarrow{h} A f \circ h = g \circ h を満たすならば射  X \xrightarrow{u} E が一意的に存在して  e \circ u = h を満たすとき、 E と 射  E \xrightarrow{e} A の組を  f g の等化子(イコライザー)と呼びます。

余等化子は双対となります。

引き戻し(ファイバー積)・押し出し

 \mathcal{J} を対象が  a, b, c の三つで、射が恒等射のほか、 a \xrightarrow{\alpha} c b \xrightarrow{\beta} c だけの圏とします。 \mathcal{J} = \{a, b; \ a \xrightarrow{\alpha} c, b \xrightarrow{\beta} c\} と書くことにします。

 \mathcal{J} 型の図式(圏  \mathcal{J} から圏  \mathcal{C} への関手)  D に対する極限( (\Delta \to D) の終対象)が存在するとします。 A = D(a) B = D(b) C = D(c) f = D(\alpha) g = D(\beta) とおきます。

自然変換  \Delta(X) \overset{p}{\Longrightarrow} D \ (: \mathcal{J} \to \mathcal{C}) は、 \mathcal{J} の対象  j に対して成分  p_j X = \Delta(X)(j) \xrightarrow{p_j} D(j) \ (\in \mathcal{C}) \mathcal{J} の射  j \xrightarrow{f} k に対して
\begin{CD}
X @> p_j >> D(j) \\
@| @VV D(f) V \\
X @>> p_k > D(k)
\end{CD}
を可換とするものとなります。これは
\begin{CD}
A @< p_a << X @> p_b >> B \\
@V f VV @| @VV g V \\
C @<< p_c < X @>> p_c > C
\end{CD}
を可換とするものとなります。よって
\begin{CD}
A @< p_a << X @> p_b >> B \\
@V f VV @VV p_c V @VV g V \\
C @= C @= C \\
\end{CD}
を可換とするもの、すなわち
\begin{CD}
X @> p_b >> B \\
@V p_b VV @VV g V \\
A @>> f > C \\
\end{CD}
を可換とするものとなります。

よって上記の条件を満たす  \langle L, \cdot, p \rangle \langle X, \cdot, q \rangle に対して図式
\begin{CD}
A @< q_a << X @> q_b >> B \\
@| @VV u V @| \\
A @<< p_a < L @>> p_b > B
\end{CD}
が可換となるすべての射  u によって作られる射が  (\Delta \to D) の射となります。

 (\Delta \to D) の終対象  \langle L, \cdot, p \rangle は 任意の  \langle X, \cdot, q \rangle に対して  u: X \to L が存在して上記の図式が可換となるものとなります。

よって  L (または  \langle L, p_a, p_b \rangle)は  f g の引き戻し(以下の定義を参照)となります。

定義  A \xrightarrow{f} C B \xrightarrow{g} C に対して、対象  P と 射  P \xrightarrow{p} A P \xrightarrow{q} B f \circ p = g \circ q を満たすものであって、対象  X と 射  X \xrightarrow{h} A X \xrightarrow{k} B f \circ h = g \circ k を満たすならば射  X \xrightarrow{u} P が一意的に存在して  p \circ u = h q \circ u = k を満たすとき、 P と 射  P \xrightarrow{p} A P \xrightarrow{q} B の組を  f g の引き戻し(ファイバー積)と呼びます。

押し出しは双対となります。