HOME

TheInfoList



OR:

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 In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
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 In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a founda ...
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 In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in othe ...
(that is \emptyset \notin P). *The union of the sets in ''P'' is equal to ''X'' (that is \textstyle\bigcup_ A = X). The sets in ''P'' are said to exhaust or cover ''X''. See also collectively exhaustive events and
cover (topology) In mathematics, and more particularly in set theory, a cover (or covering) of a set X is a collection of subsets of X whose union is all of X. More formally, if C = \lbrace U_\alpha : \alpha \in A \rbrace is an indexed family of subsets U_\alpha\ ...
. * The
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, thei ...
of any two distinct sets in ''P'' is empty (that is (\forall A,B \in P)\; A\neq B \implies A \cap B = \emptyset). 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 a\in X then we represent the cell containing ''a'' by /math>. That is to say, /math> is notation for the cell in ''P'' which contains ''a''. Every partition, ''P'', may be identified with an equivalence relation on ''X'', namely the relation \sim_P such that for any a,b\in X we have a\sim_P b if and only if a\in /math> (equivalently, if and only if b\in /math>). The notation \sim_P 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 \sim, then some authors write P = X/\sim. 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 ''P'' is , if ''X'' is finite.


Examples

*The empty set \emptyset has exactly one partition, namely \emptyset. (Note: this is the partition, not a member of the partition.) *For any non-empty set ''X'', ''P'' = is a partition of ''X'', called the trivial partition. **Particularly, every singleton set has exactly one partition, namely . *For any non-empty
proper 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 ...
''A'' of a set ''U'', the set ''A'' together with its complement form a partition of ''U'', namely, . *The set has these five partitions (one partition per item): ** , sometimes written 1 , 2 , 3. ** , or 1 2 , 3. ** , or 1 3 , 2. ** , or 1 , 2 3. ** , or 123 (in contexts where there will be no confusion with the number). *The following are not partitions of : ** is not a partition (of any set) because one of its elements is the
empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in othe ...
. ** is not a partition (of any set) because the element 2 is contained in more than one block. ** is not a partition of because none of its blocks contains 3; however, it is a partition of .


Partitions and equivalence relations

For any
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
on a set ''X'', the set of its
equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es is a partition of ''X''. Conversely, from any partition ''P'' of ''X'', we can define an equivalence relation on ''X'' by setting 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 In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
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.


Refinement of partitions

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 ''α'' ≤ ''ρ''. This "finer-than" relation on the set of partitions of ''X'' is a
partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
(so the notation "≤" is appropriate). Each set of elements has a least upper bound (their "join") and a
greatest lower bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest ...
(their "meet"), so that it forms a lattice, and more specifically (for partitions of a finite set) it is a
geometric lattice In the mathematics of matroids and lattices, a geometric lattice is a finite atomistic semimodular lattice, and a matroid lattice is an atomistic semimodular lattice without the assumption of finiteness. Geometric lattices and matroid lattices, r ...
.. The ''partition lattice'' of a 4-element set has 15 elements and is depicted in the Hasse diagram on the left. The meet and join of partitions α and ρ are defined as follows. The meet \alpha \wedge \rho is the partition whose blocks are the intersections of a block of ''α'' and a block of ''ρ'', except for the empty set. In other words, a block of \alpha \wedge \rho is the intersection of a block of ''α'' and a block of ''ρ'' that are not disjoint from each other. To define the join \alpha \vee \rho, form a relation on the blocks ''A'' of ''α'' and the blocks ''B'' of ''ρ'' by ''A'' ~ ''B'' if ''A'' and ''B'' are not disjoint. Then \alpha \vee \rho is the partition in which each block ''C'' is the union of a family of blocks connected by this this relation. Based on the equivalence between geometric lattices and matroids, this lattice of partitions of a finite set corresponds to a matroid in which the base set of the matroid consists of the
atoms Every atom is composed of a nucleus and one or more electrons bound to the nucleus. The nucleus is made of one or more protons and a number of neutrons. Only the most common variety of hydrogen has no neutrons. Every solid, liquid, gas ...
of the lattice, namely, the partitions with n-2 singleton sets and one two-element set. These atomic partitions correspond one-for-one with the edges of a complete graph. The matroid closure of a set of atomic partitions is the finest common coarsening of them all; in graph-theoretic terms, it is the partition of the vertices of the complete graph into the connected components of the subgraph formed by the given set of edges. In this way, the lattice of partitions corresponds to the lattice of flats of the graphic matroid of the complete graph. Another example illustrates refinement of partitions from the perspective of equivalence relations. If ''D'' is the set of cards in a standard 52-card deck, the ''same-color-as'' relation on ''D'' – which can be denoted ~C – has two equivalence classes: the sets and . The 2-part partition corresponding to ~C has a refinement that yields the ''same-suit-as'' relation ~S, which has the four equivalence classes , , , and .


