Kolmogorov & Fomin show that every subset of a countable set is countable by taking a set $A$ with elements $a_{1}, a_{2}, …$, and a subset of $A$ called $B$ with elements $a_{n_1}, a_{n_2}, …$, then arguing that if the $n_i$ have a largest element B is a finite set, otherwise B is countable with the correspondence $i \iff a_{n_i}$.
This is pretty much the only way I've seen this theorem proved anywhere, and while I appreciate how concise this approach is, for me it's much more intuitive to think of this in terms of the contradiction:
Theorem: Every subset of a countable set is countable.
Proof. First, we prove a lemma:
Lemma: Let $f:A\rightarrow B$ be a bijection, $C \subseteq A$, and $f\vert_{C}:C\rightarrow B$ the restriction of $f$ to $C$. Then $f\vert_{C}$ is a bijection.
Proof: Since $f$ is a bijection, $b = f(c)$ is uniquely defined for each $c \in C$, $b \in B$. Hence $f\vert_{C}$, is a bijection, and the lemma is proved.
Now let $A$ be a countable set, with $B$ a subset of $A$.
Let's suppose that $B$ is not countable. In other words we suppose that there does not exist a bijection between $B$ and some subset of the natural numbers.
Since A is countable, there is a bijection $\phi:A\rightarrow\mathbb{N}$. Because $\phi$ is a bijection, it is defined for each element of $A$ including those in $B$, hence the restriction $\phi\vert_{B}:B\rightarrow\mathbb{N}$ must exist. Note that $\phi\vert_{B}$ is also bijective by our lemma.
But this is impossible, since by hypothesis $B$ is not countable, so no such bijection can exist. Then we have reached a contradiction, and must assume otherwise — namely, $B$ must be countable. Since $B$ was arbitrarily chosen, we can assume this holds in general for all subsets of countable sets. $\square$
My questions are the following:
- Is this proof sound?
- Given the length of my proof, I can see the appeal of the K&F style proof over this (assuming mine is sound). Are there places where mine could be made more concise? For example, I considered that the lemma might not be necessary since it (seems to) follow directly from the definition
Best Answer
A simple proof.
A set $S$ is countable when there is an injection $f:S \to \mathbb{N}$.
Let $S$ be countable and A a subset of S.
Thus exists injection $f:S \to \mathbb{N}$.
As $f|_A:A \to \mathbb{N}$ is an injection, $A$ is countable.