1
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ I'm asking whether this is correct, not an alternative method $\endgroup$ – user370967 Jul 13 '17 at 20:09
  • $\begingroup$ Yes it is correct. But do you know the proof that countable Union of countable sets is countable? $\endgroup$ – user251257 Jul 13 '17 at 20:11
  • $\begingroup$ Yes, and that one uses the diagonal argument (I'm working through Rudin's book, where it is proven). I find the diagonal argument somewhat unrigorous, that's why I want to avoid it as much as possible. $\endgroup$ – user370967 Jul 13 '17 at 21:16
  • $\begingroup$ you avoid a particular technique, but use a result proven by that technique... btw. that result need countable choice, which is stronger than what you want to prove. $\endgroup$ – user251257 Jul 13 '17 at 21:36
  • $\begingroup$ @user251257 Isn't the 'diagonal argument' the technique Cantor used to prove the un-countability of sets? I am familiar with the 'zig-zag' method to enumerate all elements of an infinite 2D array ... is that what you mean? If so, I have never seen that referred to as the 'diagonal argument' ... or did I miss something? IT should have a name though .... $\endgroup$ – Bram28 Jul 13 '17 at 22:21
2
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If you can elaborate why this graphical method is rigirous, I will award you the bounty. $\endgroup$ – user370967 Sep 22 '17 at 15:05
  • 1
    $\begingroup$ You (just) need to show that $\phi$ is a bijection. You may do that by induction. That is the proof. The zig-zag path is just an interpretation: Try to write down at each couple $(m,n) \in {\Bbb N}^2$ the value of $\phi(m,n)$. Connecting them in increasing order yields the path. $\endgroup$ – H. H. Rugh Sep 22 '17 at 15:53
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your proof is what I made rigorous with the induction argument, it seems. $\endgroup$ – user370967 Sep 21 '17 at 18:30
  • $\begingroup$ @Math_QED But I do not use induction as you see and this proof looks simple. You wanted some other proofs, right? $\endgroup$ – user480281 Sep 21 '17 at 18:35
  • $\begingroup$ Yes, but this is essentially the same proof, just not with induction. Thanks for the answer though (+1) $\endgroup$ – user370967 Sep 21 '17 at 18:36
  • $\begingroup$ @Math_QED For me, it is not essentially the same, whether there is induction or there is no induction is logically very different matter. $\endgroup$ – user480281 Sep 21 '17 at 18:39
  • $\begingroup$ I can argue that the use of $...$ is not rigorous. To make it rigorous, you would have to use an induction argument anyway. $\endgroup$ – user370967 Sep 21 '17 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy