Computing Pushforwards on Finite and Countable Spaces

Collecting Mass Along Fibers

A map can send several distinct points to the same output. The pushforward measure records their combined mass: it does not choose one representative point, nor does it count the output only once. On a finite or countable space, this calculation reduces to summing the masses in each fiber.

Throughout this tutorial, \(X\) and \(Y\) are finite or countable sets equipped with their power-set sigma-algebras \(2^X\) and \(2^Y\). Let \(\mu\) be a measure on \((X,2^X)\), and let \(T:X\to Y\) be a function. Every such \(T\) is measurable because every subset of \(Y\) is measurable. The spaces are complete because every subset of every null set belongs to the power-set sigma-algebra. No finiteness or sigma-finiteness is assumed for \(\mu\); these properties do hold in the examples below. A measure on a finite or countable power-set space is determined by its point masses \(a_x=\mu(\{x\})\), which may be infinite.

For a countable family of nonnegative numbers, its sum means the supremum of its finite subsums, so the sum may equal \(+\infty\). The fundamental calculation is that the mass at \(y\) is the sum of the masses of all points in its fiber. Summing these point masses over a set of outputs gives the measure of that set.

Proof. Set \(\nu(B)=\mu(T^{-1}(B))\). Then \(\nu(\varnothing)=\mu(\varnothing)=0\). If \(B_1,B_2,\ldots\) are pairwise disjoint subsets of \(Y\), their inverse images are pairwise disjoint, and \(T^{-1}(\bigcup_j B_j)=\bigcup_jT^{-1}(B_j)\). Countable additivity of \(\mu\) therefore gives \(\nu(\bigcup_jB_j)=\sum_j\nu(B_j)\), so \(\nu\) is a measure. For any \(A\subseteq X\), the singleton sets \(\{x\}\), \(x\in A\), are disjoint and have union \(A\); countable additivity gives \(\mu(A)=\sum_{x\in A}\mu(\{x\})\). For \(B\subseteq Y\), the inverse image \(T^{-1}(B)\) is the disjoint union of the fibers \(T^{-1}(\{y\})\) for \(y\in B\). Applying countable additivity to this partition, and then to the singleton partition of each fiber, gives $$ \nu(B)=\sum_{y\in B}\mu(T^{-1}(\{y\})) =\sum_{y\in B}\sum_{T(x)=y}\mu(\{x\}) =\sum_{T(x)\in B}\mu(\{x\}). $$ The last equality groups the same nonnegative point masses according to their output; it also holds for infinite sums by countable additivity. If \(B=\varnothing\), both sides are zero. If \(X=\varnothing\), every sum and every measure of an inverse image is zero, so the formula still holds. \(\square\)

Finite Spaces: Add the Masses That Merge

More generally, a finite collection of atoms can be written using Dirac measures. For \(x\in X\), the Dirac measure \(\delta_x\) assigns mass \(1\) to sets containing \(x\) and mass \(0\) to sets not containing \(x\). The following consequence makes explicit how a map groups such atoms.

Proof. For any \(B\subseteq Y\), the definition of pushforward and of each Dirac measure gives $$ (T_\#\mu)(B)=\mu(T^{-1}(B)) =\sum_{j=1}^k c_j\,\delta_{x_j}(T^{-1}(B)) =\sum_{\substack{1\le j\le k\\T(x_j)\in B}}c_j. $$ Group this finite sum by the value \(y=T(x_j)\). The result is the mass that the displayed measure on \(Y\) assigns to \(B\), proving equality of the measures. If \(k=0\), both measures are zero and the same equality holds with an empty sum. \(\square\)

Countable Spaces: Dirac Sums and Counting Measure

Counting measure assigns to each set its number of elements, with value \(+\infty\) for an infinite set. On a countable space it is sigma-finite and complete when the sigma-algebra is the power set, but it is not finite if the space is infinite. A pushforward of counting measure therefore counts points in fibers, not merely distinct outputs.

A Common Counting Error

A frequent mistake is to transfer the mass of one input point to its output and overlook the other points in the fiber. For instance, let \(X=\{p,q\}\) with \(\mu(\{p\})=2\) and \(\mu(\{q\})=3\), and let both points map to \(z\in Y=\{z\}\). A wrong calculation might select \(q\) as the representative of the fiber and write \(\nu(\{z\})=3\). But \(T^{-1}(\{z\})=\{p,q\}\), so the definition gives $$ \nu(\{z\})=\mu(\{p,q\})=2+3=5. $$ The correction is to sum over every point in the fiber, once each. The result passes the total-mass check: \(\nu(Y)=5=\mu(X)\). Counting distinct outputs alone would instead give \(1\), which is not the mass of the pushforward.

The fiber formula is especially useful when the input measure is specified by point masses. First identify each fiber, then add its masses; for a set of outputs, add the masses of all fibers in that set. Empty fibers have mass zero, and infinite fibers or infinitely many outputs are handled by nonnegative countable sums. No finiteness assumption is needed for the formula, though a computed mass can be infinite.