[집합] 파티션 ⇔ 동치관계

← )  집합 X위의 동치관계는 하나의 파티션을 만들고,
→ )  X의 파티션은 하나의 동치관계를 만든다.

즉, 동치관계와 파티션은 서로 동치이다.

--------------------------------------------------------------------------------------------

← ) 에 대한 증명.
집합 X위에 동치관계 ~ 가 주어졌다고 하자. 이 때 다음이 성립한다.

1.
x/~ 의 모든 원소들은 X 로 부터 오므로 당연히 부분집합이고, nonempty 임은 ~ 가 reflective 라는 것으로 부터 증명된다. 즉, x~x 이므로 x/~ 는 x를 원소로 갖는다.

2.
대우명제로 증명해보자.

3.
x/~ = y/~ ⇒ x~ y 는 1, 2 로 부터 증명된다.1에 의해서 x/~ 와 y/~ 는 각각 공집합이 아니고, 게다가 두 집합이 같으므로 교집합이 공집합이 아니다. 그러므로 2에 의해서 x~y 가 된다.

이제, x~y ⇒ x/~ = y/~ 만 증명하면 3번은 증명이 된다.

x ~y 일때,  x / ~  ⊂  y /~  의 증명:  z ∈ x/~  이면 z~x 이고, 또한 x ~ y 이므로, z ~y 가 되고, 따라서 z ∈ y/~ 가 된다. 따라서, x / ~  ⊂  y /~ 이다.
반대방향도 마찬가지로 하면 된다.


이제,  x / ~ 들 모두 union 해서 그것이 X 가 됨을 보이기만 하면,  X / ~  이 X 의 파티션임이 증명된다.

그런데 이것은 자명하다. 왜냐면 x/~ 가 항상 x를 포함하고, x는 X의 원소이므로, X의 모든 원소에 대해서 합집합하면 당연히 X가 되기 때문이다.

따라서, X위에서 equivalence relation ~ 가 하나 주어지면, 그에 의한 quotient set  X/~ 은 X의 파티션이다.
이때, 각각의 equivalence class  x/~ 는 그 파티션의 셀이 된다.



-----------------------------------------------------------------------------------------------------------------------

→ ) 에 대한 증명.
집합 X 의 파티션 P  가 하나 주어져있다고 하자.  이때, "파티션 P 의 같은 셀에 속하는 관계" 를 생각하고, 이관계를 X /  P  라고 표기하자.

이는 quotient set 과 표기가 동일하지만 분명하게 다르다. quotient set 의 경우에는, 분모가 릴레이션이고, 그 자체는 파티션이다. 반면 이것은, 분모가 파티션이고, 그 자체는 릴레이션이다.

이제 파티션이 하나 주어졌을때, 같은 셀에 속하는 관계가 equivalence relation 임을 보이면 된다.

정리.
집합 X의 파티션  P  가 주어져있고,  P  의 같은셀에 속한 관계를 X/P  라고 하면,  X/P  는 equivalence relation 이고, 이것에 의한 X의 quotient set  은 파티션 P  가 된다.

즉,  X / (X/P ) = P      :      파티션의 같은셀에 속하는 관계에 의한 쿼션트셋은 파티션 그자체이다.
(마치, 분수식처럼 약분된다. )


증명.
직관적으로 당연하므로, 간단히 코멘트만 하고 생략한다.
우선, X 의 임의의 원소 x 에 대해, 그것은 파티션의 정의에 의해, 어느 셀엔가 속하게 되어있다. 따라서, X의 임의의 원소는 자기자신과 같은 셀에 속하게 된다. 즉, x (X/P ) x  이다.  : reflective.
마찬가지로 시메트릭과 트랜지티브도 쉽게 확인할 수 있다.
따라서 X/P  는 equivalence relation 이다.

