[집합론] Partition과 동치관계

 

동치관계란?

 

집합 $X$에서 정의된 relation 중에서 reflexive이고 symmetric이며 transitive인 relation을 동치관계라고 한다.

(참고 : https://hellworld.tistory.com/8)

 

말로 풀어서 쓰면 역시 복잡해보이지만, 우리가 잘 알고 있는 많은 relation들은 동치관계이다.

동치관계의 예시로는 등호, 닮음 등의 관계가 있다.

 

 

집합을 원소나열법으로 나타내어 예시를 들자면 아래와 같은 relation이 동치관계이다.

 

ex) 집합 $X = \left\{1,2,3,4\right\}$에 대해 $X$ 위에서 정의된 relation $R \subseteq X \times X$ 중에서

$R_{1} = \left\{(1,1), (2,2), (3,3), (4,4) \right\}, R_{2} = \left\{ (1,1), (1,2), (2,1), (2,2) \right\}$ 등은 동치관계라고 할 수 있다. 

 

 

 

Partition과 동치관계

 

이 글에서 partition을 정의하고, partiton을 통해 relation을 하나 정의하였다.

 

다시 복습해보자면, 집합 $X$에 대해 $X$의 partition은 $X$를 겹치지 않고 나눈 부분집합들의 집합을 말한다.

또, $X$의 partition의 원소들을 block이라고 하며, 원소 $a \in X$에 대해 $a$를 포함하는 block을 $[a]$로 나타내었다. 

 

그리고 $X$의 partion의 부분집합으로 relation $\sim_{P}$를 정의하였다. 

이때, $\sim_{P}$의 정의는, $a, b \in X$에 대해 $a \sim_{P} b \iff a \in [b]$

 

 

ex) $X = \left\{10,20,30 \right\}$ 이라고 하자. 

이때 $X$의 partition중 하나 $P = \left\{(10,20), (30)\right\}$을 생각할 수 있다. 

Partition을 통해 정의된 relation $\sim_{P} \subseteq X \times X$를 원소 나열법으로 나타내면 아래와 같다.

 

$\sim_{P} = \left\{(10,10), (10,20), (20,10), (30,30) \right\}$

 

 

이때, relation $\sim_{P}$는 사실 동치관계이다. 이 relation이 동치관계임을 증명해보자. 

 

 

Reflexive

$\sim_{P}$이 reflexive임을 보이는 것은 어렵지 않다. $\forall x \in X$에 대해 $x \sim_{P} x$임을 보이기만 하면 된다. 

 

$\forall x \in X$에 대해 $x \in [x]$이므로  $x \sim_{P} x$이다. 

 

 

Symmetric

$x, y \in X$에 대해  $x \sim_{P} y$ 이면  $y \sim_{P} x$임을 보이자.

이때 relation의 정의에 의해 $x \sim_{P} y$ 이면  $x \in [y]$ 이다. 

 

귀류법으로 $x \in [y]$ 이면 $y \in [x]$일 수 밖에 없음을 증명할 수 있다. 

만약 $x \in [y]$인데 $y \notin [x]$ 라면, block $[y]$는 $x$를 포함하지만 block $[x]$는 $y$를 포함하지 않는다.

이때, block $[x]$는 원소 $x$를 무조건 포함한다.

 

따라서 $x \in ([x] \cap [y])$인데 $[x] \neq [y]$이므로 partiton의 정의에 어긋난다. 

$($Partiton의 원소들은 모두 다르고 겹치지 않아야 한다.$)$

 

따라서 모순이 발생하므로 가정이 틀린 것이다. 즉, 귀류법을 통해  $x \in [y]$ 이면 $y \in [x]$임을 증명하였다.

즉, $x \sim_{P} y$ 이면  $y \sim_{P} x$이다.

 

 

Transitive

$x, y, z \in X$에 대해  $x \sim_{P} y$ 이고 $y \sim_{P} z$ 이면 $x \sim_{P} z$임을 보이자.

 

우선 보조정리 하나를 먼저 증명해야 한다.

 

보조정리 : $x \in [y] \Rightarrow [x] = [y]$

이 정리도 귀류법으로 symmetric을 증명한 것과 비슷하게 보일 수 있다. 

 

$x \in [y] \nRightarrow [x] = [y]$라고 가정하자. 위에서 보였듯, $x \in [y]$ 이면 $y \in [x]$이다. 

그런데 만약 $[x] \neq [y]$라면 partiton의 정의에 어긋난다, 즉 모순이 발생한다.

 

따라서 가정이 거짓이므로, $x \in [y] \Rightarrow [x] = [y]$이 참이다. 

 

 

이 보조정리를 통해 우리는 아래 두 사실을 알 수 있다.

 $x \sim_{P} y$ 이면 $[x] = [y]$,  $y \sim_{P} z$ 이면 $[y] = [z]$이다.

따라서 $[x] = [y] = [z]$이므로, $x \in [z]$이다.

즉, $x \sim_{P} z$이다. 

 

 

이를 통해 relation $\sim_{P}$은 reflexive, symmetric, transitive임을 보였다. 

따라서 relation $\sim_{P}$은 동치관계이다.