집합의 분할 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Indiabundleware.jpg|섬네일|나눠 묶인 우표들. 동시에 두 묶음에 속하는 우표는 없으며, 빈 묶음도 없다.]]
[[파일:Set partitions 5; circles.svg|섬네일|5개 원소로 이루어진 집합의 [[벨 수|52]]개의 분할]]
[[파일:Genji chapter symbols groupings of 5 elements.svg|섬네일|《[[겐지모노가타리]]》의 각 장을 나타내는 54개의 기호는 5개의 원소를 분할하는 52가지 방법에 기초하였다.]]

[[수학]]에서, [[집합]]의 '''분할'''(分割, {{llang|en|partition|파티션}})은 주어진 [[집합]]의 원소들을 서로 겹치지 않는 [[부분 집합]]들로 남김 없이 분류하는 방법이다. [[덮개 (위상수학)|덮개]]의 특수한 경우이다. 덮개를 구성하는 집합들은 모든 원소를 남김 없이 원소로 포함하지만, 서로 겹칠 수 있다. [[서로소 집합족]]을 구성하는 집합들은 서로 겹치지 않지만, [[합집합]]에 포함되지 않는 원소가 존재할 수 있다. 예를 들어, 집합 <math>\{1,2,3,4,5\}</math>이 주어졌을 때, <math>\{1,4\}</math>와 <math>\{2,3,5\}</math>는 분할을 이룬다. 반면 <math>\{1,2,4\}</math>와 <math>\{2,3,5\}</math>는 2가 겹치므로 집합의 분할이 아니며, <math>\{1,4\}</math>와 <math>\{2,5\}</math>도 4가 빠져 있으므로 분할이 아니다.

분할의 개념은 [[동치 관계]]의 개념과 사실상 [[동치]]이다. 구체적으로, 주어진 집합의 분할과 [[동치 관계]] 사이에 [[일대일 대응]]이 존재하며, 이는 분할 격자와 동치 관계 격자 사이의 격자 구조를 보존한다.

[[원순서]]의 개념은 분할 위의 [[부분 순서]]의 개념과 [[동치]]이다. 이러한 대응 관계에 따라, [[부분 순서 집합]]의 [[순서론]]적 성질들은 대부분 [[원순서 집합]] 위에서도 유효하다.

[[선택 공리]]에 따라, 분할의 원소의 대표 원소들을 항상 고를 수 있다. 물론, [[유한 집합]]의 분할의 경우 [[선택 공리]]를 필요로 하지 않는다. 예를 들어, 다섯 원소 집합를 분할하는 <math>\{1,2,4\}</math>와 <math>\{2,3,5\}</math>의 대표 원소들로서 1과 3을 고를 수 있고, 2와 2를 고를 수도 있다. 이 문제에 대한 [[역 (논리학)|역]]은 분할의 대표 원소들를 고르는 함수의 존재가 [[선택 공리]]를 함의하는지 여부이며, 이는 [[열린 문제]]이다.

두 분할은 어느 하나가 다른 하나보다 더 ‘자세한’ 분류인지에 따라 비교할 수 있다. 예를 들어, 52장의 [[플레잉 카드]]는 색깔에 따라 두 종류로 분류할 수 있으며, 모양에 따라 네 종류로 분류할 수 있는데, 모양에 따른 분할은 색깔에 따른 분할보다 자세한 분류이다. 주어진 집합의 분할의 집합은 이 [[이항 관계]]에 따라 [[부분 순서 집합]]을 이루며, 또한 [[완비 격자]]를 이룬다. [[유한 집합]]의 분할 격자는 유한 [[완전 그래프]]의 [[그래프 매트로이드]]의 닫힌집합 [[격자 (순서론)|격자]]와 [[동형]]이며, 특히 [[기하 격자]]를 이룬다.

[[유한 집합]]의 분할의 수는 [[벨 수]]로 나타내어진다.

