モナドの自由代数

「モナドFのクライスリ圏は、F-自由代数の圏とみなせる」と言われます。おおよその状況は次のようです

Fのクライスリ圏 $\cong$ F-自由代数の圏 ⊆ F-代数の圏 = Fのアイレンベルク／ムーア圏

この事実に対する正確な説明や実例をあまり見ないので（僕が目にしてないだけかも）、この記事で説明し、典型的実例を紹介します。

内容：

準備：予備知識のまとめ
モナドの厳密自由代数
モナドの自由代数
厳密自由代数、自由代数、代数の関係
リストモナドのとき
線形結合モナドのとき
おわりに

準備：予備知識のまとめ

Cは圏として、(F, μ, η) はC上のモナドとします。つまり、

F:C→C は関手
μ::F*F⇒F:C→C は自然変換（'*'は関手の図式順結合記号）
η::Id_C⇒F:C→C は自然変換

(F, μ, η) は関手圏 [C, C] のモノイドになります。モナドの素材〈構成素〉の呼び名は：

圏Cは、モナドの基礎圏〈ground category〉*1
関手Fは、モナドの台関手〈underlying functor〉
自然変換μは、モナドの乗法〈multiplication〉
自然変換ηは、モナドの単位〈unit〉

記号の乱用により、次のようにも書きます。

F = (F, μ, η)

モナドFのクライスリ圏を Kl(C, F) と書き、モナドFのアイレンベルク／ムーア圏を EM(C, F) と書きます。基礎圏Cが了解されているなら、Kl(F), EM(F) と書いてもかまいません。

Fのクライスリ圏の対象は、基礎圏Cの対象と同じです。クライスリ圏の射は、基礎圏においては、A→F(B) の形をしています。次の図の上下段は同値です。

   A→B in Kl(C)
 -----------------
   A→F(B) in C

クライスリ圏の射（Cでは A→F(B) の形）をクライスリ射〈Kleisli morphism〉と呼びます。

Fのアイレンベルク／ムーア圏の対象を、Fのアイレンベルク／ムーア代数、または単にF-代数〈F-algebra〉と呼びます。Fのアイレンベルク／ムーア圏の射は、F-代数の準同型射、あるいはF-代数射〈F-algebra morphism〉です。F-代数とF-代数射の圏を F-Alg と書きます。F-代数の圏と、Fのアイレンベルク／ムーア圏はまったく同じものですから：

F-Alg = EM(F)

F-AlgはEM(F)の別名です。

モナドの厳密自由代数

この節と次の節で、モナドの厳密自由代数と自由代数を定義します。「自由」という形容詞の使い方が、加群の理論や群論などと違うように感じるかもしれませんが、本質的には同じです。

C上のモナドFの厳密自由代数〈strict free algebra〉とは、A∈|C| と F(A)∈|C| のペア (A, F(A)) のことです。厳密自由代数 (A, F(A)) と (B, F(B)) のあいだの射は、f:A→F(B) in C だとします。モナドFの厳密自由代数をF-厳密自由代数〈F-strict free algebra〉とも呼びます。

ペア (A, F(A)) は、基礎圏Cの対象Aだけから一意に決まってしまうので、F(A) を書くのは冗長です（書かなくても再現できる）。厳密自由代数のあいだの射はクライスリ射です。つまり、Fの厳密自由代数とそのあいだの射の圏は、Fのクライスリ圏と同じです。このことを次の形に書きましょう。

F-StFreeAlg = Kl(F)

左辺の F-StFreeAlg は、F-厳密自由代数の圏です。F-厳密自由代数の圏は、Fのクライスリ圏をわずかに異なった方法で再定義しているだけです。結局、F-StFreeAlgはKl(F)の別名です。

モナドFの代数〈algebra〉（Fの加群〈module〉と呼ぶこともある）は、M∈|C| と α:F(M)→M in C の組 (M, α) で次の図式を可換にするものです*2。

$\require{AMScd} \begin{CD} F(F(M)) @>{F(\alpha)}>> F(M) \\ @V{\mu_M}VV @VV{\alpha}V \\ F(M) @>{\alpha}>> M \\ \\ M @>{\eta_M}>> F(M) \\ @| @VV{\alpha}V \\ M @= M \end{CD}$

