大学数学

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

同値関係

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

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


◆定義

集合 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 が成り立つとき、xy 同値であるという。

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


順序の定義と似ていますが、異なるのは3番目の条件で、反対称律に代わり対称律となっています。対称律はおおよそ xy が「等しければ」、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 と関係する元がないからです。

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


◇例1

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

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



◇例2

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

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

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

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

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

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

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

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

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

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



◇例3

平面から原点を除いた集合 \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} で、

(x_1,y_1) = k( x_2,y_2), (x_2,y_2) = l( x_3,y_3)

となり、

(x_1,y_1)=kl(x_3,y_3)

と書けます。

k \neq 0, l \neq 0 より kl \neq 0 ですから、推移律は成り立っています。

対称律
\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) であるとすると、\exists k \in \mathbb{R} で、

(x_1,y_1) = k( x_2,y_2)

ですから、

(x_2,y_2) = \frac{1}{k} (x_1,y_1)

となるので、成り立っています。

以上から、確かに \sim同値関係となっています。


 

集合 その12へ>

<集合 その10へ

記事一覧(大学数学)に戻る

関連記事

  1. 大学数学

    集合.16 集合の濃度.1 濃度の定義と比較方法

    有限集合と無限集合、濃度直観的に意味がわかると思うのでここまで…

  2. 大学数学

    論理記号.1 よく使う論理記号一覧、命題

    論理記号とは~数学を記述する上での基本言語~数学においてよく使…

  3. 大学数学

    論理記号.3 すべての、~が存在する

    \( \forall \) すべての、任意の集合 \( X \…

  4. 大学数学

    集合.23 ツォルンの補題

    ツォルンの補題代数学などにおいてよく用いられる選択公理と同値な…

  5. 大学数学

    写像.3 写像の合成

    写像の合成高校数学で合成関数というものをやったかと思いますが、…

  6. 大学数学

    論理記号.5 論理演算

    論理演算前回までで一通りよく使う論理記号については押さえました…

コメント

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

アーカイブ

  1. 大学数学

    大学数学概説.4 大学3、4年生レベルの科目(幾何)
  2. 大学数学

    集合.4 共通集合と和集合(n個の場合)
  3. 大学数学

    論理記号.4 ~がただ一つ存在する、定義
  4. 大学数学

    集合.13 同値類と集合の分割
  5. 大学数学

    集合.10 直和(非交和、無縁和)
PAGE TOP
error: Content is protected !!