[집합론] 동치류, 동치류의 집합과 분할

사실 벤 다이어그램은 사용을 지양하는 것이 좋다

 

동치류와 동치류의 집합

 

동치류는 집합 위에서 동치관계가 정의될 때, 어떤 원소와 동치관계에 있는 원소들의 집합을 말한다.

 

 

즉, 집합 $X$ $($단, $X\neq \emptyset$$)$와 $X$ 위에서 정의된 동치관계 $\sim \subseteq (X \times X)$에서,

$X$의 각 원소 $x$에 대해 $x$의 동치류는 $x/\sim = \left\{y | (x, y) \in \sim\right\}$ 으로 정의된다. 

 

 

동치류의 집합은 $($당연하게도$)$ 이러한 동치류들을 모두 모아놓은 집합이다. 

즉, 집합 $X$의 동치류의 집합은 $X/\sim = \left\{x/\sim | x \in X  \right\}$으로 나타낼 수 있다. 

 

 

 

ex) 집합 $X = \left\{1,2,3\right\}$을 생각해보자.

$X$의 한 동치관계 $\sim = \left\{\left\{1,1 \right\}, \left\{1,2 \right\}, \left\{2,1 \right\}, \left\{2,2 \right\}, \left\{3,3 \right\} \right\}$로 정의하자. 

 

$X$의 원소 중 1의 동치류는 $\left\{1,2 \right\}$, 2의 동치류는 $\left\{1,2 \right\}$, 3의 동치류는 $\left\{3 \right\}$이다.

그리고 $X$의 동치류의 집합은 $X/\sim = \left\{\left\{1,2 \right\}, \left\{ 3\right\} \right\}$ 이다.

 

 

그런데 동치류의 집합의 모습을 잘 살펴보자. 익숙하지 않은가?

 

잘 모르겠다면, 분할 $($partiton$)$, 동치관계에 대한 글을 먼저 읽어보자.

https://hellworld.tistory.com/9

https://hellworld.tistory.com/13

 

 

 

 

동치류의 집합은 분할이다

 

사실 어떤 집합의 동치류의 집합은 분할이다. 이 글에서는 이 명제를 증명하려 한다.

 

$($복습$)$ 분할의 정의

우선 분할의 정의를 다시 떠올려보자.

분할은 어떤 집합을 겹치지 않고 나누는 부분집합들의 집합이다. 

 

어떤 집합 $\left\{B_{i} \right\}$가 집합 $X$의 분할이기 위해서는 다음 세 조건을 만족해야 한다.

 

1. $\forall B_{i} \in \left\{B_{i} \right\} \neq \emptyset$, 즉 $\left\{B_{i} \right\}$의 모든 원소는 공집합이 아니다.

2. If $i \neq j$ then $B_{i} \cap B_{j} = \emptyset$, 즉 서로 다른 $\left\{B_{i} \right\}$의 원소는 겹치지 않는다.

3. $\cup_{i}B_{i} = X$, 즉 $\left\{B_{i} \right\}$의 모든 원소의 합집합은 원래 집합 $X$를 만든다.

 

 

동치류의 집합이 분할이라는 것을 보이기 위해서는, 동치류의 집합이 분할의 세 조건을 모두 만족한다는 것을 보여야 한다. 이제, 동치류의 집합은 분할이 되기 위한 각각의 조건을 만족한다는 것을 보일 것이다. 

 

공집합이 아닌 집합 $X$와 $X$의 동치류의 집합 $X/\sim$을 생각해보자.

 

 

조건 1 만족

WTS : 동치류의 집합의 모든 원소는 공집합이 아니다.

즉, 모든 동치류는 공집합이 아니다. 

 

$\forall x \in X$에 대해 $x$의 동치류 $x/\sim = \left\{y | (x, y) \in \sim \right\}$이다.

이때, 동치관계는 reflexive 이므로 적어도 $(x, x) \in \sim$이다. 

따라서 적어도 $x \in x/\sim$ 이므로, 모든 동치류는 공집합이 아니다.

 

따라서 동치류의 집합의 모든 원소는 공집합이 아니다. 

 

 

조건 2 만족

