圏論の問題

難易度 2大学院の講義の演習問題レベル大学院数学圏論

半順序集合 $(Q, \leq)$ は、対象を $Q$ の元とし、 $p \leq q$ のときに限り $p$ から $q$ への射がちょうど $1$ つ存在する（それ以外のときは射が存在しない）圏とみなす。

集合 $X = {1, 2, 3, 4}$ の部分集合全体を包含関係 $\subseteq$ で順序づけた半順序集合を圏とみなしたものを $P$ とし、 $3$ つの元からなる全順序集合 ${0 < 1 < 2}$ を圏とみなしたものを $3$ とする。

関手 $F : 3 \to P$ の個数を求めよ。ただし、2 つの関手は、対象への対応と射への対応がともに一致するときに限り同じとみなす。

この問題で使うもの

関手と関手の数え上げ（説明と入口の問題）
圏の定義と有限の圏（説明と入口の問題）

この問題を解けるようになるまで（8 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

半順序集合を圏とみなすと、2 対象の間の射は高々 1 つである。このとき関手は対象の対応だけで決まるかどうか、また対象の対応にどんな条件が必要かを考える。

ヒント 2

関手 $3 \to P$ は、 $A_{0} \subseteq A_{1} \subseteq A_{2} \subseteq X$ を満たす部分集合の列 $(A_{0}, A_{1}, A_{2})$ と 1 対 1 に対応する。

ヒント 3

列を数えるには、 $X$ の各元 $x$ について「 $x$ が初めて属する $A_{i}$ の番号 $i$ 、またはどれにも属さない」のどれかを選ぶと考えればよい。各元の選び方が何通りあるかを数える。

答えと解説

答えを見る

256

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

関手は単調写像と同じ　半順序集合を圏とみなすと、任意の 2 対象の間の射は高々 $1$ つである。関手 $F : 3 \to P$ は、各対象 $i$ に対象 $F (i)$ を、各射 $i \to j$ （ $i \leq j$ ）に射 $F (i) \to F (j)$ を対応させる。

射 $i \to j$ の行き先として射 $F (i) \to F (j)$ が存在しなければならないので、 $i \leq j$ ならば $F (i) \subseteq F (j)$ が必要である。
逆に、対象の対応 $i \mapsto A_{i}$ が $i \leq j \Rightarrow A_{i} \subseteq A_{j}$ を満たせば、射 $i \to j$ を（ただ $1$ つの）射 $A_{i} \to A_{j}$ に送ることで射の対応が一意に決まる。恒等射は恒等射に、合成は合成に送られる（ $P$ の $A_{i}$ から $A_{k}$ への射は $1$ つしかないので、等式は自動的に成り立つ）。

したがって、関手は対象の対応だけで決まり、その個数は
$A_{0} \subseteq A_{1} \subseteq A_{2} \subseteq X$
を満たす部分集合の列 $(A_{0}, A_{1}, A_{2})$ の個数に等しい（真部分集合である必要はない）。

列の数え上げ　各元 $x \in X$ について、 $x$ がどの $A_{i}$ に属するかは、「 $x$ が初めて属する番号」
$m (x) = min {i : x \in A_{i}} \in {0, 1, 2} または x \in / A_{2}$
で決まる。 $A_{0} \subseteq A_{1} \subseteq A_{2}$ なので、 $x \in A_{i}$ となるのは $i \geq m (x)$ のときに限るからである。逆に各元にこの $4$ 通りの状態を任意に割り当てれば、条件を満たす列がただ $1$ つ定まる。

よって列の個数は、 $4$ 個の元それぞれに $4$ 通りを割り当てる方法の数で
$4^{4} = 256$

答え: $256$

別解

半順序集合の圏の間の関手は、順序を保つ写像（単調写像）と同じである。対象の対応 $F (0) = A, F (1) = B, F (2) = C$ が決まれば、各射は一意に決まり、 $0 \leq 1 \leq 2$ から $A \subseteq B \subseteq C$ が必要十分条件となる（恒等射・合成は自動的に保たれる）。したがって関手の個数は、 $X$ の部分集合の列 $A \subseteq B \subseteq C$ の個数に等しい。

各元 $x \in X$ について、 $x$ が最初に現れる位置は「 $A$ から」「 $B$ から」「 $C$ から」「どれにも現れない」の 4 通りで、元ごとに独立に選べる。これが列と 1 対 1 に対応するので、個数は $4^{4} = 256$ 。

検算：一般に $n$ 元集合では $4^{n}$ 個。 $n = 1$ のとき、 ${\emptyset \subseteq \emptyset \subseteq \emptyset}$ など単調列は $\emptyset, {1}$ の 2 元の全順序から 3 項の単調列で $(1 3 + 1) = 4$ 個で一致する。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる