圏論の問題
モノイドとは単位元をもつ半群のことであり、モノイド準同型は積と単位元を保つ写像とする。モノイドとモノイド準同型のなす圏を 、集合と写像のなす圏を とし、忘却関手 の左随伴(自由モノイド関手)を とする。
を集合 からそれ自身への写像全体が写像の合成を積、恒等写像を単位元としてなすモノイドとし、 とする。hom 集合 の元の個数を求めよ。
この問題で使うもの
- 随伴と hom 集合の数え上げ(説明と入口の問題)
この問題を解けるようになるまで(10 技能)
読み込み中…
右端(太枠)がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
随伴 の定義にある hom 集合の全単射 を使いましょう。
ヒント 2
右辺は集合 から の台集合への写像全体なので、その個数は です。
ヒント 3
は からそれ自身への写像全体なので です。あとは を使って計算します。
答えと解説
答えを見る
どこでつまずきましたか?(選ぶと、戻る場所を案内します)
解説を読む
であるから、集合 とモノイド について自然な全単射
がある。具体的には、 は 上の語(有限列)全体が連結を積、空語を単位元としてなすモノイド であり、モノイド準同型 はその生成元 の像 を指定すれば一意に定まり、逆に任意の指定が準同型に拡張される(、空語は単位元へ)。
したがって
の元は から への写像なので、各元の行き先を 通りずつ選べて 。また である。
よって求める個数は 。
別解
随伴 より (自由モノイドの普遍性)。 は からそれ自身への写像全体の集合で、その元の個数は 。 から 27 元集合への写像の個数は 。
検算: は で生成される自由モノイドで、準同型は の像 を任意に決めれば一意に定まる(語 の像は像の積、空語は恒等写像)。この対応は全単射なので 。