Inclusion–Exclusion, the Pigeonhole Principle and Double Counting

Let $S$ and $T$ be finite sets and let $a : S \times T \to \mathbb{R}$, or $a : S \times T \to \mathbb{N}$, written $a_{ij}$ for $a(i,j)$. Then $S \times T$ is finite and

$\sum_{i \in S}\Big(\sum_{j \in T} a_{ij}\Big) \;=\; \sum_{p \in S \times T} a_p \;=\; \sum_{j \in T}\Big(\sum_{i \in S} a_{ij}\Big),$

all three sums being the sums over a finite index set of The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form, carried by Finite sums and finite products, by recursion when the values are real and by Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ when they are natural.

This is not a clause of The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition. That theorem splits one sum along a partition of its own index set; the identity above exchanges the roles of two different index sets, and it is what an argument that counts a set of pairs in two ways needs. Both outer index sets may be empty, in which case all three quantities are $0$ (respectively $1$ for the product form of the underlying recursion), since a sum over the empty index set is the empty sum.

• What is actually used. Only the splitting clause and the reindexing clause, and each of them is stated for a real-valued and for a natural-valued summand. One argument therefore proves both readings, and nothing about subtraction or about the order enters.

• Why the slices and not an induction. The two partitions of $S \times T$ are the same set cut two ways, so the identity is a statement about one sum, not a statement relating two recursions. That is why no induction appears and why the empty cases need no separate treatment: a sum over an empty index set is the empty sum, and the argument passes through it unchanged.

Let $X$ and $Y$ be finite sets (Finite, countably infinite, countable, uncountable, The cardinality $\lvert A\rvert$ of a finite set) and let $R \subseteq X \times Y$ be a relation between them. For $x \in X$ and $y \in Y$ set

$R_x := \{\, y \in Y \ :\ (x,y) \in R \,\}, \qquad R^{y} := \{\, x \in X \ :\ (x,y) \in R \,\},$

the row fibre of $R$ at $x$ and the column fibre of $R$ at $y$.

(a) Everything here is finite. $X \times Y$ is finite (The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$, and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$, clause 1), so $R$ is finite as a subset of it, and $R_x \subseteq Y$ and $R^{y} \subseteq X$ are finite as subsets of finite sets (A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$, clause 1). Hence $\lvert R\rvert$, $\lvert R_x\rvert$ and $\lvert R^{y}\rvert$ are all defined, and each is a natural number (The cardinality $\lvert A\rvert$ of a finite set).

(b) The fibres are the slices of $R$, up to a bijection. For $x \in X$,

$R \cap (\{x\} \times Y) \;=\; \{x\} \times R_x ,$

since $(u,v)$ lies in the left-hand side exactly when $u = x$, $v \in Y$ and $(x,v) \in R$, that is exactly when $u = x$ and $v \in R_x$. The map $y \mapsto (x,y)$ is a bijection of $R_x$ onto $\{x\} \times R_x$, its two-sided inverse being the second-coordinate map (Injection, surjection, bijection), so $\lvert\{x\} \times R_x\rvert = \lvert R_x\rvert$ by the transport clause (c) of The cardinality $\lvert A\rvert$ of a finite set. Symmetrically $R \cap (X \times \{y\}) = R^{y} \times \{y\}$ and $\lvert R^{y} \times \{y\}\rvert = \lvert R^{y}\rvert$.

(c) The slices partition $R$. The sets $\{x\} \times R_x$, for $x \in X$, are pairwise disjoint, because a point of $\{x\} \times R_x$ has first coordinate $x$; and their union is $R$, because every $(u,v) \in R$ has $u \in X$ and $v \in R_u$. Symmetrically the sets $R^{y} \times \{y\}$, for $y \in Y$, are pairwise disjoint with union $R$.

(d) Neighbours. When $X = Y$ and $R$ is symmetric ($(x,y) \in R$ implies $(y,x) \in R$) and irreflexive ($(x,x) \notin R$ for every $x$), $R_x = R^{x}$ and this common set is called the set of neighbours of $x$; it is a subset of $X \setminus \{x\}$.

