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 x-y}$ ${\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,k-m,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 .

See also

• Classification (statistics)
• Partition function
• Equivalence relation
• Stirling number # Stirling numbers of the second kind (number of k-element partitions of an n-element set)

Individual evidence

1. ↑ Follow A000110 in OEIS