エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで数式の変形を表すことを考えていくブロクです。

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

第5章 普遍性

最初の方は定義を引用するだけとします。

①終対象と始対象

定義 5.1 \mathcal{C} の対象  T が、 \mathcal{C} の任意の対象  X に対して  X から  T への射がただ一つ存在するとき、 T \mathcal{C} の終対象と呼びます。この一意的な射を  !X と書きます。 \mathcal{C} の反対圏  \mathcal{C}^\mathrm{op} の終対象を  \mathcal{C} の始対象と呼びます。

終対象(始対象)は存在するとは限らず、一意的でもありませんが、存在すれば同型となります。これを同型を除いて一意と言います。

集合圏  \mathbf{Set} では、終対象は「一点のみからなる集合」、始対象は空集合となります。

量系の圏  \mathbf{Qua} では、量  0 のみからなる量系が終対象かつ始対象となります。このような対象を零対象と呼びます。

②積と余積

定義 5.2 圏の対象  A, B に対して、対象  P、射  P \xrightarrow{p_A} A、射  P \xrightarrow{p_B} B の三つ組  \langle P, p_A, p_B \rangle A, B の積であるとは、対象  X、射  X \xrightarrow{x_A} A、射  X \xrightarrow{x_B} B の三つ組  \langle X, x_A, x_B \rangle に対して  x_A = p_A \circ x x_B = p_B \circ x を満たす射  X \xrightarrow{x} P がただ一つ存在することを言います。このとき対象  P A \times B と書き、射  x を(この本では)  \begin{pmatrix} x_A \\ x_B \end{pmatrix} と書きます。 p_A, p_B を射影と呼びます。

 \mathbf{Set} では集合の直積が積、 \mathbf{Qua} では集合の直積で定まるものとなります。

定義 5.3 圏の対象  A, B に対して、対象  S、射  S \xleftarrow{\iota_A} A、射  S \xleftarrow{\iota_B} B の三つ組  \langle S, \iota_A, \iota_B \rangle A, B の余積であるとは、対象  X、射  X \xleftarrow{x_A} A、射  X \xleftarrow{x_B} B の三つ組  \langle X, x_A, x_B \rangle に対して  x_A = x \circ \iota_A x_B = x \circ \iota_B を満たす射  X \xleftarrow{x} P がただ一つ存在することを言います。このとき対象  P A + B と書き、射  x を(この本では)  \begin{pmatrix} x_A & x_B \end{pmatrix} と書きます。 \iota_A, \iota_B を入射と呼びます。

 \mathbf{Set} では集合の「非交和」が余積、 \mathbf{Qua} では  A + B A \times B が同型となります。

③積関手

積を持つ圏  \mathcal{C} において、射  A \xrightarrow{f} A' と射  B \xrightarrow{g} B' に対して  A \times B から  A' \times B' への射で、 p_{A'} \circ (f \times g) = f \circ p_A p_{B'} \circ (f \times g) = g \circ p_B を満たすただ一つの射( f, g の積)  f \times g = \begin{pmatrix} f \circ p_A \\ g \circ p_B \end{pmatrix} が存在します。

積を持つ圏  \mathcal{C} において、任意の対象  A に対して「 A と積をとる関手」 A \times () が、任意の対象  X に対しては対象  A \times X を、任意の射  X \xrightarrow{f} Y に対しては射  A \times X \xrightarrow{1_A \times f} A \times Y を対応させるものとして定義できます。 A \times X は同型を除いて一意に定まるので一つを選ぶことで定義することができます。この関手は  \mathcal{C} から  \mathcal{C} 自身への関手( \mathcal{C} 上の自己関手)となります。

各対象  X に対して  A \times X から  X への射影  p_X を対応させる対応付けは、関手  A \times () から  \mathcal{C} 上の恒等関手への自然変換となります。

線型代数の土壌

この項は後で見ていくことにします。

⑤極限と余極限の例

この項は後で見ていくことにします。できれば図式を使わずに説明したいと思います。

⑥射圏,そして一般射圏
  •  \mathbf{1} を「対象を一つだけ持ち、射としてその対象の恒等射のみを持つ圏」
  •  \mathbf{2} を「対象を二つ持ち、射としてその対象の恒等射の他に一方の対象から他方の対象への射(射を  0 \to 1 とします)を一つだけ持つ圏」

とします。

  • 圏の対象  X に対して、圏  \mathbf{1} からの関手で圏  \mathbf{1} の対象を  X
  • 圏の射  f に対して、圏  \mathbf{2} からの関手で圏  \mathbf{2} の恒等射ではない射を  f

対応させるものが存在します。

「射を対象とする圏」は「圏  \mathbf{2} から  \mathcal{C} への関手を対象とする圏」、すなわち  \mathrm{Fun}(\mathbf{2}, \mathcal{C}) とみなすことができます。圏  \mathbf{2} から  \mathcal{C} への関手  F, G に対して 射  0 \to 1 F によって  X \xrightarrow{f} Y G によって  X' \xrightarrow{f'} Y' に写されるとします。自然変換  F \overset{t}{\Longrightarrow} G \require{AMScd}
\begin{CD}
X @> f >> Y \\
@V t_0 VV @VV t_1 V \\
X' @>> f' > Y'
\end{CD}
が可換となるので  \mathrm{Fun}(\mathbf{2}, \mathcal{C}) の射は「図式を可換にするような射の組  \langle t_0, t_1 \rangle」と考えられます。このような圏を射圏と呼びます。

この射圏の概念を一般化したものがコンマ圏(「圏論の道案内 ~矢印でえがく数学の世界~」では「一般射圏」)となります。

