圏論の問題

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

0 以上の整数 $n$ に対して $[n] = {0, 1, \dots, n}$ を通常の順序で全順序集合とみなし、対象を $[n] (n \geq 0)$ 、射を（広義）単調写像とする圏を $Δ$ とする。単体的集合とは関手 $X : Δ^{op} \to Set$ のことで、 $X_{n} = X ([n])$ とおき、 $X_{n}$ の要素を $n$ -単体という。 $n \geq 1$ と $0 \leq i \leq n - 1$ に対して、全射単調写像 $σ_{i} : [n] \to [n - 1]$ を
$σ_{i} (j) = {j j - 1 (j \leq i) (j \geq i + 1)$
で定める。 $x \in X_{n}$ が退化しているとは、ある $0 \leq i \leq n - 1$ と $y \in X_{n - 1}$ により $x = X (σ_{i}) (y)$ と書けることをいい、そうでない単体を非退化という（ $0$ -単体はすべて非退化）。

0 以上の整数 $p$ に対して $Δ [p] = Hom_{Δ} (-, [p])$ とし（ $θ : [m] \to [n]$ に対して $Δ [p] (θ) (f) = f \circ θ$ ）、単体的集合 $X, Y$ の積 $X \times Y$ を $(X \times Y)_{n} = X_{n} \times Y_{n}$ 、 $(X \times Y) (θ) = X (θ) \times Y (θ)$ で定める。

0 以上の整数 $p, q$ に対して、単体的集合 $Δ [p] \times Δ [q]$ は、 $n > p + q$ ならば非退化 $n$ -単体をもたず、非退化 $(p + q)$ -単体をちょうど $(p p + q)$ 個もつことを示せ。

この問題で使うもの

単体的集合と非退化単体（説明と入口の問題）
単体的集合の積の非退化単体（説明と入口の問題）
組合せ（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$Δ [p] \times Δ [q]$ の $n$ -単体は単調写像の組 $(f, g)$ 、すなわち $[n]$ から積順序集合 $[p] \times [q]$ への単調写像だと見て、「退化している」を $f, g$ の値の条件に言い換える。

ヒント 2

単調写像 $f$ が $f^{'} \circ σ_{i}$ と書けるのは $f (i) = f (i + 1)$ のときに限る。これを $f$ と $g$ に同じ $i$ で使うと、非退化 $⟺$ $(f (j), g (j))$ が $[p] \times [q]$ の狭義増加列、となる。

ヒント 3

狭義増加列では各ステップで成分の和 $a + b$ が少なくとも 1 増える。和は $0$ 以上 $p + q$ 以下なので、長さの上限と、上限に達するとき列が $(0, 0)$ から $(p, q)$ への格子路になることがわかる。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

単調写像 $f$ について $f = f^{'} \circ σ_{i}$ と書けることと $f (i) = f (i + 1)$ が同値であることを、 $f^{'}$ を具体的に構成して両方向とも示している（3 点）
積の単体 $(f, g)$ が退化することと、同じ $i$ で $f (i) = f (i + 1)$ かつ $g (i) = g (i + 1)$ となることの同値性を述べ、非退化を $[p] \times [q]$ の狭義増加列として言い換えている（2 点）
成分の和が各ステップで 1 以上増えることから、 $n > p + q$ の非退化単体がないことを導いている（2 点）
$n = p + q$ のとき列が $(0, 0)$ から $(p, q)$ へ 1 成分ずつ 1 増える格子路になることを示し、どのステップで第 1 成分が増えるかの選び方との全単射（逆向きの構成を含む）で個数 $(p p + q)$ を得ている（3 点）

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

模範解答を読む

$X = Δ [p] \times Δ [q]$ とおく。定義より $X_{n}$ の要素は単調写像の組 $(f, g)$ （ $f : [n] \to [p]$ , $g : [n] \to [q]$ ）であり、 $X (σ_{i}) (f^{'}, g^{'}) = (f^{'} \circ σ_{i}, g^{'} \circ σ_{i})$ である。

ステップ 1（補題）. $n \geq 1$ , $0 \leq i \leq n - 1$ とし、 $r \geq 0$ とする。単調写像 $f : [n] \to [r]$ について、ある単調写像 $f^{'} : [n - 1] \to [r]$ により $f = f^{'} \circ σ_{i}$ と書けるための必要十分条件は $f (i) = f (i + 1)$ である。

（証明） $f = f^{'} \circ σ_{i}$ なら $σ_{i} (i) = σ_{i} (i + 1) = i$ より $f (i) = f^{'} (i) = f (i + 1)$ 。逆に $f (i) = f (i + 1)$ のとき、 $f^{'} (k) = f (k) (k \leq i)$ 、 $f^{'} (k) = f (k + 1) (k \geq i + 1)$ と定める。 $f^{'}$ は $f$ を $[n] ∖ {i + 1}$ に制限したものを順序を保って番号を付け直したものなので単調である。 $j \leq i$ なら $f^{'} (σ_{i} (j)) = f^{'} (j) = f (j)$ 、 $j = i + 1$ なら $f^{'} (σ_{i} (i + 1)) = f^{'} (i) = f (i) = f (i + 1)$ 、 $j \geq i + 2$ なら $f^{'} (σ_{i} (j)) = f^{'} (j - 1) = f (j)$ （ $j - 1 \geq i + 1$ のため）。よって $f = f^{'} \circ σ_{i}$ 。 $□$

補題の $f^{'}$ の作り方は $i$ だけで決まるので、 $f (i) = f (i + 1)$ かつ $g (i) = g (i + 1)$ なら同じ $i$ で $(f, g) = (f^{'} \circ σ_{i}, g^{'} \circ σ_{i}) = X (σ_{i}) (f^{'}, g^{'})$ と書ける。逆に $(f, g) = X (σ_{i}) (f^{'}, g^{'})$ なら補題の必要性より $f (i) = f (i + 1)$ かつ $g (i) = g (i + 1)$ 。したがって
$(f, g) が退化 ⟺ ある i で (f (i), g (i)) = (f (i + 1), g (i + 1)) .$

ステップ 2（鎖による言い換え）. $[p] \times [q]$ に成分ごとの順序（ $(a, b) \leq (a^{'}, b^{'}) ⟺ a \leq a^{'}$ かつ $b \leq b^{'}$ ）を入れ、 $h (j) = (f (j), g (j))$ とおく。 $f, g$ が単調なので $h (0) \leq h (1) \leq \dots \leq h (n)$ 。ステップ 1 より、 $(f, g)$ が非退化 $⟺$ すべての $i$ で $h (i) \neq = h (i + 1)$ $⟺$ $h (0) < h (1) < \dots < h (n)$ （狭義増加列）。 $n = 0$ のときもこの言い換えは（条件が空なので）成り立つ。また $(f, g) \mapsto h$ は $X_{n}$ と「 $[n]$ から $[p] \times [q]$ への単調写像」全体との全単射である。

ステップ 3（ $n > p + q$ のとき）. $s (a, b) = a + b$ とおく。 $(a, b) < (a^{'}, b^{'})$ なら $a \leq a^{'}$ , $b \leq b^{'}$ で少なくとも一方は狭義なので $s (a^{'}, b^{'}) \geq s (a, b) + 1$ 。よって非退化 $n$ -単体に対し $s (h (n)) \geq s (h (0)) + n \geq n$ 。一方 $s (h (n)) \leq p + q$ 。ゆえに $n \leq p + q$ であり、 $n > p + q$ なら非退化 $n$ -単体は存在しない。

ステップ 4（ $n = p + q$ のとき）. 非退化 $(p + q)$ -単体に対し、 $p + q \geq s (h (n)) \geq s (h (0)) + n \geq p + q$ なので、すべて等号が成り立つ。すなわち $h (0) = (0, 0)$ 、 $h (n) = (p, q)$ であり、各 $j$ で $s (h (j + 1)) = s (h (j)) + 1$ 。 $h (j) < h (j + 1)$ で和が 1 だけ増えるので、 $h (j + 1)$ は $h (j)$ の第 1 成分か第 2 成分のちょうど一方に 1 を加えたものである。

そこで、非退化 $(p + q)$ -単体に、集合 $S = {j \in {0, \dots, p + q - 1} ∣ h (j + 1) の第 1 成分 = h (j) の第 1 成分 + 1}$ を対応させる。第 1 成分は $0$ から $p$ まで 1 ずつ増えるので $∣ S ∣ = p$ 。逆に $∣ S ∣ = p$ をみたす部分集合 $S \subset {0, \dots, p + q - 1}$ が与えられたとき、 $h (0) = (0, 0)$ から始めて、 $j \in S$ なら第 1 成分に、 $j \in / S$ なら第 2 成分に 1 を加えて $h (j + 1)$ を定めると、第 1 成分は合計 $p$ 、第 2 成分は合計 $q$ 増えるので値は $[p] \times [q]$ に収まり、 $h$ は狭義増加、すなわち（ステップ 2 より）非退化 $(p + q)$ -単体を与える。この 2 つの対応は互いに逆である（ $h$ は $h (0) = (0, 0)$ と各ステップでどちらの成分が増えるかで決まるため）。

よって非退化 $(p + q)$ -単体の個数は、 $p + q$ 元集合の $p$ 元部分集合の個数 $(p p + q)$ に等しい。

以上より、 $Δ [p] \times Δ [q]$ は $n > p + q$ の非退化 $n$ -単体をもたず、非退化 $(p + q)$ -単体をちょうど $(p p + q)$ 個もつ。 $■$

この問題の確認

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

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

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