# countable sets

• May 18th 2012, 02:40 PM
stuffthings
countable sets
I need some help with this proof:

Let C be a countable set. Prove C^n is countable for all n.

I was thinking to show that the Cartesian product of any countable sets is countable by writing them out in a table and going through the elements diagonally to count them, similar to a proof I have seen to show that the rational numbers are countable.

this proves C^2 is countable since C is countable.
then using induction I can say that C^n+1 is countable because it = C^n (which is countable from the induction premise) x C and is therefore the cartesian product of two countable sets.
• May 18th 2012, 02:50 PM
Plato
Re: countable sets
Quote:

Originally Posted by stuffthings
Let C be a countable . Prove C^n is countable for all n.

Suppose that $\mathbb{N}$ is the set of natural numbers.
Map $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ by $(j,k)\mapsto 2^j\cdot 3^k$.
Show that is an injection.
Thus $C\times C$ is countable. Now use induction.