同値関係

定義 1..6   集合$A$の直積集合 $A \times A$の部分集合$F$が与えられているとする．$x,y \in A$であって $(x,y) \in F$であるとき，$x \sim y$と書き，$x$と$y$は$\sim$という関係にあるという．特に，次の３つの条件を満たすものを同値関係(equivalence relation)という．

1. 反射律(reflexive)$a \sim a$
2. 対称律(symmetric) $a \sim b \Rightarrow b \sim a$
3. 推移律(transitive) $a \sim b, b \sim c \Rightarrow a \sim c$

$\sim$を同値関係とする．$A$の元$a$に同値である$A$の元全体を$C_{a}$で表して，$C_{a}$を$a$の同値類(equivalence class)といい，$a$を同値類$C_{a}$の代表元という．

定理 1..5   $\sim$を$A$上の同値関係とする．すべての同値類から１つずつ元を選んで集めた集合を$\Gamma$とする．このとき，全ての $a,b \in \Gamma$に対して， $C_{a} \cap C_{b} = \phi$ならば， $${A = \cup_{a \in \Gamma}C_{a}}$$と表せる．逆に， $${A = \cup_{a \in \Gamma}C_{a}\ \mbox{かつ}\ a \neq b\ (a,b \in \Gamma)}$$ ならば $A$上に同値関係を構築することができる．

つまり，$A$上に同値関係があれば，もとの集合$A$は同値類 $C_{a}\ (a \in \Gamma)$によって分割される．このことを集合$A$は同値関係$\sim$によって類別されるといい，$\Gamma$をこの同値関係$\sim$の完全代表系という

問 1..7   $n$は１より大きい整数， $a, b \in {\mathcal Z}$に対して， $a \sim b \Leftrightarrow a \equiv b\ ($mod$\ n)$と定義すると，$\sim$は同値関係であることを示せ．また，同値類$C_{a}$を求めよ．このとき，$C_{a}$は剰余類という．

$n$を法とする剰余類の集合を ${\mathcal Z}_{n}$で表すと，

$${\mathcal Z}_{n} = \{C_{0}, C_{1}, \ldots, C_{n-1}\}$$

問 1..8   $C_{a} = C_{a'} \ \Leftrightarrow a \equiv a'\ ($mod$\ n)$を示せ．

例 1..1   4を法とする剰余類の集合 ${\mathcal Z}_{4}$を考える．

$${\mathcal Z}_{4} = \{C_{0}, C_{1}, C_{2}, C_{3}\}$$

$C_{2} = \{x \in {\mathcal Z} : x \equiv 2\ ($mod${4})\} = \{2 + 4k: k \in {\mathcal Z}\}$と表せるので，$C_{2}$と書く代わりに$\bar{2}$で表すことにする．すると， ${\mathcal Z}_{4} = \{\bar{0}, \bar{1}, \bar{2}, \bar{3}\}$と表せる．

問 1..9   $n$を法とする剰余類の集合 ${\mathcal Z}_{n} = \{\overline{0}, \overline{1}, \ldots, \overline{n-1}\}$には， ${\mathcal Z}$の演算から自然に演算が導入される．すなわち， ${\mathcal Z}_{n} \times {\mathcal Z_{n}}$の元 $(\overline{a},\overline{b})$に ${\mathcal Z_{n}}$の元 $\overline{a+b}$を対応させると写像を与えることを示せ．

例題 1..5   剰余類の集合 ${\mathcal Z}_{n}$は上で定めた加法 $\overline{a} + \overline{b} = \overline{a+b}$により群になる．

(G1) $\forall \overline{a}, \overline{b}, \overline{c} \in {\mathcal Z}_{n},\ \overli... ... \overline{(a+b)} + \overline{c} = (\overline{a} + \overline{b}) + \overline{c}$
(G2) $\exists \overline{0}, \forall \overline{a} \in {\mathcal Z}_{n}, \ \overline{a} + \overline{0} = \overline{0} + \overline{a} = \overline{a}$
(G3) $\forall \overline{a},\ \exists \overline{-a},\ \overline{a} + \overline{-a} = \overline{-a} + \overline{a} = -\overline{a} + \overline{a} = \overline{0}$