# 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 $S$, a partition of $S$ is a collection $\pi$ of inhabited subsets of $S$ such that

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

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

$\forall A\in \pi ,\phantom{\rule{thickmathspace}{0ex}}\exists B\in \rho ,\phantom{\rule{thickmathspace}{0ex}}A\subseteq B.$\forall A \in \pi,\; \exists B \in \rho,\; A \subseteq B .

Refinement is a partial order on the class of partitions of $S$.

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

### Of numbers

Given a natural number $n$, a composition of $n$ is a list of positive natural numbers whose sum is $n$, and a partition of $n$ 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 $n$ corresponds to a finite set $\left[n\right]$, and every partition of $\left[n\right]$ (as defined above) gives a partition of $n$, but different partitions of $\left[n\right]$ may give the same partition of $n$. Conversely, a composition of $n$ defines a partition of $\left[n\right]$, but not every partition of $\left[n\right]$ arises in this way.

More precisely, we have the following, where $↣$ indicates an injection and $↠$ indicates a surjection:

$\mathrm{Comp}\left(n\right)↣\mathrm{Part}\left(\left[n\right]\right)↠\mathrm{Part}\left(n\right);$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 $p$ gives the number of partitions of $n$ as a function of $n$; this is OEIS A000041. Its (ordinary) generating function is

$\sum _{n=0}^{\infty }p\left(n\right){x}^{n}=\prod _{k=1}^{\infty }\left(1-{x}^{k}{\right)}^{-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 $n$ for positive $n$ (where the above are additive), also called (ordered and unordered) factorizations; these are (ordered and unordered) lists of natural numbers greater than $1$ whose product is $n$.

### Of intervals

Given real numbers $a$ and $b$, a partition $\pi$ of the interval $\left[a,b\right]$ is an inhabited finite list ${c}_{0},\dots ,{c}_{n}$ such that:

• ${c}_{0}=a$,
• ${c}_{i}\le {c}_{i+1}$ for $i,
• ${c}_{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

$\parallel \pi \parallel ≔\underset{i}{\mathrm{max}}\left({c}_{i+1}-{c}_{i}\right).${\|\pi\|} \coloneqq \max_i (c_{i+1} - c_i) .

A tag of $\pi$ is a list ${t}_{0},\dots ,{t}_{n-1}$ such that ${c}_{i}\le {t}_{i}\le {c}_{i+1}$ for $i. Tagged partitions are used to define the Riemann integral, the Darboux integral?, and the gauge integral?.

### Of measure spaces

Given a measure space $S$ (or more generally a measurable space equipped with a notion of null sets), a partition of $S$ is a collection $\pi$ of positive? (non-null) measurable subsets of $S$, such that:

• For $A,B\in \pi$, if $A\cap B$ is positive, then $A$ and $B$ are equivalent;
• The union $\bigcup \pi$ is full.

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 $S$, a partition of unity on $S$ is a collection $U$ of continuous maps from $S$ to the unit interval such that, for each point $x$ in $S$:

• $f\left(x\right)>0$ for only finitely many $f$ in $U$;
• ${\sum }_{f}f\left(x\right)=1$ (where this sum is defined by the previous clause).

### General

Let $M$ be an abelian monoid (written additively) with the property that $a+b=0$ only if $a,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 $M$ declared nonzero, then require that $\left\{0\right\}$ be its complement. Then a finite composition of an element $x$ of $M$ is a finite list of nonzero elements of $M$ whose sum is $x$, and a finite partition of $x$ is the same thing without regard to order (so a multiset instead of a list, which is why $M$ must be abelian). If we now equip $M$ with some notion of sum of some infinite series, we can generalise to (not necessarily finite) partitions (and even compositions, for ordered series).

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

A partition of a set (or measure space) $S$ is a partition of $S$ itself in the monoid of (measurable) multisubsets of $S$ (modulo equivalence almost everywhere). This monoid has all infinite sums, so there is no finiteness requirement.

A partition of unity is a partition of the constant function with value $1$ 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.)

Finally, a partition of an interval is a finite partition in the monoid generated by the compact intervals subject to the relations

$\left[a,b\right]+\left[b,c\right]=\left[a,c\right].$[a,b] + [b,c] = [a,c] .

Formally, a tagged partition may be defined as a partition with an even number of parts, although this may not be a very fruitful way to look at it.

Revised on August 19, 2013 20:03:59 by Toby Bartels (98.23.159.237)