Exercise 3.6.10 (Pigeonhole principle)

Strategy. We will prove the contrapositive, which reads: Let $A_1,\dots ,A_n$ be finite sets. If there does not exist an $i\in \{1,\dots ,n\}$ such that $\#(A_i)\ge 2$, then $\#({\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{i\in \{1,\dots ,n\}}{A}_i)\le n$.

Proof. Suppose there does not exist an $i\in \{1,\dots ,n\}$ such that $\#(A_i)\ge 2$. Then, by Proposition 2.2.13, we have $\#(A_i)<2$ for all $i\in \{1,\dots ,n\}$. This implies, by the contrapositive of Proposition 2.2.12 (e),

Let’s denote ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{i\in \{1,\dots ,n\}}{A}_i$ by $A_1\cup A_2\cup \cdots \cup A_n$. Then we have

We need to show $A_2\cup \cdots \cup A_n$ is a finite set before going on: We’re given that $A_2$ and $A_3$ are finite. This means, by Proposition 3.6.14 (b), that $A_2\cup A_3$ is a finite set. With $A_2\cup A_3$ and $A_4$ finite, we have, again by Proposition 3.6.14 (b), that $(A_2\cup A_3)\cup A_4=A_2\cup A_3\cup A_4$ is finite. Repeating this process up to $i=n$, we will get that $A_2\cup \cdots \cup A_n$ is a finite set.

Now, with $A_1$ and $A_2\cup \cdots \cup A_n$ being finite sets, we have, by Proposition 3.6.14 (b), that $A_1\cup (A_2\cup \cdots \cup A_n)$ is finite and

By repeating the above two arguments $n-1$ more times and combining $(2)$ and $(3)$, we get

where $(5)$ follows from $(4)$ by statement $(1)$. We’re done.