同値関係と商集合

同値関係、同値類、代表元、商集合の定義を紹介し、商集合の例を挙げる。

同値関係の定義

定義(同値関係)
X を空でない集合とする。

{}^{\forall}x, y \in X に対し, x \sim y であるか, x \nsim y であるかが定められていて,

以下の3つの条件(i)\sim (iii)を満たすとき、2 項関係 \sim同値関係という。

(i) x \sim x     ( 反射律 )

(ii) x \sim y \Rightarrow y \sim x   (対称律)

(iii)x \sim y かつ y \sim z\Rightarrow x \sim z    (推移律)

同値類と代表元の定義

定義(同値類と代表元)
x \in X に対し,

[x] = \{y\in X \mid x \sim y\}

x同値類といい、x[x]代表元という。

商集合の定義

定義(商集合)
X/\sim\ =\ \{[x] \mid x\in X\}X\sim による商集合という。

例題

例題
\mathbb{Z} \ni n, m に対し,関係 \sim

n \sim m \Leftrightarrow n -m \in 3\mathbb{Z} で定める。

このとき, \sim は同値関係である。これを示せ。

 

証明の方針:

関係 \sim が上で述べた同値関係の定義をみたしていることを確かめればよい。

(i) \sim (iii) の順に示す。

解答例

{}^{\forall}n.m.l \in \mathbb{Z} をとる。

(i) n - n = 0 = 3\cdot 0 \in3\mathbb{Z}

より、n \sim n はよい。

(ii) n \sim m とする。

n - m \in 3\mathbb{Z} より、

n - m = 3k となる k\in\mathbb{Z} が存在する。

m - n = -3k = 3(-k) \in 3\mathbb{Z}      ( -k\in\mathbb{Z} より )

よって、m \sim n.

(iii) n \sim m, m \sim l とする。

n \sim m より,

n - m = 3k となる k\in\mathbb{Z} が存在する。

m \sim l より、

m - l = 3s となる s\in \mathbb{Z} が存在する。

n - l = (n - m) + ( m - l )

= 3k + 3s

=3(k + s)

\in 3\mathbb{Z}              ( k + s \in \mathbb{Z} より )

よって, n \sim l.

以上より, \sim は同値関係である。

商集合の具体的な記述

\mathbb{Z}\sim による商集合 \mathbb{Z}/\sim は?

[0] = \{\cdots,-6,-3,0,3,6,\cdots\}

[1] = \{\cdots,-5,-2,1,4,7,\cdots\}

[2] =\{\cdots,-4,-1,2,5,8,\cdots\}

であるから,

\mathbb{Z}\sim による商集合 \mathbb{Z}/\sim

\mathbb{Z}/\sim\ =\ \{\ [0], [1], [2]\ \}.

である。