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.
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 .
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.
The set has exactly 5 partitions:
The only partition of the empty set is the empty set.
Every single element set has exactly one partition, namely .
Every non-empty set has exactly one single-element partition , it is called the "trivial partition".
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:
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 .
Conversely, if a partition of is given, then becomes through
- " If and when an item in there, where and are included"
defines an equivalence relation, somewhat more formal:
The equivalence of equivalence relations and partitions manifests itself in the equality of the partitions and the equality of the relations.
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
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.)
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 .
- Classification (statistics)
- Partition function
- Equivalence relation
- Stirling number # Stirling numbers of the second kind (number of k-element partitions of an n-element set)