Intuition - Countable iff Surjection iff Injection [Velleman P310 Thm 7.1.5]

239 Views Asked by At

Define $I_n = \{1, 2, ..., n \} $. Let $A$ be a nonempty set. TFAE :
(i) $A$ is finite (ie: a bijection $h:A\rightarrow I_{N}$ exists)
or A is countably infinite (ie: a bijection $h:A\rightarrow \mathbb{N} $ exists.)
(ii) $A = \emptyset$ or There exists a surjection $f: \mathbb{N} \rightarrow A$. $\quad$ (iii) There exists an injection $g: A \rightarrow \mathbb{N}$.

What's the intuition? Are there pictures? I'm not enquiring about formal arguments, so this is not a duplicate of any other question.

1

There are 1 best solutions below

0
On BEST ANSWER

There's two main ideas involved in the proof of these statements.

  1. Taking an injection $A \rightarrow \mathbb{N}$, and building an injection the other way around $\mathbb{N} \rightarrow A$ or $I_N \rightarrow A$.

  2. Taking an surjection from a smaller set, and turning it into a surjection from a larger set.

Once you have intuition for these things, it should be easier to understand the formal proof.


First, to "turn around" the injection $A \rightarrow \mathbb{N}$, you can relabel the elements that get hit. Label the first natural number to get hit by $1$, the second number to get hit by $2$, and so forth. Either an infinite number of things get hit, or a finite number of things gets hit, so you now can turn around the arrows to get an injection from either $\mathbb{N} \rightarrow A$ or $I_N \rightarrow A$ respectively.

enter image description here


Second, to take a surjection from a smaller set and turn it into a surjection from a larger set, just map everything from the smaller set the same, and map the the extra stuff to a single element.

enter image description here