Prove every subset of a countable set is countable.

Hello there, I am trying to prove that any subset of a countable set is countable. I know that a set is countable if it is finite, or if it has the same cardinality as the set of natural numbers. (For a set A to have the same cardinality as the natural numbers, there must exist a bijection from A to N).

I have tried to split the proof into two cases, case (1) where A is a finite set, and case (2) where A has the same cardinality as the natural numbers. In fact , I'll write out what I've done.

Case (1): A is a finite set.

If A is a finite set, then we can list the elements as a finite sequence, i.e.

{a_1, a_2, a_3,.....,a_n} where n is some positive integer. Now take a subset of the a_i (where i = 1,2,.....,n)

say for instance we take {a_k,.....,a_m} where 1<=k<=m<=n.

Then we can put these a_i's into a finite sequence , i.e.

{a_k,....,a_m} and hence any subset of a countable finite set is countable.

Case (2): A and N (the naturals) have the same cardinality .

So we know that there exists a bijection from A to N, say

f : A ->N where f is some real function.

Hence, for all aEA, there exists a unique n E N such that f(a) = n. Also the image of f = N .

Therefore, if we take a subset of the countable set A, say B, then it is still true that for all b E B, there exists a unique n E N such that f(b) = n, and image of f is still equal to the codomain. Therefore, we still have a bijection from B to N.

So, whenever we take a subset of a countable set with the same cardinality as N, we get a countable set.

We have proven that in both cases, a subset of a countable set is countable, and so we are done.

I'm not sure if my proof is correct!!! I'd be grateful for any help, or if you know how to prove this, please let me know !!!

Thanks very much for your time!!!

Reply 1

dvs

Your proof is correct as far as I can tell. However, case (1) is easier than you made it out to be: if a set is finite, then its subsets are finite and hence countable. For (2), just look at the sequence of elements of A {a_n} (remember, there's a bijection from A to N), and now go through {a_n} generating a sequence {b_n} such that b_i=a_j where j is the smallest integer such that a_j is in B.

Reply 2

RichE

Say A is countable and B is a subset of A.

As A is countable there is an injective map f:A -> N

There is also an injective map g:B -> A given by inclusion.

Then fg:B-> N is injective and B is countable.