서로소 집합 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:DisjointSets.svg|섬네일|오른쪽|서로소인 두 집합]]

[[집합론]]에서 '''서로소 집합'''(-素集合, {{llang|en|disjoint sets}})는 공통 원소가 없는 두 [[집합]]이다.<ref name="halmos">{{인용|title=Naive Set Theory|series=Undergraduate Texts in Mathematics|first=P. R.|last=Halmos|authorlink=Paul Halmos|publisher=Springer|year=1960|language=en|isbn=9780387900926|page=15|url=http://books.google.com/books?id=x6cZBQ9qtgoC&pg=PA15}}</ref> 예를 들어서 {{mset|1, 2, 3}}과 {{mset|4, 5, 6}}은 서로소이며 {{mset|1, 2, 3}}과 {{mset|3, 4, 5}}는 아니다.

== 정의 ==
두 집합 <math>A,B</math>가 <math>A\cap B=\varnothing</math>을 만족시키면, '''서로소 집합'''이라고 한다.

[[집합족]] <math>\mathcal A</math>가 다음 조건을 만족시키면, '''서로소 집합족'''({{llang|en|disjoint family of sets}})이라고 한다.
* 임의의 <math>A,B\in\mathcal A</math>에 대하여, <math>A=B</math>이거나, <math>A\cap B=\varnothing</math>이다.<ref name="halmos" />

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

== 예 ==
<gallery widths="250">
파일:Veranschaulichung von disjunkten Mengen.svg|드럼과 기타의 집합, 카드와 책의 집합은 서로소이다.
파일:Example of a pairwise disjoint family of sets.svg|서로소 집합족
파일:Example of a non pairwise disjoint family of sets.svg|서로소가 아닌 집합족
</gallery>

== 성질 ==
* 모든 집합은 [[공집합]]과 서로소이다.<ref name="Oberste-Vorth">{{인용|title=Bridge to Abstract Mathematics|series=MAA textbooks|publisher=Mathematical Association of America|first1=Ralph W.|last1=Oberste-Vorth|first2=Aristides|last2=Mouzakitis|first3=Bonita A.|last3=Lawrence|year=2012|language=en|isbn=9780883857793|page=59|url=http://books.google.com/books?id=fO3tvd9qjLkC&pg=PA59}}</ref>
* 자기 자신과 서로소일 필요충분조건은 공집합이다.<ref name="Oberste-Vorth" />
* 서로소 집합족이 둘 이상의 집합으로 이루어졌다면, 그 교집합은 공집합이다.
* 공집합은 서로소 집합족이지만, 그 교모임은 모든 집합을 포함하는 [[고유 모임]]이다.<ref>See answers to the question [http://math.stackexchange.com/q/1211584/32951 ″Is the empty family of sets pairwise disjoint?″]{{깨진 링크|url=http://math.stackexchange.com/q/1211584/32951 }}</ref>
* 하나의 집합으로 이루어진 집합족은 서로소 집합족이지만, 그 교집합은 공집합이 아닐 수 있다.
* 교집합이 공집합인 집합족은 서로소 집합족이 아닐 수 있다.<ref>{{인용|title=A Transition to Advanced Mathematics|first1=Douglas|last1=Smith|first2=Maurice|last2=Eggen|first3=Richard|last3=St. Andre|publisher=Cengage Learning|year=2010|language=en|isbn=9780495562023|page=95|url=http://books.google.com/books?id=jJUs0ZDOOHoC&pg=PA95}}</ref> 예를 들어, 집합족 {{1, 2}, {2, 3}, {1, 3}}의 교집합은 공집합이지만, 이는 서로소 집합족이 아니다.

==관련 개념==
{{참고|집합의 분할|분리합집합|헬리 족}}

위상수학에는 [[서로 분리된 집합]]의 여러 종류의 개념이 있는데 이들은 서로소보다 더 엄격한 조건을 가진다. 예를 들어, 서로소인 [[폐포 (위상수학)|폐포]]를 가지거나 서로소인 [[근방]]을 가진 두 집합을 서로 분리된 집합이라고 할 수 있다. 이와 비슷하게, 거리공간에서 [[양수로 분리된 집합]]<!-- Positively separated sets -->은 0이 아닌 거리로 분리된 두 집합을 뜻한다.<ref>{{인용|title=Metric Spaces|volume=57|series=Cambridge Tracts in Mathematics|first=Edward Thomas|last=Copson|publisher=Cambridge University Press|year=1988|language=en|isbn=9780521357326|page=62|url=http://books.google.com/books?id=egc5AAAAIAAJ&pg=PA62}}</ref>

집합 <math>X</math>의 [[집합의 분할|분할]]은 합집합이 <math>X</math>이고 서로소인 집합들로 이루어진 [[집합족]]이다.<ref name="h60-28">{{harvtxt|Halmos|1960|p=28}}</ref> 모든 분할은 하나의 [[동치 관계]]와 대응한다.<ref name="h60-28" /> [[서로소 집합 데이터 구조]]<!-- Disjoint-set data structure --><ref>{{인용|first1=Thomas H. |last1=Cormen |author1-link=Thomas H. Cormen |first2=Charles E. |last2=Leiserson |author2-link=Charles E. Leiserson |first3=Ronald L. |last3=Rivest |author3-link=Ronald L. Rivest |first4=Clifford |last4=Stein |author4-link=Clifford Stein |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press |year=2001 |language=en |isbn=0-262-03293-7 |chapter=Chapter 21: Data structures for Disjoint Sets |pages=498&ndash;524 }}</ref>와 [[분할 세분화]]<!-- Partition refinement --><ref>{{인용
 | last1 = Paige | first1 = Robert
 | last2 = Tarjan | first2 = Robert E.
 | doi = 10.1137/0216062
 | mr = 917035
 | issue = 6
 | journal = SIAM Journal on Computing
 | pages = 973–989
 | title = Three partition refinement algorithms
 | volume = 16
 | year = 1987
 | language = en}}</ref>는 컴퓨터 과학에서 각각 합집합, 세분화 연산의 대상이 되는 집합의 분할을 효율적으로 유지하는 기술이다.

[[분리합집합]]은 두 가지 의미를 가진다. 서로소 집합들의 경우 그들의 [[합집합]]이 바로 그들의 분리합집합이고,<ref>{{인용|title=Discrete Mathematics: An Introduction to Proofs and Combinatorics|first=Kevin|last=Ferland|publisher=Cengage Learning|year=2008|language=en|isbn=9780618415380|page=45|url=http://books.google.com/books?id=gSeC4_uEPTUC&pg=PA45}}</ref> 서로소가 아닌 경우 서로소가 되게끔 변형한 뒤 합집합을 취한다.<ref>{{인용|title=A Basis for Theoretical Computer Science|series=The AKM series in Theoretical Computer Science: Texts and monographs in computer science|first1=Michael A.|last1=Arbib|first2=A. J.|last2=Kfoury|first3=Robert N.|last3=Moll|publisher=Springer-Verlag|year=1981|language=en|isbn=9783540905738|page=9}}</ref> 임의의 원소를 자신과 속하는 집합의 지표의  [[순서쌍]]으로 대체하는 것은 변형의 한 방법이다.<ref>{{인용|title=Understanding Formal Methods|first1=Jean François|last1=Monin|first2=Michael Gerard|last2=Hinchey|publisher=Springer|year=2003|language=en|isbn=9781852332471|page=21|url=http://books.google.com/books?id=rUudIPZD-B0C&pg=PA21}}</ref><ref>{{인용|first=John M.|last=Lee|title=Introduction to Topological Manifolds|volume=202|series=Graduate Texts in Mathematics|publisher=Springer|edition=2nd|year=2010|language=en|isbn=9781441979407|page=64}}</ref>

[[헬리 족]]<!-- Helly family -->은 교집합이 공집합인 최소 부분집합족은 모두 서로소인 집합족이다. 여기서 '최소'는 그 부분집합족이 교집합이 공집합인 부분집합족을 가지지 않는다는 것이다. 모든 [[폐구간]]의 집합은 헬리 족의 한 예이다.<ref>{{인용|title=Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability|first=Béla|last=Bollobás|authorlink=Béla Bollobás|publisher=Cambridge University Press|year=1986|language=en|isbn=9780521337038|page=82|url=http://books.google.com/books?id=psqFNlngZDcC&pg=PA82}}</ref>

== 같이 보기 ==
* 서로소 볼록 집합에 대한 [[초평면 분리 정리]]
* [[배반 사건]]
* 수론에서의 [[서로소 정수|서로소]]<!-- 
* Set packing은 가장 큰 서로소 부분 집합족을 구하는 문제이다. -->

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=DisjointSets|title=Disjoint sets}}
* {{nlab|id=disjoint subsets|title=Disjoint subsets}}
* {{플래닛매스|urlname=disjoint|title=disjoint}}

[[분류:집합론의 기본 개념]]
[[분류:집합족]]