同値関係

定義 1..6   集合$A$の直積集合 $A \times A$の部分集合$F$が与えられているとする.$x,y \in A$であって $(x,y) \in F$であるとき,$x \sim y$と書き,$x$$y$$\sim$という関係にあるという.特に,次の3つの条件を満たすものを同値関係(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$上の同値関係とする.すべての同値類から1つずつ元を選んで集めた集合を$\Gamma$とする.このとき,全ての $a,b \in \Gamma$に対して, $C_{a} \cap C_{b} = \phi$ならば, $\displaystyle{A = \cup_{a \in \Gamma}C_{a}}$と表せる.逆に, $\displaystyle{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$は1より大きい整数, $a, b \in {\mathcal Z}$に対して, $a \sim b \Leftrightarrow a \equiv b\ ($mod$\ n)$と定義すると,$\sim$は同値関係であることを示せ.また,同値類$C_{a}$を求めよ.このとき,$C_{a}$剰余類という.

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

$\displaystyle {\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}$を考える.

$\displaystyle {\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}$