집합의 분할


수학에서 집합의 분할(集合-分割, partition of a set)은 집합의 원소들을 비공(non-empty, 非空) 부분집합들에게 나눠주어, 모든 원소가 각자 정확히 하나의 부분집합에 속하게끔 하는 것이다. 집합 의 분할은 의 공집합이 아닌 부분집합들로 이루어진, 분리합집합이 인 집합들이다.
정의[편집]
집합 의 분할은 다음 조건을 만족하는 집합족 로 정의된다.[1]
즉,
- ,
- 이고 이면
여기서, 공집합을 배제하는 것은 정형화를 위한 선택적인 규정이다.
예[편집]
- 한원소 집합 의 분할은 로 유일하다.
- 공집합의 분할은 공집합으로 유일하다.
- 공집합이 아닌 집합 는 모두 분할 를 가진다. 이를 자명 분할(trivial partition)이라고 한다.
- 공집합이 아닌 집합 의 공집합이 아닌 진부분집합 와 여집합 는 의 분할을 이룬다.
- 집합 의 분할은 5개이다.
- , 즉
- , 즉
- , 즉
- , 즉
- , 즉
- 다음은 의 분할이 아니다.
- 은 공집합을 원소로 포함하므로, 의 분할이 아니며, 다른 어떤 집합의 분할도 아니다.
- 은 서로소이지 않으므로, 의 분할이 아니며, 다른 어떤 집합의 분할도 아니다.
- . 합집합이 이 아니기 때문이다.
- 정수는 홀수와 짝수로, 음과 양의 정수 및 0으로, 소수와 합성수 및 0과 1로 분류되며, 이들은 모두 정수 집합에 대한 분할에 대응한다.
동치관계와의 관계[편집]
집합 위의 임의의 동치관계 에 대해, 그에 의한 몫집합 은 의 분할이다. 역으로 의 임의의 분할 에 대해,
즉 가 안의 같은 집합에 속한다는, 위의 이항관계 는 위의 동치관계이다. 그러므로 동치관계와 분할의 개념은 동등하다.[2]
선택 공리에 의하면 집합 의 임의의 분할에 대하여 분할의 각 원소에서 하나의 원소를 취하여 구성한 의 부분집합이 존재한다. 그러므로 집합 상의 동치관계가 주어졌을 때 각 동치류로부터 하나의 대표 원소를 선택해내는 것이 가능하다.
분할의 세분[편집]

집합 의 두 분할 에 대하여, 의 모든 원소가 의 어떤 원소의 부분집합이라면, 를 의 세분(細分, refinement)이라고 하고, 로 표기한다. (가 보다 더 섬세하다(纖細, finer), 또는 가 보다 더 엉성하다(coarser)로 읽는다.)
는 의 모든 분할의 집합 위의 부분 순서이다. 임의의 부분집합이 상한과 하한을 가지므로, 이는 격자를 이루며, 나아가 유한 집합의 분할인 경우 기하격자를 이룬다.[3] 4원소 집합의 분할격자는 15개의 원소가 있으며, 왼쪽 그림에서 하세 도형으로 표현된다.
이 분할격자는, 기하격자와 동일한 개념인 매트로이드에도 대응한다. 이때 기저집합은 격자의 원자들, 즉 (n - 2)원소 집합과 2원소 집합으로 이루어진 분할들로 이루어진다. 이들 원자 분할은 완전 그래프의 변들과 일대일 대응한다. 어떤 주어진 원자 분할들의 집합의 매트로이드 폐포는, 그들 모두보다 엉성한 분할들 중 가장 섬세한 하나이며, 그래프 이론적으로 이는 주어진 변들에 의한 부분 그래프의 연결성분이다. 이로써 이 분할 격자는 완전 그래프의 그래프 매트로이드이다.
동치관계에 의한 분할의 세분의 예로, D를 52장의 플레잉카드의 집합이라 하면, D 상의 '같은 색깔'에 의한 동치관계 ~C는 두 개의 동치류, 즉 {붉은색 카드}, {검은색 카드}를 가지고, '같은 슈트'에 의한 동치관계 ~S는 {하트}, {다이아몬드}, {클럽}, {스페이드} 4개의 동치류를 가진다. ~S에 대응하는 분할은 ~C에 대응하는 분할의 세분이다.
비교차 분할[편집]
집합 위의 순환순서는 간단히 말해 원 위에[4] 모든 원소를 서로 다른 위치에 나열하고, 회전방향을 정하여 형성되는 삼항관계이다. 그 예로 모든 요일들의 집합 위에 자연적으로 정의한 순환순서에서, [화요일 , 수요일 , 토요일], [금요일 , 수요일 , 목요일]이 성립하지만 [금요일 , 화요일 , 월요일]은 성립하지 않는다.
순환순서가 정의된 유한집합 의 분할 와 그에 대응하는 동치관계 에 대하여, 만약 의 서로 다른 두 원소 에서 각각 임의의 서로 다른 두 원소 를 취했을 때, 그들이 와 를 동시에 만족하지 않는다면, 분할 (또는 동치관계 )가 교차하지 않는다고 한다. 이는 다르게 말해 원 또는 다각형에 표기한 분할이 교착하지 않는다는 것이다. 집합의 모든 비교차 분할 역시 격자를 이룬다. 그러나 이음 연산이 일치하지 않기 때문에, 모든 분할이 이루는 격자의 부분격자는 아니다.
분할의 수[편집]
n개 원소의 집합을 분할하는 방법수는 벨 수 이다. 앞의 6개의 벨 수는 다음과 같다.
벨 수에 대해 점화식
이 성립하며, 다음과 같은 지수생성함수를 가진다.
벨 삼각형을 이용하여 벨 수를 계산할 수도 있다. 각 행의 첫 수는 이전 행의 마지막 수이고, 뒤 잇는 수들은 왼쪽과 왼쪽 위의 수를 더한 것이다. 벨 수는 삼각형의 양 옆에서 각각 차례대로 나열된다. 삼각형 안에 있는 수도 의미를 가지는데, 예를 들어 3행 2열의 수가 3이라는 것은 집합 의 모든 한원소 집합의 원소가 2이거나 2보다 작다는 것을 만족하는 분할이 3가지라는 것이다.
n원소 집합을 정확히 k 개의 집합으로 분할하는 방법 수는 제2종 스털링 수 이다.
n원소 집합의 비교차분할의 개수는 카탈랑 수 이다.
같이 보기[편집]
![]() |
위키미디어 공용에 관련된 미디어 분류가 있습니다. |
각주[편집]
- ↑ Lucas, John F. (1990). 《Introduction to Abstract Mathematics》 (영어). Rowman & Littlefield. 187쪽. ISBN 9780912675732.
- ↑ Schechter, p. 54
- ↑ Birkhoff, Garrett (1967). 《Lattice theory》. AMS Colloquium Publications (영어) 25 3판. American Mathematical Society.
- ↑ 유한 집합의 경우 다각형의 꼭짓점으로 대신해도 무방하다.
참고 문헌[편집]
- Brualdi, Richard A. (2004). 《Introductory Combinatorics》 (영어) 4판. Pearson Prentice Hall. ISBN 0-13-100119-1.
- Schechter, Eric (1997). 《Handbook of Analysis and Its Foundations》 (영어). Academic Press. ISBN 0-12-622760-8.