『プログラマーのための圏論』第3章「圏のさまざま」を読みます。

この章では、対象と射の選び方を変えながら、さまざまな圏を見ていきます。本の順番に沿って内容を整理しつつ、読んでいて気になった「自由とは何か」「普遍性は何が嬉しいのか」「射が等しいとはどういうことか」といった疑問も、その都度掘り下げます。

# 圏の定義

以降の基準になる圏の定義を正確にしておく。

圏 $\mathcal C$ は、次のデータからなる。

1. 対象の集まり
2. 任意の対象 $A,B$ に対する、$A$ から $B$ への射の集合 $\operatorname{Hom}_{\mathcal C}(A,B)$
3. 射 $f:A\to B$ と $g:B\to C$ に対する合成 $g\circ f:A\to C$
4. 各対象 $A$ に対する恒等射 $\operatorname{id}_A:A\to A$

ただし、合成と恒等射は次の法則を満たすものとする。

• 結合律

• 単位律

圏論が、すべての圏に共通する新しい等号の意味を定めるわけではない。射は各Hom集合の元なので、圏の定義では集合の元に対する通常の等号が使われている (と解釈する) 。

つまり、その等号が具体的に何を意味するかは、扱っている圏によって異なります。

• $\mathbf{Set}$ の射なら、写像として等しいこと
• 自由圏の射なら、パスを構成する辺の列が等しいこと
• 前順序集合から作った細い圏なら、同じ始点と終点を持つ射は高々一つなので、始点と終点がそれぞれ等しい2つの射は等しい

オリジナルの「等しさ」を同値関係 $\sim$ として定めることはできる。ただし、一般の同値関係では代入原理が成り立つとは限らない。

そこで商集合を作り、同値な元を同じ同値類へまとめることで、元同士の $\sim$ を、同値類同士の通常の $=$ として扱う。

# 3.1 対象がない場合

対象も射も一つもない圏を空圏という。

対象がなければ、合成できない射や恒等射を持たない対象も存在しない。そのため、圏の公理に反する例はなく、対象が0個の場合も圏として認められる。

# 3.2 有向グラフ

有向グラフの頂点を対象、辺を射と考えると、圏に似た図が得られるが、一般にはそのままでは圏にならない。

合成について閉じていないためである。

そこで、辺だけでなくパスを射にする。

有向グラフ $G$ が生成する自由圏 $F(G)$ を、次のように構成する。

• 対象：$G$ の頂点
• 射：$G$ 上の有限長の有向パス
• 合成：パスの連結
• 恒等射：各頂点における長さ0の空パス

パスの連結は結合的である。また、空パスを前後に連結しても元のパスは変わらない。したがって、圏の結合律と単位律が成り立つ。

ここでいう「自由」は、

元の辺の間に、圏の公理から必要になるもの以外の関係を課さない

という意味らしい。

# 自由圏は普遍性によって特徴づけられるらしいので、その話がしたい！

$U(\mathcal C)$ を、圏 $\mathcal C$ から合成と恒等射の構造を忘れ、対象と射だけを取り出した有向グラフとする。また、

を、頂点を同じ対象へ、辺を長さ1のパスへ送る自然なグラフ準同型とする。

このとき、任意の圏 $\mathcal C$ と任意のグラフ準同型

に対して、$U(\overline\varphi)\circ\eta_G=\varphi$ を満たす関手

がただ一つ存在する。(自由圏の普遍性)

以上の性質が成り立ち、これは自由圏の定義と同値である。

直感的には、グラフの頂点と辺を別の圏でどう解釈するかを決めれば、その解釈はパス全体を扱う関手へ一意に拡張できる、という主張である。

非空なパス $(e_1,\ldots,e_n)$ に対しては、

とするしかない。空パスは恒等射へ送る必要がある。そのため、この延長は存在するだけでなく一意になる。

普遍性の嬉しさは、おおざっぱに次のように整理できそう。

1. 対象を具体的な構成ではなく性質によって特徴づけられる
2. 構成時の選択に依存しない、同型を除く一意性が得られる
3. 生成元のような小さなデータから、目的の射を一意に構成できる
4. 一意性を使って、二つの射が等しいことを示せる
5. 対象ごとの構成を、射の対応を含む関手へ昇格できる

自由圏の場合、グラフの辺に対する解釈だけを与えれば、任意のパスに対する解釈を一つずつ手作業で定義する必要がない。普遍性が、その拡張の存在と一意性を保証してくれる。

# 3.3 順序

前順序集合 $(X,\leq)$ から、次のような圏を作れる。

• 対象：$X$ の元
• $x\leq y$ のとき：$x$ から $y$ への射が一つ存在する
• $x\nleq y$ のとき：$x$ から $y$ への射は存在しない

順序の公理は、そのまま圏の公理に対応する。

前順序集合から作った圏では、任意の2対象間の射は高々一つしかない。このような圏を細い圏という。

したがって、

は空集合または単集合である。特に、反射律によって、

は単集合になる。

# 3.4 集合としてのモノイド

モノイドは、集合 $M$ とその上の二項演算

の組で、次を満たすものである。

1. 結合法則

2. 単位元 $e$ の存在

モノイドの例には、次のようなものがある。

• 自然数と加算：単位元は $0$
• 文字列と連結：単位元は空文字列 ""
• リストと連結：単位元は空リスト []

# Haskellでのモノイド

現在のHaskellでは、Monoid はSemigroupを前提にして定義されている。

class Semigroup m => Monoid m where
    mempty :: m

Semigroup側の (<>) が結合的な二項演算、mempty が単位元に対応する。

文字列を例にした古い形式の定義は、次のようなイメージである。

