大学数学

集合.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. 大学数学

    集合.10 直和(非交和、無縁和)

    直和(非交和、無縁和)◆Def.SetTop.2.…

  2. 大学数学

    集合.4 共通集合と和集合(n個の場合)

    共通集合集合 \( A,B \) の共通集合を次のように定義し…

  3. 大学数学

    集合.18 集合の濃度.3 連続体濃度を持つ集合

    非可算集合可算濃度 \( \aleph_0 \) よりも濃度が…

  4. 大学数学

    写像.13 集合の準同型定理、引き起こされる写像

    集合の準同型定理Prop.SetTop.3.12.1.を応用す…

  5. 大学数学

    論理記号.2 否定、かつ、または、~ならば、同値記号

    \( \lnot \) 否定\( P \) を命題とすると、\…

  6. 大学数学

    集合.6 共通集合と和集合(一般の場合)

    共通集合と和集合(一般の場合)添字集合と集合族の概念を使って、…

コメント

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

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

アーカイブ

  1. 大学数学

    集合.17 集合の濃度.2 可算集合
  2. 大学数学

    写像.11 直和の普遍性
  3. 大学数学

    集合.11 二項関係.1 順序
  4. 大学数学

    集合.21 上界、下界、上限、下限、最大元、最小元、極大元、極小元
  5. 大学数学

    写像.8 単射の性質
PAGE TOP
error: Content is protected !!