A∈|C| に対して、M = F(A), α = μ_A としたとき、上の可換図式は次の形になります。

$\require{AMScd} \begin{CD} F(F(F(A))) @>{F(\mu_A)}>> F(F(A)) \\ @V{\mu_{F(A)}}VV @VV{\mu_A}V \\ F(F(A)) @>{\mu_A}>> F(A) \\ \\ F(A) @>{\eta_{F(A)}}>> F(F(A)) \\ @| @VV{\mu_A}V \\ F(A) @= F(A) \end{CD}$

これはモナドの定義そのものなので、(F(A), μ_A) はF-代数になります。こうして定義されたF-代数 (F(A), μ_A) を、記号の乱用により F(A) = (F(A), μ_A) と書き、F-代数F(A)と言ったりします。

さて、C上のモナドFの自由代数〈free algebra〉とは、A∈|C| と M∈|F-Alg| 、そしてF-代数の同型 φ;F(A)→M in F-Alg の組 (A, M, φ) のことです。自由代数 (A, M, φ) と (B, N, ψ) のあいだの射は、単にF-代数射 f:M→N in F-Alg のことです。モナドFの自由代数をF-自由代数〈F-free algebra〉とも呼びます。

F-自由代数とそのあいだの射は圏をなすので、それをF-FreeAlgと書きます。F-自由代数 (A, M, φ) は、F-代数Mに A, φ を余分に付けた形なので、Mだけを取り出すことにより、忘却関手 U:F-FreeAlg→F-Alg を定義できます。

U((A, M, φ)) := M ∈|F-Alg|
U(f:(A, M, φ)→(B, N, ψ)) := (f:M→N) ∈F-Alg(M, N)

ホムセット F-FreeAlg((A, M, φ), (B, N, ψ)) とホムセット F-Alg(M, N) は同じ集合なので、U:F-FreeAlg→F-Alg が充満忠実関手になるのは明らかです。ただし、対象に対するU:|F-FreeAlg|→|F-Alg| は単射的とは限らないので、関手Uは埋め込みにはなりません（埋め込みであることを保証できません）。

厳密自由代数、自由代数、代数の関係

モナドFの厳密自由代数 (A, F(A)) が与えられたとき、(A, F(A), id_F(A)) は自由代数になります。この対応は関手となるので、K:F-StFreeAlg→F-FreeAlg としましょう。

