서로소(Pairwise Disjoint Set) 와 파티션(Partition)

서로소(pairwise disjoint set)은 두 집합이 공유하는 요소가 없는 집합의 모음이다 (예를 들어, 그들의 교집합이 공집합인 경우). 가령, 다음의 집합의 모음들은 서로소들이다:

{ }, {1, 2, 5}, {3, 6}, {4, 9} 

여기에 서로소가 아닌 집합 모음이 있다:

{2, 6, 7}, {6, 7, 9}, {3} 

이 집합들은 서로소가 아닌데, 첫째와 둘째 집합의 교집합이 공집합이 아니기 때문이다({6, 7}). (원문이 조금 이상해서 수정함)

서로소의 합집합이 원래 집합이되는 부분집합들의 집합을 파티션이라고 부른다. 예를 들어, 다음은 집합 {1, 2, 3, 4, 5}의 파티션이다:

{{1, 2}, {3}, {4, 5}}

A pairwise disjoint collection (set) of sets is a collection of sets such that no two sets share an element (i.e. their intersection is the empty set). For example, the following collection of sets are pairwise disjoint: 

{ }, {1, 2, 5}, {3, 6}, {4, 9} 

Here's an example of a collection of sets that isn't pairwise disjoint: 

{2, 6, 7}, {6, 7, 9}, {3} 

These sets are not pairwise disjoint because the intersection of the first and third sets is not empty ({2, 6}). 

A set of subsets that are pairwise disjoint whose union is the original set is called a partition. For example, the following is a partition of the set {1, 2, 3, 4, 5}: 

{{1, 2}, {3}, {4, 5}}

출처: http://answers.yahoo.com/question/index?qid=20091125224757AAm6nE7