Chapter 40

13.2 自由モノイドの普遍構成

さのたけと
さのたけと
2021.06.02に更新

普遍構成のこれまでの経験を思い出してみれば、普遍構成というのは何かを構成することではなく、与えられたパターンに一番適合する対象を選ぶことだというのに気づくだろう。そうすると、自由モノイドを「構成」するのに普遍構成を使いたいなら、モノイドたちを束ねたもの全体というのを、その中から1つモノイドを選ぶために考えなければいけない。モノイド全体の圏というのが、そこから選び出すために必要である。でもモノイドたちは圏をなすのだろうか?

まずはモノイドを、単位元とかけ算によって定義される追加構造を備えた集合であるとみなそう。射を、モノイド構造を保つような関数として選ぶ。そのような構造を保存する関数は 準同型(homomorphism) とよばれる。モノイド準同型は、2つの元の積を2つの写った先の積に写さなければならない:

h~(a * b) = h a * h b

さらに、単位元を単位元に写さなければいけない。

例えば、整数のリストから整数への準同型を考えよう。もし[2]を2に、[3]を3に写すのなら、[2, 3]を6に写さなければならない。なぜなら、結合

[2] ++ [3] = [2, 3]

は積

2 * 3 = 6

になるからである。

いま、個別のモノイドの内部構造を忘れてモノイドたちのことを単に、対応する射を伴う対象たちと見よう。すると、モノイドの圏\mathbf{Mon}が得られる。

よし、内部構造を忘れる前に重要な性質について注意しておこう。\mathbf{Mon}のすべての対象は自明に集合に写すことができる。その集合というのは、単にそのモノイドの元たちの集合である。この集合は 台集合(underlying set)[1] とよばれる。さらに、\mathbf{Mon}の対象を集合に写すだけでなく、\mathbf{Mon}の射(準同型)を関数に写すこともできる。やっぱりこれも当たり前の類のことに思えるが、これはすぐ有用になる。この対象と射とを\mathbf{Mon}から\mathbf{Set}に写すことは、実は関手なのである。この関手はモノイド構造を「忘れる」(一旦ただの集合に入りこんでしまうと、もう単位元がどれか区別したり、かけ算を考えたりできなくなる)ので、これは 忘却関手(forgetful functor) とよばれる。忘却関手は圏論では定期的にあらわれる。

いま、\mathbf{Mon}には2つの異なる見方がある。それを単に、他の圏と同じように対象と射があるものとして扱うことができる。この視点では、モノイドの内部構造を見ることはできない。\mathbf{Mon}のある特定の対象について言えることは、それ自身と他の対象に射を通じて繋がっているということが全てである。射の「かけ算」表(合成の規則)は、もう一方の見方から導かれる: 集合としてのモノイドである。圏論に行ってしまっても、この見方を完全に失ってしまうわけではない。かけ算表には、忘却関手を通してアクセスすることができる。

普遍構成を適用するためには、モノイドの圏のなかを探し回って自由モノイドの最良の候補を選ぶための特別な性質を定義する必要がある。しかし、自由モノイドはその生成元たちで定義されるのである。生成元の異なる選択は異なる自由モノイドを作り出す(BoolのリストはIntのリストと同じではない)。構成は、生成元集合から始まらなければいけないのである。そうしたら集合に戻らなければ!

ここで忘却関手の出番だ。この忘却関手を、モノイドにX線を当てるのに使うことができる。モノイド圏のよくわからない対象も、そのX線写真を見れば生成元を特定することができるのだ。こんな感じで機能する:

生成元の集合xからはじめよう。これは\mathbf{Set}の中の集合である。

適合させたいパターンはモノイドm(\mathbf{Mon}の対象)と、\mathbf{Set}の関数pからなる:

p \mathtt{::}\ x \to U m

ここで、U\mathbf{Mon}から\mathbf{Set}への忘却関手である。これは奇妙な異種混合パターンである。半分は\mathbf{Mon}の話であり、半分は\mathbf{Set}の話なのである。

重要なアイデアは、関数pmのX線写真のなかから生成元集合を指定するということである。関数というのは、集合のなかで点を指定するのは(関数は複数の値をつぶしてしまうかもしれないので)下手かもしれないが、それは問題にならない。その下手さは普遍構成で解決されるのである。普遍構成はパターンに適合する候補たちのなかから最良のものを選んでくれるのだ。

さらに候補たちのなかでランキングを作らなくてはいけない。他にも候補が1つあったとしよう: モノイドnと、そのX線写真から生成元を特定してくれる関数qである:

q \mathtt{::}\ x \to U n

モノイドの射(これは構造を保つ準同型である)

h \mathtt{::}\ m \to n

が存在し、このUでの像がpを通して因子分解する(Uは関手なので、射を関数に写すことを思い出そう):

q = U h~.~p

ときに、mnよりも良いということにしよう。

pmのなかから生成元を選んでおり、qnのなかから「同じ」生成元を選んでいると思うことにしよう。すると、hはこれら2つのモノイドの間でこれら生成元を写していると思うことができる。定義から、hはモノイド構造を保存していることを思い出そう。つまり、あるモノイドでの生成元の積は2つ目のモノイドでの対応する2つの生成元の積に写される、などなどが成り立つのだ。

このランキングは最良の候補 --- 自由モノイド --- を見つけるのに使うことができる。これが定義だ:

m(と関数p)がxを生成元とする 自由モノイド であるとは、 先の因子分解の性質をみたすような、mから他のモノイドn(と関数q)への射h唯一つ 存在することである。

偶然にも、これは2番目の質問[2]にも答えている。関数U hU mの複数の元をU nのある1つの元につぶす力を持っている。このつぶしは、自由モノイドのいくらかの元を同一視することに対応している。したがって、xを生成元とするどんなモノイドもxに基づく自由モノイドから、いくらかの要素を同一視することによって得られる。自由モノイドは、本当に最小限の同一視だけがされたモノイドなのである。

随伴の話をするときに、また自由モノイドに戻ってくることにしよう。

(和訳:@ashiato45

脚注
  1. 訳注: 底集合という訳語もあるみたいですが国語辞典と古い文献でしか出てこないので台集合にしました。 ↩︎

  2. 訳注: 13章1節最後の「どんなモノイドもある自由モノイドから、モノイドの法則で要求されている最小の元たちよりたくさんの元たちを同一視することによって得られるのだろうか」です。 ↩︎