圏論の問題

難易度 3大学院入試の専門科目の標準レベル大学院数学圏論

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

$P = {a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}}$ とする。 $P$ 上の半順序 $\leq$ は、反射律による $c \leq c$ $(c \in P)$ と、次の $6$ つの関係だけからなるものとする。
$a_{0} \leq b_{0}, a_{1} \leq b_{0}, a_{1} \leq b_{1}, a_{2} \leq b_{1}, a_{2} \leq b_{2}, a_{0} \leq b_{2}$
（これら以外の異なる $2$ 元の間には順序関係はない。）

$F_{13} = Z /13 Z$ を $13$ 個の元からなる有限集合とみなす。関手 $F : P \to FinSet$ を、すべての対象 $c \in P$ に対して $F (c) = F_{13}$ とし、恒等射を恒等写像に、恒等射以外の $6$ 本の射を次の写像に移すものとして定める（ $x \in F_{13}$ であり、べきは $F_{13}$ の乗法で計算する）。
$F (a_{0} \leq b_{0}) F (a_{1} \leq b_{1}) F (a_{2} \leq b_{2}) : x \mapsto x^{2}, : x \mapsto x^{4}, : x \mapsto x^{3}, F (a_{1} \leq b_{0}) F (a_{2} \leq b_{1}) F (a_{0} \leq b_{2}) : x \mapsto x^{3}, : x \mapsto x^{2}, : x \mapsto x^{4} .$

$FinSet$ における $F$ の極限 $lim F$ と余極限 $colim F$ （いずれも同型を除いて一意に定まる有限集合）の要素の個数を、この順に組 $(∣ lim F ∣, ∣ colim F ∣)$ で求めよ。

この問題で使うもの

圏の定義と有限の圏（説明と入口の問題）
有限集合の圏の極限（説明と入口の問題）
有限集合の圏の余極限（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

極限は両立する元の族の集合、余極限は「各元とその像を辺で結んだグラフ」の連結成分の集合として計算する。 $b_{i}$ の成分は $a_{i}$ の成分から決まる。どの像にも入らない元も $1$ つの成分になることに注意する。

ヒント 2

$0$ を別に扱ったうえで、 $F_{13}^{\times}$ の生成元 $2$ を使って $x = 2^{e}$ とおき、 $Z /12$ 上の問題に直す。極限は連立合同式 $2 e_{0} \equiv 3 e_{1}, 4 e_{1} \equiv 2 e_{2}, 3 e_{2} \equiv 4 e_{0} (mod 12)$ の解の個数に $1$ を足したものになり、 $mod 3$ と $mod 4$ に分けて数えられる。

ヒント 3

極限では $0$ でない解が $3 \times 4 = 12$ 個ある。余極限では、 $0$ がつくる $1$ 成分のほか、 $Y_{i}$ の元のうち像に入らない孤立点が計 $16$ 個ある。 $X_{0}$ は $mod 3$ の $3$ 類、 $X_{1}$ は $1$ 類、 $X_{2}$ は偶奇の $2$ 類にまとまるので、それらが $Y$ の像を共有してどうつながるかを調べる。

答えと解説

答えを見る

(13, 21)

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

解説を読む

極限の計算. $FinSet$ での極限は、両立する元の族 $(x_{c})_{c \in P} \in \prod_{c} F (c)$ （すべての $c \leq d$ で $F (c \leq d) (x_{c}) = x_{d}$ をみたすもの）全体の集合である。 $b_{0}, b_{1}, b_{2}$ の成分は $a_{0}, a_{1}, a_{2}$ の成分から決まるので、 $lim F$ は
$x_{0}^{2} = x_{1}^{3}, x_{1}^{4} = x_{2}^{2}, x_{2}^{3} = x_{0}^{4} (x_{i} \in F_{13})$
をみたす $(x_{0}, x_{1}, x_{2})$ 全体と全単射に対応する（ $x_{i}$ は $a_{i}$ の成分）。

