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.
By definition, a set A is countable if there is a injection from A to $\displaystyle \mathbb{N}$, so trivially any finite set (including the empty set) is countable. But you need to show that the collection of subsets having n elements is countable as Hallsoflvy said
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
$\displaystyle P_2 = \{\{0,1\},\{0,2\},\cdots,\{1,2\},\{1,3\},\cdots\}$
and $\displaystyle P_2$ is a countable set. And you can see that $\displaystyle P_2$ could be injected in $\displaystyle \mathbb{N}^2$
It should be clear to you that we can take the set $\displaystyle A$ as $\displaystyle \mathbb{Z}^ +$.
Now list the prime numbers: $\displaystyle P= \left\{ {p_1 ,p_2 ,p_3 , \cdots ,p_n , \cdots } \right\}$. For example: $\displaystyle p_1 = 2\;,\,p_2 = 3\;\& \,p_6 = 13$.
Use the set of finite subsets of $\displaystyle \mathbb{Z}^ +$: $\displaystyle \mathbb{F} = \left\{ {X:X \subseteq \mathbb{Z}^ + \;\& \;X \text{ in finite}} \right\}$.
Define a function $\displaystyle f:\mathbb{F} \mapsto \mathbb{Z}^ + \;,\;f(X) = \prod\limits_{n \in X} {p_n } $.
Let us look at some examples: $\displaystyle f\left( {\left\{ 6 \right\}} \right) = 13,\;f\left( {\left\{ {2,4} \right\}} \right) = 3 \cdot 7\;\& \;f\left( {\left\{ {3,4,6} \right\}} \right) = 5 \cdot 7 \cdot 13$.
Now using the prime factorization theorem, it easy to prove that $\displaystyle f$ is an injection from $\displaystyle \mathbb{F}$ to $\displaystyle \mathbb{Z}^+$.
Thereby proving that $\displaystyle \mathbb{F}$ is countable.