위키백과

집합의 분할: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
TedBot (토론 | 기여)
봇, 업로더
2,725,142 편집
잔글 봇: 틀 이름 및 스타일 정리
편집 요약 없음
3번째 줄:
[[파일:Genji chapter symbols groupings of 5 elements.svg|thumb|《[[겐지 이야기]]》의 각 장을 나타내는 54개의 기호는 5개의 원소를 분할하는 52가지 방법에 기초하였다.]]
 
[[수학]]에서, '''집합의 분할'''(集合-分割, {{llanglang|en|partition of a set}})은 집합의 원소들을 [[공집합|비공]] [[부분집합]]들에게 나눠주어, 모든 원소가 오직각자 정확히 하나의 부분집합에 속하게끔 하는 것이다.
 
== 정의 ==
집합 <math>X</math>의 분할은 <math>X</math>의 공집합이 아닌 부분집합들로 이루어진, 합집합이 <math>X</math>가 되는 집합이다집합들이다. 즉, 다음 조건을 만족하는 [[집합족]] <math>P</math>이다.<ref>{{서적 인용|author=Lucas, John F.|title=Introduction to Abstract Mathematics|publisher=Rowman & Littlefield|year=1990|language=en|isbn=9780912675732|page=187|url=http://books.google.com/books?id=jklsb5JUgoQC&pg=PA187}}</ref>
 
* <math>\emptyset \notin P</math>, 즉 <math>P</math>는 공집합을 원소로 하지 않는다.
* <math>\bigcup_{A\in P}A=X</math>, 즉 <math>P</math>는 <math>X</math>의 [[덮개 (위상수학)|덮개]]이다.
* <math>A,B\in P</math>이고 <math>A\ne B</math>이면 <math>A\cap B=\emptyset</math>, 즉 <math>P</math>는 [[서로소 집합|서로소 집합족]]이다.<!-- blocks parts cells rank -->
 
== 예 ==
* [[한원소 집합]] <math>\{x\}</math>의 분할은, <math>\{\{x\}\}</math>로 유일하다.
* 공집합의 분할은, 공집합으로 유일하다.
* 공집합이 아닌 집합 <math>X</math>는 모두 분할 <math>P=\{X\}</math>를 가지며 이를 '''자명 분할'''({{llang|en|trivial partition}})이라고 한다.
* 집합 <math>U</math>의 공집합이 아닌 [[진부분집합]]집합 <math>AX</math>와는 [[여집합]]모두 분할 <math>U-AP=\{X\}</math>는를 <math>U</math>의가진다. 이를 '''자명 분할'''({{lang|en|trivial 분할을partition}})이라고 이룬다한다.
* 공집합이 아닌 집합 <math>U</math>의 공집합이 아닌 [[진부분집합]] <math>A</math>와 [[여집합]] <math>U-A</math>는 <math>U</math>의 분할을 이룬다.
* 집합 <math>\{1,2,3\}</math>의 분할은 5개이다.
** <math>\{\{1,2,3\}\}</math>, 즉 <math>123</math>
줄 22 ⟶ 23:
** <math>\{\{3\},\{1,2\}\}</math>, 즉 <math>3|12</math>
** <math>\{\{1\},\{2\},\{3\}\}</math>, 즉 <math>1|2|3</math>
** <math>\{\{1\},\{2\}\}</math>는 <math>\{1,2,3\}</math>의 분할이 아니다. 합집합이 <math>\{1,2,3\}</math>이 아니기 때문이다.
* 정의에서 알 수 있듯이, 공집합을 포함하거나 서로소가 아닌 집합족은 집합의 분할이 아니다. 그러므로 <math>\{\{\},\{1,2\},\{3\}\}</math>, <math>\{\{1,2\},\{2,3\}\}</math>와 같은 집합족은 어떤 집합의 분할도 될 수 없다.
 
== 유한 집합의 분할의 수 ==
{{참고|벨 수|카탈랑 수}}
 
<math>n</math>개 원소의 집합을 분할하는 방법수는 [[벨 수]] <math>B_n</math>이다. 앞의 6개의 벨 수는 다음과 같다.
 
줄 47 ⟶ 46:
 
== 동치관계와의 관계 ==
집합 <math>X</math> 상의위의 임의의 [[동치관계]] <math>\sim</math>에 대해, 그그에 의한 [[몫집합]] <math>X/{\sim}</math>은 <math>X</math>의 한 분할이다. 역으로 <math>X</math>의 임의의 분할에 대해 <math>X</math> 상의 동치 관계, <math>x\sim, y</math>를 <math>x,y</math>가 <math>P</math> 안의 같은 집합에 속하는속한다는 것으로관계는 정의할<math>X</math> 수위의 동치 있다관계이다. 그러므로 동치관계와 분할의 개념은 동등하다.<ref name="schechter54">Schechter, ''p''. 54</ref>
 
[[선택 공리]]에 의하면 집합 <math>X</math>의 임의의 분할에 대하여 분할의 각 원소에서 하나의 원소를 취하여 구성한 <math>X</math>의 부분집합이 존재한다. 그러므로 집합 상의 동치관계가 주어졌을 때 각 동치류로부터 하나의 대표 원소를 선택해내는 것이 가능하다.
줄 54 ⟶ 53:
[[파일:Set partitions 4; Hasse; circles.svg|thumb|300px|4 원소 집합의 분할과 [[분할의 세분|세분]]에 의한 부분 순서]]
 
집합 <math>X</math>의 두 분할 <math>\alpha ,\rho</math>에 대하여, <math>\alpha</math>의 모든 원소가 <math>\rho</math>의 어떤 원소의 부분집합일 경우부분집합이라면, <math>\alpha</math>를 <math>\rho</math>의 '''세분'''(細分, {{llanglang|en|refinement}})이라고 하고, <math>\alpha\le\rho</math>라고로 표기한다. (<math>\alpha</math>가 <math>\rho</math>보다 '''더 섬세하다'''(纖細, {{lang|en|finer}}), 또는 <math>\rho</math>가 <math>\alpha</math>보다 '''더 엉성하다'''({{lang|en|coarser}})로 읽는다.)
 
<math>\le</math>는 <math>X</math>의 모든 분할의 집합 위의 [[부분순서]]이다. 임의의 부분집합이 [[상한과 하한]]을 가지므로, 이는 [[격자 (순서론)|격자]]를 이루며, 나아가 유한집합의 분할인 경우 [[기하격자]]를 이룬다.<ref>{{citation|title=Lattice Theory|volume=25|series=Colloquium Publications|publisher=American Mathematical Society|first=Garrett|last=Birkhoff|authorlink=Garrett Birkhoff|edition=3rd|year=1995|isbn=9780821810255|page=95|url=http://books.google.com/books?id=0Y8d-MdtVwkC&pg=PA95}}.</ref> 4원소 집합의 분할격자는 15개의 원소가 있으며, 왼쪽 그림에서 [[하세 도형]]으로 표현된다. 이 분할격자는, 기하격자와 동일한 개념인 [[매트로이드]]에도 대응한다. 이때 기저집합은 격자의 [[원자 (순서론)|원자]]들, 즉 (''n'' - 2)원소 집합과 2원소 집합으로 이루어진 분할들로 이루어진다. 이들 원자 분할은 [[완전 그래프]]의 변들과 일대일 대응한다. 어떤 주어진 원자 분할들의 집합의 [[매트로이드#폐포|매트로이드 폐포]]는, 그들 모두보다 엉성한 분할들 중 가장 섬세한 하나이며, 그래프 이론적으로 이는 주어진 변들에 의한 부분 그래프의 [[연결성분]]이다. 이로써 이 분할 격자는 완전 그래프의 [[그래프 매트로이드]]<!-- graphic matroid -->이다.
<math>\le</math>는 <math>X</math>의 모든 분할의 집합 상의 이항관계로서 [[부분 순서]]를 이룬다.
<!-- 내용 추가 필요, 추가할 내용에 붙여야 할 출처 개수:1 -->
 
동치관계에 의한 분할의 세분의 예로, ''D''를 52장의 [[플레잉카드]]의 집합이라 하면, ''D'' 상의 '같은 색깔'에 의한 동치관계 ~<sub>C</sub>는 두 개의 동치류, 즉 {붉은색 카드}, {검은색 카드}를 가지고, '같은 슈트'에 의한 동치관계 ~<sub>S</sub>는 {하트}, {다이아몬드}, {클럽}, {스페이드} 4개의 동치류를 가진다. ~<sub>S</sub>에 대응하는 분할은 ~<sub>C</sub>에 대응하는 분할의 세분이다.
 
== 비교차 분할 ==
원본 주소 "https://ko.wikipedia.org/wiki/집합의_분할"