파티션의 활용 : 부분집합의 파티션

 

 

포스팅을 통해서 다음을 이해해 보려고 합니다.

 

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의 파티션을 이루게 됩니다.