# Proof: if $A \subseteq B$ and $B$ is countable, then $A$ is either countable, finite, or empty.

In Abbott's "Understanding Analysis," Abbott offers the following idea to run through the proof:

Assume B is a countable set. Thus, there exists a bijection $f:\mathbb{N} \rightarrow B$. Let $A\subseteq B$ be an infinite subset of $B$. We show $A$ is countable. Let $n_1=\min\{n\in \mathbb{N}: f(n)\in A\}$. As a start to a definition for $g: \mathbb{N}\rightarrow A$, set $g(1)=f(n_1)$. Show how to inductively continue this process to produce a bijection $g:\mathbb{N}\rightarrow A$.

I'm not seeing how to inductively continue this process to produce a definition for a bijection. Thanks for the help!

• Isn't cardinality monotone, i.e., if $A \subset B \rightarrow |A| \leq |B|$? – Gary. May 31 '15 at 19:45
• I would like to comment. Countable does NOT mean bijective with natural numbers. "Countable or finite " is unnecessary. Finite sets are countable. – user223391 May 31 '15 at 20:33
• @Gary If you define $|A| \le |B|$ to mean that there is an injection from $A$ to $B$, then yes, that implication is clearly true. However, the OP's definition of "countable" seems to be "having a bijection with $\mathbb{N}$", so the point of the question is to get a bijection rather than just an injection (in the case that the subset is not finite.) – Trevor Wilson May 31 '15 at 21:39

Let $n_2$ be the next $n$ (after $n_1$) such that $f(n) \in A$. Let $g(2):=f(n_2)$. Can you see how to continue?

To prove $g$ is onto, note that $\{g(1),g(2),\dots,g(K)\} = A \cap \{f(1), \dots, f(n_K)\}$. Further, $n_i$ increases strictly and $f$ is onto.

• So, if $g(1)=g(2)$, it would have to be the case that $n_1=n_2$ by definition. My only question is how would $n_2$ be defined in terms of a min? And then for onto, let $k\in A$. Then, how do I know there exists $n_j \in \mathbb{N}$ with $n_j=min\{n\in \mathbb{N}:f(n) \in A\}$? – Moz May 31 '15 at 19:45
• Note that $n_2=\min \{n \in \mathbb{N} : n>n_1, \: f(n) \in A \}$. – TorsionSquid May 31 '15 at 19:51
• Ah, I see specifically what you mean by the next one. Thanks! – Moz May 31 '15 at 19:56
• To prove $g$ is onto, note that $\{g(1),g(2),\dots,g(K)\} = A \cap \{f(1), \dots, f(n_K)\}$. Further, $n_i$ increases strictly and $f$ is onto. – TorsionSquid May 31 '15 at 19:59
• I am not able to see onto in the following way. Since $f$ is a bijection, there exists $a \in A$ satisfying $a=f(j)$ for some $j\in \mathbb{N}$. Then, $n_j>j$. I'm not sure how to get the necessary equality. – Moz May 31 '15 at 20:51

It is easier to produce a bijection in the other direction: $h:A\to\mathbb N$, by

$$h(n) = \#\{a\in A\mid a<n\}$$

• It's easier to define the function, but I'm not sure if it's really easier to prove that it's a bijection; to show that it is onto, it seems like you still need the induction argument from TorsionSquid's answer. – Trevor Wilson May 31 '15 at 21:46