Partition of a set

In mathematics, a partition of a set is a grouping of its 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 non-empty subsets of X such that every element x in X is in exactly one of these subsets (i.e., the subsets are nonempty mutually disjoint sets). Equivalently, a family of sets P is a partition of X if and only if all of the following conditions hold: The family P does not contain the empty set (that is ). The union of the sets in P is equal to X (that is ). The sets in P are said to exhaust or cover X. See also collectively exhaustive events and cover (topology). The intersection of any two distinct sets in P is empty (that is ). The elements of P are said to be pairwise disjoint or mutually exclusive. See also mutual exclusivity. The sets in are called the blocks, parts, or cells, of the partition. If then we represent the cell containing by . That is to say, is notation for the cell in which contains . Every partition may be identified with an equivalence relation on , namely the relation such that for any we have if and only if (equivalently, if and only if ). The notation evokes the idea that the equivalence relation may be constructed from the partition. Conversely every equivalence relation may be identified with a partition. This is why it is sometimes said informally that "an equivalence relation is the same as a partition". If P is the partition identified with a given equivalence relation , then some authors write . This notation is suggestive of the idea that the partition is the set X divided in to cells. The notation also evokes the idea that, from the equivalence relation one may construct the partition. The rank of is , if is finite.