Proof of Counting by Fibres, Double Counting and the Pigeonhole Principle

Throughout, every subset of a finite set 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 (iv)), and for a family $(C_{i})_{i\in I}$ of finite sets $i\mapsto\#C_{i}$ is a map $I\to\mathbb{N}_{0}$ (The Maps i ↦ #C(i) and S ↦ #S (i)); this applies to the fibres $f^{-1}\{y\}\subseteq A$ and to the sets $R_{a}\subseteq B$ and $R'_{b}\subseteq A$ below; and natural numbers read in $\mathbb{R}$ keep their order, their products and their finite sums (Reading Natural Numbers in ℝ: Injectivity, Order and Pascal's Rule (ii), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (iii), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (vi)). Sums of natural numbers are taken in $\mathbb{N}_{0}$ until Step 4.

Step 1: counting by fibres ((i)). The fibres $f^{-1}\{y\}$, $y\in B$, are pairwise disjoint: if $a\in f^{-1}\{y\}\cap f^{-1}\{y'\}$, then $y=f(a)=y'$. Their union is $A$: each fibre is a subset of $A$, and each $a\in A$ lies in the fibre over $f(a)$. Since $B$ is finite, the count of a disjoint finite union, The Number of Elements of a Disjoint Finite Union (i), applied to the index set $B$ and the family $(f^{-1}\{y\})_{y\in B}$, gives

$$\#A=\#\bigcup_{y\in B}f^{-1}\{y\}=\sum_{y\in B}\#f^{-1}\{y\}.$$

Step 2: fibres of equal size ((iv)). If every fibre has $r$ elements, then the same family, with The Number of Elements of a Disjoint Finite Union (ii), gives $\#A=\#B\cdot r$, and $\#B\cdot r=r\cdot\#B$ by commutativity of the multiplication of $\mathbb{N}_{0}$ (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (vi)).

Step 3: double counting ((ii)). The set $A\times B$ 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 (v)), hence so is its subset $R$. Let $p:R\to A$ and $q:R\to B$ be the projections $p(x,y)=x$ and $q(x,y)=y$. By (i) applied to $p$ and to $q$,

$$\#R=\sum_{a\in A}\#p^{-1}\{a\},\qquad\#R=\sum_{b\in B}\#q^{-1}\{b\}.$$

Fix $a\in A$. The map $y\mapsto(a,y)$ is a bijection from $B$ onto $\{a\}\times B$ (Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (v), with the set $a$ and the set $B$), so its restriction $\iota_{a}:R_{a}\to R$ to $R_{a}$ is injective. It maps $R_{a}$ onto $p^{-1}\{a\}$, because a pair $(x,y)\in R$ has $p(x,y)=a$ exactly when it is $(a,y)$ with $y\in R_{a}$. An injective map does not change the number of elements of a finite set: Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iii), applied to the finite set $R_{a}$ and the map $\iota_{a}$, gives $\#p^{-1}\{a\}=\#R_{a}$. Thus the maps $a\mapsto\#p^{-1}\{a\}$ and $a\mapsto\#R_{a}$ from $A$ to $\mathbb{N}_{0}$ are equal, their sums agree, and $\#R=\sum_{a\in A}\#R_{a}$.

In the same way, for $b\in B$ the map $x\mapsto(x,b)$ is injective, since equal ordered pairs have equal first components (The Characteristic Property of Ordered Pairs and Nested Tuples of Sets (i)), and its restriction $\kappa_{b}:R'_{b}\to R$ to $R'_{b}$ maps $R'_{b}$ onto $q^{-1}\{b\}$. Hence Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iii), applied to $R'_{b}$ and $\kappa_{b}$, gives $\#q^{-1}\{b\}=\#R'_{b}$ for every $b\in B$, and $\#R=\sum_{b\in B}\#R'_{b}$.

Step 4: the pigeonhole principle ((iii)). Suppose, to the contrary, that $\#f^{-1}\{y\}\ge k+1$ fails for every $y\in B$. As $k+1$ is the successor of $k$, this says that $k<\#f^{-1}\{y\}$ fails, that is, $\#f^{-1}\{y\}\le k$ for every $y\in B$ (The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor (vi) with Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders (vii)). We compare sums in $\mathbb{R}$, where these inequalities hold. Sums in $\mathbb{R}$ preserve inequalities (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 (viii)) and sum a constant to the number of terms times it (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)); so, with (i),

$$\#A=\sum_{y\in B}\#f^{-1}\{y\}\le\sum_{y\in B}k=\#B\cdot k=k\cdot\#B,$$

and hence $\#A\le k\cdot\#B$ in $\mathbb{N}_{0}$. But the hypothesis $k\cdot\#B<\#A$ says exactly that $\#A\le k\cdot\#B$ fails (Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders (vii)). This contradiction shows that some $y\in B$ has $\#f^{-1}\{y\}\ge k+1$.