Partition of a set

In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in exactly one subset. In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in exactly one subset. Every equivalence relation on a set defines a partition of this set, and every partition defines an equivalence relation. A set equipped with an equivalence relation or a partition is sometimes called a setoid, typically in type theory and proof theory. A partition of a set X is a set of nonempty subsets of X such that every element x in X is in exactly one of these subsets (i.e., X is a disjoint union of the subsets). Equivalently, a family of sets P is a partition of X if and only if all of the following conditions hold: The sets in P are called the blocks, parts or cells of the partition. The rank of P is |X| − |P|, if X is finite. For any equivalence relation on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting x ~ y precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent. The axiom of choice guarantees for any partition of a set X the existence of a subset of X containing exactly one element from each part of the partition. This implies that given an equivalence relation on a set one can select a canonical representative element from every equivalence class. A partition α of a set X is a refinement of a partition ρ of X—and we say that α is finer than ρ and that ρ is coarser than α—if every element of α is a subset of some element of ρ. Informally, this means that α is a further fragmentation of ρ. In that case, it is written that α ≤ ρ.