• A relation, not a matrix. The object counted here is a subset of a product of two finite sets. Nothing about arrays, entries or indices by position is used, and the two fibre families are the only structure the counting arguments need.

• No graph vocabulary. Clause (d) fixes the words symmetric, irreflexive and neighbour for a relation on a single finite set. Nothing among this page's declared prerequisites defines a graph, and none of the results stated with clause (d) needs one.

• Both fibre families are indexed by a finite set, which is what lets the cardinalities be summed at all: a sum over a finite index set is defined only when the index set is finite (The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form).

Let $X$ and $Y$ be finite sets and let $R \subseteq X \times Y$, with row fibres $R_x$ and column fibres $R^{y}$ as in A relation $R \subseteq X \times Y$ between finite sets, its row fibres $R_x$ and its column fibres $R^y$. Then, in $\mathbb{N}$,

$\sum_{x \in X}\lvert R_x\rvert \;=\; \lvert R\rvert \;=\; \sum_{y \in Y}\lvert R^{y}\rvert ,$

the sums being those of The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form.

Both index sets may be empty. If $X = \varnothing$ then $R = \varnothing$, every column fibre is empty, and all three quantities are $0$; the same holds with the roles of $X$ and $Y$ exchanged.

• Where the hypotheses are spent. Finiteness of $X$ and of $Y$ is what makes the two index sets legitimate index sets for a sum, and finiteness of $R$ is what makes $\lvert R\rvert$ defined. Disjointness of the slices is automatic, since a slice is determined by one coordinate of its points, which is why no hypothesis of that kind appears in the statement.

• The count stays in $\mathbb{N}$. Every quantity here is a cardinality, and the sums are the $\mathbb{N}$-valued ones. Nothing is embedded into $\mathbb{R}$ until an identity with a subtraction or a division has to be written.

Let $X$ and $Y$ be finite sets with $X \ne \varnothing$, let $R \subseteq X \times Y$, and let $R_x$ be its row fibres (A relation $R \subseteq X \times Y$ between finite sets, its row fibres $R_x$ and its column fibres $R^y$). Since $\lvert X\rvert \ne 0$, the real number

$\mu \;:=\; \frac{\iota(\lvert R\rvert)}{\iota(\lvert X\rvert)}$

is defined, where $\iota : \mathbb{N} \to \mathbb{R}$ is the canonical natural (The canonical natural $\iota(n) = n \cdot 1_F$ of a field). Then there are $x_{+}, x_{-} \in X$ with

$\iota(\lvert R_{x_{+}}\rvert) \ \ge\ \mu \qquad\text{and}\qquad \iota(\lvert R_{x_{-}}\rvert) \ \le\ \mu .$

The two elements need not be distinct, and neither inequality need be an equality: $\mu$ is a real number and a fibre size is a natural number, so no fibre need meet the average exactly.

• Why $X \ne \varnothing$ is a hypothesis and not decoration. It is used twice: to make $\iota(\lvert X\rvert)$ invertible, so that $\mu$ exists at all, and to produce the element at which the vanishing test is contradicted. With $X = \varnothing$ there is no fibre to exhibit and no quotient to compare it to.

• The average lives in $\mathbb{R}$ and the fibre sizes live in $\mathbb{N}$. A quotient of two natural numbers is not in general a natural number, so the comparison has to be made after both sides are carried into $\mathbb{R}$ by $\iota$. This is the reason the statement is written with $\iota$ throughout rather than as $\lvert R_x\rvert \ge \lvert R\rvert/\lvert X\rvert$, which is not an inequality between elements of one ordered set.

• Nothing is claimed about attainment. The proof produces an $x_{+}$ and an $x_{-}$ and no more; a relation whose fibre sizes all differ from $\mu$ exists, and it is exhibited on the companion page.

Let $m, n \in \mathbb{N}$ with $n \ge 1$ (The natural numbers $\mathbb{N}$ (von Neumann), Order on the natural numbers, On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$), and put

$Q(m,n) \;:=\; \{\, q \in \mathbb{N} \ :\ m \le n\,q \,\} ,$

the multiplication being that of $\mathbb{N}$ (Multiplication of natural numbers).

