집합의 분할

나눠 묶인 우표들. 동시에 두 묶음에 속하는 우표는 없으며, 빈 묶음도 없다.

5개 원소로 이루어진 집합의 52개의 분할

《겐지모노가타리》의 각 장을 나타내는 54개의 기호는 5개의 원소를 분할하는 52가지 방법에 기초하였다.

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

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

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

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

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

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

정의

집합 $X$의 분할은 서로소 집합들로 구성된 덮개이다. 즉, 다음 세 조건을 만족시키는 집합족 ${\mathcal {P}}\subseteq {\mathcal {P}}(X)$이다.

• 공집합을 원소로 하지 않는다. 즉, $\varnothing \notin {\mathcal {P}}$이다. (이는 본질적으로 같은 분류 방법이 실제로도 같게 하기 위한 조건이다. 일부 저자는 이 조건을 생략한다.)
• $X$를 덮는다. 즉, $\textstyle \bigcup {\mathcal {P}}=X$이다. 즉, 임의의 $x\in X$에 대하여, $x\in P_{x}$인 $P_{x}\in {\mathcal {P}}$가 존재한다.
• 서로소 집합족이다. 즉, 임의의 $P,Q\in {\mathcal {P}}$에 대하여, 만약 $A\neq B$라면 $A\cap B=\varnothing$이다.

성질

동치 관계와의 관계

 동치 관계 문서를 참고하십시오.

집합 $X$ 위의 임의의 동치 관계 $\sim$에 대하여, 그 몫집합 $X/{\sim }$은 $X$의 분할이다. 반대로, $X$의 임의의 분할 ${\mathcal {P}}$가 주어졌을 때, $X$ 위에 이항 관계

$x\sim y\iff \exists P\in {\mathcal {P}}\colon x,y\in P$

를 정의할 수 있다. 즉, 이는 두 원소가 분할 속 어떤 같은 집합에 속하는 이항 관계를 나타낸다. 이는 $X$ 위의 동치 관계이다. 동치 관계와 분할 사이의 두 연산은 서로 역연산이므로, 동치 관계와 분할의 개념은 사실 서로 동치이다.^:54

원순서와의 관계

 이 부분의 본문은 원순서 집합입니다.

집합 $X$가 주어졌을 때, $X$ 위의 원순서의 개념은 $X$의 분할 및 이 분할 위의 부분 순서의 조합과 동치이다.

집합론적 성질

체르멜로-프렝켈 집합론 ${\mathsf {ZF}}$에서, 다음 두 명제가 서로 동치이며, 이를 분할 원리(分割原理, 영어: partition principle)라고 한다.

• 임의의 두 집합 $X,Y$에 대하여, 만약 전사 함수 $X\to Y$가 존재한다면, 단사 함수 $Y\to X$가 존재한다.
• 임의의 집합 $X$ 및 그 분할 ${\mathcal {P}}$에 대하여, 단사 함수 ${\mathcal {P}}\to X$가 존재한다. 즉, 집합의 분할의 크기는 집합의 크기를 넘지 않는다.

선택 공리는 분할 원리를 함의한다. 이는 선택 함수 $f\colon {\mathcal {P}}\to X$가 존재하며, 임의의 $P\in {\mathcal {P}}$에 대하여 $f(P)\in P$이므로 $f$가 단사 함수이기 때문이다. 그러나 선택 공리와 분할 원리가 동치인지 여부는 아직도 알려지지 않았다.

순서론적 성질

집합 $X$의 덮개는 합집합이 $X$ 전체인 집합족이다. 집합 $X$의 두 덮개 ${\mathcal {C}}$, ${\mathcal {D}}$가 주어졌을 때,

• 만약 임의의 $C\in {\mathcal {C}}$에 대하여, $C\subseteq D$인 $D\in {\mathcal {D}}$를 찾을 수 있다면, ${\mathcal {C}}$가 ${\mathcal {D}}$의 세분이라고 한다. 이를 ${\mathcal {C}}\lesssim {\mathcal {D}}$로 적자.
• 임의의 $C\in {\mathcal {C}}$에 대하여, $\textstyle \operatorname {star} (C,{\mathcal {C}})=\bigcup _{C'\in {\mathcal {C}}}^{C\cap C'\neq \varnothing }C'$라고 하자. 만약 임의의 $C\in {\mathcal {C}}$에 대하여, $\operatorname {star} (C,{\mathcal {C}})\subseteq D$인 $D\in {\mathcal {D}}$를 찾을 수 있다면, ${\mathcal {C}}$가 ${\mathcal {D}}$의 성형 세분이라고 한다. 이를 ${\mathcal {C}}^{\star }\lesssim {\mathcal {D}}$라고 적자.

