집합론, 그 열두 번째 이야기 | 동치류

 

앞선 동치관계의 글에서, 집합 $X$위의 동치관계 $\sim$ 는 같다의 성질을 잘 가짐을 알았다.

 

어떤 집합 $X$와 그 위의 동치관계 $\sim$이 주어질 때,

$x \in X$ 에 대한 동치류(Equivalence calss) $\overline{x}$ 는 다음처럼 정의되는 집합이다.

$$\overline{x}=\left \{ x' \in X : x \sim x' \right \}$$

또한, 이 때 $x$를 $\overline{x}$의 대표원(Representative) 이라고 한다.

 

이 때, $a, b \in X$ 와 $X$ 위의 동치관계 $~$에 대해 다음 세 가지 명제는 동치이다.

$1.\; a \sim b$      $2.\; \overline{a} = \overline{b}$      $3.\; \overline{a} \cap \overline{b} \neq \varnothing$

증명은 아래와 같다

 

Part 1. $a \sim b \Rightarrow \overline{a} = \overline{b}$

 

$\forall x \in \overline{a},\;x \sim a$임은 정의에 의해 자명하다. 또, $a\sim b$ 이므로 동치관계의 추이성에 의해

$$x\sim a \wedge a \sim b \Rightarrow x\sim b$$ 따라서 $x \sim b$ 이므로 $x \in \overline{b}$, $$\therefore \overline{a} \subseteq \overline{b}$$

$\forall y \in \overline{b},\;y \sim b$임은 정의에 의해 자명하다. 또, $a \sim b$ 이므로 동치관계의 대칭성에 의해 $b \sim a$, 그러므로 $$y \sim b \wedge b \sim a \Rightarrow y \sim a$$ 따라서 $y \sim a$ 이므로 $y \in \overline{a}$ $$\therefore \overline{b} \subseteq \overline{a}$$

 

$\therefore\;\; \overline{a} = \overline{b}$

 

Part 2. $\overline{a} = \overline{b} \Rightarrow \overline{a} \cap \overline{b} \neq \varnothing$

 

$\overline{a} = \overline{b}$ 이므로 $\overline{a} \cap \overline{b} = \overline{a}$이고, 동치관계의 반사성에 의해 $$a \sim a \Rightarrow \overline{a} \neq \varnothing$$

 

$\therefore\;\; \overline{a} \cap \overline{b} = \overline{a} \neq \varnothing$

 

Part 3. $\overline{a} \cap \overline{b} \neq \varnothing \Rightarrow a \sim b$

 

$\overline{a} \cap \overline{b} \neq \varnothing$ 이므로 $\exists x \in X\;s.t.\;\left ( x \in \overline{a} \wedge x \in \overline{b} \right )$

정의에 의해, $x \in \overline{a} \Rightarrow x \sim a$이고, $x \in \overline{b} \Rightarrow x \sim b$

동치관계의 추이성에 의해, $$a \sim x \wedge x \sim b \Rightarrow a \sim b$$

 

$\therefore\;\; a \sim b$

 

 

또, 이러한 동치류들을 모아놓은 집합을 몫집합(Quotient set) 이라 하고, 아래처럼 쓸 수 있다.

$$X/ \sim \;= \left \{ \overline{x} : x \in X \right \}$$

$X/ \sim$ 은 집합 $X$위의 동치관계 $\sim$에 대한 몫집합이라는것을 의미한다.

몫집합은 상집합이라고 부르기도 한다.