(번역) Disjoint sets

Original article: w:Disjoint sets

 

수학(mathematics)에서, 두 집합(sets)은 만약 그들이 공통에서 원소(element)를 가지지 않으면 서로소 집합(disjoint sets)이라고 말합니다. 동등하게, 두 서로소 집합은 그의 교집합(intersection)이 빈 집합(empty set)인 집합입니다. 예를 들어, {1, 2, 3} 및 {4, 5, 6}은 서로소 집합이지만, {1, 2, 3} 및 {3, 4, 5}는 서로소가 아닙니다. 두 집합보다 많은 모음이 만약 모음의 임의의 두 서로소 집합은 서로소이면 서로소라고 불립니다.

Generalizations

서로소 집합의 이 정의는 집합의 가족(family of sets) $(A_i{)}_{i\in I}$으로 확장될 수 있습니다: 그 가족은 만약 $i\ne j$일 때마다 $A_i\cap A_j=\varnothing$이면 서로소입니다. 가족에 대해 쌍별 서로소(pairwise disjoint) 또는 서로 서로소(mutually disjoint)의 개념은 미묘하게 다른 방식에서 때때로 정의되며, 그것에서 반복된 동일한 구성원은 허용됩니다: 그 가족은 만약 $A_i\ne A_j$일 때마다 $A_i\cap A_j=\varnothing$이면 쌍별 서로소입니다 (그 가족에서 모든 각 두 서로소 집합은 서로소입니다). 예를 들어, 집합 { {0,1,2}, {3,4,5}, {6,7,8}, ... }의 모음은, 정수의 두 패리티 클래스의 집합 { {...,-2,0,2,4,...}, {...,-3,-1,1,3,5 }}에서 처럼, 서로소입니다; 10 구성원을 가진 가족 $(\{n+2k\mid k\in \mathbb{Z}\}{)}_{n\in \{0,1,\dots ,9\}}$은 서로소이지만 (왜냐하면 짝수와 홀수의 클래스는 각각 다섯 번 존재하기 때문입니다), 그것은 이 정의에 따라 쌍별 서로소입니다 (왜냐하면 우리는 두 구성원이 같은 클래스일 때 두 구성원의 비-빈 교집합을 오직 얻기 때문입니다).

두 집합은 만약 그들의 교집합이 어떤 의미에서 작으면 거의 서로소 집합(almost disjoint sets)이라고 말합니다. 예를 들어, 그들의 교집합이 유한 집합(finite set)인 두 무한 집합(infinite set)은 거의 서로소라고 말해질 수 있습니다.

토폴로지(topology)에서, 서로소성보다 더 엄격한 조건을 가진 분리된 집합(separated sets)의 다양한 개념이 있습니다. 예를 들어, 두 집합이 그들이 서로소 닫힘(closure) 또는 서로소 이웃(neighborhoods)을 가질 때 분리된 것으로 여겨질 수 있습니다. 비슷하게, 메트릭 공간(metric space)에서, 양으로 분리된 집합(positively separated sets)은 비-영 거리(distance)에 의해 분리된 집합입니다.

Intersections

두 집합, 또는 집합의 가족의 서로소성은 그들의 쌍의 교집합(intersections)의 관점에서 표현될 수 있습니다.

두 집합 A와 B가  서로소인 것과 그들의 교집합 $A\cap B$가 빈 집합(empty set)인 것은 필요충분 조건입니다. 모든 각 집합은 빈 집합과 서로소이고, 빈 집합은 자체로부터 서로소인 유일한 집합인 이 정의로부터 따릅니다.

만약 모음이 적어도 두 집합을 포함하면, 모음이 서로소라는 조건은 전체 모음의 교집합이 빈 것임을 의미합니다. 어쨌든, 집합의 모음은 서로소인 것없이 빈 교집합을 가질 수 있습니다. 추가적으로, 두 집합보다 작은 모음은 자명하게 서로소이지만, 비교할 쌍이 없기 때문에, 한 집합의 모음의 교집합은 해당 집합과 같으며, 이것은 비-빈일 수 있습니다. 예를 들어, 세 세트 { {1, 2}, {2, 3}, {1, 3} }은 빈 교집합을 가지지만 소로소이지 않습니다. 실제로, 이 모음에서 두 서로소 집합이 없습니다. 역시 집합의 빈 가족은 쌍 서로소입니다.

헬리 가족(Helly family)은 빈 교집합을 갖는 오직 부분-가족이 쌍별 서로소인 것들 이내에서 집합의 시스템입니다. 예를 들어, 실수(real number)의 닫힌 구간(closed interval)은 헬리 패밀리를 형성합니다: 만약 닫힌 구간의 가족이 빈 교집합을 가지고 최소이면 (즉, 가족의 부분-가족이 빈 교집합을 가지지 않으면), 그것은 쌍별 서로소이어야 합니다.

Disjoint unions and partitions

집합 X의 분할(partition of a set)은 그의 합집합(union)이 X인 서로 서로소 비-빈 집합의 임의의 모음입니다. 모든 각 분할은 동치 관계(equivalence relation), 두 원소가 분할에서 같은 집합에 속하는지 여부를 설명하는 이항 관계(binary relation)에 의해 동등하게 설명될 수 있습니다. 서로소-집합 데이터 구조(Disjoint-set data structure)와 분할 세분화(partition refinement)는, 각각, 두 집합을 병합하는 합집합 연산 또는 하나의 집합을 둘로 나누는 세분화 연산에 따라 집합의 분할을 효율적으로 유지하는 것에 대해 컴퓨터 과학에서 두 가지 기술입니다.

서로소 합집합(disjoint union)은 두 가지 중 하나를 의미할 수 있습니다. 가장 간단하게, 그것은 서로소인 집합의 합집합을 의미할 수 있습니다. 그러나 만약 둘 이상의 집합이 이미 서로소가 아니면, 그들의 서로소 합집합은 수정된 집합의 합집합을 형성하기 전에 그들을 서로소로 만들기 위해 집합을 수정함으로써 형성될 수 있습니다. 예를 들어, 두 집합은 각 원소를 원소의 순서화된 쌍과 그것이 첫 번째 또는 두 번째 집합에 속하는지 여부를 나타내는 이진 값으로 대체함으로써 서로소로 만들어질 수 있습니다. 두 집합보다 많은 것의 가족에 대해, 우리는 각 원소를 원소의 순서화된 쌍과 그것을 포함하는 집합의 인덱스를 비슷하게 대체할 수 있습니다.

See also

• Hyperplane separation theorem for disjoint convex sets
• Mutually exclusive events
• Relatively prime, numbers with disjoint sets of prime divisors
• Separoid
• Set packing, the problem of finding the largest disjoint subfamily of a family of sets

External links

 

• Weisstein, Eric W. "Disjoint Sets". MathWorld.