K((A, F(A))) := (A, F(A), id_F(A)) ∈|F-FreeAlg|
K(f:(A, F(A))→(B, F(B))) := (f^#:F(A)→F(B)) ∈F-FreeAlg(F(A), F(B))

射に対するKの定義を補足します。f:(A, F(A))→(B, F(B)) in F-StFreeAlg は、f:A→F(B) in C でした。モナドには、対応するクライスリ拡張オペレータがあります。(-)^# がFのクライスリ拡張オペレータです。F-StFreeAlg から F-FreeAlg へと至るプロセスを図にすると：

   f:(A, F(A))→(B, F(B)) in F-StFreeAlg
 ------------------------------------------
   f:A→F(B) in C
 ---------------------
   f^#:F(A)→F(B) in C
 --------------------------------------
   f^#:(F(A), μ_A)→(F(B), μ_B) in F-Alg
 -----------------------------------------------------
   f^#:(A, F(A), id_F(A))→(B, F(B), id_F(B)) in F-FreeAlg

上の図の各段のあいだの対応は、ホムセットのあいだの全単射になるので、Kは充満忠実関手になります。(A, F(A)) ←→ (A, F(A), id_F(A)) も1：1の対応なので、Kは充満埋め込み関手になります。

今まで出現した圏と関手をまとめておきましょう。

F-Alg = EM(F)	圏の同一性（別名）
F-StFreeAlg = Kl(F)	圏の同一性（別名）
U:F-FreeAlg→F-Alg	充満な忘却関手
K:F-StFreeAlg→F-FreeAlg	充満な埋め込み関手

モナドFに対して、Kl(F) = F-StFreeAlg, F-FreeAlg, F-Alg = EM(F) は異なる3つの圏です。埋め込みKがあるので、F-StFreeAlg⊆F-FreeAlg とみなしてかまいません。しかし、F-FreeAlg⊆F-Alg とは言えません。

「F-自由代数」（あるいは「自由F-代数」という言葉は実は曖昧です。次の3つの意味のどれかで使われます。

圏F-StFreeAlgの対象
圏F-FreeAlgの対象
忘却関手Uの像であるF-Algの部分圏の対象

「自由モノイド」「自由群」などは1番の意味でしょう。「自由加群」は3番の意味だと思います。「自由ベクトル空間」は1番の意味のときもあれば3番の意味のときもあります。「自由ベクトル空間」という言葉がどうもハッキリしないのは、この曖昧性のためでしょう。

1番または2番の意味だとするなら、「自由ではないベクトル空間」＝「基底が特定されてないベクトル空間」もある。
3番の意味だとすると、すべてのベクトル空間は「自由ベクトル空間」＝「基底が存在するベクトル空間」になる。

ベクトル空間については、典型的実例として後述します（次々節）。

リストモナドのとき

基礎圏Set上のリストモナド List = (List, flatten, single) と、List-代数の圏〈Listのアイレンベルク／ムーア圏〉については、次の記事に書いてあります。

アイレンベルグ／ムーア圏その2:リストモナドのとき

リストモナドListに関して、List-StFreeAlg, List-FreeAlg, List-Alg の3つの圏を見ていきます。

上記の過去記事から、List-Alg = EM(List) $\cong$ Mon = (モノイドの圏) です。List-代数とはモノイドのことです。

List-厳密自由代数は、(A, List(A)) の形です（Aだけから決まる）。ここで、List(A) は単なる集合ではなくて、連接演算と空列によりモノイドとみなします。List-厳密自由代数とは、リスト（あるいは文字列）の連接モノイドのことになります。

List-自由代数は、定義より、リストの連接モノイドと同型なモノイドになります。(A, M, φ) がList-自由代数だとすると、φ:List(A)→M はモノイドの同型写像です。single_A:A→List(A) と φ:List(A)→M を結合すると、A→M という単射ができます。この単射により A⊆M とみなせます。この状況で、モノイドMは、部分集合Aで自由生成されています。つまり、List-自由代数とは、特定された自由生成系を持つモノイドになります。

自然数の足し算モノイド (N, +, 0) は、自由生成系{1}を持ちます。これは、NがList-自由代数であることを意味します。もう少し詳しく言うと; List({1}) は、1だけからなるリスト（1をいくつか並べた列）の集合です*3。リストの長さ length:List({1})→N は、リストの連接モノイドから自然数の足し算モノイドへの同型になります。したがって、({1}, N, length) はList-自由代数です。

すべてのList-代数〈モノイド〉がList-自由代数〈自由生成系を持つモノイド〉なわけではありません。集合 {0, 1} に 1 + 1 = 0 として足し算を入れると、{1}が生成系になりますが、自由生成系ではありません。実際、List({1}) と {0, 1} は同型にはなりません。

線形結合モナドのとき

$\newcommand{\U}[1]{\langle{#1}\rangle}$ 集合Aに対して、Aの要素を実数係数で（形式的に）線形結合したモノ全体の集合を LinComb(A) とします。LinCombは集合圏Set上の自己関手になり、さらにモナドに仕立てることができます。このモナドを LinComb = (LinComb, linflatten, unit) とします。

Aの要素の（有限な）線形結合は、 $\sum_{a\in A} x^a a$ の形に書きます*4。有限個のaを除いて x^a ∈R はゼロです。a∈A と a∈LinComb(A) の区別がしたいときは、LinComb(A) に入ったaを<a>と書くことにします。この書き方を採用すると、x∈LinComb(A) は $x = \sum_{a\in A} x^a \U{a}$ です。

LinComb(LinComb(A)) の要素Xは次のような表示を持ちます。

$X = \sum_{x\in LinComb(A)}X^{x}\U{x} \:\in LinComb(LinComb(A)) \\ x = \sum_{a\in A}x^a\U{a} \:\in LinComb(A) \\$
モナドの演算である linflatten, unit の定義は次のようです。

$\mbox{For }\; X \in LinComb(LinComb(A)), \\ linflatten(X) \\ = linflatten(\sum_{x\in LinComb(A)}X^{x}\U{x}) \\ := \sum_{x\in LinComb(A),\, a\in A} X^{x} x^a \U{a} \:\in LinComb(A) \\ \:\\ \mbox{For}\; a \in A, \\ unit(a) \\ := \U{a} \; \in LinComb(A)$

分かりにくいかも知れませんが、要するに通常の線形計算です。

線形結合モナドLinCombのアイレンベルク／ムーア圏〈代数の圏〉は、ベクトル空間の圏と同一視可能です（係数体は実数体に固定して、Rは書かないことにします）。

LinComb-Alg $\cong$ Vect

LinComb-厳密自由代数は、定義により (A, LinComb(A)) です。Aが有限のときは、LinComb(A) は R^A と書いても同じことなので、(A, R^A) でもいいでしょう。圏 LinComb-StFreeAlg の射はクライスリ射だったので、f:A→LinComb(B) in Set の形をしています。f(a) = y とすると、 $y = \sum_{b \in B} y^b \U{b}$ と書けます。係数達 y^b はaにも依存するので $f(a) = \sum_{b \in B} y^b_a \U{b}$ 、この $y^b_a$ 達は行列成分と考えることができます。

行列のインデックスとして任意の集合を許すとして、A, B をインデックス集合とする実数成分の“B行A列の行列”の全体を Mat(A, B) と書くことにします。通常の行列計算を拡張して、Mat(A, B) をホムセットとする圏Matを構成できます。圏 LinComb-StFreeAlg の射は、行列と1：1対応するので、LinComb-厳密自由代数の圏は、行列の圏と同一視可能です。

LinComb-StFreeAlg $\cong$ Mat

LinComb-自由代数は、定義より、LinComb(A) の形のベクトル空間と同型なベクトル空間になります。(A, V, φ) がLinComb-自由代数だとすると、φ:LinComb(A)→V はベクトル空間の同型写像です。unit_A:A→List(A) と φ:LinComb(A)→V を結合すると、A→V という単射ができます。この単射により A⊆V はベクトル空間Vの基底とみなせます。像が基底となる単射写像 φ:A→V は、ベクトル空間Vのフレーム〈frame〉と呼びます。よって、LinComb-自由代数 (A, V, φ) とは、フレームφを備えたベクトル空間〈framed vector space〉です。

フレーム付きベクトル空間の圏をFrmVectとすると：

LinComb-FreeAlg $\cong$ FrmVect

先に述べたモナドの厳密自由代数／自由代数の一般論を考慮すると：

LinComb-Alg = EM(LinComb) $\cong$ Vect = (ベクトル空間の圏)
LinComb-StFreeAlg = Kl(LinComb) $\cong$ Mat = (行列の圏)
LinComb-FreeAlg $\cong$ FrmVect = (フレーム付きベクトル空間の圏)
U:FrmVect→Vect （充満な忘却関手）
K:Mat→FrmVect （充満な埋め込み関手）

Uはフレームを忘れる関手で、Kは、(A, LinComb(A)) を、標準的なフレーム unit_A:A→LinComb(A) が付いたフレーム付きベクトル空間とみなす関手です。

おわりに

前節の線形結合モナドの例において、モナドの厳密自由代数／自由代数／代数がそれぞれ、形式的線形結合のベクトル空間／フレーム付きベクトル空間／ベクトル空間になっていました。3つの圏とそのあいだの関係もクリアになりました。

他のモナドに対しても同様な3つの圏を考えることによって、曖昧に使われている「自由☓☓☓」の意味をハッキリさせることができると思います。

*1:呼び名はハッキリとは決まってません。台圏、ベース圏とか呼ぶこともあります。

*2:Hさんのご指摘により、3箇所のミスを修正しました。本文中に編集タグを残すと見にくいので書き換えましたが、次の3箇所です。(1)「α:F(M)→FM in C」 (2)「A∈|AC| に対して」 (3)「f:A→F(AB) in C」。

*3:自然数の表現としての List({1}) の要素は、自然数の一進記法とかタリー〈tally〉表現とか呼ばれます。

*4:添字を上付きにしているのは、微分幾何の習慣からの影響です。上下の添字を両方使う方法は、慣れると便利。

準備： 予備知識のまとめ