The cartesian product of a finite amount of countable sets is countable.

Question

I want to prove that the cartesian product of a finite amount of countable sets is countable. I can use that the union of countable sets is countable.

My attempt:

Let $A_1,A_2, \dots, A_n$ be countable sets.

We prove the statement by induction on $n$

For $n = 1$, the statement clearly holds, as $A_1$ is countable. Now, suppose that $B := A_1 \times A_2 \times \dots A_{n-1}$ is countable.

We have: $$B \times A_n = \{(b,a)|b \in B, a \in A_n\}$$ $$= \bigcup_{a \in A_n} \{(b,a)|b \in B\}$$

and $\{(b,a)|b \in B\}$ is countable for a fixed $a \in A_n$, since the function $f_a: B \to B \times \{a\}: b \to (b,a)$ is a bijection, and $B$ is countable by induction hypothesis. Because the union of countable sets remains countable, we have proven that $(A_1 \times \dots A_{n-1}) \times A_n$ is countable, and because $f: (A_1 \times \dots A_{n-1}) \times B \to A_1 \times \dots A_{n-1} \times A_n: ((a_1, \dots, a_{n-1}),a_n) \mapsto (a_1, \dots, a_{n-1},a_n)$ is a bijection, the result follows.

Questions:

• Is this proof correct/rigorous?
• Are there other proofs that are easier?
• Someone pointed out that we can prove this theorem using the 'zigzag'-argument. Can someone provide this proof? I think this zigzag-method is too graphical, and therefore not rigorous, so if someone can clarify why this method is completely rigorous, I would be more than glad to award him the bonus.

Answer 1

The phrase 'the union of countable sets is countable' is wrong unless you add the word 'countable' before 'union'.

The zig-zag argument is nothing but a graphical way to describe a bijection between $ {\Bbb N}\times{\Bbb N}$ and $ {\Bbb N}$. You may also give an explicit formula for such a bijection. Using the French notation that $0\in {\Bbb N}$, you may check that

$$ \phi (m,n) = m + \sum_{k=1}^{m+n} k $$ yields such a bijection. The inverse map is the 'zig-zag' path. Having constructed this function we may iterate to solve when taking further products. For example: $$ (m,n,p) \in {\Bbb N}\times{\Bbb N} \times {\Bbb N}\mapsto \phi(\phi(m,n),p) \in {\Bbb N} $$ is a bijection etc...

Update: Some hints for the bijection:

1) Injectivity: Show that if $(m,n) \neq (m',n') \in {\Bbb N} \times {\Bbb N}$ then $$m + \sum_{k=1}^{m+n} k \neq m' + \sum_{k=1}^{m'+n'} k$$ (distinguish the cases when $m+n=m'+n'$ and $m+n \neq m'+n'$)

2) Surjectivity: We have $\phi(0,0)=0$. Suppose $\phi(m,n)=j$. Then if $n>0$ note that $\phi(m+1,n-1)=j+1$, while if $n=0$ then $\phi(0,m+1)=j+1$. Conclude using induction ...

Answer 2

For countable $A_1,...,A_m$ form their cartesian product $A_1 \times ... \times A_m=\{(a_1,...,a_m) ; a_1 \in A_1,...,a_m \in A_m\}$.

This cartesian product can be written as $\bigcup_{j_1=1}^{w_1}... \bigcup_{j_m=1}^{w_m} \{(a_{j_1 1}...a_{j_m m} )\}$ where $w_k$ is either finite or equal to $\infty$ for $k=1,...,m$.

Since we have finite number of unions and every of them is at most countable then cartesian product is also countable.