세분은 덮개 집합 위의 원순서를 이룬다. 성형 세분은 추이적 관계이지만, 일반적으로 반사 관계가 아니다. 모든 성형 세분은 세분이지만, 그 역은 성립하지 않는다.

특히, 모든 분할은 덮개이므로 세분 관계와 성형 세분 관계를 정의할 수 있다. 분할의 세분은 분할의 원소들을 추가로 분할하여 얻는 집합 전체의 분할이다. (덮개 원소에 대하여 다시 덮개를 부여하면 덮개의 세분을 얻지만, 모든 덮개의 세분이 이렇게 얻어지는 것은 아니다.) 분할의 경우, 세분과 성형 세분은 서로 동치이다. 이는 집합 $X$의 분할 ${\mathcal {P}}$은 서로소 집합족이므로, 임의의 $P\in {\mathcal {P}}$에 대하여

$\operatorname {star} (P,{\mathcal {P}})=P$

이기 때문이다. 또한, 세분은 분할의 집합 위의 부분 순서를 이룬다. 즉, 만약 ${\mathcal {P}}\lesssim {\mathcal {Q}}\lesssim {\mathcal {P}}$라면, ${\mathcal {P}}={\mathcal {Q}}$이다. (이는 덮개의 경우 성립하지 않는다.) 따라서, 분할의 세분 관계는 $\leq$로 적을 수 있다. 세분 관계를 갖춘 분할 집합은 완비 격자를 이룬다. 즉, 임의의 분할들의 족에 대하여, 이들 모두를 세분하는 가장 엉성한 분할이 존재하며, 또한 이들 모두에 의하여 세분되는 가장 섬세한 분할이 존재한다. 구체적으로, 집합 $X$의 임의의 분할들의 족 $({\mathcal {P}}_{i})_{i\in I}$에 대하여,

$\bigwedge _{i\in I}{\mathcal {P}}_{i}=\left\{\bigcap _{i\in I}P_{i}\colon P_{i}\in {\mathcal {P}}_{i}\right\}$

는 각 분할의 원소들의 교집합들로 구성된 분할이다. 이 분할은 모든 ${\mathcal {P}}_{i}$의 세분이며, 모든 ${\mathcal {P}}_{i}$를 세분하는 임의의 분할은 이 분할의 세분이다. 또한, 집합 $X$의 임의의 덮개 ${\mathcal {C}}$에 대하여, ${\mathcal {C}}\lesssim {\mathcal {C}}^{\star \star \cdots }$인 가장 섬세한 분할 ${\mathcal {C}}^{\star \star \cdots }$가 존재하며, 이는 다음과 같다.^{:249, Exercise 36A.2}

${\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}}\}$

특히, 임의의 분할족 $({\mathcal {P}}_{i})_{i\in I}$에 대하여,

$\bigvee _{i\in I}{\mathcal {P}}_{i}={\bigg (}\bigcup _{i\in I}{\mathcal {P}}_{i}{\bigg )}^{\star \star \cdots }$

는 분할이며, 모든 ${\mathcal {P}}_{i}$를 세분으로 갖는 분할 가운데 가장 섬세하다.

유한 집합의 분할 격자는 기하 격자를 이룬다.^:95 구체적으로, 크기 $n$의 유한 집합 $\{1,\ldots ,n\}$의 분할 격자는 완전 그래프 $K_{n}$의 그래프 매트로이드의 닫힌집합 격자와 동형이다.

집합 $X$의 덮개 ${\mathcal {C}}$에 대하여, 다음 세 조건이 서로 동치이다.^{:249, Exercise 36A.3}