== 정의 ==
집합 <math>X</math>의 '''분할'''은 [[서로소 집합]]들로 구성된 [[덮개 (위상수학)|덮개]]이다. 즉, 다음 세 조건을 만족시키는 [[집합족]] <math>\mathcal P\subseteq\mathcal P(X)</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>\varnothing\notin\mathcal P</math>이다. (이는 본질적으로 같은 분류 방법이 실제로도 같게 하기 위한 조건이다. 일부 저자는 이 조건을 생략한다.)
* <math>X</math>를 [[덮개 (위상수학)|덮는다]]. 즉, <math>\textstyle\bigcup\mathcal P=X</math>이다. 즉, 임의의 <math>x\in X</math>에 대하여, <math>x\in P_x</math>인 <math>P_x\in\mathcal P</math>가 존재한다.
* [[서로소 집합족]]이다. 즉, 임의의 <math>P,Q\in\mathcal P</math>에 대하여, 만약 <math>A\ne B</math>라면 <math>A\cap B=\varnothing</math>이다.

== 성질 ==
=== 동치 관계와의 관계 ===
{{참고|동치 관계}}
집합 <math>X</math> 위의 임의의 [[동치 관계]] <math>\sim</math>에 대하여, 그 [[몫집합]] <math>X/{\sim}</math>은 <math>X</math>의 분할이다. 반대로, <math>X</math>의 임의의 분할 <math>\mathcal P</math>가 주어졌을 때, <math>X</math> 위에 이항 관계
:<math>x\sim y\iff\exists P\in\mathcal P\colon x,y\in P</math>
를 정의할 수 있다. 즉, 이는 두 원소가 분할 속 어떤 같은 집합에 속하는 이항 관계를 나타낸다. 이는 <math>X</math> 위의 [[동치 관계]]이다. 동치 관계와 분할 사이의 두 연산은 서로 역연산이므로, 동치 관계와 분할의 개념은 사실 서로 [[동치]]이다.<ref name="schechter">{{서적 인용|last= Schechter |first= Eric |title= Handbook of Analysis and Its Foundations |year= 1997 |publisher= Academic Press |language=en |isbn= 0-12-622760-8}}</ref>{{rp|54}}

=== 원순서와의 관계 ===
{{본문|원순서 집합}}
[[집합]] <math>X</math>가 주어졌을 때, <math>X</math> 위의 [[원순서]]의 개념은 <math>X</math>의 분할 및 이 분할 위의 [[부분 순서]]의 조합과 [[동치]]이다.

=== 집합론적 성질 ===
[[체르멜로-프렝켈 집합론]] <math>\mathsf{ZF}</math>에서, 다음 두 명제가 서로 [[동치]]이며, 이를 '''분할 원리'''(分割原理, {{llang|en|partition principle}})라고 한다.
* 임의의 두 집합 <math>X,Y</math>에 대하여, 만약 [[전사 함수]] <math>X\to Y</math>가 존재한다면, [[단사 함수]] <math>Y\to X</math>가 존재한다.
* 임의의 집합 <math>X</math> 및 그 분할 <math>\mathcal P</math>에 대하여, [[단사 함수]] <math>\mathcal P\to X</math>가 존재한다. 즉, 집합의 분할의 [[집합의 크기|크기]]는 집합의 크기를 넘지 않는다.
[[선택 공리]]는 분할 원리를 함의한다. 이는 선택 함수 <math>f\colon\mathcal P\to X</math>가 존재하며, 임의의 <math>P\in\mathcal P</math>에 대하여 <math>f(P)\in P</math>이므로 <math>f</math>가 [[단사 함수]]이기 때문이다. 그러나 [[선택 공리]]와 분할 원리가 [[동치]]인지 여부는 아직도 알려지지 않았다.

