同値関係

整数での$\bmod$演算などで，今までもでてきましたが$X$上の関係$R$が特に 次をみたすとき$R$は$X$上の同値関係と言います． （1）$X$の任意の元$x \in X$について $xRx$

$$(\forall x \in X)((xRx) \Rightarrow yRx)$$

　「自分自身は友達」 （2）$X$の任意の二つの元$x \in X$,$y \in X$について$xRy$ならば$yRx$

$$(\forall x \in X)(\forall y \in X)(xRy \Rightarrow yRx )$$

　「君が僕の友達なら，僕は君の友達」 （3）$X$の任意の三つの元$x,y,z \in X$について$xRy$かつ$yRz$ならば $xRz$

$$(\forall x \in X) (\forall y \in X) (\forall z \in X) ((xRy ~and~ yRz ) \Rightarrow xRz )$$

「友達の友達は，友達だ」 $xRy$を「$x$と$y$は（関係$R$について）同値」などと言います．

$$\Delta = \{ (x,x)\vert x \in X\}$$

とおき，写像のグラフと同様に

$$R^{ - 1} = \{ (y,x)\vert(x,y) \in R\}$$

$$R \cdot R = \{ (x,z)\vert(\exists y)((x,y) \in R ~and~ (y,z) \in R)\}$$

とすると上の条件 は以下の(1') ,(2') ,(3') と同じです．

$$\begin{eqnarray*} &&(1'）\Delta \subseteq R \\ 　 &&(2'）R = R^{ - 1}　\\ &&(3'）R \cdot R \subseteq R \end{eqnarray*}$$

[証明]

（1） $\Leftrightarrow$（1'）については $xRx$が$(x,x) \in R$の別表現でしたから

$$\begin{eqnarray*} &&(\forall x \in X)(xRx ) \Leftrightarrow (\forall x \in X)((... ...\Delta \Rightarrow w \in R) \Leftrightarrow \Delta \subseteq R \end{eqnarray*}$$

(2) $\Leftrightarrow$（2'）については
まず（2）を仮定すれば，
　$X$の元$x,y$を任意にとると

$$\begin{eqnarray*} &&(x,y) \in R \Leftrightarrow xRy \\ && xRy \Rightarrow yRx... ...) \in R \\ && (y,x) \in R \Leftrightarrow (x,y) \in R^{ - 1} \end{eqnarray*}$$

となるので

$$(\forall w)(w \in R \Rightarrow w \in R^{ - 1} )$$

すなわち　 $R \subseteq R^{ - 1}$
全く同様に

$$R^{ - 1} \subseteq R$$

よって　

$$(2')\ R = R^{ - 1}$$

　 が成立．
逆に（2’）を仮定すれば，
$X$の元$x,y$を任意にとると

$$\begin{eqnarray*} &&xRy \Leftrightarrow (x,y) \in R \\ &&(x,y) \in R \Leftr... ...rightarrow (y,x) \in R \\ &&(y,x) \in R \Leftrightarrow yRx \end{eqnarray*}$$

すなわち

$$(2) \ (\forall x \in X) (\forall y \in X) (xRy \Rightarrow yRx )$$

が成立．

(3） $\Leftrightarrow$（3'）についてはまず（3）を仮定すれば，
$X$の元$x,z$を任意にとると

$$\begin{eqnarray*} &&(x,z) \in R \cdot R \Leftrightarrow (\exists y)((x,y) \in R... ...d ~yRz \Rightarrow xRz \\ && xRz \Leftrightarrow (x,z) \in R \end{eqnarray*}$$

となるので

$$(\forall w)(w \in R \cdot R \Rightarrow w \in R)$$

すなわち　

$$(3')\ R \cdot R \subseteq R$$

　が成立．
逆に（3’）を仮定すれば，
$X$の元$x,y,z$を任意にとると

$$\begin{eqnarray*} &&xRy ~and~yRz \Leftrightarrow (x,y) \in R ~and~(y,z) \in R \... ...n R \cdot R \\ &&(x,z) \in R \cdot R \Rightarrow (x,z) \in R \end{eqnarray*}$$

となり，$x,y,z$を任意は任意にとったので

$$(3）\ (\forall x \in X) (\forall y \in X) (\forall z \in X) ((xRy ~and~yRz ) \Rightarrow xRz$$

が成立．

[証明終り]

問題

1. $X=\{ a,b,c \}$ とするとき $R=\{ (a,a),(a,b),(b,a),(b,b),(c,c) \}$ は同値関係の例です．他の例を作ってください．
   

2. $X=Z$　$Z$は整数全体の集合
   
   $$R = \{ (n,m)\vert m \in Z ~and~n \in Z ~and~(\exists k \in Z)(n - m = 7k)\}$$
   
   
   とするとき$R$は同値関係であることを示して下さい．
   特にこの関係について$mRn$を $m \equiv n(\bmod 7)$で表します．