How can I show that if A is a countable set, then A has countably many finite subsets?
To show that the collection of subsets with exactly n members are countable (for every integer n), can that be done by first showing that n = 1 is countable, then showing n+1 is countable under the assumption that n is countable -- i.e. induction?
If that is a correct way to proceed, how exactly does one show something as trivial that a set with one element is countable? I really having some trouble with this as I don't understand the operations that should be used.
A collection of subsets with exactly n elements, where n is of the natural numbers -- doesn't that mean every set in the collection is merely a finite set and is thus countable?
Or does "collection of subsets" mean something else than merely all the sets that can be constructed with n elements where n is of the natural numbers?
Not sure I understand you. We mean the collection itself is countable (the set of subsets)
in fact HallsofIvy said
First show that for every integer n, the collection of subsets with exactly n members IS countable.
For instance the collection of subsets with cardinality 2 is
and is a countable set. And you can see that could be injected in
It should be clear to you that we can take the set as .
Now list the prime numbers: . For example: .
Use the set of finite subsets of : .
Define a function .
Let us look at some examples: .
Now using the prime factorization theorem, it easy to prove that is an injection from to .
Thereby proving that is countable.