# Math Help - Countable sets?

1. ## Countable sets?

How can I show that if A is a countable set, then A has countably many finite subsets?

2. Originally Posted by posix_memalign
How can I show that if A is a countable set, then A has countably many finite subsets?
First show that for every integer n, the collection of subsets with exactly n members is countable. Then show that the union of all those sets (a countable collection of countable sets) is countable.

3. Originally Posted by HallsofIvy
First show that for every integer n, the collection of subsets with exactly n members is countable. Then show that the union of all those sets (a countable collection of countable sets) is countable.
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.

4. By definition, a set A is countable if there is a injection from A to $\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

5. Originally Posted by tah
By definition, a set A is countable if there is a injection from A to $\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?

6. 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

$P_2 = \{\{0,1\},\{0,2\},\cdots,\{1,2\},\{1,3\},\cdots\}$

and $P_2$ is a countable set. And you can see that $P_2$ could be injected in $\mathbb{N}^2$

7. Originally Posted by tah
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

$P_2 = \{\{0,1\},\{0,2\},\cdots,\{1,2\},\{1,3\},\cdots\}$

and $P_2$ is a countable set. And you can see that $P_2$ could be injected in $\mathbb{N}^2$
Sorry that I don't understand this, I'm trying really hard.

So I should show that $P_n$ is countable? Can I do this with induction?

8. It should be clear to you that we can take the set $A$ as $\mathbb{Z}^ +$.
Now list the prime numbers: $P= \left\{ {p_1 ,p_2 ,p_3 , \cdots ,p_n , \cdots } \right\}$. For example: $p_1 = 2\;,\,p_2 = 3\;\& \,p_6 = 13$.

Use the set of finite subsets of $\mathbb{Z}^ +$: $\mathbb{F} = \left\{ {X:X \subseteq \mathbb{Z}^ + \;\& \;X \text{ in finite}} \right\}$.

Define a function $f:\mathbb{F} \mapsto \mathbb{Z}^ + \;,\;f(X) = \prod\limits_{n \in X} {p_n }$.

Let us look at some examples: $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 $f$ is an injection from $\mathbb{F}$ to $\mathbb{Z}^+$.
Thereby proving that $\mathbb{F}$ is countable.