서로소 집합

집합론에서 서로소 집합(-素集合, 영어: disjoint sets)는 공통 원소가 없는 두 집합이다.^[1] 예를 들어서 1, 2, 3}과 4, 5, 6}은 서로소이며 1, 2, 3}과 3, 4, 5}는 아니다.

서로소인 두 집합

정의

두 집합 ${\displaystyle A,B}$가 ${\displaystyle A\cap B=\varnothing }$을 만족시키면, 서로소 집합이라고 한다.

집합족 ${\displaystyle {\mathcal {A}}}$가 다음 조건을 만족시키면, 서로소 집합족(영어: disjoint family of sets)이라고 한다.

• 임의의 ${\displaystyle A,B\in {\mathcal {A}}}$에 대하여, ${\displaystyle A=B}$이거나, ${\displaystyle A\cap B=\varnothing }$이다.^[1]

기수 ${\displaystyle \kappa }$에 대하여, 두 집합 ${\displaystyle A,B}$가 ${\displaystyle |A\cap B|<\kappa }$를 만족시키면, ${\displaystyle \kappa }$-거의 서로소 집합(영어: ${\displaystyle \kappa }$-almost disjoint sets)이라고 한다. 비슷하게 ${\displaystyle \kappa }$-거의 서로소 집합족(영어: ${\displaystyle \kappa }$-almost disjoint family of sets)을 정의할 수 있다. 여기서 ${\displaystyle \kappa =1}$을 취하면 서로소 집합 및 서로소 집합족의 개념을 얻는다.

예

• 
  드럼과 기타의 집합, 카드와 책의 집합은 서로소이다.
• 
  서로소 집합족
• 
  서로소가 아닌 집합족

성질

• 모든 집합은 공집합과 서로소이다.^[2]
• 자기 자신과 서로소일 필요충분조건은 공집합이다.^[2]
• 서로소 집합족이 둘 이상의 집합으로 이루어졌다면, 그 교집합은 공집합이다.
• 공집합은 서로소 집합족이지만, 그 교모임은 모든 집합을 포함하는 고유 모임이다.^[3]
• 하나의 집합으로 이루어진 집합족은 서로소 집합족이지만, 그 교집합은 공집합이 아닐 수 있다.
• 교집합이 공집합인 집합족은 서로소 집합족이 아닐 수 있다.^[4] 예를 들어, 집합족 {{1, 2}, {2, 3}, {1, 3}}의 교집합은 공집합이지만, 이는 서로소 집합족이 아니다.

관련 개념

 집합의 분할, 분리합집합 및 헬리 족 문서를 참고하십시오.

위상수학에는 서로 분리된 집합의 여러 종류의 개념이 있는데 이들은 서로소보다 더 엄격한 조건을 가진다. 예를 들어, 서로소인 폐포를 가지거나 서로소인 근방을 가진 두 집합을 서로 분리된 집합이라고 할 수 있다. 이와 비슷하게, 거리공간에서 양수로 분리된 집합은 0이 아닌 거리로 분리된 두 집합을 뜻한다.^[5]

집합 ${\displaystyle X}$의 분할은 합집합이 ${\displaystyle X}$이고 서로소인 집합들로 이루어진 집합족이다.^[6] 모든 분할은 하나의 동치 관계와 대응한다.^[6] 서로소 집합 데이터 구조^[7]와 분할 세분화^[8]는 컴퓨터 과학에서 각각 합집합, 세분화 연산의 대상이 되는 집합의 분할을 효율적으로 유지하는 기술이다.

분리합집합은 두 가지 의미를 가진다. 서로소 집합들의 경우 그들의 합집합이 바로 그들의 분리합집합이고,^[9] 서로소가 아닌 경우 서로소가 되게끔 변형한 뒤 합집합을 취한다.^[10] 임의의 원소를 자신과 속하는 집합의 지표의 순서쌍으로 대체하는 것은 변형의 한 방법이다.^[11][12]

헬리 족은 교집합이 공집합인 최소 부분집합족은 모두 서로소인 집합족이다. 여기서 '최소'는 그 부분집합족이 교집합이 공집합인 부분집합족을 가지지 않는다는 것이다. 모든 폐구간의 집합은 헬리 족의 한 예이다.^[13]

같이 보기

• 서로소 볼록 집합에 대한 초평면 분리 정리
• 배반 사건
• 수론에서의 서로소