$Q(m,n)$ is nonempty, so the definition below has something to pick from. Since $n \ne 0$, Every nonzero natural number is a successor gives $n = \sigma(d)$ for some $d \in \mathbb{N}$, and then $n \cdot m = \sigma(d)\cdot m = d\cdot m + m = m + d\cdot m$ by the successor-left law of Distributivity and the successor law for multiplication and the commutativity of addition (Addition is commutative), so $m \le n\cdot m$ by the definition of the order (Order on the natural numbers), which asks for a natural $j$ with $m + j = n m$ and is met by $j = d\cdot m$. Hence $m \in Q(m,n)$.

Definition. $\big\lceil m/n \big\rceil$ is the least element of $Q(m,n)$, which exists by the well-ordering principle (The well-ordering principle) applied to the nonempty subset $Q(m,n)$ of $\mathbb{N}$. It is a natural number, and it is defined for $n \ge 1$ only.

Four clauses, recorded here because they are what the notation is used for.

(a) $m \le n\big\lceil m/n\big\rceil$. This is membership of $\big\lceil m/n\big\rceil$ in $Q(m,n)$.

(b) Minimality. If $q \in \mathbb{N}$ satisfies $m \le n q$ then $\big\lceil m/n\big\rceil \le q$; equivalently, every $q$ with $q < \big\lceil m/n\big\rceil$ satisfies $n q < m$, by trichotomy (Trichotomy of the order on $\mathbb{N}$).

(c) Two values read off directly. $\big\lceil 0/n\big\rceil = 0$, since $0 \le n\cdot 0$ makes $0$ the least element of $\mathbb{N}$ that qualifies; and $\big\lceil m/1\big\rceil = m$, since $m \le 1\cdot m = m$ while $m \le 1\cdot q$ forces $m \le q$ (Zero and one under multiplication, Multiplication is commutative).

(d) The reading in $\mathbb{R}$. With $\iota : \mathbb{N} \to \mathbb{R}$ the canonical natural (The canonical natural $\iota(n) = n \cdot 1_F$ of a field), clause (a) gives $\iota(m) \le \iota(n)\,\iota\big(\lceil m/n\rceil\big)$ by the multiplicativity of $\iota$ (clause 0 of Laws of finite sums and products in $\mathbb{N}$, and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$) and its strict monotonicity (clause 7); and $\iota(n) > 0$ because $n \ge 1$. Since $\mathbb{R}$ is an ordered field (Ordered field, Field), dividing by $\iota(n)$ gives

$\frac{\iota(m)}{\iota(n)} \ \le\ \iota\Big(\big\lceil m/n\big\rceil\Big) .$

• This is not a floor and it is not a ceiling function. It is defined for a pair of natural numbers with $n \ge 1$, its value is a natural number, and it is fixed by one order property and one minimality property. It is not defined for a real argument, it does not extend to negative numbers, and it carries no division: the symbol $m/n$ inside the brackets is part of the notation and not an operation performed anywhere above.

• Why it is introduced at all. The strong form of the pigeonhole principle says that some fibre has at least "the average, rounded up" elements, and that phrase needs a name for the rounding. The least $q$ with $m \le nq$ is exactly what the proof produces, and the well-ordering principle is exactly what makes it exist, so nothing stronger is required.

• Nothing among this page's declared prerequisites supplies a division with remainder, and the definition above deliberately does not attempt one: no $r$ with $m = nq + r$ and $r < n$ is produced or claimed here.

Let $A$ and $B$ be finite sets, let $k \in \mathbb{N}$, let $f : A \to B$, and for $b \in B$ write

$f^{-1}[\{b\}] \;:=\; \{\, a \in A \ :\ f(a) = b \,\}$

for the fibre of $f$ over $b$ (Injection, surjection, bijection). Then:

1. The counting form. If $\lvert A\rvert > k\,\lvert B\rvert$ then there is $b \in B$ with $\lvert f^{-1}[\{b\}]\rvert > k$.
2. The ceiling form. If $B \ne \varnothing$ then there is $b \in B$ with $\lvert f^{-1}[\{b\}]\rvert \ge \big\lceil \lvert A\rvert/\lvert B\rvert\big\rceil$ ($\lceil m/n \rceil$ for naturals $m$ and $n \ge 1$: the least $q \in \mathbb{N}$ with $m \le n q$, which is defined because $\lvert B\rvert \ge 1$).

