0
$\begingroup$

This is basically a problem of my assignment, it says...

A set is said to be countable if it is either finite or there is an enumeration(list) of the set. Then prove that All subsets of countable sets are countable.

While proving the above, do I have to prove all these 3 cases separately?

  • Finite subset of a finite set is countable.

  • Finite subset of a countably infinite set is countable.

  • Infinite subset of a countably infinite set is countable.

This is my confusion. And if we want to prove that a set $S$ is countable, we have to show that the function $f:\mathbb{N}\rightarrow S$ is a bijection. Using it, I can prove the 3rd part(infinite subset of countably infinite set); but how can I use this definition to prove the 1st two? Or, if I show that a finite set is countable, will that be enough to say that the 1st two are true?

Please anyone help me solve it. Thanks in advance.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Some authors use the term "countable" to only refer to infinite sets for which there exists a bijective function with the natural numbers. Other authors, like the author of the assignment you are referring to, use the term "countable" to refer to any sets (finite or infinite) for which there exists an injective function to the natural numbers. I.e. the first author means that a countable set has the same cardinality as the natural numbers while the second author means that a countable set has cardinality less than or equal to that of the natural numbers. $\endgroup$ – JMoravitz May 23 at 15:55
  • $\begingroup$ According to your definition, a finite set is countable. Thus there are countable sets for which there can be no bijection with $\mathbb N$. $\endgroup$ – lulu May 23 at 15:56
0
$\begingroup$

For finite subsets, it would be sufficient (given your definition) to say that any finite subset is countable. However, a more rigorous proof will follow my answer to this question here.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Since finite subsets are countable by definition, you do not have to prove anything.

For infinite subsets, you consider the sub-sequence formed by terms of your subset and ignoring the terms which are not in your subset.

|cite|improve this answer
$\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.