Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Partition of a set
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.