nLab
partition

Partitions

Idea

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.

Definitions

Each of the following definitions is a special case of a general concept to follow.

Of sets

Given a set SS, a partition of SS is a collection π\pi of inhabited subsets of SS (called blocks) such that

  • For A,BπA, B \in \pi, if ABA \cap B is inhabited, then A=BA = B;
  • The union π\bigcup \pi is all of SS (the improper subset).

A partition π\pi refines a partition ρ\rho (of the same set) if every block of π\pi is contained in some block of ρ\rho:

Aπ,Bρ,AB. \forall A \in \pi,\; \exists B \in \rho,\; A \subseteq B .

Refinement is a partial order on the class of partitions of SS.

Partitions of SS are in bijective correspondence with equivalence relations on SS; a partition is precisely a collection of equivalence classes. Refinement corresponds to implication between relations.

Partitions of SS are also closely related to surjections out of SS. Any partition π\pi of SS induces a surjection SπS \to \pi that assigns each element of SS to a unique block, and, conversely, any surjection f:SBf : S \to B induces a partition of SS by taking the blocks to be the fibers {f 1(x)xB}\{f^{-1}(x) \mid x \in B\}. 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 fgf \le g just in case there exists a (necessarily unique) hh such that g=hfg = h \circ f. Then the operations we have just described give an equivalence

Part(S)SSurj Part(S) \rightleftarrows S \downarrow Surj

between the partial order of partitions ordered by refinement and the preorder of surjections ordered by factorization.

Of numbers

Given a natural number nn, a composition of nn is a list of positive natural numbers whose sum is nn, and a partition of nn is an unordered list, or multiset, or 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.

Every natural number nn corresponds to a finite set [n][n], and every partition of [n][n] (as defined above) gives a partition of nn, but different partitions of [n][n] may give the same partition of nn. Conversely, a composition of nn defines a partition of [n][n], but not every partition of [n][n] arises in this way.

More precisely, we have the following, where \rightarrowtail indicates an injection and \twoheadrightarrow indicates a surjection:

Comp(n)Part([n])Part(n); Comp(n) \rightarrowtail Part([n]) \twoheadrightarrow Part(n) ;

the composite of this is also a surjection, which is split? by the definition of a partition as a monotone composition.

The partition function pp gives the number of partitions of nn as a function of nn; this is OEIS A000041. Its (ordinary) generating function is

n=0 p(n)x n= k=1 (1x k) 1. \sum_{n=0}^\infty p(n) x^n = \prod_{k=1}^\infty (1 - x^k)^{-1} .

Partitions are often described using Young diagrams.

One may also speak of multiplicative compositions and partitions of nn for positive nn (where the above are additive), also called (ordered and unordered) factorizations; these are (ordered and unordered) lists of natural numbers greater than 11 whose product is nn.

Of intervals

Given real numbers aa and bb, a partition π\pi of the interval [a,b][a,b] is an inhabited finite list c 0,,c nc_0, \ldots, c_n such that: * c 0=ac_0 = a, * c ic i+1c_i \leq c_{i+1} for i<ni \lt n, * c n=bc_n = b.

A partition π\pi refines a partition ρ\rho if every element of the list ρ\rho belongs to the list π\pi. The mesh (or norm) of π\pi is

πmax i(c i+1c i). {\|\pi\|} \coloneqq \max_i (c_{i+1} - c_i) .

A tag of π\pi is a list t 0,,t n1t_0, \ldots, t_{n-1} such that c it ic i+1c_i \leq t_i \leq c_{i+1} for i<ni \lt n. Tagged partitions are used to define the Riemann integral, the Darboux integral?, and the gauge integral.

Of measure spaces

Given a measure space SS (or more generally a measurable space equipped with a notion of null sets), a partition of SS is a collection π\pi of positive? (non-null) measurable subsets of SS, such that: * For A,BπA, B \in \pi, if ABA \cap B is positive, then AA and BB are equal; * The union π\bigcup \pi is full.

(One might merely allow AA and BB to be equivalent, meaning that their symmetric difference is null, when ABA \cap B is positive, but this does not give a good notion of tagged partition; really, we should think of

so insist that π\pi be saturated: if AA and BB are equivalent and AπA \in \pi, then BπB \in \pi. Alternatively, especially if one views the partition an indexed collection of subsets, then one would still require A=BA = B when ABA \cap B 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.

Of unity on topological spaces

Given a topological space SS, a partition of unity on SS is a collection UU of continuous maps from SS to the unit interval such that, for each point xx in SS: * f(x)>0f(x) \gt 0 for only finitely many ff in UU; * ff(x)=1\sum_f f(x) = 1 (where this sum is defined by the previous clause).

General

Let MM be an abelian monoid (written additively) with the property that a+b=0a + b = 0 only if a,b=0a, b = 0. (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 MM declared nonzero, then require that {0}\{0\} be its complement. Then a finite composition of an element xx of MM is a finite list of nonzero elements of MM whose sum is xx, and a finite partition of xx is the same thing without regard to order (so a multiset instead of a list, which is why MM must be abelian). If we now equip MM 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 MM.

Composititions and partitions of natural numbers are immediate examples of the finite notion, using the monoid {0,1,2,}\{0, 1, 2, \ldots\} under addition; multiplicative compositions and partitions use instead {1,2,}\{1, 2, \ldots\} under multiplication.

A partition of unity is a partition of the constant function with value 11 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] SS is a partition of SS itself in the monoid of [measurable] multisubsets of SS [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

[a,b]+[b,c]=[a,c]. [a,b] + [b,c] = [a,c] .

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.

The lattice of partitions of a finite set

For any finite set SS with nn elements, the partially ordered set of partitions of SS forms a lattice (called Π n\Pi_n). Viewing partitions as equivalence relations on SS, this lattice structure may be described as follows (Birkhoff):

  • the bottom element is the diagonal relation on SS
  • the top element is the total relation on SS
  • the meet of two equivalence relations π\pi and ρ\rho on SS is the equivalence relation πρ\pi \wedge \rho defined by x(πρ)yx(\pi\wedge \rho)y iff xπyx\pi y and xρyx\rho y
  • the join of two equivalence relations π\pi and ρ\rho is the meet of all equivalence relations σ\sigma such that πσ\pi \subseteq \sigma and ρσ\rho \subseteq \sigma (this is well-defined since Π n\Pi_n is finite)

Dually, viewing partitions as surjections from SS, the lattice structure may be described as follows:

  • the bottom element is the identity function SSS \to S
  • the top element is the unique function S1S \to 1 to the 1-element set
  • the join of two surjections π:SB\pi : S \to B and ρ:SC\rho : S \to C is their pushout
  • the meet of two surjections π:SB\pi : S \to B and ρ:SC\rho : S \to C is the join of all surjections σ:SA\sigma : S \to A for which there exist functions f:ABf : A \to B and g:ACg : A \to C such that π=fσ\pi = f \circ \sigma and ρ=gσ\rho = g \circ \sigma

References

Last revised on May 3, 2018 at 14:35:54. See the history of this page for a list of all contributions to it.