5
$\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$
10
  • 1
    $\begingroup$ I'm asking whether this is correct, not an alternative method $\endgroup$
    – user370967
    Jul 13, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 22:21

2 Answers 2

Reset to default
4
+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$
5
  • $\begingroup$ If you can elaborate why this graphical method is rigirous, I will award you the bounty. $\endgroup$
    – user370967
    Sep 22, 2017 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, 2017 at 15:53
  • $\begingroup$ What would the formula for the inverse map look like? Does it exist in "closed form"? I'm struggling to see how, given a natural number $l$, I can achieve the $l = m + \sum_{k=1}^{m+n} k$ decomposition (and further, that this decomposition is unique), so that I can obtain $(m,n)$ given $l$. Would it be possible to comment on that? $\endgroup$
    – EE18
    Sep 20 at 19:50
  • $\begingroup$ @EE18 Well, if you call $N=n+m$ then you want to solve $\ell = \phi(m,n)=m+N(N+1)/2$ with $N$ being an integer and $0\leq m\leq N$. Then $N$ is the largest integer for which $N(N+1)/2\leq \ell$ which leads to the closed formulae $N=\lfloor \sqrt{2\ell+1/4} -1/2 \rfloor$, $m=\ell-N(N+1)/2$ and $n=N-m$ but this probably doesn't help on anyone's intuition. But you may in fact program it and see it works (I just did so). To gain intuition I think it is better simply to calculate $\phi(m,n)$ for small values of $m,n$ and plot the values in a coordinate system. Then the zig-zag curve appears. $\endgroup$
    – H. H. Rugh
    Sep 21 at 20:49
  • $\begingroup$ Thank you for this nice answer Prof. Rugh. My number theory is rather weak, so I didn't follow some of the inferences you made on the way through, but your point at the end re: what actually helps intuition is well taken. Thanks again! $\endgroup$
    – EE18
    Sep 21 at 20:53
0
$\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$
6
  • $\begingroup$ Your proof is what I made rigorous with the induction argument, it seems. $\endgroup$
    – user370967
    Sep 21, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 18:53

You must log in to answer this question.