# Subset of a countable set is itself countable

How is it proved that if $$A \subset B\ \text{with}\ B\ \text{countable}$$ then $A$ is either countable, finite, or empty? I think the proof involves a $1-1$ correspondence between $\mathbb{N}$ and $A$ but other than that I do not know how to proceed.

EDIT: I have checked the solution and it advises me to proceed as follows. " As a start to a definition of $$g: \mathbb{N} \rightarrow A$$ set $$g(1)=f(n_1)$$ Then show how to inductively continue this process to produce a $1-1$ function $g$ from $\mathbb{N}$ onto $A$."

So the proof according to my book involves induction.

• Misleading title... What if you used a contradiction? – abiessu Nov 4 '13 at 15:03
• Maybe you can use the well-order of the natural numbers. – Stefan Hamcke Nov 4 '13 at 15:03
• Thank you for your responses but since I am a begginer, could you please be a little more specific? – JohnK Nov 4 '13 at 15:04
• "countable finite or empty" There is something wrong in your question. – Michael Greinecker Nov 4 '13 at 15:06
• The inclusion of $A$ in $B$ gives via the bijection $B\equiv\Bbb N$ an injection $i:A\to\Bbb N$. Now you can define a function $f: 1↦\min i[A],\ 2↦\min i[A]\setminus\{f(1)\},\ 3↦\min i[A]\setminus\{f(1),f(2)\},...$ – Stefan Hamcke Nov 4 '13 at 15:08

Via the bijection $\Bbb N\cong B$ we have an injection $i:A\to\Bbb N$.

Define $$f(n+1)=\min\{k∈i[A]∣k>f(n)\}$$ for $n≥1$ and $$f(1)=\min i[A]$$

We claim that for each $n$ we have $\{f(1)<f(2)<...<f(n)\}$ is a subset of $i[A]$ and contains each $i(a)$ less than $f(n)$.
Proof: Induction over $n$:
For $n=1$ clearly $f(1)∈i[A]$, and since there is no $i(a)<f(1)$, the claim is true.
Assume that the statement is true for $n$. Then by definition of $f$, the number $f(n+1)$ is larger than $f(n)$, so the set $\{f(1)<...<f(n)<f(n+1)\}$ is a subset of $i[A]$. Since $f(n+1)$ is the minimal element of $i[A]$ larger than $f(n)$, it must contain each $i(a)$ less than $f(n+1)$.

So we have shown that $f:\Bbb N↦i[A]$ is an injection. Now, for $a\in A$ we have the natural number $l=i(a)$. Since $l$ is less than $f(n)$ for some $n\in\Bbb N$, $f$ being strictly increasing, it must thus be one of $f(1),f(2),...,f(n-1)$.

Any subset of a countable set is countable.

Take $A\subset B$ where $B$ is countable. Then $|A|\leq|B|$ since $A\subset B$. By definition, $|A|\leq|B|$ if there is a one-to-one function from $A$ into $B$. We also see that $|B|\leq\aleph_0$ since $B$ is countable. Thus, $|A|\leq\aleph_0$.

• Your response is very intuitive and thank you for it but I fear that I am required to produce a bisection for that exercise. – JohnK Nov 4 '13 at 20:17

Hint: Define an injection $f:B \to \mathbb{N}$ (this is possible as B is countable). Define the inclusion mapping $I:A \to B$. Consider $f\circ I:A \to \mathbb{N}.$ What can you say about $I$? What can you then say about $f \circ I$? What can you then conclude about $A$?

Hint: Suppose $f$ is the function that maps $B$ to $\mathbb{N}$, sort each item in $B$ by it's $f$ value.