Noncrossing partitions

A partition of the set ''N'' = with corresponding equivalence relation ~ is noncrossing if it has the following property: If four elements ''a'', ''b'', ''c'' and ''d'' of ''N'' having ''a'' < ''b'' < ''c'' < ''d'' satisfy ''a'' ~ ''c'' and ''b'' ~ ''d'', then ''a'' ~ ''b'' ~ ''c'' ~ ''d''. The name comes from the following equivalent definition: Imagine the elements 1, 2, ..., ''n'' of ''N'' drawn as the ''n'' vertices of a regular ''n''-gon (in counterclockwise order). A partition can then be visualized by drawing each block as a polygon (whose vertices are the elements of the block). The partition is then noncrossing if and only if these polygons do not intersect. The lattice of noncrossing partitions of a finite set forms a subset of the lattice of all partitions, but not a sublattice, since the join operations of the two lattices do not agree. The noncrossing partition lattice has recently taken on importance because of its role in free probability theory.


Counting partitions

The total number of partitions of an ''n''-element set is the Bell number ''Bn''. The first several Bell numbers are ''B''0 = 1, ''B''1 = 1, ''B''2 = 2, ''B''3 = 5, ''B''4 = 15, ''B''5 = 52, and ''B''6 = 203 . Bell numbers satisfy the
recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
: B_=\sum_^n B_k and have the exponential generating function :\sum_^\infty\fracz^n=e^. The Bell numbers may also be computed using the
Bell triangle In mathematics, the Bell triangle is a triangle of numbers analogous to Pascal's triangle, whose values count partitions of a set in which a given element is the largest singleton. It is named for its close connection to the Bell numbers, which ma ...
in which the first value in each row is copied from the end of the previous row, and subsequent values are computed by adding two numbers, the number to the left and the number to the above left of the position. The Bell numbers are repeated along both sides of this triangle. The numbers within the triangle count partitions in which a given element is the largest singleton. The number of partitions of an ''n''-element set into exactly ''k'' (non-empty) parts is the Stirling number of the second kind ''S''(''n'', ''k''). The number of noncrossing partitions of an ''n''-element set is the Catalan number :C_n=.


See also

* Exact cover *
Block design In combinatorial mathematics, a block design is an incidence structure consisting of a set together with a family of subsets known as ''blocks'', chosen such that frequency of the elements satisfies certain conditions making the collection of bl ...
*
Cluster analysis Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). It is a main task of ...
* Weak ordering (ordered set partition) *
Partial equivalence relation In mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) is a homogeneous binary relation that is symmetric and transitive. If the relation is also reflexive, the ...
* Partition refinement * List of partition topics *
Lamination (topology) In topology, a branch of mathematics, a lamination is a : * "topological space partitioned into subsets" * decoration (a structure or property at a point) of a manifold in which some subset of the manifold is partitioned into sheets of some lowe ...
* Rhyme schemes by set partition * Partition algebra * MECE principle


Notes


References

* * {{Authority control Basic concepts in set theory Combinatorics Families of sets