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

[[수학]]에서 '''집합의 분할'''(集合의 分割, {{llang|en|partition of a set}})은 집합의 원소들을 비공 [[부분집합]]들에게 나눠주어 모든 원소가 오직 하나의 부분집합에 속하게끔 하는 것이다.

 

집합 <math>X</math>의 분할은 <math>X</math>의 공집합이 아닌 부분집합들로 이루어진 합집합이 <math>X</math>가 되는 집합이다. 즉, 다음 조건을 만족하는 [[집합족]] <math>P</math>이다.<ref>{{cite book|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>

rank -->

 

* [[한원소 집합]] <math>\{x\}</math>의 분할은 <math>\{\{x\}\}</math>로 유일하다.

* 공집합이 아닌 집합 <math>X</math>는 모두 분할 <math>P=\{X\}</math>를 가지며 이를 '''자명 분할'''({{llang|en|trivial partition}})이라고 한다.

* 정의에서 알 수 있듯이, 공집합을 포함하거나 서로소가 아닌 집합족은 집합의 분할이 아니다. 그러므로 <math>\{\{\},\{1,2\},\{3\}\}</math>, <math>\{\{1,2\},\{2,3\}\}</math>와 같은 집합족은 어떤 집합의 분할도 될 수 없다.

 

{{참고|벨 수|카탈랑 수}}

<math>n</math>개 원소의 집합을 분할하는 방법수는 [[벨 수]] <math>B_n</math>이다. 앞의 6개의 벨 수는 다음과 같다.

n 원소 집합을 정확히 k 개의 집합으로 분할하는 방법 수는 [[스털링 수#제2종 스털링 수|제2종 스털링 수]] <math>S(n,k)</math>이다.

 

집합 <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> 안의 같은 집합에 속하는 것으로 정의할 수 있다. 그러므로 동치관계와 분할의 개념은 동등하다.<ref name="schechter54">Schechter, ''p''. 54</ref>

 

[[선택 공리]]에 의하면 집합 <math>X</math>의 임의의 분할에 대하여 분할의 각 원소에서 하나의 원소를 취하여 구성한 <math>X</math>의 부분집합이 존재한다. 그러므로 집합 상의 동치관계가 주어졌을 때 각 동치류로부터 하나의 대표 원소를 선택해내는 것이 가능하다.

 

[[File: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>의 '''세분'''({{llang|en|refinement}})이라고 하고 <math>\alpha\le\rho</math>라고 표기한다.

분할의 세분의 예로, ''D''를 52장의 [[플레잉카드]]의 집합이라 하면, ''D'' 상의 '같은 색깔'에 의한 동치관계 ~_C는 두 개의 동치류, 즉 {붉은색 카드}, {검은색 카드}를 가지고, '같은 슈트'에 의한 동치관계 ~_S는 {하트}, {다이아몬드}, {클럽}, {스페이드} 4개의 동치류를 가진다. ~_S에 대응하는 분할은 ~_C에 대응하는 분할의 세분이다.

 

{{참고|비교차 분할}}

 

순환순서가 정의된 유한집합 <math>N=\{1,2,\ldots,n\}</math>의 분할 <math>\mathcal C</math>와 대응하는 동치관계 <math>\sim</math>에 대하여, 만약 <math>\mathcal C</math>의 서로 다른 두 원소 <math>C_1,C_2</math>에서 각각 임의의 서로 다른 두 원소 <math>a,b\in C_1,x,y\in C_2</math>를 취했을 때, 그들이 <math>[a,x,b]</math>와 <math>[b,y,a]</math>를 동시에 만족하지 않는 경우, 분할 <math>\mathcal C</math>(또는 동치관계 <math>\sim</math>)가 교차하지 않는다고 한다. 이는 다르게 말해 원 또는 다각형에 표기한 분할이 교착하지 않는다는 것이다.

:<math>C_n=\frac{1}{n+1} {2n \choose n}</math>

 

{{위키공용분류|Set partitions|집합의 분할}}

<!--

* [[라미네이션 (위상수학)]]

 

{{각주}}

 

*{{cite book |last= Brualdi |first= Richard A. |title= Introductory Combinatorics |edition= 4|year= 2004 |publisher= Pearson Prentice Hall |language=en |isbn= 0-13-100119-1}}

*{{cite book |last= Schechter |first= Eric |title= Handbook of Analysis and Its Foundations |year= 1997 |publisher= Academic Press |language=en |isbn= 0-12-622760-8}}