Every quantity here is a natural number and the comparisons are those of $\mathbb{N}$ (Order on the natural numbers). Clause 1 at $k = 0$ says that a nonempty $A$ has a nonempty fibre. Clause 1 is vacuous when $B = \varnothing$, since then $k\,\lvert B\rvert = 0$, the hypothesis says $A \ne \varnothing$, and there is no function from a nonempty set to $\varnothing$ for the conclusion to be about. Clause 2 at $A = \varnothing$ says only that some fibre has at least $0$ elements, since $\lceil 0/\lvert B\rvert\rceil = 0$.

• Where the ceiling earns its keep. Clause 2 is not a separate argument: it is clause 1 applied at the single value $q$ with $\sigma(q) = c$, and the only thing that has to be checked is that this $q$ satisfies $\lvert A\rvert > q\lvert B\rvert$, which is exactly the minimality of $c$. That is the whole reason the ceiling was defined by minimality rather than by a division.

• The case $c = 0$ is not a degenerate nuisance. It occurs precisely when $A = \varnothing$, where the conclusion is empty of content but still needs an element of $B$ to be stated about, and that is where $B \ne \varnothing$ is spent in clause 2.

• Disjointness of the fibres is free, since a fibre is determined by the value it lies over. This is what lets the sum rule be applied with no hypothesis beyond finiteness, in contrast to a union of arbitrary sets.

A sieve family consists of a finite set $X$, called the ambient set, a finite set $I$, called the index set, and a family $(A_i)_{i \in I}$ of subsets of $X$, that is a function $I \to \mathcal{P}(X)$ (Finite, countably infinite, countable, uncountable, The cardinality $\lvert A\rvert$ of a finite set). For $J \subseteq I$ set

$A_J \;:=\; \begin{cases} \displaystyle\bigcap_{i \in J} A_i, & J \ne \varnothing,\\[4pt] X, & J = \varnothing,\end{cases}$

and write $U := \bigcup_{i \in I} A_i$ for the union of the family.

Why the ambient set has to be named, and why $A_\varnothing := X$ is a stipulation. For $J \ne \varnothing$ the intersection $\bigcap_{i \in J}A_i$ is the set of elements belonging to every $A_i$ with $i \in J$, and it is determined by the family alone. For $J = \varnothing$ that description is satisfied by every set whatsoever, so it determines nothing; an intersection of no subsets of $X$ is $X$ only relative to $X$. Naming $X$ as part of the data and stipulating $A_\varnothing = X$ is what makes the symbol $A_J$ defined for all $J \subseteq I$, which is what the complementary form of the sieve identity requires.

(a) Every $A_J$ is a finite subset of $X$. For $J \ne \varnothing$ pick $i \in J$; then $A_J \subseteq A_i \subseteq X$. For $J = \varnothing$, $A_J = X$. In both cases $A_J \subseteq X$ is finite by clause 1 of A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$, and so is $U \subseteq X$; hence $\lvert A_J\rvert$ and $\lvert U\rvert$ are natural numbers (The cardinality $\lvert A\rvert$ of a finite set).

(b) The index sets of the sieve's sums are finite. $\mathcal{P}(I)$ is finite with $\lvert\mathcal{P}(I)\rvert = 2^{\lvert I\rvert}$ ($\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$); the set $\mathcal{P}(I) \setminus \{\varnothing\}$ of nonempty subsets of $I$ and the set $[I]^{j}$ of $j$-element subsets of $I$ are subsets of $\mathcal{P}(I)$, hence finite (A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$), and $\lvert [I]^{j}\rvert = \binom{\lvert I\rvert}{j}$ (The set $[A]^{k}$ of $k$-element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$).

(c) Monotonicity. If $J \subseteq J' \subseteq I$ then $A_{J'} \subseteq A_J$. For $J = \varnothing$ this is clause (a); otherwise an element lying in every $A_i$ with $i \in J'$ lies in every $A_i$ with $i \in J$.

(d) The trace of a point. For $x \in X$ put