CSB Theorem

A visual argument for CSB Theorem

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.

  1. Draw” gray $A$ and white $B$.
  2. Draw” the given injections $f: A \to B$ ($A$ contained in $B$) and $g: B \to A$ ($B$ contained in $A$). (Figure 13.4)
  3. Draw” an infinite chain of alternating injections starting from $A$. (Figure 13.5)
  4. In “diagram $A$ at step infinity $\infty$” ($A$ containing $B$ containing $A$ …), label the “gray region” as $G$.
  5. Label remaining white region as $W$. (i.e. $W := A \setminus G$)
  6. 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)
  7. 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.


No comment