圏論の問題
半順序集合 は、対象を の元とし、 のときに限り から への射がちょうど つ存在する(それ以外のときは射が存在しない)圏とみなす。合成は、 と の射の合成を の射とすることで定め、恒等射は の射とする。
集合 に、成分ごとの順序
(各成分の は整数の通常の大小)を入れた半順序集合を考える。これを上のように圏とみなしたとき、この圏の射の総数(恒等射も含める)を求めよ。
この問題で使うもの
- 圏の定義と有限の圏(説明と入口の問題)
この問題を解けるようになるまで(4 技能)
読み込み中…
右端(太枠)がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る(前提が先)
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
技能「圏の定義と有限の圏」を使う。半順序集合を圏とみなしたとき、射の総数は となる順序対 の個数に等しい。
ヒント 2
は「 かつ 」なので、成分ごとに数えて積の法則を使える。
ヒント 3
で となる組は 個である。 で となる組を数え、掛け合わせる。
答えと解説
答えを見る
どこでつまずきましたか?(選ぶと、戻る場所を案内します)
解説を読む
方針. 半順序集合を圏とみなすと、 から への射は のときちょうど つ、それ以外は 個である。したがって射の総数は、 を満たす順序対 ( も含む)の個数に等しい。
1. 数えるものを言い換える. , とすると、 は「 かつ 」である。第 1 成分の条件と第 2 成分の条件は独立に選べるので、積の法則が使える。
2. 第 1 成分. で となる組 は の 個。
3. 第 2 成分. で となる組 は
の 個。
4. 積の法則. となる順序対 の個数は 。
よって射の総数は である(内訳は、恒等射が対象の個数と同じ 個、恒等射でない射が 個)。
別解
射の総数は を満たす順序対 の個数に等しい。成分ごとの順序なので、 となる対の個数は、第 1 成分で となる の個数と、第 2 成分で となる の個数の積である。
第 1 成分: の 個。第 2 成分: の 個(一般に 元の全順序では )。よって 。
検算: 対象は 個。恒等射が 個。 の対の個数は で、各 について 以上の元の個数を数える: :6, :4, :2, :3, :2, :1。合計 で一致。