This isn’t a substitute for books .
Reminder
- $A \preceq B$: $A$ can be “injected” into $B$.
- $A \sim B$: $A$ and $B$ share the same cardinality.
- $A \prec B$: $A$ can be “injected” into $B$, but it’s “smaller” than $B$.
- A finite set can be “counted” from one to some nonnegative integer.
- Infinite is the “antonym” of finite.
Wolf’s proof
When I first saw this proof in Robert S. Wolf’s Proof, Logic and Conjecture: The Mathematician’s Toolbox, I gave it up since it wasn’t as intuitive as the statement.
An informal argument
Later, I found some interesting illustrations in Richard Hammack’s Book of Proof.
- “Draw” gray $A$ and white $B$.
- “Draw” the given injections $f: A \to B$ ($A$ contained in $B$) and $g: B \to A$ ($B$ contained in $A$). (Figure 13.4)
- “Draw” an infinite chain of alternating injections starting from $A$. (Figure 13.5)
- In “diagram $A$ at step infinity $\infty$” ($A$ containing $B$ containing $A$ …), label the “gray region” as $G$.
- Label remaining white region as $W$. (i.e. $W := A \setminus G$)
- “Draw” a “homologous” diagram with the one in step 4 on the right-hand side, but starting from $B$. (i.e. $B$ containing $A$ containing $B$…) (Figure 13.6)
- It’s natural to associate the gray regions $G \subseteq A$ with $f(G)
\subseteq B$ on both sides. It remains to settle $W$.
- Applying $f$ on $W$ won’t lead to any useful results.
- Another given injection $g$ can’t be applied on $W$ due to domain mismatch.
- Reverse the “direction” of $g$ to that it points to the white region wrapping gray $f(A)$.
It’s nice to see a constructive and formal proof immediately following this intriguing argument. The later actually guides me through the former.