1
$\begingroup$

Proposition. A subset of a countable set is countable. Proof. Let $X$ be a countable set and let $A \subseteq X$. Then there is a bijection $f:X \to \mathbb{N}$. Let $\varphi: A \to X$ be the inclusion mapping defined by $\varphi(x)=x$. Since the composition of injections is also an injection, it follows that $f \circ \varphi: A \to \mathbb{N}$ is also an injection. Thus $A$ is countable.

If $X$ were to be countably infinite, could we expand the above proof to show that every subset of $X$ is either finite or countably infinite? It seems like we would just have to show that $\varphi$ is also a surjection, but I am not sure how.

$\endgroup$
1
$\begingroup$

Your proof should describe $f$ as an injection, rather than a bijection. Otherwise, it looks fine.

Now, if $X$ is countably infinite, then we can alter the proof as you say. However, it would be easier to prove it as a corollary. To start with, prove that every infinite subset of $\Bbb N$ is in bijection with $\Bbb N.$ Consequently, every countable set is either finite or countably infinite. Can you prove these claims and proceed from there?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.