Relation and Partition(2)

관계와 분할(2)

앞서 관계의 정의와 역관계와 합성관계에 관한 몇 가지 정리들을 알아보았다.
관계를 더욱 풍성하게 만들어 줄 동치에 대해 알아보자.

2. 분할

2.1 [DEF] 분할의 정의

집합족(집합을 원소로 갖는 집합)을 이용해 분할을 정의한다.

(1) 분할 : $P$

집합 $X$의 부분집합의 집합 중, 다음 세 조건을 만족하는 집합족을 분할 $P$라 정의한다. $P := { \; A \; | \; A \subset X \; }$

1. 공집합을 원소로 하지 않는다. $\; \forall A \in P, A \neq \emptyset\; $
2. $X$를 덮는다. $\; \cup P = X$
3. 서로소 집합족이다. $\; \forall A_1, A_2 \in P, \; A_1 \cup A_2 = \emptyset \vee A_1 = A_2 $
   
   위에서 ‘덮는다‘는 말은 분할 $P$의 모든 원소의 합집합이 $X$가 된다는 뜻이다.
   알고리즘에서의 disjoint set 자료구조를 알고있다면 분할과 그 뉘앙스가 비슷함을 느낄 수 있을 것이다.

(2) 동치류 : $E_x$

$E$가 집합 $X$ 위에서의 동치관계일 때, $x \in X$의 동치류를 다음과 같이 정의한다. \(E_x = \{\, y \in X \, | _xE_y \,\}\) 즉, $x$의 동치류란 동치관계 $E$에 의해 $x$와 관계가 있는 원소들을 모두 모은 것이다.
$E$이 동치관계이기 때문에 모인 동치류의 원소 $y$들은 모두 $x$에 대해 반사적이고 대칭적이고 추이적이다.

(3) 상집합 : $X/E$

집합 $X$의 모든 동치류의 집합(족) \(X/E = \{\, E_x \, | x \in X \, \}\) 동치관계 $E$에 의한 모든 동치류들을 모은 집합을 $E$에 의한 $X$의 상집합이라 한다.
즉, $X$의 모든 원소 $x$마다 $E$에 의해 존재하는 동치류 $E_x$를 전부 모든 것이다.

(4) 분할 $P$에 의한 관계 : $R_p = X/P$

\(R_p = \{\, (x, y) \, | \, \exists A, \; x, y \in A \, \}\) 한편, 집합 $X$에서의 분할 $P$가 있을 때, 같은 분할 내의 원소들 끼리의 관계를 떠올릴 수 있는데, 이를 ‘분할에 의한 관계’ 라 하고 위와 같이 정의한다.
표기법이 (3)번의 상집합과 동일한 것을 알 수 있는데, 이러한 표기법을 이용한 분할에 의한 관계와 상집합 간의 독특한 정리 역시 살펴볼 수 있다.

2.2 [THM] 여러 가지 정리

2.2.1 동치관계 $E$

공집합이 아닌 집합 $X$위의 동치관계 $E$에 대하여 다음이 성립한다.

1. $E_x \neq \emptyset$
2. $E_x = E_y \Leftrightarrow \ _x E_y$
3. $E_x \cap E_y \neq \emptyset \Leftrightarrow \ _x E_y$
4. $X/E$는 $X$의 분할이다.

[PROOF]

1. 가정에 따라 공집합이 아닌 집합 $X$에는 원소가 존재한다. 정의에 의해 동치관계 $E$는 반사성을 띄고, 따라서 존재하는 원소 $x$가 동치류 $E_x$ 안에 포함됨을 알 수 있다. 그러므로 $E_x$는 공집합이 될 수 없다.
   
   \(\begin{aligned} X \neq \emptyset &\Rightarrow \exists x \in X \\ 동치관계\; E &\Rightarrow \forall x \in X, \; {}_x E_x \quad (Reflexive) \\ \therefore x \in E_x &\rightarrow \neg \emptyset \quad \square \end{aligned}\)

2. 충분조건과 필요조건을 각각 증명하자.
   • $E_x = E_y \Rightarrow {}_x E_y$
     \(\begin{aligned} \forall x \in E_x &\Rightarrow x \in E_y \quad \because E_x = E_y \\ &\Leftrightarrow {}_y E_x \quad \because E_y := \{x \; |\; {}_y E_x \} \\ &\Rightarrow {}_x E_y \quad \because 대칭관계 \quad \square \end{aligned}\)
     
     
   • ${}_x E_y \Rightarrow E_x = E_y\quad$ [전략] $E_x \subset E_y \wedge E_y \subset E_x$
     
     By Definition, $ {}_x E_y \Rightarrow {}_y E_x \quad \because (Symmetric) $
     
     If $z \in E_x$,
     \(\begin{aligned} z \in E_x &\Leftrightarrow {}_x E_z \quad \because (Def)\\ &\Rightarrow {}_y E_z \quad \because {}_y E_x \wedge {}_x E_z \Rightarrow {}_y E_x \; (Transive) \\ &\Leftrightarrow z \in E_y \quad \therefore E_x \subset E_y \end{aligned}\)
     
     If $z \in E_y$,
     \(\begin{aligned} z \in E_y &\Leftrightarrow z \in E_x \quad \therefore E_y \subset E_x \end{aligned}\)
