同値関係と集合の分割

同値関係と集合の分割（同値類）が 1 対 1 に対応することを使える。 $n$ 元集合上の同値関係の個数（ベル数 $B_{n} = \sum_{k} S (n, k)$ ）や、類の個数・大きさに条件のある同値関係の個数を求められる

前提

第 2 種スターリング数の漸化式と条件つき分割（大学数学離散数学・組合せ論）

説明

集合 $X$ 上の同値関係は、 $X$ の分割と 1 対 1 に対応します。分割とは、 $X$ を空でない互いに交わらない部分集合に切り分けることです。この対応を使うと、「同値関係を数える」問題を「分割を数える」問題に言い換えられます。その結果、 $n$ 元集合上の同値関係の個数はベル数 $B_{n} = \sum_{k = 1}^{n} S (n, k)$ で求まり、類の個数や大きさに条件がある同値関係も、対応する分割を数えれば求められます。

なぜそうしてよいのか

まず言葉を確認します。 $X$ 上の関係 $\sim$ が同値関係であるとは、次の 3 つが成り立つことです。反射律: すべての $a$ で $a \sim a$ 。対称律: $a \sim b$ ならば $b \sim a$ 。推移律: $a \sim b$ かつ $b \sim c$ ならば $a \sim c$ 。 $a$ の同値類を $[a] = {x \in X ∣ x \sim a}$ と定めます。 $X$ の分割とは、空でない部分集合（ブロック）の集まりで、どの 2 つも交わらず、合併が $X$ になるものです。

【同値関係 → 分割】反射律より $a \in [a]$ なので、各類は空でなく、類の合併は $X$ です。 $[a]$ と $[b]$ が共通の元 $c$ をもつとします。 $x \in [a]$ なら $x \sim a$ です。また $c \sim a$ と対称律から $a \sim c$ が成り立ち、 $c \sim b$ でもあります。推移律を 2 回使うと $x \sim b$ なので $[a] \subseteq [b]$ です。逆向きも同様なので $[a] = [b]$ となり、異なる類は交わりません。よって類の全体は分割です。さらに $a \sim b ⟺ [a] = [b]$ が成り立ちます。実際、 $a \sim b$ なら $a \in [a] \cap [b]$ なので、いま示したことから $[a] = [b]$ です。逆に $[a] = [b]$ なら $a \in [a] = [b]$ なので $a \sim b$ です。

【分割 → 同値関係】「 $a \approx b ⟺ a, b$ が同じブロックに入る」と定めます。反射律: 合併が $X$ なので $a$ はどれかのブロックに入り、 $a \approx a$ です。対称律: 定義が $a, b$ について対称です。推移律: $a \approx b$ なら $a, b \in P$ 、 $b \approx c$ なら $b, c \in Q$ となるブロック $P, Q$ があります。 $P$ と $Q$ はどちらも $b$ を含み、異なるブロックは交わらないので $P = Q$ です（ $b$ を含むブロックは 1 つしかない）。よって $a, c \in P$ となり、 $a \approx c$ です。

【往復すると元に戻る】分割から $\approx$ を作ると、その類 $[a]$ は「 $a$ と同じブロックに入る元の全体」、つまり $a$ を含むブロックそのものです。各ブロックは空でないので、どのブロックもある $[a]$ として現れ、元の分割に戻ります。逆に $\sim$ の類から $\approx$ を作ると、 $a \approx b ⟺ [a] = [b] ⟺ a \sim b$ なので、元の $\sim$ に戻ります。こうして 2 つの操作は互いに逆になり、同値関係と分割は 1 対 1 に対応します。この対応で「類の個数」は「ブロックの個数」に、「類の大きさ」は「ブロックの大きさ」に移ります。したがって類がちょうど $k$ 個の同値関係は $S (n, k)$ 個あり、全部で $B_{n} = \sum_{k = 1}^{n} S (n, k)$ 個です（ $n \geq 1$ ）。

手順