(i) どれかが $0$ のとき： $x_{0} = 0 \Rightarrow x_{1}^{3} = 0 \Rightarrow x_{1} = 0 \Rightarrow x_{2}^{2} = 0 \Rightarrow x_{2} = 0$ 。同様に $x_{1} = 0$ なら $x_{0}^{2} = 0$ から $x_{0} = 0$ 、 $x_{2} = 0$ なら $x_{1}^{4} = 0$ から $x_{1} = 0$ となるので、解は $(0, 0, 0)$ の $1$ 個。

(ii) すべて $0$ でないとき： $2^{6} = 64 \equiv - 1 (mod 13)$ より $2$ の位数は $12$ で、 $2$ は巡回群 $F_{13}^{\times}$ の生成元である。 $x_{i} = 2^{e_{i}}$ （ $e_{i} \in Z /12$ ）とおくと条件は
$2 e_{0} \equiv 3 e_{1}, 4 e_{1} \equiv 2 e_{2}, 3 e_{2} \equiv 4 e_{0} (mod 12) .$
中国剰余定理により $Z /12 ≅ Z /3 \times Z /4$ なので、 $mod 3$ と $mod 4$ に分けて数える。
- $mod 3$ ：第 1 式 $2 e_{0} \equiv 0$ より $e_{0} \equiv 0$ 。第 2 式 $e_{1} \equiv 2 e_{2} \equiv - e_{2}$ 。第 3 式 $0 \equiv e_{0}$ は成立。解は $(0, - t, t)$ の $3$ 個。
- $mod 4$ ：第 3 式 $3 e_{2} \equiv 0$ より $e_{2} \equiv 0$ 、このとき第 2 式 $0 \equiv 2 e_{2}$ も成立。第 1 式 $2 e_{0} \equiv 3 e_{1}$ に $3^{- 1} \equiv 3$ を掛けて $e_{1} \equiv 6 e_{0} \equiv 2 e_{0}$ 。解は $(s, 2 s, 0)$ の $4$ 個。

よって $0$ でない解は $3 \cdot 4 = 12$ 個。合わせて $∣ lim F ∣ = 1 + 12 = 13$ 。

余極限の計算. $FinSet$ での余極限は、直和 $∐_{c} F (c)$ を「 $z \in F (c)$ と $F (c \leq d) (z) \in F (d)$ を同一視する」関係で生成される同値関係で割った商集合である。したがって、 $6$ 個のコピー $X_{i} = F (a_{i})$ , $Y_{i} = F (b_{i})$ の元をすべて頂点とし、各 $z \in X_{i}$ とその像を辺で結んだグラフの連結成分の個数が $∣ colim F ∣$ である（どの像にも入らない $Y_{i}$ の元も $1$ 点だけの連結成分として数える）。

$0$ は $0$ にのみ移り、 $0$ 以外は $0$ 以外に移るので、 $6$ 個のコピーの $0$ はちょうど $1$ つの連結成分をなす。

残りは $x = 2^{e}$ の指数 $e \in Z /12$ で考える。辺は次の通りである。
$X_{0} ∋ e \mapsto 2 e \in Y_{0}, 4 e \in Y_{2}; X_{1} ∋ e \mapsto 3 e \in Y_{0}, 4 e \in Y_{1}; X_{2} ∋ e \mapsto 2 e \in Y_{1}, 3 e \in Y_{2} .$

*どの像にも入らない $Y$ の元（孤立点）*：
- $Y_{0}$ の像は ${0, 2, 4, 6, 8, 10} \cup {0, 3, 6, 9}$ の $8$ 個なので、孤立点は ${1, 5, 7, 11}$ の $4$ 個。
- $Y_{1}$ の像は ${0, 4, 8} \cup {0, 2, 4, 6, 8, 10}$ の $6$ 個なので、孤立点は $6$ 個。
- $Y_{2}$ の像は ${0, 4, 8} \cup {0, 3, 6, 9}$ の $6$ 個なので、孤立点は $6$ 個。

孤立点は計 $16$ 個である。

