Proof of Counting Subsets

Throughout, subsets of finite sets are finite (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iv)), and so are the intervals $\{0,\dots,n\}$ and $[k]$ (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vii)) and the sets of maps between finite sets (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (ix)); every $S\in\mathcal{P}(A)$ has $\#S\le n$ (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iv)), and $S\mapsto\#S$ is a map $\mathcal{P}(A)\to\{0,\dots,n\}$ (The Maps i ↦ #C(i) and S ↦ #S (ii)). A set $S$ lies in $\mathcal{P}_{j}(A)$ exactly when $S\subseteq A$, $S$ is finite and $\#S=j$ (The k-Element Subsets of a Set (ii)).

Step 1: subsets of a given size ((i)). Let $I=\operatorname{Inj}([k],A)$, a finite set, and for $\varphi\in I$ let $\Phi(\varphi)=\varphi([k])$ be its image. The image of an injection has as many elements as its domain (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iii)), and $\#[k]=k$ (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (i)); so $\Phi(\varphi)$ is a $k$-element subset of $A$, and $\Phi$ is a map $I\to\mathcal{P}_{k}(A)$.

$\Phi$ is surjective, so $\mathcal{P}_{k}(A)$ is finite. If $S\in\mathcal{P}_{k}(A)$, then $\#S=k$ means that there is a bijection $\beta$ from $[k]$ onto $S$ (The Number of Elements of a Finite Set (i)); since its image $S$ is contained in $A$, $\beta$ is also an injection $[k]\to A$ (Gluing Maps on Disjoint Domains, and Shrinking the Codomain (iii)), with image $S$. Hence $\mathcal{P}_{k}(A)=\Phi(I)$ is the image of a finite set, and so it is finite (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vi)).

The fibres of $\Phi$. Let $S\in\mathcal{P}_{k}(A)$. An injection $\varphi\in I$ with $\varphi([k])=S$ is, being injective, a bijection from $[k]$ onto its image $S$ (Gluing Maps on Disjoint Domains, and Shrinking the Codomain (iii)). Conversely, as above, every bijection $[k]\to S$ is an injection $[k]\to A$ with image $S$. So the fibre $\Phi^{-1}\{S\}$ consists of the same maps as $\operatorname{Bij}([k],S)$, and since $\#[k]=k=\#S$, it has $k!$ elements (Counting Maps, Injections, Bijections and Permutations (iii)).

Counting. By Counting by Fibres, Double Counting and the Pigeonhole Principle (iv), then Counting Maps, Injections, Bijections and Permutations (ii) and Properties of the Falling Factorial (ii),

$$k!\cdot\#\mathcal{P}_{k}(A)=\#\operatorname{Inj}([k],A)=(n)_{k}=k!\binom{n}{k}.$$

Cancelling the nonzero factor $k!$ (The Factorial: Recursion, Positivity and Bounds by Powers (ii), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (ix)) gives $\#\mathcal{P}_{k}(A)=\binom{n}{k}$.

Step 2: all subsets ((ii)). Every subset $S$ of $A$ is finite with $j=\#S\in\{0,\dots,n\}$, so $S\in\mathcal{P}_{j}(A)$; and each $\mathcal{P}_{j}(A)$ is contained in $\mathcal{P}(A)$. Hence

$$\mathcal{P}(A)=\bigcup_{j=0}^{n}\mathcal{P}_{j}(A).$$

The sets $\mathcal{P}_{j}(A)$ are pairwise disjoint, because a set in $\mathcal{P}_{j}(A)\cap\mathcal{P}_{j'}(A)$ has $j=\#S=j'$ elements, and each of them is finite by Step 1. A finite union of finite sets is finite (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (x)), so $\mathcal{P}(A)$ is finite. Counting the disjoint union (The Number of Elements of a Disjoint Finite Union (i)), then using Step 1 and the row sum of binomial coefficients (Binomial Identities (i)), all in $\mathbb{N}_{0}$,

$$\#\mathcal{P}(A)=\sum_{j=0}^{n}\#\mathcal{P}_{j}(A)=\sum_{j=0}^{n}\binom{n}{j}=2^{n}.$$

Step 3: grouping by size ((iii)). Let $g:\mathbb{N}_{0}\to\mathbb{R}$, and let

$$T=\{(j,S)\in\{0,\dots,n\}\times\mathcal{P}(A):S\in\mathcal{P}_{j}(A)\}.$$

Summing over dependent pairs (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (vi)), for the family $(\mathcal{P}_{j}(A))_{j\in\{0,\dots,n\}}$ whose union is $\mathcal{P}(A)$ by Step 2, and the map $(j,S)\mapsto g(j)$ on $T$, gives

$$\sum_{j=0}^{n}\sum_{S\in\mathcal{P}_{j}(A)}g(j)=\sum_{(j,S)\in T}g(j).$$

The map $\sigma:\mathcal{P}(A)\to T$, $\sigma(S)=(\#S,S)$, is a bijection: it lands in $T$ because $S\in\mathcal{P}_{\#S}(A)$; it is injective because $S$ is its second component; and a pair $(j,S)\in T$ has $\#S=j$, so it equals $\sigma(S)$. Reindexing the sum on the right by $\sigma$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (iii)) turns it into $\sum_{S\in\mathcal{P}(A)}g(\#S)$. On the left, the inner sum has the constant term $g(j)$, so it equals $\#\mathcal{P}_{j}(A)\cdot g(j)$ (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (v)), which is $\binom{n}{j}g(j)$ by Step 1. Together,

$$\sum_{S\in\mathcal{P}(A)}g(\#S)=\sum_{j=0}^{n}\#\mathcal{P}_{j}(A)\,g(j)=\sum_{j=0}^{n}\binom{n}{j}g(j).$$