WTS : 동치류의 집합의 원소 중 서로 다른 원소는 공통 원소를 갖지 않는다.

즉, 서로 다른 동치류는 겹치지 않는다.

 

귀류법을 이용해서 증명할 수 있다.

가정 : 동치류의 집합의 서로 다른 두 원소 $B, C$와 $X$의 한 원소 $p$에 대해 $p \in (B \cap C)$라 하자.

즉, 서로 다른 동치류가 하나의 공통 원소를 갖는다고 가정하였다.

 

$B = \left\{y | (b, y) \in \sim \right\}$, $C = \left\{y | (c, y) \in \sim \right\}$라고 하자.

가정에 의해 $p \in (B \cap C)$, 즉, $p \in B$ 이고 $p \in C$이다.

따라서 $(b, p) \in \sim$이고, $(c, p) \in \sim$이다. 

이때, $\sim$은 동치관계이므로 symmetric 하기 때문에 $(p, c) \in \sim$도 성립한다.

그런데 $\sim$은 또한 transitive하므로 $(b, p) \in \sim$이고 $(p, c) \in \sim$이면 $(b, c) \in \sim$이다.

 

즉 $(b, c) \in \sim$이므로 $B = C$이다. 

왜냐하면, $(x, b) \in \sim$을 만족하는 모든 $x$는 $(x, c) \in \sim$을 만족하기 때문이다. 

 

결국 서로 다른 동치류 $B, C$가 서로 같다는 결론이 도출되므로, 모순이 발생한다.

따라서 가정이 거짓임을 알 수 있으며, 서로 다른 동치류는 공통된 원소를 갖지 않는다는 사실을 보였다. 

 

 

조건 3 만족

WTS : 동치류의 집합의 모든 원소의 합집합은 원래 집합 $X$를 만든다. 

즉, $\cup X/\sim = X$이다. 그런데 두 집합이 같다는 것은 서로가 서로의 부분집합이라는 것으로도 나타낼 수 있다.

따라서 조건 3은 ① $\cup X/\sim \subseteq X$와 ② $X \subseteq \cup X/\sim$라는 것 두 명제를 보일 것이다. 

 

참고로 집합 $A$가 집합 $B$의 부분집합임을 보이기 위해서는, $A$의 모든 원소가 $B$의 원소임을 보이면 된다. 

 

 

① $\cup X/\sim \subseteq X$, 즉 동치류의 집합의 모든 원소의 합집합은 $X$의 부분집합임을 보이자.

즉, $\cup X/\sim$의 모든 원소가 $X$의 원소임을 보이자.

 

집합 $\cup X/\sim$는 $X$의 모든 원소의 동치류 $x/\sim$의 원소로만 구성된다. 

그런데 $X$의 원소의 동치류는 $X$ 위의 동치관계로 도출되는 집합이기 때문에 $X$의 원소만으로 구성된다.

따라서 $X$의 모든 원소의 동치류 $x/\sim$와 동치류의 원소 $\forall y \in x/\sim$에 대해 $y \in X$이다. 

즉, 모든 동치류의 합집합 $\cup X/\sim$의 모든 원소는 $X$의 원소이다. 

따라서 $\cup X/\sim \subseteq X$이다. 

 

 

② $X \subseteq \cup X/\sim$, 즉 집합 $X$가 모든 동치류의 합집합의 부분집합임을 보이자. 

즉, $X$의 모든 원소가 $\cup X/\sim$의 원소임을 보이자.

 

조건 1을 만족함을 증명할 때 보였듯, $X$의 모든 원소 $x$에 대해 적어도 $(x, x)\in \sim$이다. 

따라서, $X$의 모든 원소 $x$에 대해 $x \in x/\sim$이다. 

결국 $X$의 모든 원소 $x$는 적어도 하나의 동치류의 원소이다.

따라서 $X$의 모든 원소는 동치류의 합집합의 원소이다. 

 

따라서 ①, ②가 참이므로 모든 동치류의 합집합은 원래 집합 $X$와 동일하다. 

 

 

 

따라서 집합 $X$의 동치류의 조건 1, 2, 3에 의해 집합 $X/\sim$은 $X$의 분할이다. ■