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

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

代数的構造による圏論(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 と書きます。