📂集合論

同値類, 商集合

定義 ¹

集合 $X$ 上で 同値関係 $R$ が定義されているとしよう。$x \in X$ に対して $x / R := \left\{ y \in X : y R x \right\}$ を $x$ の 同値類と呼ぶ。与えられた $X$ のすべての同値類を集めた集合を $X / R := \left\{ x / R : x \in X \right\}$ と表す。

このとき $X / R$ を $R$ による $X$ の 商集合^{the quotient set of $X$ of $R$} といい、$X$ modulo^{[モジュロ]} $R$ と読む。

説明

表現はやや汚く見えるが、例を考えれば全く難しい概念ではない。自然数集合 $\mathbb{N}$ 上で $3$ で割った余りが等しければ同値とし、$x,y \in \mathbb{Z}$ が同値なら $x \equiv y \pmod{3}$ のように表すことにしよう。$5,7$ は $3$ で割った余りがそれぞれ $2,1$ なので同値でないが、$11,17$ は $3$ で割った余りが $2$ になるので $11 \equiv 17 \pmod{3}$ のように書ける。 $$ 1 \equiv 4 \equiv 7 \equiv 10 \equiv \cdots \pmod{3} \\ 2 \equiv 5 \equiv 8 \equiv 11 \equiv \cdots \pmod{3} \\ 3 \equiv 6 \equiv 9 \equiv 12 \equiv \cdots \pmod{3} $$ 上の計算からわかるように $1$ の同値類は $( 1 / \equiv) = \left\{ 1, 4, 7, 10, \cdots \right\}$ であり、$2$ の同値類は $(2 / \equiv) = \left\{ 2, 5, 8, 11, \cdots \right\}$ であり、$3$ の同値類は $(3 / \equiv) = \left\{ 3, 6, 9, 12, \cdots \right\}$ である。$3$ より大きい数からは上の三つの同値類が繰り返されるため、したがって $$ (\mathbb{N} / \equiv) = \left\{ 1 / \equiv , 2 / \equiv , 3 / \equiv \right\} $$ 上の例から確認できるように、同値類は次のような常識的な性質を持つ。

基礎性質

• [1] $x / R \ne \emptyset$
• [2] $ x / R \cap y / R \ne \emptyset \iff xRy$
• [3] $x/R = y/R \iff x R y$
• [4] $x / R \cap y / R \ne \emptyset \iff x/R = y/R $

証明

[1]

$R$ は $X$ 上の同値関係なので 反射性 によりすべての $x \in X$ に対して $x R x$ であり、$x \in x / R$ でなければならない。

■

戦略 [2][3]: $x,y$ と別の $z$ を一つ取って同値関係の 対称性 と 推移性 を利用して式を結びつける。

[2]

$x/R$ と $y/R$ は空集合でなく $X$ 上の同値関係なので $x/R \cap y/R \ne \emptyset$ であり、これはある $z$ に対して $$ \begin{align*} & z \in x / R \land z \in y / R \\ \iff & z R x \land z R y \\ \iff & x R z \land z R y \\ \iff & x R y \end{align*} $$ であることと同値である。

■

[3]

$( \implies )$ $x/R = y/R$ ならば $x/R \cap y/R \ne \emptyset$ なので [2] により $x R y$

---

$( \impliedby )$ $x R y$ ならばすべての $z \in x / R$ に対して $z R x$ である。$x R y$ なので $R$ の推移性により $z R y$ であり、$z \in y / R$ である。整理すると $$ z \in x / R \implies z \in y / R $$ 集合 の包含関係の形に書き換えると $$ x / R \subset y / R $$ 同様の方法で $ y / R \subset x / R$ を得られるので $$ x / R = y / R $$

■

[4]

三段論法 により [2] と [3] から $$ x / R \cap y / R \ne \emptyset \iff xRy \iff x/R = y/R $$

■