# Cartesian product of a family of countable sets is countable!

1. Sep 13, 2009

### sutupidmath

Proposition: Let $$\{A_n\}_{n\in I}$$ be a family of countable sets. Prove that

$$\bigotimes_{i=1}^n A_i$$

is a countable set.

Proof:

Since $$\{A_n\}_{n\in I}$$

are countable, there are 1-1 functions

$$f_n:A_n->J$$

(J, the set of positive integers)

Now let us define a function

$$h:\bigotimes_{i=1}^n A_i->J$$

such that

$$h(a_1,a_2,...,a_n)=(p_1)^{f_1(a_1)}*(p_2)^{f_2(a_2)}*...*(p_n)^{f_n(a_n)}$$

Where p_i are prime numbers such that

$$2\leq p_1<p_2<...<p_n$$

Now from the Fundamental Theorem of Arithmetic,it is clear that h is a 1-1 function. So, based on some previous theorems, we conclude that

$$\bigotimes_{i=1}^n A_i$$

is a countable set.

Is this correct?

2. Sep 13, 2009

### VeeEight

Your topic title should include the word finite (you have written it up as such in your proposition, though)

That is pretty much the proof I have always seen for the theorem, although you may have to explain the 'previous theorems' you mentioned

3. Sep 13, 2009

### sutupidmath

THe previous theorem(s) are basically that every infinite subset of J is countable. And also that every subset of a countable set is countable.

The reason i posted this is that i've only seen a theorem that proves for the case of only two sets A, B, so i wanted to generalize on the idea. THe motvation behind this came from another problem i was working on. It looked like i needed to prove this proposition before could tackle that problem...and it worked out fine.

4. Sep 14, 2009

### HallsofIvy

Staff Emeritus
In fact, it is true that a the union of countable collection of countable sets is countable:
Imagine writing the sets in a row and the members of each set is a column below the set. Now, "zig-zag" through the array.