同値関係と商集合

15.同値関係

同値関係

集合\(A\)上の二項関係\(R(\subset A \times A)\)が同値関係:
\(\forall x,y,z\in A\)

1.\(x\equiv_Rx\)
2.\(x\equiv_Ry \rightarrow y\equiv_Rx\)
3.\(x\equiv_Ry \land y\equiv_Rz \rightarrow x\equiv_Rz\)

コメント

何を持って「同じ」とするかによって様々な同値関係が定義できる。
例えば相等関係\((=)\)や論理式の同値\((\Leftrightarrow )\)などは同値関係である。

同値類

\(A\)上の同値関係\(R\)に関する\(a(\in A)\)の同値類
\([a]_R = \{x\in A|x\equiv_R a\}\)

直感的説明

\([a]_R\)は\(a\)と同値な要素からなる集合

同値類の性質

次の\(3\)つははすべて互いの必要十分条件である

1.\(x\equiv _R y \)
2.\([x]_R=[y]_R\)
3.\([x]_R\cap[y]_R \neq \phi\)

証明

1\(\Rightarrow\)2
\(x\equiv_R y\)とする
\(a\in [x]_R\Leftrightarrow a\equiv_R x \Leftrightarrow a\equiv_Ry \Leftrightarrow a \in [y]_R\)
よって
\([x]_R=[y]_R\)

2\(\Rightarrow\)3
\([x]_R=[y]_R\)とする
\([x]_R\cap [y]_R=[x]_R \cap [x]_R=[x]_R\)
\(x\equiv_R x \Leftrightarrow x\in [x]_R\)より\([x]_R \neq \phi\)
よって
\([x]_R\cap [y]_R \neq \phi\)

3\(\Rightarrow\)1
\([x]_R \cap [y]_R\neq \phi\)とする
\(z\in [x]\cap [y]\)を満たす\(z\)がとれ
\(x\equiv_R z \land y\equiv_R z\)を満たすので
\(x\equiv_R y\)

よって\(1\Leftrightarrow 2 \Leftrightarrow 3\)

同値類別

\(A\)の任意の要素はどれかの同値類に属し、異なる同値類は同じ元を持たない。よって集合\(A\)は\(A\)上の同値類によって交わりなく分割できる

\(A=[a_1]_R\cup [a_2]_R...\cup [a_n]_R\)

\(([a_i]\cap[a_j]=\phi (i \neq j))\)

16.商集合

商集合

\(A\)上の同値関係\(R\)に対して商集合
\(A/R = \{[a]_R|a\in A\}\)

商集合は同値類(\(A\)の部分集合)を要素とする\(A\)の部分集合族である

注意

集合または集合族において同じ要素が複数ある場合、重複を除いて一つの要素として扱う。

例えば\(A=\{a_1,a_2\}  \)で\([a_1]=[a_2]\)なら\(A/R=\{[a_1]\}\)となる。この時適当に\(a_1\)を選んだが、この場合\(a_1\)をこの同値類の代表元という

完全代表系

各同値類から1つずつ代表元を取って集めたもの

集合\(\mathbb{Z}\)(整数全体の集合)に対して、\(\mathbb{Z}\)上の二項関係 \(R=\{(x,y)\in \mathbb{Z}^2|x-y\in 3\mathbb{Z}\}\)
(\(3\mathbb{Z}\)は整数で\(3\)の倍数の集合)

\(\forall x,y,z\in \mathbb{Z}\)に対して

1.\(x-x=0\in 3\mathbb{Z}\)
2.\(x-y\in 3\mathbb{Z} \rightarrow y-x=\in 3\mathbb{Z}\)
3.\((x-y\in 3\mathbb{Z} \land y-z\in 3\mathbb{Z})\rightarrow x-z \in 3\mathbb{Z}\)


が成り立つので\(R\)は\(\mathbb{Z}\)上の同値関係である
除法の定理から任意の整数は
\(x=3q+r \)     \((r=0,1,2\) \(q\in \mathbb{Z})\)
と表せるので
\(x-y=3(q_1-q_2)+(r_1-r_2)\)から
\(x〜_Ry\Leftrightarrow r_1=r_2\)である

同値類は代表元をそれぞれ\(0,1,2\)として
\([0]_R=\{...,-6,-3,0,3,6,...\}\)
\([1]_R=\{...,-5,-2,1,4,7,...\}\)
\([2]_R=\{...,-4,-1,2,5,8,...\}\)

分割 \(\mathbb{Z}=[0]_R\cup [1]_R\cup [2]_R\)

商集合 \(\mathbb{Z}/R=\{[0]_R,[1]_R,[2]_R\}\)

なお\(\{0,1,2\}\)や\(\{3,-2,5\}\)は\(R\)に関する完全代表系であるが\(\{0,1,2,3\}\)や\(\{0,1\}\)は完全代表系ではない