同値関係の条件を分割の言葉に翻訳する。「類が $k$ 個」は「 $k$ ブロック」に、「各類の大きさが〜」は「各ブロックの大きさが〜」に、「 $a \sim b$ 」は「 $a, b$ が同じブロック」に読み替える。
ブロック数だけが条件なら、必要な $S (n, k)$ を漸化式 $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ で表にして求める（ $S (n, 1) = S (n, n) = 1$ ）。
ブロックの大きさ $s_{1}, \dots, s_{k}$ が指定されているときは、まずブロックに番号をつけて $\frac{n !}{s _{1} ! \dots s _{k} !}$ 通りと数える。次に、同じ大きさのブロックが $m$ 個ある大きさごとに $m!$ で割る。大きさの異なるブロックは大きさで区別がつくので、その分は割らない。例: ${1, \dots, 5}$ で大きさ $2, 2, 1$ なら $\frac{5 !}{2 ! 2 ! 1 !} \div 2! = 15$ 。
条件を満たすブロック数（または大きさの型）ごとの個数を足し合わせる。条件がなければ $B_{n} = \sum_{k = 1}^{n} S (n, k)$ となる。

例題

5 元集合 $X = {1, 2, 3, 4, 5}$ 上の同値関係の個数を求めよ。

例題の解答

手順 1: 同値関係と $X$ の分割は 1 対 1 に対応するので、求める個数は $X$ の分割の個数に等しい。ブロック数 $k = 1, \dots, 5$ ごとに数えると、それぞれ $S (5, k)$ 個ある。

手順 2: 漸化式 $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ で表を作る（ $k = 1, 2, \dots$ の順）。
$n = 1$ : $1$
$n = 2$ : $1, 1$
$n = 3$ : $1, 1 + 2 \cdot 1 = 3, 1$
$n = 4$ : $1, 1 + 2 \cdot 3 = 7, 3 + 3 \cdot 1 = 6, 1$
$n = 5$ : $1, 1 + 2 \cdot 7 = 15, 7 + 3 \cdot 6 = 25, 6 + 4 \cdot 1 = 10, 1$

（手順 3 の大きさの条件はないので使わない。）

手順 4: 足し合わせると $B_{5} = 1 + 15 + 25 + 10 + 1 = 52$ となる。和の両端の項も同値関係に対応しているので、忘れずに含める。 $k = 1$ はすべての元が互いに同値な関係、 $k = 5$ は等号の関係（ $a \sim b ⟺ a = b$ ）である。

したがって同値関係は $52$ 個。

答え: $52$

よくある誤り

ブロックに順番（ラベル）をつけたまま数えてしまう誤り。 ${1, 2, 3}$ で類が 2 個の同値関係を「各元を類 A・類 B に振り分ける全射」として $2^{3} - 2 = 6$ 個とするのは誤り。類にはラベルがないので、正しくは $6 \div 2! = 3 = S (3, 2)$ 個。
同じ大きさのブロックの入れ替え分を割り忘れる誤り。 ${1, 2, 3, 4}$ ですべての類が大きさ 2 の同値関係を $(2 4) = 6$ 個とするのは誤り。大きさ 2 のブロックが 2 個あるので、正しくは $(2 4) \div 2! = 3$ 個（ ${12∣34}, {13∣24}, {14∣23}$ ）。
大きさの異なるブロックまで入れ替え分で割ってしまう誤り。 ${1, 2, 3, 4}$ で類の大きさが 3 と 1 の同値関係を $\frac{4 !}{3 ! 1 !} \div 2! = 2$ 個とするのは誤り。大きさで区別がつくので割らず、正しくは $4$ 個（1 元だけの類をどれにするかで決まる）。
和の両端 $k = 1$ と $k = n$ を落とす誤り。 $B_{3}$ を $S (3, 2) = 3$ だけで済ませるのは誤り。全体が 1 類の関係と等号の関係も含めて、正しくは $B_{3} = 1 + 3 + 1 = 5$ 。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

有限位相と前順序の対応（大学数学集合と位相）