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?
Thanks
Lemma: is countable for all
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.
Obviously. In retrospect, here is a better way to do this problem.
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.