instance Monoid String where
    mempty = ""
    mappend = (++)

ただし、型クラスの定義そのものは、演算が本当に結合律や単位律を満たすことまでは表現しない。それらの法則を守るのは、インスタンスを実装するプログラマの責任である。

# C++でのモノイド

C++では、Conceptsを使って、モノイド "らしい" インターフェースを次のように表現できる。

template<typename T>
struct mempty;

template<typename T>
T mappend(T, T) = delete;

template<typename M>
concept Monoid = requires (M m) {
    { mempty<M>::value() } -> std::same_as<M>;
    { mappend(m, m) } -> std::same_as<M>;
};

文字列に対しては、例えば次の実装を与える。

template<>
struct mempty<std::string> {
    static std::string value() { return ""; }
};

template<>
std::string mappend(std::string s1, std::string s2) {
    return s1 + s2;
}

これも「適切な型の単位元と二項演算が存在する」ことは確認できるが、結合法則と単位律までは保証しない。

Haskellでは、次の二つの書き方を考えられる。

mappend = (++)
mappend s1 s2 = (++) s1 s2

プログラムとしては同じ結果になるが、数学的には別の解釈ができると言っている。

• 前者：二つの関数、つまり $\mathbf{Hask}$ の射そのものが等しい
• 後者：すべての引数に対して同じ結果を返すという、外延的な等しさを示している

(冒頭の「＝」とは...？につながる)

# 3.5 圏としてのモノイド

ただ一つの対象 $*$ を持つ圏を考える。この圏では、すべての射が

という自己射である。

この自己射全体を集合 $M$ とすると、射の合成は $M$ 上の二項演算になる。合成は結合的で、恒等射 $\operatorname{id}_*$ が単位元になる。したがって、自己射全体はモノイドをなす。

逆に、任意のモノイドから、ただ一つの対象を持つ圏を作れる。

モノイドをわざわざ一対象圏として捉えることに、どのような利点があるのか。
白状すると、現時点では私にはわからなかった。

ので、お茶を濁すために周辺の話を2つほど。

1. モノイド準同型は、一対象圏同士の関手として扱える

モノイド準同型 $h:M\to N$ は、唯一の対象を唯一の対象へ、射 $m\in M$ を射 $h(m)\in N$ へ送る。

準同型が積と単位元を保つという条件は、関手が射の合成と恒等射を保つという条件にそのまま対応する。逆に、一対象圏同士の関手からはモノイド準同型が得られる。

2. モノイド作用は、一対象圏としてのモノイド $M$ から集合の圏 $\mathbf{Set}$ への関手として扱える

この関手は、唯一の対象 $*$ に集合 $X$ を割り当て、各元 $m\in M$ に自己写像 $F(m):X\to X$ を割り当てる。関手の法則

は、$m\cdot x:=F(m)(x)$ とおけば、モノイド作用の法則 $e\cdot x=x$ および $(mn)\cdot x=m\cdot(n\cdot x)$ になる。

# 3.6 課題

# 1. 以下から自由圏を生成せよ。

1. 一つの頂点を持ち、辺のないグラフ

2. 1つのノードと1つの（有向）辺を持つグラフ（ヒント：この辺は自身と合成できる）

3. 2つのノードと、それらの間の（有向）辺を1つ持つグラフ

3. 1つのノードと、アルファベットa, b, c … zでマークされた26個の（有向）辺を持つグラフ

厳密には、

• アルファベットを $A=\{a,b,\ldots,z\}$とする
• $\operatorname{Ob}(F(G))=\{*\}$
• $\operatorname{Hom}_{F(G)}(*,*)=A^*=\coprod_{n\geq 0}A^n =\{\varepsilon,a,b,\ldots,z,aa,ab,\ldots\}$
  • ここで $A^0=\{\varepsilon\}$ とし、空語 $\varepsilon$ が恒等射 $\operatorname{id}_*$ に対応する
• 射 $u,v\in A^*$ の合成はパスの連結、すなわち語の連結である。
  • 先に $u$、続いて $v$ をたどるとき、$v\circ u=uv$ と定める
  • この合成は結合的であり、
  • 空語 $\varepsilon$ は当然 $\varepsilon u=u=u\varepsilon$ を満たすため、
• $F(G)$ は自由モノイド $A^*$ を一対象圏とみなしたものに等しい

# 2. 以下はどんな順序だろうか？

1. 複数の集合を要素とする集合と、その上の包含関係。なお、AがBに包含されるとは、Aの全要素がBの要素でもあることを指す。
   • 半順序
2. C++の型の集合とその上の部分型関係。なお、T1がT2の部分型であるとは、T2へのポインターを期待する関数にT1をコンパイルエラーを発生させずに渡せることを指す。
   • 半順序？
     • 追いきれていないが、あり得る場合とその組み合わせを網羅的に見ればよさそう

# 3. Boolが2つの値TrueとFalseの集合であることを踏まえて、それが2つの演算子&& (AND) と|| (OR) のそれぞれについて（集合論的）モノイドをなすことを示せ。

いいよ。

# 4. AND演算子を伴うBoolモノイドを圏として表せ。射と合成の規則を列挙せよ。

# 5. モジュロ3加算をモノイドの圏として表せ。

# まとめ

この章に登場した圏を並べると、次のようになる。

圏の定義そのものは、対象・射・合成・恒等射と二つの法則だけである。しかし具体例を追っていくと、有向グラフ、順序、モノイドを同じ言葉で捉えられるだけでなく、自由な構成、普遍性、等号の意味にまで疑問が広がった。

第3章は「圏にはいろいろな具体例がある」という紹介であると同時に、圏論が異なる構造の共通部分をどのように取り出すのかを見せる章だったように思う。