A partition is any of various ways of dividing a mathematical object into nontrivial parts that (in some sense) cover the object while being mutually disjoint.
Each of the following definitions is a special case of a general concept to follow.
Given a set , a partition of is a collection of inhabited subsets of (called blocks) such that
A partition refines a partition (of the same set) if every block of is contained in some block of :
Refinement is a partial order on the class of partitions of .
Partitions of are in bijective correspondence with equivalence relations on ; a partition is precisely a collection of equivalence classes. Refinement corresponds to implication between relations.
Partitions of are also closely related to surjections out of . Any partition of induces a surjection that assigns each element of to a unique block, and, conversely, any surjection induces a partition of by taking the blocks to be the fibers . In general, many different surjections can map to the same partition under this correspondence. However, there is a natural preorder on surjections defined by taking just in case there exists a (necessarily unique) such that . Then the operations we have just described give an equivalence
between the partial order of partitions ordered by refinement and the preorder of surjections ordered by factorization.
Given a natural number ,
a composition of is a list of positive natural numbers whose sum is ,
a partition of is an unordered list, or multiset, of such numbers.
That is, different compositions define the same partition if the compositions differ only by order. A partition may also be defined as a monotone composition.
In practice, notably in the representation theory of the symmetric group/general linear group, partitions of natural numbers are often given as anti-monotone sequences, denoted as
Often, especially in representation theory (of the symmetric group/general linear group), partitions of a natural number appear as Young diagrams with boxes. While Young diagrams in themselves are just an equivalent way of thinking of or depicting partitions, they are used to indicate (“concept with an attitude”) that decorations of partitions to Young tableaux play a role in a given discussion.
The partition function gives the number of partitions of as a function of ; this is OEIS A000041. Its (ordinary) generating function is
Every natural number corresponds to a finite set , and every partition of (as defined above) gives a partition of , but different partitions of may give the same partition of . Conversely, a composition of defines a partition of , but not every partition of arises in this way.
More precisely, we have the following, where indicates an injection and indicates a surjection:
the composite of this is also a surjection, which is split by the definition of a partition as a monotone composition.
One may also speak of multiplicative compositions and partitions of for positive (where the above are additive), also called (ordered and unordered) factorizations; these are (ordered and unordered) lists of natural numbers greater than whose product is .
Given real numbers and , a partition of the interval is an inhabited finite list such that: * , * for , * .
A partition refines a partition if every element of the list belongs to the list . The mesh (or norm) of is
A tag of is a list such that for . Tagged partitions are used to define the Riemann integral, the Darboux integral, and the gauge integral.
Given a measure space (or more generally a measurable space equipped with a notion of null sets), a partition of is a collection of positive? (non-null) measurable subsets of , such that: * For , if is positive, then and are equal; * The union is full.
(One might merely allow and to be equivalent, meaning that their symmetric difference is null, when is positive, but this does not give a good notion of tagged partition; really, we should think of
so insist that be saturated: if and are equivalent and , then . Alternatively, especially if one views the partition an indexed collection of subsets, then one would still require when is positive.)
Then a partition of a set is simply a partition of the measure space given by counting measure.
Partitions in this sense can be used to define the Lebesgue integral in analogy to the definition of the Riemann integral using partitions of intervals.
Given a topological space , a partition of unity on is a collection of continuous maps from to the unit interval such that, for each point in : * for only finitely many in ; * (where this sum is defined by the previous clause).
Let be an abelian monoid (written additively) with the property that only if . (In other words, the nonzero elements form an ideal; there's probably a name for this kind of monoid, but I don't know it.) For purposes of constructive mathematics, we should start with an ideal of elements of declared nonzero, then require that be its complement. Then a finite composition of an element of is a finite list of nonzero elements of whose sum is , and a finite partition of is the same thing without regard to order (so a multiset instead of a list, which is why must be abelian). If we now equip with some notion of sum of some infinite series, we can generalise to (not necessarily finite) partitions (and even compositions, for ordered series), which really should be viewed as indexed families of elements of .
Composititions and partitions of natural numbers are immediate examples of the finite notion, using the monoid under addition; multiplicative compositions and partitions use instead under multiplication.
A partition of unity is a partition of the constant function with value in the monoid of continuous maps to the nonnegative real line. Here we define an infinite sum of functions when only finitely many of the functions are nonzero at each point. (We could in principle define more infinite sums than these, which would give a notion more general than the usual one of partition of unity.)
A partition of a set [or measure space] is a partition of itself in the monoid of [measurable] multisubsets of [modulo equivalence almost everywhere]. This monoid has all infinite sums, so there is no finiteness requirement. (Every multisubset in a partition is in fact a subset, but working in the monoid of subsets under union, rather than multisubsets under multi-union, would allow the parts to overlap.)
Finally, a partition of an interval is a finite partition in the monoid generated by the compact intervals subject to the relations
In the last few examples, each part of a partition is an inhabited set. In such cases, a tagged partitition is a partition in which each part has been equipped with one of its elements.
For any finite set with elements, the partially ordered set of partitions of forms a lattice (called ). Viewing partitions as equivalence relations on , this lattice structure may be described as follows (Birkhoff):
Dually, viewing partitions as surjections from , the lattice structure may be described as follows:
Garrett Birkhoff, Lattice Theory, AMS, third edition, 1973.
Marcelo Aguiar and Swapneel Mahajan. Monoidal Functors, Species and Hopf Algebras, 2010.
Last revised on July 30, 2022 at 17:59:57. See the history of this page for a list of all contributions to it.