定義 5.7  \mathcal{A} \mathcal{B} \mathcal{C} を圏、 \mathcal{A} \xrightarrow{F} \mathcal{C} \xleftarrow{G} \mathcal{B} を関手とします。 \mathcal{A} の対象  X \mathcal{B} の対象  Y \mathcal{C} の射  F(X) \xrightarrow{f} G(Y) を、三つ組  \langle X, Y, f \rangle で表します。これらを対象として、 \langle X, Y, f \rangle から  \langle X', Y', f' \rangle への射としては、 \mathcal{A} の射  X \xrightarrow{\alpha} X' \mathcal{B} の射  Y \xrightarrow{\beta} Y' の組  \langle \alpha, \beta \rangle
\begin{CD}
F(X) @> f >> G(Y) \\
@V F(\alpha) VV @VV G(\beta) V \\
F(X') @>> f' > G(Y')
\end{CD}
を可換にするものを考えます。この圏をコンマ圏(「圏論の道案内 ~矢印でえがく数学の世界~」では「一般射圏」)と呼び、 (F \downarrow G)(Wikipediaによる。「圏論の道案内 ~矢印でえがく数学の世界~」では「 (F \to G)」)と表します。

⑦極限,余極限の定義

定義 5.8 \mathcal{J} から圏  \mathcal{C} への関手のことを  \mathcal{J} 型の図式と呼びます。

 \mathcal{C} の任意の対象  X に対して、圏  \mathcal{J} の任意の対象を  X に、任意の射を  X の恒等射  1_X に対応させる関手が存在します。この関手を  X への定関手と呼びます。定関手は  \mathrm{Fun}(\mathcal{J}, \mathcal{C}) の対象となります。

対角関手  \Delta とは、 \mathcal{C} から  \mathrm{Fun}(\mathcal{J}, \mathcal{C}) への関手で、 \mathcal{C} の対象  X に対して  X への定関手を対応させるものです。 \mathcal{C} の射  X \xrightarrow{f} Y は定関手  \Delta(X) から定関手  \Delta(Y) への自然変換  \Delta(f) に写されます。 \Delta(f) のすべての成分が  f であるとします。 \mathcal{J} の任意の射  A \xrightarrow{a} B は定関手で恒等射に写されるので
\begin{CD}
X @> 1_X >> X \\
@V \Delta(f)_A VV @VV \Delta(f)_B V \\
Y @>> 1_Y > Y
\end{CD}
が可換である必要があります。これは  \Delta(f) のすべての成分が  f であれば成り立ちます。

(1)  \mathcal{J} 型の図式  D \mathrm{Fun}(\mathcal{J}, \mathcal{C}) の対象だから、圏  \mathbf{1} から  \mathrm{Fun}(\mathcal{J}, \mathcal{C}) への関手と同一視すれば、一般射圏  (\Delta \to D) を考えることができます。

 (\Delta \to D) の終対象を極限と呼びます。双対的に  (D \to \Delta) の始対象を余極限と呼びます。圏  \mathcal{J} が有限個の対象、射から構成されているとき、特に有限極限、有限余極限と呼びます。

(2)「圏論入門 - Haskellで計算する具体例から」の定義では、 \mathcal{J} 型の図式  D に対して、 \mathcal{C} の対象  A (錐の頂点と呼びます)、 \mathcal{J} のすべての対象  j に対して射(射影と呼びます)  p_j: A \to D(j) で、任意の  \mathcal{J} の射  f: j \to k に対して  D(f) \circ p_j = p_k (以下の図式が可換。「錐の条件」)であるものを、 A から  D への錐と呼び、 (A, \{p_j\}) と書きます。
\begin{CD}
A @> p_j >> D(j) \\
@| @VV D(f) V \\
A @>> p_k > D(k)
\end{CD}

 (\mathcal{C}, D) を、圏  \mathcal{C} の任意の対象  A から  D への錐を対象とし、錐  (A, \{p_j\}) から錐  (A', \{q_j\}) への射は  \mathcal{A} の射  u: A \to A' で、任意の  \mathcal{J} の対象  j に対して  q_j \circ u = p_j (以下の図式が可換。「射の条件」)であるものを射とする圏とします。(「圏  \mathcal{C} の射の合成」を射の合成をとして圏  (\mathcal{C}, D) が圏となることが図式からわかります。)
\begin{CD}
A @> p_j >> D(j) \\
@V u VV @| \\
A' @>> q_j > D(j)
\end{CD}

 (\mathcal{C}, D) に終対象があるとき、その終対象、あるいはその終対象の頂点を  \mathcal{J} 型の図式  D の極限と呼びます。

 D を圏  \mathbf{1} (対象を  X とする)から  \mathrm{Fun}(\mathcal{J}, \mathcal{C}) への関手と同一視」したものを  D' とします。(1) の  (\Delta \to D) は、 \mathcal{C} の対象  A \mathbf{1} の(ただ一つの)対象  X \mathrm{Fun}(\mathcal{J}, \mathcal{C}) の射  \Delta(A) \xrightarrow{p} D'(X) = D からなる三つ組  \langle A, X, p \rangle を対象として、 \langle A, X, p \rangle から  \langle A', X, p' \rangle への射としては、 \mathcal{C} の射  A \xrightarrow{u} A' \mathbf{1} の(ただ一つの)射  1_X の組  \langle u, 1_X \rangle
\begin{CD}
\Delta(A) @> p >> D = D'(X)\\
@V \Delta(u) VV @| \\
\Delta(A') @>> p' > D = D'(X)
\end{CD}
を可換とする射(「 (\Delta \to D) の射の条件」)からなる圏となります。

 p, p' は自然変換  \Delta(A) \overset{p}{\Longrightarrow} D \ (: \mathcal{J} \to \mathcal{C}) であるから、 \mathcal{J} の対象  j に対して成分  p_j A = \Delta(A)(j) \xrightarrow{p_j} D(j) \ (\in \mathcal{C}) \mathcal{J} の射  j \xrightarrow{f} k に対して
\begin{CD}
A @> p_j >> D(j) \\
@| @VV D(f) V \\
A @>> p_k > D(k)
\end{CD}
を可換とするものとなります。これは (2) の「錐の条件」と同じものとなります。

 (\Delta \to D) の射の条件」から
\begin{CD}
A @> p_j >> D(j) \\
@V u VV @| \\
A' @>> p'_j > D(j)
\end{CD}
は可換となります。これは (2) の「射の条件」と同じものとなります。

よって (2) の  (\mathcal{C}, D) は圏となり、 (\Delta \to D) に終対象が存在することと  (\mathcal{C}, D) に終対象が存在することは同値となります。 (\Delta \to D) の終対象の  A (\mathcal{C}, D) の終対象の頂点となります。

(3) (Wikipediaでは) 対象  L から  D への錐  (L, \{p_j\}) であって、任意の錐  (N, \{q_j\}) に対して射  u: N \to L が一意的に存在して  \mathcal{J} の任意の対象  j に対して  p_j \circ u = q_j を満たすとき、錐  (L, \{p_j\}) または対象  L \mathcal{J} 型の図式  D の極限と呼びます。

このとき、錐  (L, \{p_j\}) は (2) の定義の圏  (\mathcal{C}, L) の終対象、対象  L はその頂点となります。

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

自然変換については良い書き方が見つからないので、ほぼ「圏論の道案内 ~矢印でえがく数学の世界~」に従って書いていきます。

第4章 自然変換

④自然変換の例2:hom 関手間の自然変換

まず「第3章 関手 ②関手の例1:順序を保つ写像,反変関手・双対圏」から定義を追加しておきます。

双対圏

 \mathcal{C} の対象と射を対象と射をとする圏で、射  f に対して、 \mathcal{C} での  f の域を余域、 \mathcal{C} での  f の余域を域とするものは圏となります。この圏を  \mathcal{C} の双対圏と呼び  \mathcal{C}^\mathrm{op} と書きます。

反変関手

 \mathcal{C}^\mathrm{op} からの関手を  \mathcal{C} からの反変関手と呼びます。通常の関手を共変関手とも呼びます。

共変関手・反変関手の定義

 \mathcal{C} から圏  \mathcal{D} への対応  F が、以下の条件(F1)、(F2)、(F3)、(F4)、(F5)を満たすとき  \mathcal{C} から  \mathcal{D} への関手(共変関手)と呼びます( F: \mathcal{C} \to \mathcal{D} と書きます)。以下の条件(F1)、(F2)、(F3')、(F4')、(F5)を満たすとき  \mathcal{C} から  \mathcal{D} への反変関手と呼びます

  • (F1)  \mathcal{C} の各対象  X \mathcal{D} の対象  F(X) に対応させる。
  • (F2)  \mathcal{C} の射  f \mathcal{D} の射  F(f) に対応させる。
  • (F3)  f: X \to Y \ (\in \mathcal{C}) ならば  F(f): F(X) \to F(Y) \ (\in \mathcal{D}) が成り立つ。
  • (F3')  f: X \to Y \ (\in \mathcal{C}) ならば  F(f): F(Y) \to F(X) \ (\in \mathcal{D}) が成り立つ。
  • (F4)  f: X \to Y \ (\in \mathcal{C}) g: Y \to Z \ (\in \mathcal{C}) ならば  F(g \circ f) = F(g) \circ F(f) が成り立つ。
  • (F4')  f: X \to Y \ (\in \mathcal{C}) g: Y \to Z \ (\in \mathcal{C}) ならば  F(g \circ f) = F(f) \circ F(g) が成り立つ。
  • (F5)  \mathcal{C} の各対象  X に対して  F(1_X) = 1_{F(X)} が成り立つ。

続いて「第3章 関手 ③関手の例2:hom 関手」あたりの引用から始めます。

 \mathcal{C} の対象  X から  Y への射の集まりを  \mathrm{Hom}_\mathcal{C}(X, Y) と書くことにします。すべての対象  X Y に対して  \mathrm{Hom}_\mathcal{C}(X, Y) が集合であるような圏を局所的に小さな圏と呼びます。

共変 hom 関手

局所的に小さな圏  \mathcal{C} において対象  A を固定すると、 \mathcal{C} の対象  X をとるごとに射の集合  \mathrm{Hom}_\mathcal{C}(A, X) が定まります。射  f: X \to Y について、 \alpha \in \mathrm{Hom}_\mathcal{C}(A, X) との合成  f \circ \alpha を考えると、これは  A から  Y への射だから「 f と合成する」ことは集合  \mathrm{Hom}_\mathcal{C}(A, X) から \mathrm{Hom}_\mathcal{C}(A, Y) への写像となります。

 \mathcal{C} から  \mathbf{Set} への関手(共変関手)  h_A を、

  • 対象  X に対しては  h_A(X) = \mathrm{Hom}_\mathcal{C}(A, X) を対応させ、
  •  f: X \to Y に対しては  a \in \mathrm{Hom}_\mathcal{C}(A, X) について  h_A(f)(a) = f \circ a であるような集合間の写像  h_A(f): \mathrm{Hom}_\mathcal{C}(A, X) \to \mathrm{Hom}_\mathcal{C}(A, Y) を対応させるもの

と定義することができます。

[証明]【(F3)  f: X \to Y \ (\in \mathcal{C}) のとき、 h_A(f): h_A(X) \to h_A(Y) \ (\in \mathbf{Set}) となります。

(F4)  f: X \to Y \ (\in \mathcal{C}) g: Y \to Z \ (\in \mathcal{C}) a \in h_A(X) とすると、
 h_A(g \circ f)(a) = (g \circ f) \circ a
 (h_A(g) \circ h_A(f))(a) = h_A(g) ( h_A(f)(a) ) = h_A(g) (f \circ a) = g \circ (f \circ a)
であることから  \mathbf{Set} の結合律(写像の合成の結合律)  (f \circ g) \circ a = f \circ (g \circ a) より  h_A(g \circ f) = h_A(g) \circ h_A(f) となります。

(F5)  \mathcal{C} の対象  X \xi \in h_A(X) に対して、 h_A(1_X)(\xi) = 1_X \circ \xi = \xi となるので  h_A(1_X) h_A(X) の恒等写像となります。

よって  h_A \mathcal{C} から  \mathbf{Set} への関手(共変関手) となります。】

反変 hom 関手

 \mathcal{C} の対象  B を固定して、 \mathcal{C} から  \mathbf{Set} への 反変関手  ^Bh を、

  • 対象  X に対しては  ^Bh(X) = \mathrm{Hom}_\mathcal{C}(X, B) を対応させ、
  •  f: X \to Y に対しては  \beta \in \mathrm{Hom}_\mathcal{C}(Y, B) について  ^Bh(f)(\beta) = \beta \circ f であるような集合間の写像  ^Bh(f): \mathrm{Hom}_\mathcal{C}(Y, B) \to \mathrm{Hom}_\mathcal{C}(X, B) を対応させるもの

と定義することができます。

[証明]【(F3')  f: X \to Y \ (\in \mathcal{C}) のとき、 ^Bh(f): {}^Bh(Y) \to {}^Bh(X)\ ( \in \mathbf{Set}) となります。

(F4')  f: X \to Y \ (\in \mathcal{C}) g: Y \to Z \ (\in \mathcal{C}) a \in {}^Bh(Z) とすると、
 ^Bh(g \circ f)(a) = a \circ (g \circ f)
 (^Bh(f) \circ {}^Bh(g))(a) = {}^Bh(f) ( ^Bh(g)(a) ) = {}^Bh(f) (a \circ g) = (a \circ g) \circ f
であることから  \mathbf{Set} の結合律(写像の合成の結合律)  a \circ (g \circ f) = (a \circ g) \circ f より  ^Bh(g \circ f) = {}^Bh(f) \circ {}^Bh(g) となります。

(F5)  \mathcal{C} の対象  X \xi \in {}^Bh(X) に対して、 ^Bh(1_X)(\xi) = \xi \circ 1_X = \xi となるので  ^Bh(1_X) ^Bh(X) の恒等写像となります。

よって  ^Bh \mathcal{C} から  \mathbf{Set} への反変関手となります。】

hom 関手間の自然変換

 \mathcal{C} における  A' から  A への射  a に対し、 \mathcal{C} から  \mathbf{Set} への関手  h_A から  h_{A'} への自然変換  h_a を、

  •  \mathcal{C} の各対象  X
    •  h_A(X) = \mathrm{Hom}_\mathcal{C}(A, X) の任意の要素  g を、 h_{A'}(X) = \mathrm{Hom}_\mathcal{C}(A', X) の要素  g \circ a に写す  \mathbf{Set}の射  (h_a)_X」を対応させるもの

として定義することができます。

この図式はうまく引用できませんができるだけやってみると以下のようになります。 \require{AMScd}
\begin{CD}
\mathbf{Set} @. @. @. @. @. \mathcal{C} \\
\\
h_{A'}(Y) @< h_{A'}(f) << h_{A'}(X) @. @. \overset{h_{A'}}{\Longleftarrow} @. @. Y @<< f < X \\
@A (h_a)_Y AA @AA (h_a)_X A @. @AA h_{a} A \\
h_{A}(Y) @<< h_{A}(f) < h_{A}(X) @. @. \underset{h_{A}}{\Longleftarrow}
\end{CD}

 h_{A}(X) \ni g \stackrel{ (h_a)_X }{\mapsto} g \circ a \stackrel{ h_{A'}(f) }{\mapsto} f \circ (g \circ a) \in h_{A'}(Y)
 h_{A}(X) \ni g \stackrel{ h_{A}(f) }{\mapsto} f \circ g \stackrel{ (h_a)_Y }{\mapsto} (f \circ g) \circ a \in h_{A'}(Y)

結合律  (f \circ g) \circ a = f \circ (g \circ a) より上記の図式は可換となります。

関手圏の関手

上記の

  •  \mathcal{C} の対象  A \mathcal{C} から  \mathbf{Set} への関手  h_A
  •  \mathcal{C} A' から  A への射  a \mathcal{C} から  \mathbf{Set} への関手  h_A から  h_{A'} への自然変換  h_a (ここで  h_a \mathcal{C} の各対象  X に以下の  \mathbf{Set}の射  (h_a)_X を対応させる自然変換)
    • (*) ( \mathbf{Set}の射  (h_a)_X は、 h_A(X) = \mathrm{Hom}_\mathcal{C}(A, X) の任意の要素  g を、 h_{A'}(X) = \mathrm{Hom}_\mathcal{C}(A', X) の要素  g \circ a に対応させる)

を対応させるものを  F とすると、以下の条件(F1)、(F2)、(F3')、(F4')、(F5)を満たすので、 F \mathcal{C} から  \mathrm{Fun}(\mathcal{C}, \mathbf{Set}) への反変関手となります。

  • (F1)  \mathcal{C} の各対象  A \mathrm{Fun}(\mathcal{C}, \mathbf{Set}) の対象  F(A) = h_A に対応させる。
  • (F2)  \mathcal{C} の射  a \mathrm{Fun}(\mathcal{C}, \mathbf{Set}) の射  F(a) = h_a に対応させる。
  • (F3')  A' \xrightarrow{a} A \ (\in \mathcal{C}) ならば  h_A \xrightarrow{h_a} h_{A'} \ (\in \mathrm{Fun}(\mathcal{C}, \mathbf{Set})) が成り立つ。
  • (F4')  A'' \xrightarrow{b} A' \ (\in \mathcal{C}) A' \xrightarrow{a} A \ (\in \mathcal{C}) ならば  h_{a \circ b} = h_b \circ h_a が成り立つ。
  • (F5)  \mathcal{C} の各対象  A に対して  h_{1_A} = 1_{h_A} が成り立つ。

[証明]【(F3)
\begin{eqnarray*}
& & F(Y) \xrightarrow{F(f)} F(X) \ (\in \mathrm{Fun}(\mathcal{C}, \mathbf{Set})) \\
& \iff & F(Y) \overset{F(f)}{\Longrightarrow} F(X) \ (: \mathcal{C} \to \mathbf{Set}) \\
& \iff & F(Y)(A) \xrightarrow{F(f)_A} F(X)(A) \ (\in \mathbf{Set}) (\forall A \in \mathrm{ob}(\mathcal{C}))
\end{eqnarray*} より
\begin{eqnarray*}
& & A' \xrightarrow{a} A \ (\in \mathcal{C}) \implies h_A \xrightarrow{h_a} h_{A'} \ (\in \mathrm{Fun}(\mathcal{C}, \mathbf{Set})) \\
& \iff & A' \xrightarrow{a} A \ (\in \mathcal{C}) \implies h_A(X) \xrightarrow{(h_a)_X} h_{A'}(X) \ (\in \mathbf{Set}) (\forall X \in \mathrm{ob}(\mathcal{C}))
\end{eqnarray*} となるので(*)より成り立ちます。

(F4')  (h_a)_X は反変 hom 関手  {}^Xh を使って書くと  (h_a)_X = {}^Xh(a') と書けるので( a' \mathcal{C} の双対圏での  a に対応する射)
\begin{CD}
h_A(X) = \mathrm{Hom}(A, X) @> h_A(f) >> h_A(Y) = \mathrm{Hom}(A, Y) \\
@V (h_a)_X = {}^Xh(a') VV @VV (h_a)_Y = {}^Yh(a') V \\
h_{A'}(X) = \mathrm{Hom}(A', X) @>> h_{A'}(f) > h_{A'}(Y) = \mathrm{Hom}(A', Y)
\end{CD} となります。反変 hom 関手の議論から  \mathcal{C} の射  a: A' \to A に対して  (h_a)_X 対応させる対応は反変関手となり  (h_{a \circ b})_X = (h_{b})_X \circ (h_{a})_X が成り立ちます。よって自然変換の合成の定義より  h_{a \circ b} = h_{b} \circ h_{a} が成り立ちます。

(F5)  h_{1_A} は、 h_A から  h_{A} への自然変換  h_a \mathcal{C} の各対象  X に以下の  \mathbf{Set}の射  (h_a)_X を対応させる自然変換となります。

  •  \mathbf{Set}の射  (h_a)_X は、 h_A(X) の任意の要素  g g に対応させる写像

 1_{h_A} \mathcal{C} の各対象  X に対して  (1_{h_A})_X = 1_{h_A(X)} なので  h_{1_A} = 1_{h_A} (各成分が一致)が成り立ちます。】

よって

  •  \mathcal{C} の対象  A \mathrm{Fun}(\mathcal{C}, \mathbf{Set}) の対象  h_A を、
  •  A' から  A への射  a h_A から  h_{A'} への射  h_a

対応させる対応付け  h_{()} は、 \mathcal{C} から  \mathrm{Fun}(\mathcal{C}, \mathbf{Set}) への反変関手、つまり  \mathcal{C}^\mathrm{op} から  \mathrm{Fun}(\mathcal{C}, \mathbf{Set}) への関手となります。

 \mathcal{C} \mathcal{C}^\mathrm{op} を入れ替えると、 \mathcal{C} から  \mathrm{Fun}(\mathcal{C}^\mathrm{op}, \mathbf{Set}) への関手  ^{()}h を定義することができます。

⑤自然変換の例3:米田の補題

 F を圏  \mathcal{C} から  \mathbf{Set} への関手とします。このとき  \mathcal{C} の任意の対象  A に対して、「 h_A から  F へのすべての自然変換」と「 F(A) の要素」とは一対一に対応します。すなわち

  • (1)  h_A から  F への自然変換  t が与えられると、 a := t_A(1_A) F(A) の要素  a が定められ(この対応を  t \stackrel{ \mu}{\mapsto} a とします)
  • (2)  F(A) の要素  a が与えられると、 t_X(f) := F(f)(a)  (t_X: h_A(X) \to F(X))によって自然変換  t が定められ(この対応を  a \stackrel{ \nu_X}{\mapsto} t_X とします)
  • (3)  \mathcal{C} の任意の対象  X に対して、 t \stackrel{ \mu}{\mapsto} a \stackrel{ \nu_X}{\mapsto} t'_X ならば  t_X = t'_X
  • (4)  a \stackrel{ \nu_A}{\mapsto} t_A \stackrel{ \mu}{\mapsto} a' ならば  a = a' が成り立ちます。

[証明]【(2)  \mathcal{C} の任意の射  f: X \to Y と射  g: A \to X に対して
 (t_Y \circ h_A(f))(g) = t_Y(h_A(f)(g)) = t_Y(f \circ g) = F(f \circ g)(a) = (F(f) \circ F(g))(a)
 (F(f) \circ t_X)(g) = F(f)(t_X(g)) = F(f)(F(g)(a)) = (F(f) \circ F(g))(a)
となり、 \mathcal{C} の任意の射  f: X \to Y に対して  t_Y \circ h_A(f) = F(f) \circ t_X となります。よって  t h_A から  F への自然変換となります。

(3)  t h_A から  F への自然変換とすると  \mathcal{C} の任意の射  f: X \to Y に対して  t_Y \circ h_A(f) = F(f) \circ t_X が成り立ちます。よって  \mathcal{C} の任意の射  f: X \to Y g: A \to X に対して  (t_Y \circ h_A(f))(g) = (F(f) \circ t_X)(g) となります。
 t_Y(f \circ g) = t_Y(h_A(f)(g)) = (t_Y \circ h_A(f))(g) = (F(f) \circ t_X)(g) = F(f)(t_X(g))
から  t_Y(f \circ g) =  F(f)(t_X(g)) となります。

ここで  X = A とすると  \mathcal{C} の任意の射  f: A \to Y g: A \to A に対して  t_Y(f \circ g) =  F(f)(t_A(g)) が成り立ちます。

ここで  g = 1_A とすると  \mathcal{C} の任意の射  f: A \to X に対して  t_X(f) =  F(f)(t_A(1_A)) が成り立ちます。

よって  \mathcal{C} の任意の対象  X に対して、 t \stackrel{ \mu}{\mapsto} a \stackrel{ \nu_X}{\mapsto} t'_X ならば  t'_X(f) = F(f)(a) = F(f)(t_A(1_A)) = t_X(f) となり  t_X = t'_X が成り立ちます。

(4)  a \stackrel{ \nu_A}{\mapsto} t_A \stackrel{ \mu}{\mapsto} a' ならば  a' = t_A(1_A) = F(1_A)(a) = 1_{F(A)}(a) = a となり  a = a' が成り立ちます。】

よって  \mathrm{Hom}_{\mathrm{Fun}(\mathcal{C}, \mathbf{Set})}(h_A, h_B) \mathrm{Hom}_{\mathcal{C}^\mathrm{op}}(A, B) の間に一対一対応があることがわかります。

 \mathcal{C} \mathcal{C}^\mathrm{op} を入れ替えると、  \mathrm{Hom}_{\mathrm{Fun}(\mathcal{C}^\mathrm{op}, \mathbf{Set})}(^Ah, ^Bh) \mathrm{Hom}_{\mathcal{C}}(A, B) の間に一対一対応があることがわかります。

 \mathcal{C} \mathcal{D} を局所的に小さな圏とし、 F \mathcal{C} から  \mathcal{D} への関手とします。 F \mathcal{C} の対象  X, Y について定まる  \mathrm{Hom}_{\mathcal{C}}(X, Y) から  \mathrm{Hom}_{\mathcal{C}}(F(X), F(Y)) への写像単射であるとき忠実(full)、全射であるとき充満(faithful)、全単射であるとき充満忠実(fully faithful)であると言います。

 \mathcal{C} から  \mathrm{Fun}(\mathcal{C}^\mathrm{op}, \mathbf{Set}) への関手  ^{()}h は、「埋め込み」(あるいは「充満忠実」)となります。 ^{()}h を「米田埋め込み」と呼びます。

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

このブログでは、通常の論理プログラミングでは無限に動くプログラムを書くことができないので「極限」の考え方でなんとかできないか、ということでやっています。ある種の射影的極限、帰納的極限は外積の定義を書いたところで書いたように、構成的に定義することができるようなので、このやり方で書いてみるとプログラミング言語で書くことができるのではないかと考えています。

この本では、極限の説明の前に「コンマ圏」があるので、「コンマ圏」についても「構成的な書き方」ができるか考えてみたいと思います。この本では、さらにその前に自然変換の説明があり、自然変換をメインに説明されているようです。自然変換については、そのように書き方を変えることができるかどうかわかりませんが、できるならやってみます。その前に、自然変換の定義が間違っていたようなので、圏の定義から書き直しておきます。

圏の定義

 \mathcal{C} というものは、以下の(集合とは限らない)類

  • 対象の類  \mathrm{ob}(\mathcal{C})
  • 対象の間の射の類  \mathrm{hom}(\mathcal{C})

で構成されて以下の条件が成り立つとき、 \mathcal{C} を圏と呼びます。

  •  f \in \mathrm{hom}(\mathcal{C}) には域と呼ばれる対象  A \in \mathrm{ob}(\mathcal{C}) および余域と呼ばれる対象  B \in \mathrm{ob}(\mathcal{C}) がただ一つ存在します。このとき「 f A から  B への射である」と言い、 f: A \to B (または  f: A \to B \ (\in \mathcal{C}))と書き、 A \mathrm{dom}(f) B \mathrm{cod}(f) と書きます。
  •  f: A \to B g: B \to C であるとき、射の合成と呼ばれる  g \circ f: A \to C が一意的に存在し、以下の結合律、単位律が成り立ちます。
    • 結合律:  f: A \to B g: B \to C h: C \to D ならば  h \circ (g \circ f) = (h \circ g) \circ f が成り立ちます。
    • 単位律: 任意の  A ∈ \mathrm{ob}(\mathcal{C}) に対して  A の恒等射と呼ばれる射  1_A: A \to A が存在して、任意の射  f: A \to X および  g: X \to A に対して  1_A \circ f = f g \circ 1_A = g が成り立ちます。

関手の定義

 \mathcal{C} から圏  \mathcal{D} への対応  F が、以下の条件を満たすとき  \mathcal{C} から  \mathcal{D} への関手と呼びます( F: \mathcal{C} \to \mathcal{D} と書きます)。

  •  \mathcal{C} の各対象  X \mathcal{D} の各対象  F(X) に対応させる。
  •  \mathcal{C} の射  f \mathcal{D} の射  F(f) に対応させる。
  •  f: X \to Y \ (\in \mathcal{C}) ならば  F(f): F(X) \to F(Y) \ (\in \mathcal{D})
  •  f: X \to Y \ (\in \mathcal{C}) g: Y \to Z \ (\in \mathcal{C}) ならば  F(g \circ f) = F(g) \circ F(f)
  •  \mathcal{C} の各対象  X に対して  F(1_X) = 1_{F(X)} が成り立つ。

自然変換の定義

 \require{AMScd}  F G を圏  \mathcal{C} から  \mathcal{D} への関手とします。以下の条件が成り立つものを  F から  G への 自然変換  t と呼び、 F \overset{t}{\Longrightarrow} G (または  F \overset{t}{\Longrightarrow} G \ (: \mathcal{C} \to \mathcal{D}))と書きます。

  •  \mathcal{C} の各対象  X \mathcal{D} の射  t_X: F(X) → G(X) を対応させる。 t_X t X 成分と呼ぶ。
  •  f: X → Y \ (\in \mathcal{C}) に対して  G(f) \circ t_{X} = t_{Y} \circ F(f) が成り立つ。(以下の図式は可換)

\begin{CD}
F(X) @> t_{X} >> G(X) \\
@V F(f) VV @VV G(f) V \\
F(Y) @>> t_{Y} > G(Y)
\end{CD}

関手圏

 F G H を圏  \mathcal{C} から圏  \mathcal{D} への関手、 F \overset{t}{\Longrightarrow} G G \overset{u}{\Longrightarrow} H を自然変換とするとき、これらの合成(垂直合成)を  (ut)_X := u_X \circ t_X ( X \mathcal{C} の対象)と定義すると、自然変換  F \overset{ut}{\Longrightarrow} H となります。すなわち

  •  ut \mathcal{C} の対象  X (ut)_X: F(X) \to H(X) を対応させ
  •  f: X → Y \ (\in \mathcal{C}) ならば  H(f) \circ (ut)_{X} = H(f) \circ u_{X} \circ t_{X} = u_{Y} \circ G(f) \circ t_{X} \\ = u_{Y} \circ t_{Y} \circ F(f) = (ut)_{Y} \circ F(f)

が成り立ちます。(以下の図式は可換)
\begin{CD}
F(X) @> t_{X} >> G(X) @> u_{X} >> H(X) \\
@V F(f) VV @VV G(f) V @VV H(f) V \\
F(Y) @>> t_{Y} > G(Y) @>> u_{Y} > H(Y)
\end{CD}
この合成(垂直合成)は結合律、単位律を満たします。

  • (結合律)  F G H I を圏  \mathcal{C} から圏  \mathcal{D} への関手、 F \overset{t}{\Longrightarrow} G G \overset{u}{\Longrightarrow} H H \overset{v}{\Longrightarrow} I を自然変換とすると、 \mathcal{D} の射の結合律より  X \mathcal{C} の対象のとき  ( (vu)t)_X = (vu)_X \circ t_X = (v_X \circ u_X) \circ t_X \\ = v_X \circ (u_X \circ t_X) = v_X \circ (ut)_X = (v(ut))_X
  • (単位律)  F G H を圏  \mathcal{C} から圏  \mathcal{D} への関手、 F \overset{t}{\Longrightarrow} G G \overset{v}{\Longrightarrow} H を自然変換とします。 \mathcal{C} の対象  X に対して  u_X = 1_{G(X)} とすると以下の(1)より  u は自然変換  G \overset{u}{\Longrightarrow} G となり、(2-1)、(2-2)より  u はこの合成(垂直合成)の単位元となります。
    • (1)  f: X → Y \ (\in \mathcal{C}) ならば  G(f) \circ t_{X} = t_{X} \circ G(f)
    • (2-1) 任意の  \mathcal{C} の対象  X に対して  (ut)_X = u_X \circ t_X = 1_{G(X)} \circ t_X = t_X となることから  ut = t (任意の成分が一致)
    • (2-2) 任意の  \mathcal{C} の対象  X に対して  (vu)_X = v_X \circ u_X = v_X \circ 1_{G(X)} = v_X となることから  vu = v (任意の成分が一致)

 \mathcal{C} から圏  \mathcal{D} への関手を対象とし、それらの間の自然変換を射とする圏を、圏  \mathcal{C} から圏  \mathcal{D} への関手圏と呼び、 \mathrm{Fun}(\mathcal{C}, \mathcal{D}) と書きます。

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

「第4章 自然変換」を見ていきます。コンマ圏のところまでは、どうやれば良いのかわからないのでそのままの書き方で書いていくことにします。

第4章 自然変換

①自然変換の定義1

 F G を圏  \mathcal{C} から  \mathcal{D} への関手とします。
このとき、 F から  G への 自然変換  t

  •  \mathcal{C} の各対象  X \mathcal{D} の射  t_X: F(X) → G(X) を対応させる。
  •  \mathcal{C} の任意の射  f: X → Y に対して  G(f) \circ t_{X} = t_{Y} \circ F(f) が成り立つ。

というものを言います。このとき  F \overset{t}{\Longrightarrow} G と書きます。 t_X t X 成分と呼びます。

図式は同じようには描けないのですが描いておきます。
 \require{AMScd}
\begin{CD}
@. Y @< f << X \\
@. @. @. \\
G @. G(Y) @< G(f) << G(X) \\
@A t AA @A t_Y AA @AA t_X A \\
F @. F(Y) @<< F(f) < F(X) 
\end{CD}

 t': F \to G および  t: G \to H を関手  F,G,H: \mathcal{C} \to \mathcal{D} の間の自然変換とするとき、これらの合成を  (tt')_X := t_X \circ t'_X と定義すると、自然変換  tt': F \to H となります。この合成は結合律、単位律を満たします。

 \mathcal{C} から圏  \mathcal{D} への関手を対象とし、それらの間の自然変換を射とする圏を、圏  \mathcal{C} から圏  \mathcal{D} への関手圏と呼び、 \mathrm{Fun}(\mathcal{C}, \mathcal{D}) と書きます。

関手圏の射として同型射であるような自然変換を自然同値と呼びます。また、関手圏の対象として同型であるような関手を自然同値であると言います。

例:有向グラフは、圏 DiGraph
 E \overset{o}{\underset{d}{\rightrightarrows}} V
から  \mathbf{Set} への関手とみなすことができます。(第3章①)

関手としての有向グラフ  F, G について、「 F から  G への自然変換」はグラフの構造を保つようなものとなります。

関手圏は、「有向グラフを対象とし、その構造を保つ対応付けを射とする圏」となります。

「米田の補題」によって「局所的に小さいあらゆる圏は関手圏に埋め込める」ということらしいので、「米田の補題」のところ(④⑤)まで見た後でまた考えることにします。

②自然変換の定義2

 \mathcal{C} から圏  \mathcal{D} への関手  F \mathcal{D} から  \mathcal{C} への関手  G で、関手圏の対象として  G \circ F = 1_\mathcal{C} F \circ G = 1_\mathcal{D} なるものが存在するとき  \mathcal{C} \mathcal{D} は圏同値であると言います。

③自然変換の例1:前順序集合に関する例

前順序集合は、二つの対象の間に射が存在しないか、ただ一つしかないという圏となります。(第2章⑥)

 \mathcal{C} \mathcal{D} を前順序集合とし、 F, G \mathcal{C} から  \mathcal{D} への関手(順序を保つ写像)とします。このとき、 F から  G への自然変換とは、「任意の  X に対して  F(X) \le G(X)」として定義される順序関係となります。このとき、図式の可換性は自明となります。

このとき関手圏  \mathbf{Fun}(\mathcal{C}, \mathcal{D}) は、 \mathcal{C} から  \mathcal{D} への「順序を保つ写像全体」に「自然な順序付け」をしたものとなります。

任意の集合は、恒等射しか存在しない圏(離散圏)と考えられます。つまり、任意の集合は前順序集合と考えられます。

このとき、「自明な前順序集合」としての任意の集合  \mathcal{C} から、ある前順序集合  \mathcal{D} への任意の写像は順序を保つ写像となります。

関手圏  \mathbf{Fun}(\mathcal{C}, \mathcal{D}) は、「集合  \mathcal{C} から、ある前順序集合  \mathcal{D} への写像全体」に「自然な順序付け」をしたものとなります。

以上、ほぼ定義を引用しただけです。

「エレファントな整数論」で写像から作られる前順序集合について調べているのですが、今のところ圏論的な議論として書けるような内容がないので何かできたらまた書きたいと思います。

トポスについて書かれていたのでこれも引用しておきます。

関手圏  \mathbf{Fun}(\mathcal{C}, \mathbf{Set}) は普通の集合の圏  \mathbf{Set} にとてもよく似た性質を持つ圏、いわゆる「トポス」となる。

トポスについては詳しくないので想像で書きますが、論理式の中には論理プログラミングとして書けるものと書けないものがあって、論理プログラミングとして書けるプログラムの「型」を表すものとして使えるのではないか、と考えています。

サーバー側のプロクラムとクライアント側のプログラムで全体で1つのプログラムの中で、クライアント側のプログラムを変更する事は全体としてはどういう意味になっているのかということを考えると、クライアント側の「型」とサーバー側の「型」を合成したものと考えることができます。

様々なクライアント側のプログラムを作るためのプログラミング言語がありますが、そのプログラムを論理プログラミングのプログラムとして表したときの「型」を表すような機能があれば、そのクライアント側のプログラムを更新するだけで全体を更新することができると考えられます。

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

圏論の道案内」では自然変換を中心に説明されているということなので、「第4章 自然変換」のあたりから読んでいこうと考えています。

その前の「第3章 関手」ではいろいろな例が書かれていますが、これは自然変換に関連したものと思われます。

その前に「前順序」の説明があるのですが、これは自然変換と関係があるのかどうかよくわかりませんでした。

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

第4章を見ていく前に、第2章、第3章について簡単に見ていきます。

第2章 圏

 \mathcal{C} は以下のものからなります(一部Wikipediaによる)。

  • 対象の類  \mathrm{ob}(\mathcal{C})
  • 対象の間の射の類  \mathrm{hom}(\mathcal{C})

以下の条件が成り立つとき  \mathcal{C} を圏と呼びます。

 f \in \mathrm{hom}(\mathcal{C}) には域と呼ばれる対象  A \in \mathrm{ob}(\mathcal{C}) および余域と呼ばれる対象  B \in \mathrm{ob}(\mathcal{C}) がただ一つ存在します。このとき「 f A から  B への射である」と言い、 f: A \to B と書き、 A \mathrm{dom}(f) B \mathrm{cod}(f) と書きます。

 f, g に対し、 \mathrm{cod}(f) = \mathrm{dom}(g) であるとき、射の合成と呼ばれる  \mathrm{dom}(f) から  \mathrm{cod}(g) への射  g \circ f が一意的に存在します。以下の結合律、単位律が成り立ちます。

結合律: 射  f, g, h \mathrm{cod}(f) = \mathrm{dom}(g) かつ  \mathrm{cod}(g) = \mathrm{dom}(h) であるならば  h \circ (g \circ f) = (h \circ g) \circ f が成り立ちます。

単位律: 各対象  A ∈ \mathrm{ob}(\mathcal{C}) に対して  A の恒等射と呼ばれる射  1_A: A \to A が存在して、任意の射  f: A \to X および  g: X \to A に対して  1_A \circ f = f g \circ 1_A = g が成り立ちます。

第3章 関手

①関手の定義

 \mathcal{C} から圏  \mathcal{D} への関手  F とは以下の条件を満たすものを言います。

  •  \mathcal{C} の各対象  X \mathcal{D} の各対象  F(X) に対応させる。
  •  \mathcal{C} の射  f: X \to Y \mathcal{D} の射  F(f): F(X) \to F(Y) に対応させる。
  •  \mathcal{C} の任意の射  f: X \to Y g: Y \to Z に対して  F(g \circ f) = F(g) \circ F(f) が成り立つ。
  •  \mathcal{C} の各対象  X ∈ \mathcal{C} に対して  F(1_X) = 1_{F(X)} が成り立つ。
④関手の例3:モノイド準同型(1)

ここでは可換モノイドを「量系」という用語で表しています。量系(可換モノイド)を対象とし、その間の準同型を射とする圏を「量系の圏  \mathbf{Qua}」(「可換モノイドの圏  \mathbf{CMon}」)と呼びます。

⑤関手の例4:モノイド準同型(2)

ここでは半環を「数系」という用語で表しています。「数系  A 上の量系」という用語も使われています。これは一般的な用語がないようで、このブログでは独自に半環上のフラクタル加群と呼んでいます。これが自然変換として扱われているのかどうかまだよくわかりません。

⑥関手の例5:モノイド準同型(3)

ここは以下のような内容が書かれています。引用しておきます。

 A を数系とする。 A 上の量系を対象とし「 \mathbf{Qua} の射であって数による乗法と可換なもの」を射とする圏を  A\mathbf{-Qua} と書く。

数系  A 上の量系  M A\mathbf{-Qua} における同型として  M \cong A であるとき、これをスカラー量系と呼び、その射をスカラー量と呼ぶ。

⑦関手の例6:線型表現(1)

ここは以下のような内容が書かれています。引用しておきます。

数系  A が、乗法についても可換なモノイドとなるとき可換数系と呼ぶ。

 A可換環であるとき、 A 上の量系は加群となり、 A 上の加群と呼ばれる。 A 上の加群を対象とし、 A\mathbf{-Qua} の射を射とする圏を  A\mathbf{-Mod} と書く。

線型空間の間の  K\mathbf{-Mod} の射をを特に線型写像と呼び、体  K 上の線型空間を対象とし、線型写像を射とする圏を  K\mathbf{-Vect} と書く。

 G から  K\mathbf{-Vect} への関手は  G K 上の線型表現と呼ばれる。

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

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

圏論の道案内」という本では可換モノイド、半環が取り上げられているので、この本を読みながら検討していきます。出版社のサイトにある目次を引用しておきます。
gihyo.jp

第1章 道案内の前に

第2章 圏

  • ①圏の定義1:対象と射,域と余域
  • ②圏の定義2:合成
  • ③圏の定義3:結合律
  • ④圏の定義4:恒等射
  • ⑤圏の定義:完全版
  • ⑥圏の例1:前順序,半順序,全順序
  • ⑦圏の例2:モノイドと群
  • ⑧圏の例3:集合圏
  • ⑨圏の例4:モノイドの圏

第3章 関手

  • ①関手の定義
  • ②関手の例1:順序を保つ写像,反変関手・双対圏
  • ③関手の例2:hom 関手
  • ④関手の例3:モノイド準同型(1)
  • ⑤関手の例4:モノイド準同型(2)
  • ⑥関手の例5:モノイド準同型(3)
  • ⑦関手の例6:線型表現(1)
  • ⑧関手の例7:線型表現(2)
  • 発展 ⑨関手の例8:ホモロジー,ブラウワーの不動点定理

第4章 自然変換

  • ①自然変換の定義1
  • ②自然変換の定義2
  • ③自然変換の例1:前順序集合に関する例
  • ④自然変換の例2:hom 関手間の自然変換
  • ⑤自然変換の例3:米田の補題
  • ⑥自然変換の例4:単位系の変換
  • 発展 ⑦自然変換の例5:絡作用素,ユニタリ同値,フーリエ変換
  • 第3章・第4章のまとめ

第5章 普遍性

  • ①終対象と始対象
  • ②積と余積
  • ③積関手
  • 線型代数の土壌
  • ⑤極限と余極限の例
  • ⑥射圏,そして一般射圏
  • ⑦極限,余極限の定義

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

  • ①冪
  • ②CCC

第7章 圏論集合論

第8章 随伴

  • ①積と冪との間の関係
  • ②随伴

第9章 モナド

エレファントな整数論(23)

写像の分類の説明

 M を集合、 s: M \to M写像とします。 \bar{s}: \mathfrak{P}(M) \to \mathfrak{P}(M) \mathcal{R}_x s^*: M \to \mathfrak{P}(M) を前回と同じものとします。 x_0 \in M をとり  N = s^*(x_0) とおきます。前回の説明を続けていきます。

 x \in N に対して

  •  N_{\le x} = \{ y \in N \mid y \le x \}
  •  N_{\cong x} = \{ y \in N \mid y \le x \ かつ \ x \le y \}

とおきます。

以下の条件を考えます。条件  (N_6) から  (N_8) を追加します。

  •  (N_1) 任意の  x \in N に対して  s(x) \ne x
  •  (N_2) 任意の  x \in N に対して  s(x) \ne x_0
  •  (N_3)  N 上で  s単射
  •  (N_4)  N 上で  \le は全順序
  •  (N_5)  N は無限集合
  •  (N_6)  X \subseteq N かつ  X \ne \varnothing ならば   X は極小元を持つ
  •  (N_7) 任意の  x \in N に対して  N_{\cong x} = \{x\}
  •  (N_8) 任意の  x \in N に対して  s(x) \not\le x

これらの条件により以下の表のようにタイプ  T_1 から  T_5 に分類することができます。

タイプ  N_1  N_2  N_3  N_4  N_5  N_6  N_7  N_8 図式
 T_1 = N_1 \land N_2 \land N_3  0 \to 1 \to \cdots
 T_2 = N_1 \land N_2 \land \neg N_3 × × × × × ×  0 \to 1 \to \cdots \to n \to \cdots \to n
 T_3 = N_1 \land \neg N_2 × × × × × ×  0 \to 1 \to \cdots \to 0
 T_4 = \neg N_1 \land N_2 × × × ×  0 \to 1 \to \cdots \to n \to n
 T_5 = \neg N_1 \land \neg N_2 × × × ×  0 \to 0

この表が成り立つことを以下で示します。

(P1)  x, y \in M x < y ならば  s(x) \le y

[証明] (O5)より  s^*(x) = \{x\} \cup s^*(s(x)) となりますが、 x \ne y なので  y \in s^*(s(x)) となり、 s(x) \le y となります。[証明終わり]

(P2)  x, y \in M x \le y ならば  s(x) \le s(y)

[証明]  x = y ならば  s(x) = s(y) \le s(y) x < y ならば(P1)より  s(x) \le y となり  s(x) \le y \le s(y) となります。[証明終わり]

(P3)  x, y \in M x < y かつ  s(x) = s(y) ならば  s^2(x) \le s(x)

[証明] (P1)より  s(x) \le y となり (P2)より  s^2(x) \le s(y) = s(x) となります。[証明終わり]

(P4)  x, y \in M x < y ならば  y = s(z) となる  z \ge x が存在する

[証明] (O5)より  s^*(x) = \{x\} \cup s^*(s(x)) となり、 y \ne x なので  y \in s^*(s(x)) となります。(O6)より  \bar{s}(s^*(x)) = s^*(s(x)) \ni y となるので  y = s(z) となる  z \ge x が存在します。[証明終わり]

(P5)  x, y \in N ならば  x \le y または  y \le x

[証明]  x = x_0 のときは  y \in N = s^*(x) より  x \le y となります。

 x \le y または  y \le x を仮定して  s(x) \le y または  y \le s(x) を示します。 x \le y のとき(O5)より  y \in s^*(x) = \{x\} \cup s^*(s(x)) y =x のとき(O8)より  y \le s(x) y \in s^*(s(x)) のとき(O7)より  s(x) \le y y \le x のとき(O8)より  y \le x \le s(x) となり  y \le s(x) が成り立ちます。

よって帰納法により主張が成り立ちます。[証明終わり]

表の内容の証明

(T1)  N_2 \land N_3 \implies N_4

[証明]  (N_2) 任意の  x \in N に対して  s(x) \ne x_0 (N_3)  N 上で  s単射を仮定して  (N_4)  N 上で  \le は全順序であることを示します。

まず半順序であることを示します。任意の  x, y \in N に対して  x \le y y \le x ならば  x = y であることを、帰納法でを示します。

まず  x = x_0 のときを示します。任意の  y \in N に対して  x_0 \le y y \le x_0 ならば  x_0 = y であることを帰納法で示します。

(P2)より  y < x_0 ならば  x_0 = s(z) となる  z \ge y が存在します。 (N_2) よりこのような  z は存在しないので  y = x_0 となります。

 x \in N に対して、任意の  y \in N に対して  x \le y y \le x ならば  x = y であるとき、任意の  y \in N に対して  s(x) \le y y \le s(x) ならば  s(x) = y であることを示します。

 s(x) \ne y と仮定すると、(P2)より  y = s(y') となる  y' \ge s(x) と、 s(x) = s(z) となる  z \ge y が存在します。 (N_3) より  x = z となります。 x \le s(x) \le y' \le s(y') = y \le z = x なので  x \le y' y' \le x となり仮定より  x = y' となります。よって  s(x) = s(y') = y となります。

帰納法により  \le が半順序であることが示されました。

(P5)より  \le は全順序となります。[証明終わり]

(T2)  N_1 \land N_4 \implies N_3

[証明]  (N_1) 任意の  x \in N に対して  s(x) \ne x (\neg N_3)  N 上で  s単射ではないと仮定して  (\neg N_4)  N 上で  \le は全順序ではないことを示します。

 (\neg N_3) より  x \ne y s(x) = s(y) となる  x, y \in N が存在します。(P5)より  x \le y または  y \le x となります。 x \le y とします。 x \ne y なので(P1)より  s(x) \le y となります。 s(y) = s(x) \le y y \le s(y) (N_1)より  s(y) \ne y となるので、 \le は半順序ではありません。[証明終わり]

(T3)  N_1 \land N_4 \implies N_2

[証明]  (N_1) 任意の  x \in N に対して  s(x) \ne x (\neg N_2)  x_1 \in N が存在して  s(x_1) = x_0 を仮定して  (\neg N_4)  N 上で  \le は全順序ではないことを示します。

 (\neg N_2) より  s(x_1) = x_0 となる  x_1 \in N が存在します。 (N_1) より  s(x_0) \ne x_0 となるので  x_1 \ne x_0 となって (P1)より  s(x_0) \le x_1 となります。よって  s(x_0) \le x_1 \le s(x_1) = x_0 となりますが、 x_0 \le s(x_0) s(x_0) \ne x_0 であるので  \le は半順序ではありません。[証明終わり]

(T4)  \neg N_1 \implies N_4

[証明]  (\neg N_1)  x_1 \in N が存在して  s(x_1) = x_1 を仮定して  (N_4)  N 上で  \le は全順序であることを示します。

 (\neg N_1) より  s(x_1) = x_1 となる  x_1 \in N が存在します。 x_1 = x_0 のときは  N = \{ x_0 \} となるので  \le は全順序となります。 x_1 \ne x_0 とします。

 x \in N に対して  N_{\le x} = \{ y \in N \mid y \le x \} とおきます。

 x, y \in N x < y とすると (P4)より  y = s(z) となる  z \ge x が存在します。

ここで  y \le x と仮定すると  y \le x \le z s(y) \le s(z) = y となり、 N_{\le y} \in \mathcal{R}_{x_0} となるので  N = N_{\le y} となります。よって  x_1 \le y y \in s^*(x_1) = \{x_1\} となります。また  x_1 \le y \le x となるので同様に  x \in s^*(x_1) = \{x_1\} となって、 x = x_1 = y となります。これは  x < y に矛盾となります。

よって  x \le y x \ne y ならば  y \le x とはなりません。

よって  x \le y かつ  y \le x ならば  x = y となり、 \le は半順序、(P5)より全順序となります。[証明終わり]

(T5)  N_2 \land N_3 \implies N_5

[証明]  (N_2) 任意の  x \in N に対して  s(x) \ne x_0 (N_3)  N 上で  s単射を仮定して  (N_5)  N は無限集合であることを示します。

 (N_3) より  s: N \to N単射で、 (N_2) より  \bar{s}(N) \subseteq N \setminus \{x_0\} となるので  s全射ではありません。よって  N は無限集合となります。[証明終わり]

(T6)  N_1 \land N_4 \implies N_6

[証明]  (N_1) 任意の  x \in N に対して  s(x) \ne x (N_4)  N 上で  \le は全順序を仮定して  (N_6)  X \subseteq N かつ  X \ne \varnothing ならば   X は極小元を持つことを示します。

 Y = \{ y \in N \mid 任意の \ x \in X \ に対して \ y \le x \} とおきます。任意の  x \in N に対して  x_0 \le x なので  x_0 \in Y となります。

 X \ne \varnothing より  x \in X が存在します。(O5)より  x \le s(x) (N_1) より  x \ne s(x) であり、 (N_4) より  \le は全順序なので  s(x) \not\le x となります。よって  s(x) \notin Y となり  Y \ne N となります。

よって

  •  0 \in Y かつ  Y \ne N

となり(O1)より

  • (*1)  y \in Y かつ (*2)  s(y) \notin Y

となる  y が存在します。(*2)よりある  x_1 \in X が存在して  s(y) \not\le x_1 となります。 (N_4) より  \le は全順序なので  x_1 < s(y)、よって  x_1 \le y となります。(*1)より任意の  x \in X に対して  y \le x なので  y \le x_1 となり、 (N_4) より  \le は全順序なので  y = x_1 \in X となります。よって (*1)より  y X の最小元となります。[証明終わり]

(T7)  N_4 \iff N_7

[証明] (P5)より
 (N_4)  N 上で  \le は全順序  \iff  \le は半順序
 \iff  (N_7) 任意の  x \in N に対して  N_{\cong x} = \{x\}
が成り立ちます。[証明終わり]

自然数の定義

 N とは別に、 \mathbf{N}^{(T_1)} N と同様に定義します。このとき  x_0 0 s \sigma として定義します。 \mathbf{N}^{(T_1)} (T_1) を満たすとします。
 \nu :  \mathbf{N}^{(T_1)} \to N
 \begin{cases}
\nu(0) = x_0 \\
\nu(\sigma(n)) = s(\nu(n)) & (n \ne 0)
\end{cases}
と定義します。 \nu(\mathbf{N}^{(T_1)}) \in \mathcal{R}_{x_0} となるので  \nu全射となります。

(N1)  N_{\le s(x)} = N_{\le x} \cup N_{\cong s(x)}

[証明]  N_{\le s(x)} \supseteq N_{\le x} N_{\le s(x)} \supseteq N_{\cong s(x)} が成り立つので  N_{\le s(x)} \supseteq N_{\le x} \cup N_{\cong s(x)} が成り立ちます。

 y \in N_{\le s(x)} \setminus N_{\le x} をとります。 y \le s(x) かつ  y \not\le x であるので、(P5)より  y \not\le x ならば  x < y となり(P1)より  s(x) \le y となります。よって  y \le s(x) かつ  s(x) \le y となり  y \in N_{\cong s(x)} となります。[証明終わり]

(N2)  n \in \mathbf{N}^{(T_1)} に対して  \mathbf{N}^{(T_1)}_{\le n} は有限集合

[証明]  \mathbf{N}^{(T_1)}_{\le 0} = \{ 0 \} となるので  \mathbf{N}^{(T_1)}_{\le 0} は有限集合となります。

 \mathbf{N}^{(T_1)}_{\le n} が有限集合と仮定します。(N1)、(T7)より  \mathbf{N}^{(T_1)}_{\le \sigma(x)} = \mathbf{N}^{(T_1)}_{\le n} \cup \mathbf{N}^{(T_1)}_{\cong \sigma(n)} = \mathbf{N}^{(T_1)}_{\le n} \cup \{\sigma(n)\} となり、(FM6)より  \mathbf{N}^{(T_1)}_{\le \sigma(n)} は有限集合となります。

よって帰納法により主張が成り立ちます。[証明終わり]

(N3) 集合  X が全順序  \le に関する最大元を持たないならば  X は無限集合

[証明]  X が最大元を持たないので任意の  x \in X に対して  x < y となる  y \in X が存在します。そのような  y の一つを  s(x) とおくことによって  s: X \to X を定義することができます。以前の議論と同様に、 s^*: X \to \mathfrak{P}(X) を定義します。 x_0 \in X をとります。 s s^*(x_0) への制限は単射となりますが、 x_0 は像に含まれないので全射ではありません。よって  s^*(x_0) は無限集合となり、 X も無限集合となります。[証明終わり]

(N4) 集合  X が全順序  \le に関する最小元を持たないならば  X は無限集合

[証明] (N3)と同様です。[証明終わり]

(T8)  N_5 \iff N_8

[証明]  (\Longrightarrow):  (\neg N_8)  x_1 \in N が存在して  s(x_1) \le x_1 であることを仮定して  (\neg N_5)  N は有限集合であることを示します。

 \nu全射なので(T6)より  x_1 = \nu(n) となる最小の  n \in \mathbf{N}^{(T_1)} が存在します。(N2)より  \mathbf{N}^{(T_1)}_{\le n} は有限集合なので(FM2)より  N = \nu(\mathbf{N}^{(T_1)}_{\le n}) は有限集合となります。

 (\Longleftarrow):  (N_8) 任意の  x \in N に対して  s(x) \not\le x であることを仮定して  (N_5)  N は無限集合であることを示します。

 (N_8) ならば  (N_1) 任意の  x \in N に対して  s(x) \ne x かつ  (N_2) 任意の  x \in N に対して  s(x) \ne x_0 となることは明らか。

 x < y かつ  y < x となる  x, y \in N が存在すると仮定すると、(P1)より  s(x) \le y となり、 s(x) \le y < x から  s(x) \le x となるので  (N_8) は成り立ちません。よって  (N_8) が成り立つならばそのような  x, y \in N は存在しないので  \le は半順序となり、(P5)より (N_4)  N 上で  \le は全順序となります。

よって(T2)より  (N_3)、(T5)より  (N_5) が成り立ちます。[証明終わり]

(T9)  N_5 \implies N_2

[証明]  (\neg N_2)  x_1 \in N が存在して  s(x_1) = x_0 を仮定して  (\neg N_5)  N は有限集合であることを示します。

 (\neg N_2) ならば  (\neg N_8) となるので、(T8)より  N は有限集合となります。[証明終わり]

(T10)  N_5 \implies N_3

[証明]  (\neg N_3)  N 上で  s単射ではないと仮定して  (\neg N_5)  N は有限集合であることを示します。

 (\neg N_3) より  x \ne y s(x) = s(y) となる  x, y \in N が存在します。(P5)より  x \le y または  y \le x となります。 x \le y とします。(P3)より  s^2(x) = s(x) となり(T8)より  N は有限集合となります。 y \le x の場合も同様です。[証明終わり]

(T11)  \neg N_2 \implies N_3

[証明]  (\neg N_2)  x_1 \in N が存在して  s(x_1) = x_0 を仮定して  (N_3)  N 上で  s単射であることを示します。

 (\neg N_2) ならば (T9)より  N は有限集合となります。(P4)より  y \ne x_0 ならば  y = s(z) となる  z \in N が存在します。よって  (\neg N_2) より任意の  y \in N に対して  y = s(z) となる  z \in N が存在するので  s全射となります。よって  s単射となります。[証明終わり]

(T12)  N_2 \land N_3 \implies N_1

[証明]  (\neg N_1)  x_1 \in N が存在して  s(x_1) = x_1 (N_2) 任意の  x \in N に対して  s(x) \ne x_0 を仮定して  (\neg N_3)  N 上で  s単射ではないことを示します。

 (\neg N_1) ならば  (\neg N_8) となるので、(T8)より  N は有限集合となります。 (N_2) より  s全射ではないので、単射ではありません。[証明終わり]

(T13)  N_4 \iff N_6

[証明]  (\Longrightarrow):  (N_4)  N 上で  \le は全順序であることを仮定して  (N_6)  X \subseteq N かつ  X \ne \varnothing ならば   X は極小元を持つことを示します。

 (N_4) が成り立つのは  (T_1) (T_4) (T_5) の場合となります。

 (T_1) の場合は(T6)より  (N_6) が成り立ちます。 (T_4) (T_5) の場合は(T9)、(T10)より  N は有限集合となります。(N4)より  (N_6) が成り立ちます。

 (\Longleftarrow):  (\neg N_4)  N 上で  \le は全順序ではないことを仮定して  (\neg N_6)  X \subseteq N かつ  X \ne \varnothing かつ極小元を持たない   X が存在することを示します。

 (N_4) が成り立たないは  (T_2) (T_3) の場合となります。このとき  (N_1) が成り立ちます。

 \le は全順序ではないとすると(P5)より半順序ではありません。よって  x < y かつ  y < x となる  x, y \in N が存在します。(P1)より  s(x) \le y となり、 s(x) \le y < x から  s(x) \le x となります。 (N_1) が成り立つので  s(x) \ne x となります。よって  \{x\} は極小元を持たないので  (N_6) は成り立ちません。[証明終わり]

以上で表の説明が終わりました。

  • (T1)  N_2 \land N_3 \implies N_4
  • (T2)  N_1 \land N_4 \implies N_3
  • (T3)  N_1 \land N_4 \implies N_2
  • (T4)  \neg N_1 \implies N_4
  • (T5)  N_2 \land N_3 \implies N_5
  • (T6)  N_1 \land N_4 \implies N_6
  • (T7)  N_4 \iff N_7
  • (T8)  N_5 \iff N_8
  • (T9)  N_5 \implies N_2
  • (T10)  N_5 \implies N_3
  • (T11)  \neg N_2 \implies N_3
  • (T12)  N_2 \land N_3 \implies N_1
  • (T13)  N_4 \iff N_6

集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)