Wait! You want to prove that A is countable so
you need a bijective function from to A right?
Q- Prove that the collection of all finite subsets of N are countable
What I have so far:
Let be the set of all subsets of consisting of elements, be the set of all finite subsets of . Then is a union of ....
Now I need to find a bijective function of this union to the real numbers? How should I proceed from where I am?
Proof: Let be given by . This is clearly an injection.
Now, let be given by where is the th prime. It is clear that this is an injection since the representation of a number by a prime decomposition is unique (fundamental theorem of arithmetic)
So, the conclusion follows by virtue of the Schroder-Bernstein theorem.
Now, let be set of all finite subsets of with cardinality . Define by where (this is possible because of finiteness). This is clearly an injection, for to suppose that would mean that and so . It follows that each is countable.
And then since it follows that is the countable union of countable sets, and thus countable.
Let be as normal and define on it the relation which (as can be readily proved) is an equivalence relation, and thus forms a partition of . Define by (make the proper addendum so that mapping is well-defined). Clearly this is an injection. Now, form a mapping by . This is readily verified to be a bijection. It follows that is an injection and so is countable by the lemma. And since and the countable union of countable sets is countable it follows that is countable.