# Partition (set theory)

In the set theory is a partition (also decomposition or classification ) of an amount M a lot P , the elements of non-empty subsets of M , so that each element of are M in exactly one element of P is contained. In other words: A partition of a set is a decomposition of this set into nonempty pairwise disjoint subsets. In particular, every partition of a set is also a cover for the set.

## Examples

The set system (= the set family) is a partition of the set . The elements of are pairwise disjoint subsets of . is not a partition of the set because 1 is in but not in any element of . ${\ displaystyle P = \ left \ {\ left \ {3,5 \ right \}, \ left \ {2,4,6 \ right \}, \ left \ {7,8,9 \ right \} \ right \}}$${\ displaystyle M = \ left \ {2,3,4,5,6,7,8,9 \ right \}}$${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle P}$${\ displaystyle N = \ left \ {1,2,3,4,5,6,7,8,9 \ right \}}$${\ displaystyle N}$${\ displaystyle P}$

The family of sets is not a partition of any set, because and with 2 contain a common element, i.e. they are not disjoint. ${\ displaystyle \ left \ {\ left \ {1,2 \ right \}, \ left \ {2,3 \ right \} \ right \}}$${\ displaystyle \ left \ {1,2 \ right \}}$${\ displaystyle \ left \ {2,3 \ right \}}$

The set has exactly 5 partitions: ${\ displaystyle \ left \ {1,2,3 \ right \}}$

• ${\ displaystyle \ left \ {\ left \ {1,2,3 \ right \} \ right \}}$
• ${\ displaystyle \ left \ {\ left \ {1 \ right \}, \ left \ {2,3 \ right \} \ right \}}$
• ${\ displaystyle \ left \ {\ left \ {2 \ right \}, \ left \ {3,1 \ right \} \ right \}}$
• ${\ displaystyle \ left \ {\ left \ {3 \ right \}, \ left \ {1,2 \ right \} \ right \}}$
• ${\ displaystyle \ left \ {\ left \ {1 \ right \}, \ left \ {2 \ right \}, \ left \ {3 \ right \} \ right \}}$

The only partition of the empty set is the empty set.

Every single element set has exactly one partition, namely . ${\ displaystyle \ left \ {x \ right \}}$${\ displaystyle \ left \ {\ left \ {x \ right \} \ right \}}$

Every non-empty set has exactly one single-element partition , it is called the "trivial partition". ${\ displaystyle M}$${\ displaystyle \ left \ {M \ right \}}$

## Number of partitions of a finite set

The number of partitions in a -element set is called Bell's number (after Eric Temple Bell ). The first bell numbers are: ${\ displaystyle B_ {n}}$${\ displaystyle n}$

${\ displaystyle B_ {0} = 1, \ quad B_ {1} = 1, \ quad B_ {2} = 2, \ quad B_ {3} = 5, \ quad B_ {4} = 15, \ quad B_ { 5} = 52, \ quad B_ {6} = 203, \ quad \ ldots}$

## Partitions and equivalence relations

If there is an equivalence relation ~ on the set , then the set of equivalence classes forms a partition of which is also called the “factor set” from ~ on . ${\ displaystyle M}$${\ displaystyle M,}$${\ displaystyle M / {\ sim}}$${\ displaystyle M}$

Conversely, if a partition of is given, then becomes through ${\ displaystyle P}$${\ displaystyle M}$

" If and when an item in there, where and are included"${\ displaystyle x \ sim _ {P} y \, \!}$${\ displaystyle A}$${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$

defines an equivalence relation, somewhat more formal:

${\ displaystyle x \ sim _ {P} y \: \ Leftrightarrow \ \ exists A \ in P {:} \ {x \ in A, y \ in A}}$

The equivalence of equivalence relations and partitions manifests itself in the equality of the partitions and the equality of the relations. ${\ displaystyle {P} = {M / {\ sim _ {P}}}}$${\ displaystyle {\ sim _ {(M / {\ sim})}} = {\ sim}}$

### example

For a fixed natural number , whole numbers are called congruent modulo if their difference is divisible by . Congruence is an equivalence relation and is denoted by. The associated partition of the set of integers is the division into the remainder classes modulo . It can be represented as ${\ displaystyle m}$ ${\ displaystyle x, y}$ ${\ displaystyle m,}$${\ displaystyle xy}$${\ displaystyle m}$${\ displaystyle {\ equiv}}$${\ displaystyle m}$

${\ displaystyle \ mathbb {Z} / {\ equiv} = \ {[0] _ {\ equiv}, [1] _ {\ equiv}, \ ldots, [m-1] _ {\ equiv} \}, }$

in which

${\ displaystyle [k] _ {\ equiv} = \ {\ ldots, k-2m, km, k, k + m, k + 2m, \ ldots \}}$

denotes the remainder class that contains. (Note that this notation is not commonly used for remainder classes. It was chosen only to illustrate the general construction above.) ${\ displaystyle k}$

## The association of partitions

If P and Q two partitions of a lot of M , then we call P "finer than" Q , if every element of P subset of an element of Q is. This clearly means that every element of Q is itself partitioned by elements of P.

The relation “finer than” is a partial order on the system of all partitions of M , and this system even becomes a complete lattice . According to the above mentioned equivalence of equivalence relations and partitions it is isomorphic to the equivalence relation association on M .