• ${\mathcal {C}}^{\star }\lesssim {\mathcal {C}}$. 즉, 스스로의 성형 세분이다.
• ${\mathcal {C}}^{\star \star \cdots }\lesssim {\mathcal {C}}$
• ${\mathcal {C}}\lesssim {\mathcal {P}}\lesssim {\mathcal {C}}$인 분할 ${\mathcal {P}}$가 존재한다.

분할의 수

n개 원소의 집합을 분할하는 방법수는 벨 수 $B_{n}$이다. 앞의 6개의 벨 수는 다음과 같다.

1, 1, 2, 5, 15, 52, 203 (OEIS의 수열 A000110)

벨 수에 대해 점화식

$B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}$

이 성립하며, 다음과 같은 지수생성함수를 가진다.

$\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}$

벨 삼각형의 구성

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

n원소 집합을 정확히 k개의 집합으로 분할하는 방법 수는 제2종 스털링 수 $S(n,k)$이다.

n원소 집합의 비교차분할의 개수는 카탈랑 수 $C_{n}$이다.

$C_{n}={\frac {1}{n+1}}{2n \choose n}$

예

4개의 원소를 갖는 집합의 분할과 세분 순서의 하세 도형. 총 15개의 분할로 이루어진다.

집합 $\{1,2,3\}$의 분할은 5개이며, 다음과 같다.

• $\{\{1,2,3\}\}$
• $\{\{1\},\{2,3\}\}$
• $\{\{2\},\{3,1\}\}$
• $\{\{3\},\{1,2\}\}$
• $\{\{1\},\{2\},\{3\}\}$

다음과 같은 집합족들은 $\{1,2,3\}$의 분할이 아니다.

• $\{\varnothing ,\{1,2\},\{3\}\}$은 공집합을 원소로 포함하므로 $\{1,2,3\}$의 분할이 아니다.
• $\{\{1,2\},\{2,3\}\}$은 서로소가 아니므로 $\{1,2,3\}$의 분할이 아니다.
• $\{\{1\},\{2\}\}$. 합집합이 $\{1,2,3\}$이 아니기 때문이다.

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

정수는 홀수와 짝수로, 음과 양의 정수 및 0으로, 소수와 합성수 및 0, 1, –1로 분류되며, 이들은 모두 정수 집합 $\mathbb {Z}$에 대한 분할을 이룬다.

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

한원소 집합 $\{x\}$의 분할은 $\{\{x\}\}$이 유일하다.

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

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

52장의 플레잉 카드의 집합

$\{\diamondsuit _{1},\ldots ,\diamondsuit _{13},\heartsuit _{1},\ldots ,\heartsuit _{13},\clubsuit _{1},\ldots ,\clubsuit _{13},\spadesuit _{1},\ldots ,\spadesuit _{13}\}$

을 생각하자. 이는 색깔에 따라 2개의 집합으로 분할될 수 있다.

${\mathcal {P}}=\{\{\diamondsuit _{1},\ldots ,\diamondsuit _{13},\heartsuit _{1},\ldots ,\heartsuit _{13}\},\{\clubsuit _{1},\ldots ,\clubsuit _{13},\spadesuit _{1},\ldots ,\spadesuit _{13}\}\}$

또한, 모양에 따라 다시 4개의 집합으로 분할될 수 있다.

${\mathcal {Q}}=\{\{\diamondsuit _{1},\ldots ,\diamondsuit _{13}\},\{\heartsuit _{1},\ldots ,\heartsuit _{13}\},\{\clubsuit _{1},\ldots ,\clubsuit _{13}\},\{\spadesuit _{1},\ldots ,\spadesuit _{13}\}\}$

모양에 따른 분할은 색깔에 따른 분할의 세분이다.

${\mathcal {P}}\leq {\mathcal {Q}}$

같이 보기

• 위키미디어 공용에 집합의 분할 관련 미디어 분류가 있습니다.
• 클러스터 분석

참고 문헌

• Brualdi, Richard A. (2004). 《Introductory Combinatorics》 (영어) 4판. Pearson Prentice Hall. ISBN 0-13-100119-1. 

외부 링크

• “Partition”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Set partition”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Partition”. 《nLab》 (영어). 
• “Partition”. 《PlanetMath》 (영어). 
• “Definition: set partition”. 《ProofWiki》 (영어).