집합의 분할

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
나눠 묶인 우표들. 동시에 두 묶음에 속하는 우표는 없으며, 빈 묶음도 없다.
5개 원소로 이루어진 집합의 52개의 분할
겐지 이야기》의 각 장을 나타내는 54개의 기호는 5개의 원소를 분할하는 52가지 방법에 기초하였다.

수학에서, 집합의 분할(集合-分割, partition of a set)은 집합의 원소들을 비공(non-empty, 非空) 부분집합들에게 나눠주어, 모든 원소가 각자 정확히 하나의 부분집합에 속하게끔 하는 것이다. 집합 의 분할은 의 공집합이 아닌 부분집합들로 이루어진, 분리합집합인 집합들이다.

정의[편집]

집합 분할은, 다음 조건을 만족하는 집합족 로 정의된다.[1]

  • 는 공집합을 원소로 하지 않는다.
  • 덮는다.
  • 서로소 집합족이다.

즉,

  • ,
  • 이고 이면

여기서, 공집합을 배제하는 것은 정형화를 위한 선택적인 규정이다.

[편집]

  • 한원소 집합 의 분할은, 로 유일하다.
  • 공집합의 분할은, 공집합으로 유일하다.
  • 공집합이 아닌 집합 는 모두 분할 를 가진다. 이를 자명 분할(trivial partition)이라고 한다.
  • 공집합이 아닌 집합 의 공집합이 아닌 진부분집합 여집합 의 분할을 이룬다.
  • 집합 의 분할은 5개이다.
    • , 즉
    • , 즉
    • , 즉
    • , 즉
    • , 즉
  • 다음은 의 분할이 아니다.
    • 은 공집합을 원소로 포함하므로, 의 분할이 아니며, 다른 어떤 집합의 분할도 아니다.
    • 은 서로소이지 않으므로, 의 분할이 아니며, 다른 어떤 집합의 분할도 아니다.
    • . 합집합이 이 아니기 때문이다.
  • 정수는 홀수와 짝수로, 음과 양의 정수 및 0으로, 소수와 합성수 및 0과 1로 분류되며, 이들은 모두 정수 집합에 대한 분할에 대응한다.

동치관계와의 관계[편집]

집합 위의 임의의 동치관계 에 대해, 그에 의한 몫집합 의 분할이다. 역으로 의 임의의 분할 에 대해,

안의 같은 집합에 속한다는, 위의 이항관계 위의 동치관계이다. 그러므로 동치관계와 분할의 개념은 동등하다.[2]

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

분할의 세분[편집]

4 원소 집합의 분할과 세분에 의한 부분 순서

집합 의 두 분할 에 대하여, 의 모든 원소가 의 어떤 원소의 부분집합이라면, 세분(細分, refinement)이라고 하고, 로 표기한다. (보다 더 섬세하다(纖細, finer), 또는 보다 더 엉성하다(coarser)로 읽는다.)

의 모든 분할의 집합 위의 부분 순서이다. 임의의 부분집합이 상한과 하한을 가지므로, 이는 격자를 이루며, 나아가 유한 집합의 분할인 경우 기하격자를 이룬다.[3]:95 4원소 집합의 분할격자는 15개의 원소가 있으며, 왼쪽 그림에서 하세 도형으로 표현된다.

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

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

비교차 분할[편집]

집합 위의 순환순서는 간단히 말해 위에[4] 모든 원소를 서로 다른 위치에 나열하고, 회전방향을 정하여 형성되는 삼항관계이다. 그 예로 모든 요일들의 집합 위에 자연적으로 정의한 순환순서에서, [화요일 , 수요일 , 토요일], [금요일 , 수요일 , 목요일]이 성립하지만 [금요일 , 화요일 , 월요일]은 성립하지 않는다.

순환순서가 정의된 유한집합 의 분할 와 그에 대응하는 동치관계 에 대하여, 만약 의 서로 다른 두 원소 에서 각각 임의의 서로 다른 두 원소 를 취했을 때, 그들이 를 동시에 만족하지 않는다면, 분할 (또는 동치관계 )가 교차하지 않는다고 한다. 이는 다르게 말해 원 또는 다각형에 표기한 분할이 교착하지 않는다는 것이다. 집합의 모든 비교차 분할 역시 격자를 이룬다. 그러나 이음 연산이 일치하지 않기 때문에, 모든 분할이 이루는 격자의 부분격자는 아니다.

분할의 수[편집]

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

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

벨 수에 대해 점화식

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

벨 삼각형의 구성

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

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

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

같이 보기[편집]

각주[편집]

  1. Lucas, John F. (1990). 《Introduction to Abstract Mathematics》 (영어). Rowman & Littlefield. 187쪽. ISBN 9780912675732. 
  2. Schechter, p. 54
  3. Birkhoff, Garrett (1967). 《Lattice theory》. AMS Colloquium Publications (영어) 25 3판. American Mathematical Society. 
  4. 유한 집합의 경우 다각형의 꼭짓점으로 대신해도 무방하다.

참고 문헌[편집]

  • 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.