集合と関係 (11)同値関係
(二項)関係とは、2つの"もの"の間で成立、不成立が明確に定義されたものである。
$x~$と$~y~$に対して関係$~R~$が成立することを\[xRy\]と書き、$x~$と$~y~$に対して関係$~R~$が成立しないことを\[x\not Ry\]と書く。
集合$~X~$に対して、関係$~R~$が次の条件を満たすとき、$R~$は$~X~$における同値関係であるという。 \begin{align} (1)&~{}^{\forall}x\in X,xRx\\ (2)&~{}^{\forall}x,y\in X,xRy\Longrightarrow yRx\\ (3)&~{}^{\forall}x,y,z\in X,xRy~かつ~yRz\Longrightarrow xRz \end{align} これらの条件をそれぞれ反射律、対称律、推移律という。
$R~$を集合$~X~$における同値関係として、各元$~x\in X~$に対して、 \[ [x]_R:=\{y\in X\mid xRy\} \] と定め、$x~$の$~R~$による同値類という。
考えている同値関係$~R~$が明らかなときは、単に$~[x]~$とも書く。
$(1)~$
$R~$は反射律を満たすので、${}^{\forall}x\in X,xRx~$である。
よって、${}^{\forall}x\in X,x\in[x]_R~$となる。
$(2)~$
$x,y\in X~$をとり、$xRy~$とする。
$z\in[y]_R~$とすると、$yRz~$であり、$R~$は推移律を満たすので$~xRz~$である。
つまり、$z\in[x]_R~$となり、$[y]_R\subset[x]_R~$である。
対称律と仮定より、$yRx~$である。
あとは同様にして$~[x]_R\subset[y]_R~$となるので、$[x]_R=[y]_R~$である。
よって、$xRy\Rightarrow[x]_R=[y]_R~$となる。
$x,y\in X~$をとり、$[x]_R=[y]_R~$とする。
$(1)$より$~y\in[y]_R=[x]_R~$となり、$xRy~$である。
よって、$[x]_R=[y]_R\Rightarrow xRy~$となる。
$(3)~$
$x,y\in X~$をとり、$[x]_R\cap[y]_R\neq\emptyset~$と仮定する。
このとき、元$~z\in[x]_R\cap[y]_R~$がとれる。
$z\in[x]_R~$より$~xRz~$であり、$z\in[y]_R~$より$~yRz~$である。
対称律より$~zRy~$となり、推移律$~xRy~$となる。
よって、$(2)$より$~[x]_R=[y]_R~$である。