3. 역시 양쪽 화살표를 각각 증명하자.
   • 동치관계의 대칭성과 추이성을 이용해 다음을 보일 수 있다.
     \(\begin{aligned} E_x \cap E_y \neq \emptyset &\Leftrightarrow \exists z, \; z \in E_x \wedge z \in E_y \\ &\Leftrightarrow \exists z, \; {}_x E_z \wedge {}_y E_z \\ &\Rightarrow \exists z, \; {}_x E_z \wedge {}_z E_y \\ &\Rightarrow {}_x E_y \end{aligned}\)
     
   • 앞서 증명한 (1번)과 (2번)을 이용해 다음을 보일 수 있다.
     
     \(\begin{aligned} {}_x E_y &\Rightarrow E_x = E_y \quad \because (2.) \\ &\Rightarrow E_x \cap E_y \neq \emptyset \quad \because (1.) \end{aligned}\)
4. 세 단계에 걸쳐 증명해보자.
   • $X/E$는 공집합을 원소로 갖지 않는다.
     \(\begin{aligned} &E_x \neq \emptyset \quad \because (1.) \\ &\therefore \; X/E = \{E_x\} \nsupseteq \emptyset \\ \end{aligned}\)
     
   • $X/E$는 서로소 집합족이다.
     \(\begin{aligned} if \; E_x \cap E_y \neq \emptyset , \quad E_x \cap E_y \neq \emptyset &\Rightarrow {}_x E_y \quad \because (3.) \\ &\Rightarrow E_x = E_y \quad \because (2.) \\ \therefore E_x \neq E_y &\Rightarrow E_x \cap E_y = \emptyset \end{aligned}\)
     
   • [전략] $\cup X/E \subseteq X \wedge X \subseteq \cup X/E $
     (1) $X$의 동치류가 $X$보다 작거나 같음은 자명하다.
     \(\begin{aligned} \cup X/E \subseteq X \quad \because Trivial \end{aligned}\)
     
     (2) $E$는 반사적이므로, 모든 원소 $x$에 대해 동치관계 ${}_x E_x$를 만족하는 동치류 $E_x$가 존재한다. 따라서 모든 $x$는 상집합 $X/E$의 원소로서 존재한다.
     \(\begin{aligned} \forall x \in X, \; \exists x \in X/E, \; st \; x \in E_x \\ \therefore X \subseteq \cup X/E \quad \square \end{aligned}\)

[THM] 2.2.2 집합 $X$의 분할 $P$

공집합이 아닌 집합 $X$의 분할 $P$에 대하여 다음이 성립한다.

1. $R_p$는 $X$ 상의 동치관계이다.
2. $X/R_p = P$

[PROOF]

1. $R_p$가 $X$ 위에서 반사적이고, 대칭적이고, 추이적임을 보이면 된다.
   
   • $R_p$는 반사적이다.
     \(\begin{aligned} \forall x \in X, \; \exists A \subset P, \; st \; x \in A \quad &\because(Def \; of \; Partition) \\ \therefore \; {}_x R_p \, {}_x \quad &\because (Def \; of \; R_p) \end{aligned}\)
     
   • $R_p$는 대칭적이다.
     \(\begin{aligned} \forall(x, \, y) \in R_p \Rightarrow \exists A \subset P, \; st \; (x, \, y) \in A \\ \therefore (y, \, x) \in R_p \quad \because (Def \; of \; R_p) \end{aligned}\)
     
   • $R_p$는 추이적이다.
     \(\begin{aligned} &\forall x, \, y, \, z \in X, \; Let \; {}_x R_p \, {}_y \wedge {}_y R_p \; {}_x \\ &\Rightarrow \exists A, \, B \subset P \; st \; x, \, y \in A \; and \; y, \, z \in B \\ &\Rightarrow A = B \quad \because (y가 \; 공통. \; Def \; of \; Partition) \\ &\Rightarrow {}_x R_p \, {}_z \quad \because (x, \, y, \, z \in A. \; Def \; of \; R_p) \\ \end{aligned}\)
2. 위에서 $R_p = E$ 임을 보였으므로 이를 이용하면 된다.
   \(\begin{aligned} R_p = E \quad \because 2.2.2.1. \\ \Rightarrow X/R_p = X/E = P \quad \because 2.2.1.4. \end{aligned}\)

이로부터 다음과 같은 표기도 가능하다.
\(\begin{aligned} &Notate \quad R_p = X/p \\ &X/R_p = X/(X/P) = P \end{aligned}\)

3. 연습문제

1. 공집합이 아닌 집합 $X$ 위의 동치관계 $E$에 대하여 $X/(X/E)=E$ 임을 증명하시오.
   [ANS]
   \(\begin{aligned} &X/E = P \quad \because 2.2.1.4. \\ &X/(X/E) = X/P = R_p = E \quad \because 2.2.2.1. \end{aligned}\)