=== 순서론적 성질 ===
[[집합]] <math>X</math>의 '''[[덮개 (위상수학)|덮개]]'''는 [[합집합]]이 <math>X</math> 전체인 [[집합족]]이다. [[집합]] <math>X</math>의 두 덮개 <math>\mathcal C</math>, <math>\mathcal D</math>가 주어졌을 때,
* 만약 임의의 <math>C\in\mathcal C</math>에 대하여, <math>C\subseteq D</math>인 <math>D\in\mathcal D</math>를 찾을 수 있다면, <math>\mathcal C</math>가 <math>\mathcal D</math>의 '''[[세분 (위상수학)|세분]]'''이라고 한다. 이를 <math>\mathcal C\lesssim\mathcal D</math>로 적자. 
* 임의의 <math>C\in\mathcal C</math>에 대하여, <math>\textstyle\operatorname{star}(C,\mathcal C)=\bigcup_{C'\in\mathcal C}^{C\cap C'\ne\varnothing}C'</math>라고 하자. 만약 임의의 <math>C\in\mathcal C</math>에 대하여, <math>\operatorname{star}(C,\mathcal C)\subseteq D</math>인 <math>D\in\mathcal D</math>를 찾을 수 있다면, <math>\mathcal C</math>가 <math>\mathcal D</math>의 '''[[성형 세분]]'''이라고 한다. 이를 <math>\mathcal C^\star\lesssim\mathcal D</math>라고 적자.
세분은 덮개 집합 위의 [[원순서]]를 이룬다. 성형 세분은 [[추이적 관계]]이지만, 일반적으로 [[반사 관계]]가 아니다. 모든 성형 세분은 세분이지만, 그 역은 성립하지 않는다.

특히, 모든 분할은 [[덮개 (위상수학)|덮개]]이므로 [[세분 (위상수학)|세분]] 관계와 [[성형 세분]] 관계를 정의할 수 있다. 분할의 세분은 분할의 원소들을 추가로 분할하여 얻는 집합 전체의 분할이다. (덮개 원소에 대하여 다시 덮개를 부여하면 덮개의 세분을 얻지만, 모든 덮개의 세분이 이렇게 얻어지는 것은 아니다.) 분할의 경우, 세분과 성형 세분은 서로 [[동치]]이다. 이는 [[집합]] <math>X</math>의 분할 <math>\mathcal P</math>은 [[서로소 집합족]]이므로, 임의의 <math>P\in\mathcal P</math>에 대하여
:<math>\operatorname{star}(P,\mathcal P)=P</math>
이기 때문이다. 또한, 세분은 분할의 집합 위의 [[부분 순서]]를 이룬다. 즉, 만약 <math>\mathcal P\lesssim\mathcal Q\lesssim\mathcal P</math>라면, <math>\mathcal P=\mathcal Q</math>이다. (이는 덮개의 경우 성립하지 않는다.) 따라서, 분할의 세분 관계는 <math>\le</math>로 적을 수 있다. 세분 관계를 갖춘 분할 집합은 [[완비 격자]]를 이룬다. 즉, 임의의 분할들의 족에 대하여, 이들 모두를 세분하는 가장 엉성한 분할이 존재하며, 또한 이들 모두에 의하여 세분되는 가장 섬세한 분할이 존재한다. 구체적으로, [[집합]] <math>X</math>의 임의의 분할들의 족 <math>(\mathcal P_i)_{i\in I}</math>에 대하여,
:<math>\bigwedge_{i\in I}\mathcal P_i=\left\{\bigcap_{i\in I}P_i\colon P_i\in\mathcal P_i\right\}</math>
는 각 분할의 원소들의 [[교집합]]들로 구성된 분할이다. 이 분할은 모든 <math>\mathcal P_i</math>의 세분이며, 모든 <math>\mathcal P_i</math>를 세분하는 임의의 분할은 이 분할의 세분이다. 또한, [[집합]] <math>X</math>의 임의의 [[덮개 (위상수학)|덮개]] <math>\mathcal C</math>에 대하여, <math>\mathcal C\lesssim\mathcal C^{\star\star\cdots}</math>인 가장 섬세한 분할 <math>\mathcal C^{\star\star\cdots}</math>가 존재하며, 이는 다음과 같다.<ref name="Willard" />{{rp|249, Exercise 36A.2}}
:<math>\mathcal C^{\star\star\cdots}=\{C\cup\operatorname{star}(C,\mathcal C)\cup\operatorname{star}(\operatorname{star}(C,\mathcal C),\mathcal C)\cup\cdots\colon C\in\mathcal C\}</math>
특히, 임의의 분할족 <math>(\mathcal P_i)_{i\in I}</math>에 대하여,
:<math>\bigvee_{i\in I}\mathcal P_i=\bigg(\bigcup_{i\in I}\mathcal P_i\bigg)^{\star\star\cdots}</math>
는 분할이며, 모든 <math>\mathcal P_i</math>를 세분으로 갖는 분할 가운데 가장 섬세하다.

[[유한 집합]]의 분할 격자는 [[기하 격자]]를 이룬다.<ref>{{서적 인용|이름=Garrett|성=Birkhoff|저자링크=개릿 버코프|날짜=1967|제목=Lattice theory|판=3판|권=25|총서=AMS Colloquium Publications|출판사=American Mathematical Society|언어=en}}</ref>{{rp|95}} 구체적으로, 크기 <math>n</math>의 [[유한 집합]] <math>\{1,\ldots,n\}</math>의 분할 격자는 [[완전 그래프]] <math>K_n</math>의 [[그래프 매트로이드]]의 닫힌집합 격자와 [[동형]]이다.

[[집합]] <math>X</math>의 [[덮개 (위상수학)|덮개]] <math>\mathcal C</math>에 대하여, 다음 세 조건이 서로 [[동치]]이다.<ref name="Willard">{{서적 인용
|성1=Willard
|이름1=Stephen
|제목=General topology
|url=https://archive.org/details/generaltopology00will_0
|언어=en
|총서=Addison-Wesley Series in Mathematics
|출판사=Addison-Wesley
|위치=Reading, Massachusetts; Menlo Park, California; London; Don Mills, Ontario
|날짜=1970
|isbn=978-0-201-08707-9
|mr=0264581
|zbl=0205.26601
}}</ref>{{rp|249, Exercise 36A.3}}
* <math>\mathcal C^\star\lesssim\mathcal C</math>. 즉, 스스로의 [[성형 세분]]이다.
* <math>\mathcal C^{\star\star\cdots}\lesssim\mathcal C</math>
* <math>\mathcal C\lesssim\mathcal P\lesssim\mathcal C</math>인 분할 <math>\mathcal P</math>가 존재한다.

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

:1, 1, 2, 5, 15, 52, 203 {{OEIS|A000110}}

벨 수에 대해 [[점화식]]

:<math>B_{n+1}=\sum_{k=0}^n{n \choose k}B_k</math>

이 성립하며, 다음과 같은 [[생성함수 (수학)|지수생성함수]]를 가진다.

:<math>\sum_{n=0}^\infty\frac{B_n}{n!}z^n=e^{e^z-1}</math>

[[파일:BellNumberAnimated.gif|right|섬네일|벨 삼각형의 구성]]

[[벨 삼각형]]을 이용하여 벨 수를 계산할 수도 있다. 각 행의 첫 수는 이전 행의 마지막 수이고, 뒤 잇는 수들은 왼쪽과 왼쪽 위의 수를 더한 것이다. 벨 수는 삼각형의 양 옆에서 각각 차례대로 나열된다. 삼각형 안에 있는 수도 의미를 가지는데, 예를 들어 3행 2열의 수가 3이라는 것은 집합 <math>\{1,2,3\}</math>의 모든 한원소 집합의 원소가 2이거나 2보다 작다는 것을 만족하는 분할이 3가지라는 것이다.

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

''n''원소 집합의 비교차분할의 개수는 [[카탈랑 수]] <math>C_n</math>이다.

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

== 예 ==
[[파일:Set partitions 4; Hasse; circles.svg|섬네일|300px|4개의 원소를 갖는 집합의 분할과 세분 순서의 [[하세 도형]]. 총 15개의 분할로 이루어진다.]]
집합 <math>\{1,2,3\}</math>의 분할은 5개이며, 다음과 같다.
* <math>\{\{1,2,3\}\}</math>
* <math>\{\{1\},\{2,3\}\}</math>
* <math>\{\{2\},\{3,1\}\}</math>
* <math>\{\{3\},\{1,2\}\}</math>
* <math>\{\{1\},\{2\},\{3\}\}</math>

다음과 같은 집합족들은 <math>\{1,2,3\}</math>의 분할이 아니다.
* <math>\{\varnothing,\{1,2\},\{3\}\}</math>은 공집합을 원소로 포함하므로 <math>\{1,2,3\}</math>의 분할이 아니다.
* <math>\{\{1,2\},\{2,3\}\}</math>은 서로소가 아니므로 <math>\{1,2,3\}</math>의 분할이 아니다.
* <math>\{\{1\},\{2\}\}</math>. 합집합이 <math>\{1,2,3\}</math>이 아니기 때문이다.

4원소 집합의 분할격자는 15개의 원소가 있으며, 왼쪽 그림에서 [[하세 도형]]으로 표현된다. 이 분할격자는, 기하격자와 동일한 개념인 [[매트로이드]]에도 대응한다. 이때 기저집합은 격자의 [[원자 (순서론)|원자]]들, 즉 (''n'' - 2)원소 집합과 2원소 집합으로 이루어진 분할들로 이루어진다. 이들 원자 분할은 [[완전 그래프]]의 변들과 일대일 대응한다. 어떤 주어진 원자 분할들의 집합의 [[매트로이드#폐포|매트로이드 폐포]]는, 그들 모두보다 엉성한 분할들 중 가장 섬세한 하나이며, 그래프 이론적으로 이는 주어진 변들에 의한 부분 그래프의 [[연결성분]]이다. 이로써 이 분할 격자는 완전 그래프의 [[그래프 매트로이드]]({{llang|en|graphic matroid}})이다.

[[정수]]는 [[홀수]]와 [[짝수]]로, 음과 양의 정수 및 0으로, [[소수 (수론)|소수]]와 [[합성수]] 및 0, 1, –1로 분류되며, 이들은 모두 정수 집합 <math>\mathbb Z</math>에 대한 분할을 이룬다.

[[공집합]]의 분할은 공집합이 유일하다.

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

공집합이 아닌 집합 <math>X</math>에 대하여, <math>\{X\}</math>는 <math>X</math>의 분할이다.

공집합이 아닌 집합 <math>X</math> 및 공집합이 아닌 [[진부분집합]] <math>\varnothing\subsetneq P\subsetneq X</math>에 대하여, <math>\{P,X\setminus P\}</math>는 <math>X</math>의 분할을 이룬다.

52장의 [[플레잉 카드]]의 집합
:<math>\{\diamondsuit_1,\ldots,\diamondsuit_{13},\heartsuit_1,\ldots,\heartsuit_{13},\clubsuit_1,\ldots,\clubsuit_{13},\spadesuit_1,\ldots,\spadesuit_{13}\}</math>
을 생각하자. 이는 색깔에 따라 2개의 집합으로 분할될 수 있다.
:<math>\mathcal P=\{\{\diamondsuit_1,\ldots,\diamondsuit_{13},\heartsuit_1,\ldots,\heartsuit_{13}\},\{\clubsuit_1,\ldots,\clubsuit_{13},\spadesuit_1,\ldots,\spadesuit_{13}\}\}</math>
또한, 모양에 따라 다시 4개의 집합으로 분할될 수 있다.
:<math>\mathcal Q=\{\{\diamondsuit_1,\ldots,\diamondsuit_{13}\},\{\heartsuit_1,\ldots,\heartsuit_{13}\},\{\clubsuit_1,\ldots,\clubsuit_{13}\},\{\spadesuit_1,\ldots,\spadesuit_{13}\}\}</math>
모양에 따른 분할은 색깔에 따른 분할의 세분이다.
:<math>\mathcal P\le\mathcal Q</math>

== 같이 보기 ==
* {{위키공용분류-줄}}
* [[클러스터 분석]]

== 참고 문헌 ==
{{각주}}
* {{서적 인용|last= Brualdi |first= Richard A. |title= Introductory Combinatorics |url= https://archive.org/details/introductorycomb0000brua_h9s5 |edition= 4|year= 2004 |publisher= Pearson Prentice Hall |language=en |isbn= 0-13-100119-1}}

== 외부 링크 ==
* {{eom|제목=Partition}}
* {{매스월드|id=SetPartition|제목=Set partition}}
* {{nlab|id=partition|제목=Partition}}
* {{플래닛매스|urlname=partition|제목=Partition}}
* {{proofwiki|id=Definition:Set Partition|제목=Definition: set partition}}
{{전거 통제}}

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