이제, 이것에 의한 X의 쿼션트 셋이 파티션 P  가 되는 것을 보인다.
X의 임의의 원소 x 에 대해,  X/P  에 의한  x의 equivalence class  x/ (X/P ) 는 x를 포함한다. 따라서 존재성이 보장된다. 또한, 이것은 x와 같은 셀에 들어있는 모든 원소를 포함한다. 그런데 x가 들어있는 파티션 P 의 셀은 파티션의 정의에 의해 유일하다. 따라서  x/ (X/P ) 는 P 의 하나의 셀이 된다. 그러므로 이것들의 콜렉션은 파티션 P 와 같다. 따라서, X / (X/P ) = P  이다.

-------------------------------------------------------------------------------------------------------------------

예.
정수집합을 홀수집합과 짝수집합으로 파티션한다.
이러한 파티션은 같은셀에 속하는 관계로써 equivalence relation을 제공한다. 실제로 이것은 congruence modulo 2 이다.

반대로, congruence modulo 2 에 의한 정수집합의 quotient set 은, 정수집합을 홀수집합과 짝수집합으로 파티션한다.


----------------------------------------------------------------------------------------------------------------------

앞에서 ,  X / (X/P ) = P  를 보면, 마치 보통의 분수식처럼 약분이 되고 있다. X / ( X/~ ) = ~  도 되는데, 이는 직관적으로 당연하다.

X/~ 는 ~ 에 의한 쿼션트 셋으로서, ~ 관계에 놓인 원소들을 묶은 파티션이다. 즉, 파티션 X/~ 의 각 셀들에 들어있는 원소들은 ~ 관계에 놓여있다. 관계 X / (X/~) 는 파티션 X/~ 의 같은 셀에 들어있는 관계이다. X/~ 의 각각의 셀들은 ~관계에 있는 원소들이므로, 같은셀에 들어있는 관계는 ~ 관계와 같다.

그때문에, 분모가 파티션이건, 릴레이션이건 가리지 않고 약분하는 기분을 느낄수 있다. 이런 젼차로, 보통 인포멀하게,  / 를 나눈다고 표현한다. (우리도 이미 / 밑에 들어가는 녀석을 무심코 '분모'라고 불러버렸다. )


한가지 잊지말아야 할 것은, 집합 X의 파티션P 에 의한 동치관계 X/P 는 X 위에서의 관계, 즉, X 와 X 의 카테션 프로덕트의 부분집합니다. 이것이 낯설다면, 릴레이션의 정의를 다시 확인하길 바란다. 릴레이션

즉,      X/P ⊂   X ²    이다.


특히,  P 의 임의의 셀을 C 라고 하면 다음과 같이 된다.

왜냐면, 관계자체가 같은 셀에 속하는 관계이므로, 같은 셀끼리만 카테션 프로덕트를 하면 된다. 다른셀에 속한 원소가 순서쌍으로 엮일 일이 없기 때문이다.


예제를 통해 확인해보자.
X = { 1 , 2, 3, 4, 5 }  라고 하고, 파티션 P = { {1,2} , {3} , {4,5} }  이 주어졌다고 할 때,


1. 파티션 P에 의한 동치관계 X/P 를 집합으로 나타내라.
 ( 릴레이션은 카테션곱의 부분집합이었음을 상기하라. 즉, X ² 의 부분집합이다.)

답:   X/P = { (1,1) , (1,2) , (2,1) , (2,2) , (3,3) , (4,4) , (4,5) , (5,4) , (5,5) }

이것은  {1,2} X { 1,2 } ∪  {3} X {3}  ∪  { 4,5}  X { 4,5}   와 같다.


2. 동치류 1/(X/P) , 2/(X/P) , 3/(X/P) , 4/(X/P) , 5/(X/P) 를 구해라.

답:   1/(X/P) = 2/(X/P) = { 1, 2 }       ,     3/(X/P) = {3}         ,          4/(X/P) = 5/(X/P) = { 4, 5 }