In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a partition of a set is a grouping of its elements into
non-empty subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
s, in such a way that every element is included in exactly one subset.
Every
equivalence relation on a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
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
Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Barwise (1978) consists of four corresponding part ...
.
Definition and Notation
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., ''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 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
In logic and probability theory, two events (or propositions) are mutually exclusive or disjoint if they cannot both occur at the same time. A clear example is the set of outcomes of a single coin toss, which can result in either heads or tails ...
.
The sets in ''P'' are called the ''blocks'', ''parts'', or ''cells'', of the partition. If
then we represent the cell containing ''a'' by