집합
파티션의 활용 : 부분집합의 파티션
밝은비
2012. 7. 11. 13:08
포스팅을 통해서 다음을 이해해 보려고 합니다.
A1, A2, ..., An가 전체 집합 (U)의 파티션이고 집합 B가 U의 부분 집합일때 A1∩B, A2∩B, ..., An∩B가 B의 파티션을 이룬다.
A1, A2, ..., An이 U의 파티션이면 다음과 같은 그림이 그려지게 됩니다.
여기에 U의 부분집합 B를 넣어보겠습니다.
여기서 잘 보면
U 뿐만 아니라 B도 A1, A2, ..., An을 이용해서 나눌수 있다는것을 알 수 있습니다.
하지만 A1, A2, ..., An은 B의 부분집합이 아니므로
(즉 A₁∪ A₂∪ ... ∪ An ≠ B 이므로 파티션 정의에서 2번째 조건을 만족시키지 못합니다.)
A1, A2, ..., An가 B의 파티션인것은 아니고
A1 ∩ B, A2 ∩ B, ..., An ∩ B가 B의 파티션을 이루게 됩니다.
증명을 해보면
일단 A1, A2, ..., An가 pairwise disjoint하기 때문에
A1 ∩ B, A2 ∩ B, ..., An ∩ B도 pairwise disjoint하게 되고 (파티션 정의 첫번째 조건)
(A1 ∩ B)∪(A2 ∩ B)∪...(An ∩ B)
= (A1∪A2∪...∪An)∩B <= 집합의 분배법칙 척용
= U∩B = B <= 즉 합집합이 B와 같습니다. (파티션 정의 두번째 조건)
따라서 A1 ∩ B, A2 ∩ B, ..., An ∩ B가 B의 파티션을 이루게 됩니다.