集合.12　二項関係.2　同値関係

ホーム
大学数学, 集合と位相
集合.12　二項関係.2　同値関係

大学数学

2018.06.15

同値関係

前回、二項関係として恒等関係（＝）や合同関係（≡）などを挙げました。これらは数の相等であれ、図形の合同であれ、合同式としての相等であれ、ある種の「等しい」という性質を持つものです。

一般の集合に対して、「等しい」という性質が満たすべき条件を一般化したものが同値関係になります。

◆定義

集合 $X$ 上の二項関係 $\sim$ が同値関係であるとは、次を満たすことを言う。

・反射律
$\forall x \in X, x \sim x$

・推移律
$\forall x,y,z \in X, ((x \sim y) \land ( y \sim z )) \Rightarrow ( x \sim z )$

・対称律
$\forall x,y \in X, ( x \sim y ) \Rightarrow ( y \sim x )$

$x \sim y$ が成り立つとき、 $x$ と $y$ は同値であるという。

$x$ と $y$ が同値でないとき、 $x \not \sim y$ と書く。

順序の定義と似ていますが、異なるのは３番目の条件で、反対称律に代わり対称律となっています。対称律はおおよそ $x$ と $y$ が「等しければ」、 $y$ と $x$ も「等しい」というような意味合いのことを言っていて、これが同値関係特有の性質なわけです。

注意：対称律と推移律が成り立てば反射律も成り立つような気分になってしまう人もいるのですが、それは誤りです。

実際、対称律は

$\forall x,y \in X, ( x \sim y ) \Rightarrow ( y \sim x )$

と言っていて、これを $z=x$ とした場合の推移律

$\forall x,y \in X, ((x \sim y) \land ( y \sim x )) \Rightarrow ( x \sim x )$

と合わせると、

$\forall x,y \in X, ( x \sim y ) \Rightarrow ( x \sim x )$

が言えます。しかし、これと反射律は同じものではありません。

仮定が成立しないケース（そもそも $x \sim y$ となるような $x,y$ が存在しない）場合が考えられるからです。

実際、簡単な例で推移律、対称律を満たすが反射律を満たさないものを構成してみましょう。

$X = \{ 1,2,3 \}$ とし、二項関係 $G(R)$ を $G(R) = \{ (1,1),(1,2),(2,1),(2,2) \}$ とします。すなわち、 $1R1,1R2,2R1,2R2$ が成り立っています。

これは反射律を満たしません。なぜなら、 $3$ と関係する元がないからです。

一方で、推移律、対称律は満たしています。

◇例１

既に例として何度も挙げていますが、任意の集合 $X$ について、集合の元として等しいという恒等関係 = は同値関係です。これは（そもそも同値関係が＝をモデルケースにしていることからも）明らかですが、同値関係であるかどうかを確かめるには、定義に立ち戻って反射律、推移律、対称律が成り立つことを確かめればよいです。

図形としての合同関係 ≡ も、 $X$ を図形全体の集合だと思えば、上の恒等関係の特別な場合だと考えることができます。

◇例２

$n$ を正の自然数とし、 $\mathbb{Z}$ 上の同値関係 $\sim_n$ を次のように定めます。

$\forall a,b \in \mathbb{Z}$ とするとき、
$a \sim_n b \overset{\mathrm{def}}{\Leftrightarrow} a-b$ は $n$ の倍数である

これが確かに同値関係になっていることを確かめましょう。

・反射律
$\forall a \in \mathbb{Z}$ とすると、
$a-a=0$ は $n$ の倍数なので、 $\sim_n$ の定義から $a \sim_n a$ が成り立ちます。

・推移律
$\forall a,b,c \in \mathbb{Z}$ とすると、
$a-b$ と $b-c$ が $n$ の倍数であるとき、
$a-c = (a-b) + (b-c)$ は $n$ の倍数同士の和なので $n$ の倍数です。よって成り立ちます。

・対称律
$\forall a,b \in \mathbb{Z}$ とすると、
$a-b$ が $n$ の倍数であるとき、
$b-a = -(a-b)$ は $n$ の倍数です。よって成り立ちます。

以上から、確かに $\sim_n$ は $\mathbb{Z}$ 上の同値関係になっています。

高校数学で、一部の方は合同式というのを習ったかと思います。

$a \sim_n b$ は普通、 $a \equiv b \, \bmod n$ と書くのでした。

$a-b$ が $n$ の倍数であるということは、 $a$ と $b$ を $n$ で割った余りは等しいことを意味しています。

◇例３

平面から原点を除いた集合 $\mathbb{R}^2 \verb|\| \{ (0,0) \}$ 上に次の二項関係 $\sim$ を定めます。

$\forall (x_1,y_1),(x_2,y_2) \in \mathbb{R}^2 \verb|\| \{ (0,0) \}$ に対して、
$(x_1,y_1) \sim (x_2,y_2) \overset{\mathrm{def}}{\Leftrightarrow} \exists k \in \mathbb{R} \verb|\| \{ 0 \}, (x_1,y_1)=k(x_2,y_2)$

これは $\mathbb{R}^2 \verb|\| \{ (0,0) \}$ 上の同値関係になっています。

このことを確かめてみましょう。

・反射律
$\forall (x,y) \in \mathbb{R}^2 \verb|\| \{ (0,0) \}$ に対して、 $(x,y) = 1*(x,y)$ なので成り立っています。

・推移律
$\forall (x_1,y_1),(x_2,y_2),(x_3,y_3) \in \mathbb{R}^2 \verb|\| \{ (0,0) \}$ に対して、
$(x_1,y_1) \sim (x_2,y_2)$ かつ $(x_2,y_2) \sim (x_3,y_3)$ であるとすると、 $\exists k,l \in \mathbb{R}$ で、