Partition of a set

In set theory is a partition (also separation or classification ) of a set M such that each element of M is contained in exactly one element of P is a set P whose elements are non-empty subsets of M.

Examples

The family of sets is a partition of the set, but no partition, because 3 and 7 do not occur in the subsets of.

The amount the family is no partition of any amount there and both contain the 2, that are not disjoint.

The partitions are

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

Number of partitions of a finite set

The number of possible partitions of an n- element set is called Bell's number (after Eric Temple Bell). The first Bell figures are

Partitions and equivalence relations

If an equivalence relation ~ given on the amount, then forms the set of equivalence classes is a partition of which is usually written as.

Conversely, given a partition of, then we can define an equivalence relation by: if and only if an element exists in, and in which are included. As the formula is the definition:

This gives the equality of partitions or of the relations thus equivalence relations and partitions are basically equivalent.

Example

For a fixed natural number integers are called congruent modulo if their difference is divisible by. Congruence is an equivalence relation and is designated by. The corresponding partition of the set of integers is the partition to the residue classes of integers modulo it has the form

In which

Each residue classes referred to, so that subsets of the same number with respect to the remainder ( Note that this notation is not generally usual for residue classes, it has only been chosen to illustrate the above general structure. )

Comparison of partitions: The " partition Association "

Are P and Q be two partitions of a set M, then we call P is finer than Q, if every element of P subset of an element of Q. Clearly, this 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 X, and this system is thus even a bandage.