* $X$ の元を含む連結成分*：
- $X_{0}$ ： $2 e = 2 e^{'} ⟺ e \equiv e^{'} (mod 6)$ 、 $4 e = 4 e^{'} ⟺ e \equiv e^{'} (mod 3)$ なので、 $X_{0}$ の元は $e mod 3$ による $3$ 類 $C_{0}, C_{1}, C_{2}$ にまとまる。それぞれの像は
- $C_{0} = {0, 3, 6, 9}$ ： $Y_{0}$ で ${0, 6}$ 、 $Y_{2}$ で ${0}$
- $C_{1} = {1, 4, 7, 10}$ ： $Y_{0}$ で ${2, 8}$ 、 $Y_{2}$ で ${4}$
- $C_{2} = {2, 5, 8, 11}$ ： $Y_{0}$ で ${4, 10}$ 、 $Y_{2}$ で ${8}$
- $X_{1}$ ： $Y_{0}$ を通じて $mod 4$ で、 $Y_{1}$ を通じて $mod 3$ で結ばれるので、全体が $1$ つにつながる。像は $Y_{0}$ で ${0, 3, 6, 9}$ 、 $Y_{1}$ で ${0, 4, 8}$ 。 $Y_{0}$ の ${0, 6}$ を共有するので $C_{0}$ とつながる。
- $X_{2}$ ： $Y_{1}$ を通じて $mod 6$ で、 $Y_{2}$ を通じて $mod 4$ で結ばれるので、偶数・奇数の $2$ 類に分かれる。
- 偶数の $e$ の像は $Y_{1}$ で ${0, 4, 8}$ 、 $Y_{2}$ で ${0, 6}$ 。 $Y_{1}$ の ${0, 4, 8}$ を通じて $X_{1}$ とつながる。
- 奇数の $e$ の像は $Y_{1}$ で ${2, 6, 10}$ 、 $Y_{2}$ で ${3, 9}$ 。 $Y_{1}$ の他の像 ${0, 4, 8}$ とも、 $Y_{2}$ の他の像 ${0}, {4}, {8}, {0, 6}$ とも共通部分がないので、独立した成分になる。
- $C_{1}$ の像 ${2, 8} \subset Y_{0}$ , ${4} \subset Y_{2}$ と $C_{2}$ の像 ${4, 10} \subset Y_{0}$ , ${8} \subset Y_{2}$ は、 $X_{1}$ の $Y_{0}$ での像 ${0, 3, 6, 9}$ にも $X_{2}$ の $Y_{2}$ での像 ${0, 3, 6, 9}$ にも含まれず、互いにも交わらないので、それぞれ独立した成分になる。

したがって、 $0$ 以外の元で $X$ の元を含む成分は $C_{0} \cup X_{1} \cup X_{2}^{偶}$ , $C_{1}$ , $C_{2}$ , $X_{2}^{奇}$ の $4$ 個である。

以上より $∣ colim F ∣ = 1 + 4 + 16 = 21$ 。

答え： $(13, 21)$

別解

極限。 $lim F$ は組 $(x_{a_{0}}, x_{a_{1}}, x_{a_{2}}, x_{b_{0}}, x_{b_{1}}, x_{b_{2}})$ で、各射について $F$ の値が整合するものの集合である。 $b$ 成分は $a$ 成分から決まるので、 $(u, v, w) = (x_{a_{0}}, x_{a_{1}}, x_{a_{2}})$ が次を満たす場合を数えればよい。
$u^{2} = v^{3}, v^{4} = w^{2}, w^{3} = u^{4} .$

