In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.

Every equivalence relation on a set defines a partition of this set, and every partition defines an equivalence relation. A set equipped with an equivalence relation or a partition is sometimes called a setoid, typically in type theory and proof theory.

Definition and notation 
A partition of a set X is a set of non-empty subsets of X such that every element x in X is in exactly one of these subsets (i.e., the subsets are nonempty mutually disjoint sets).

Equivalently, a family of sets P is a partition of X if and only if all of the following conditions hold:
The family P does not contain the empty set (that is ).
The union of the sets in P is equal to X (that is ). The sets in P are said to exhaust or cover X.  See also collectively exhaustive events and cover (topology).
 The intersection of any two distinct sets in P is empty (that is ). The elements of P are said to be pairwise disjoint or mutually exclusive. See also mutual exclusivity.

The sets in  are called the blocks, parts, or cells, of the partition.  If  then we represent the cell containing  by .  That is to say,  is notation for the cell in  which contains .  

Every partition  may be identified with an equivalence relation on , namely the relation  such that for any  we have  if and only if  (equivalently, if and only if ).  The notation  evokes the idea that the equivalence relation may be constructed from the partition.  Conversely every equivalence relation may be identified with a partition.  This is why it is sometimes said informally that "an equivalence relation is the same as a partition".  If P is the partition identified with a given equivalence relation , then some authors write .  This notation is suggestive of the idea that the partition is the set X divided in to cells.  The notation also evokes the idea that, from the equivalence relation one may construct the partition.

The rank of  is , if  is finite.

Examples 
The empty set  has exactly one partition, namely . (Note: this is the partition, not a member of the partition.)
For any non-empty set X, P =  is a partition of X, called the trivial partition.
Particularly, every singleton set {x} has exactly one partition, namely .
For any non-empty proper subset A of a set U, the set A together with its complement form a partition of U, namely, .
The set  has these five partitions (one partition per item):
 , sometimes written 1 | 2 | 3.
 , or 1 2 | 3.
 , or 1 3 | 2.
 , or 1 | 2 3.
 , or 123 (in contexts where there will be no confusion with the number).
The following are not partitions of :
  is not a partition (of any set) because one of its elements is the empty set.
  is not a partition (of any set) because the element 2 is contained in more than one block.
  is not a partition of  because none of its blocks contains 3; however, it is a partition of .

Partitions and equivalence relations 
For any equivalence relation on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting  precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent.

The axiom of choice guarantees for any partition of a set X the existence of a subset of X containing exactly one element from each part of the partition. This implies that given an equivalence relation on a set one can select a canonical representative element from every equivalence class.

Refinement of partitions 

A partition α of a set X is a refinement of a partition ρ of X—and we say that α is finer than ρ and that ρ is coarser than α—if every element of α is a subset of some element of ρ. Informally, this means that α is a further fragmentation of ρ.  In that case, it is written that α ≤ ρ.

This "finer-than" relation on the set of partitions of X is a partial order (so the notation "≤" is appropriate). Each set of elements has a least upper bound (their "join") and a greatest lower bound (their "meet"), so that it forms a lattice, and more specifically (for partitions of a finite set) it is a geometric lattice. The partition lattice of a 4-element set has 15 elements and is depicted in the Hasse diagram on the left.

The meet and join of partitions α and ρ are defined as follows.  The meet  is the partition whose blocks are the intersections of a block of α and a block of ρ, except for the empty set.  In other words, a block of  is the intersection of a block of α and a block of ρ that are not disjoint from each other.  To define the join , form a relation on the blocks A of α and the blocks B of ρ by A ~ B if A and B are not disjoint. Then  is the partition in which each block C is the union of a family of blocks connected by this relation.

Based on the equivalence between geometric lattices and matroids, this lattice of partitions of a finite set corresponds to a matroid in which the base set of the matroid consists of the atoms of the lattice, namely, the partitions with  singleton sets and one two-element set. These atomic partitions correspond one-for-one with the edges of a complete graph. The matroid closure of a set of atomic partitions is the finest common coarsening of them all; in graph-theoretic terms, it is the partition of the vertices of the complete graph into the connected components of the subgraph formed by the given set of edges. In this way, the lattice of partitions corresponds to the lattice of flats of the graphic matroid of the complete graph.

Another example illustrates refinement of partitions from the perspective of equivalence relations. If D is the set of cards in a standard 52-card deck, the same-color-as relation on D – which can be denoted ~C – has two equivalence classes: the sets {red cards} and {black cards}.  The 2-part partition corresponding to ~C has a refinement that yields the same-suit-as relation ~S, which has the four equivalence classes {spades}, {diamonds}, {hearts}, and {clubs}.

Noncrossing partitions
A partition of the set N = {1, 2, ..., n} with corresponding equivalence relation ~ is noncrossing if it has the following property: If four elements a, b, c and d of N having a < b < c < d satisfy a ~ c and b ~ d, then a ~ b ~ c ~ d. The name comes from the following equivalent definition: Imagine the elements 1, 2, ..., n of N drawn as the n vertices of a regular n-gon (in counterclockwise order). A partition can then be visualized by drawing each block as a polygon (whose vertices are the elements of the block). The partition is then noncrossing if and only if these polygons do not intersect.

The lattice of noncrossing partitions of a finite set forms a subset of the lattice of all partitions, but not a sublattice, since the join operations of the two lattices do not agree.

The noncrossing partition lattice has recently taken on importance because of its role in free probability theory.

Counting partitions 
The total number of partitions of an n-element set is the Bell number Bn. The first several Bell numbers are B0 = 1,
B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, and B6 = 203 . Bell numbers satisfy the recursion

 

and have the exponential generating function

The Bell numbers may also be computed using the Bell triangle
in which the first value in each row is copied from the end of the previous row, and subsequent values are computed by adding two numbers, the number to the left and the number to the above left of the position. The Bell numbers are repeated along both sides of this triangle. The numbers within the triangle count partitions in which a given element is the largest singleton.

The number of partitions of an n-element set into exactly k (non-empty) parts is the Stirling number of the second kind S(n, k).

The number of noncrossing partitions of an n-element set is the Catalan number

See also

 Exact cover
 Block design
 Cluster analysis
 List of partition topics
 Lamination (topology)
 MECE principle
 Partial equivalence relation
 Partition algebra
 Partition refinement
 Point-finite collection
 Rhyme schemes by set partition
 Weak ordering (ordered set partition)

Notes

References

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

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

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

즉,

 ,
 
 이고 이면 

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

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

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

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

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

분할의 세분 

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

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

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

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

비교차 분할 

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

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

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

1, 1, 2, 5, 15, 52, 203 

벨 수에 대해 점화식

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

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

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

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

같이 보기 

 클러스터 분석
 약한 순서의 정의법 중 하나는 집합의 분할에 순서를 정의하는 것이다.
 동치관계

각주

참고 문헌 
 
 

집합론의 기본 개념
집합족
조합론