# 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} = \ { _ {\ equiv},  _ {\ 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 .