- 一つでも $0$ なら、 $u = 0 \Rightarrow v = 0$ 、 $v = 0 \Rightarrow w = 0$ 、 $w = 0 \Rightarrow v = 0 \Rightarrow u = 0$ となり、すべて $0$ である。これは解 $1$ 個。
- すべて非零のとき、 $F_{13}^{\times}$ は位数 $12$ の巡回群なので、原始根 $g$ を用いて $u = g^{p}, v = g^{q}, w = g^{r}$ （ $p, q, r \in Z /12$ ）と書く。条件は次の三つになる。
$2 p \equiv 3 q, 4 q \equiv 2 r, 3 r \equiv 4 p (mod 12) .$
- 第 1 式から $q$ は偶数。 $q = 2 s$ と書くと $p \equiv 3 s (mod 6)$ で、 $q$ ごとに $p$ は $2$ 通り。
- 第 3 式の両辺は、 $3 r$ が $3$ の倍数、 $4 p$ が $4$ の倍数なので、等しいなら $12$ の倍数である。よって $r \equiv 0 (mod 4)$ かつ $p \equiv 0 (mod 3)$ 。 $p \equiv 3 s (mod 6)$ より $p$ は $3$ の倍数なので、後者は自動的に成り立つ。
- 第 2 式から $r \equiv 2 q = 4 s (mod 6)$ 。これと $r \equiv 0 (mod 4)$ から、 $r$ は $mod 12$ で一意に定まる。
- したがって $q$ が $6$ 通り、 $p$ が $2$ 通り、 $r$ が $1$ 通りで $12$ 個。

よって $∣ lim F ∣ = 12 + 1 = 13$ 。

余極限。 $colim F$ は $6 \times 13 = 78$ 点の非交和を、 $(a, x) \sim (b, F (a \leq b) x)$ から生成される同値関係で割ったものである。つまり、この関係を辺としたグラフの連結成分の個数を数える。

$x = 0$ の点は六角形 $a_{0} - b_{0} - a_{1} - b_{1} - a_{2} - b_{2} - a_{0}$ を通してすべて連結なので、成分は $1$ 個。
非零の点は指数 $Z /12$ で表す。各 $a$ の点はちょうど 2 つの $b$ の点と辺でつながるので、 $b$ の点 $36$ 個を頂点、 $a$ の点を辺とするグラフの連結成分を数えればよい。辺は次の通り。
$E_{0}$ : $(b_{0}, 2 p) - (b_{2}, 4 p)$
$E_{1}$ : $(b_{0}, 3 q) - (b_{1}, 4 q)$
$E_{2}$ : $(b_{1}, 2 r) - (b_{2}, 3 r)$
どの辺にも現れない孤立点は次の通り。
$b_{0}$ : $m \in {1, 5, 7, 11}$ の $4$ 個。
$b_{1}$ : 奇数 $n$ の $6$ 個。
$b_{2}$ : $k \in {1, 2, 5, 7, 10, 11}$ の $6$ 個。
合計 $16$ 個の成分。
残りの $20$ 頂点について、辺から成分を求める。
$E_{1}$ : $b_{0} \in {0, 3, 6, 9}$ と $b_{1} \in {0, 4, 8}$ が完全二部グラフになる。
$E_{2}$ : ${b_{1} : 0, 4, 8}$ と ${b_{2} : 0, 6}$ が連結、 ${b_{1} : 2, 6, 10}$ と ${b_{2} : 3, 9}$ が連結。
$E_{0}$ : $(b_{0}, 0) - (b_{2}, 0)$ 、 $(b_{0}, 6) - (b_{2}, 0)$ は既存の成分内の辺。ほかに ${b_{0} : 2, 8} - {b_{2} : 4}$ と ${b_{0} : 4, 10} - {b_{2} : 8}$ が現れる。
したがって非孤立の成分は次の $4$ 個で、頂点数は $9 + 3 + 3 + 5 = 20$ となり一致する。
${b_{0} : 0, 3, 6, 9; b_{1} : 0, 4, 8; b_{2} : 0, 6}$
${b_{0} : 2, 8; b_{2} : 4}$
${b_{0} : 4, 10; b_{2} : 8}$
${b_{1} : 2, 6, 10; b_{2} : 3, 9}$

非零部分の成分は $16 + 4 = 20$ 個、零の成分と合わせて $∣ colim F ∣ = 21$ 。

答えは $(13, 21)$ 。

この問題の確認

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

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

確認の方法について

間違いを報告する

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