# Is my proof that the union of countably many countable sets is countable correct?

In an effort to find a proof that builds intuition for students in my proof writing course, I devised the following. Its seems too easy to me, so I am worried something is wrong. The class is very Naive Naive Set Theory so I realize some axioms are needed but that is way too hard for my students. I guess I would just like to have this result and I used to just state it, but then I thought about this proof.

We assume that $\mathbb{N}\times \mathbb{N}$ is countable.

Suppose $A_1$, $A_2$, $A_3$,... is a sequence of countably infinite pairwise disjoint sets.

Write $A_1=\{a_{11}, a_{12}, a_{13},...\}$, $A_2=\{a_{21}, a_{22}, a_{23},...\}$,...,$A_n=\{a_{n1}, a_{n2}, a_{n3},...\}$.

Let $A=\bigcup_{i\in \mathbb{N}}A_i$. Define $f:A\rightarrow \mathbb{N}\times \mathbb{N}$ by the rule $f(a_{ij})=(i,j)$.

Since the $A_i$'s are disjoint $f$ is a function. 1-1 and onto are easily proved. Thus, $A$ is countable.

If we take off the pairwise dijoint condition then for every $A_i$ and $A_j$ with $A_i\bigcap A_j \neq \emptyset$, replace $A_j$ with $A_j-(A_i\bigcap A_j)$. I guess this is where I think I may be a little to hand wavey.

• Take the elements from the $A_i$ in a round-robin fashion, taking one more set at every round. – Yves Daoust Nov 12 '14 at 18:37
• Yeah, students never seem to believe the round robin proof so that is why I thought of this. – user43666 Nov 12 '14 at 18:57

A proof independent on the fact that $\mathbb N\times\mathbb N$ is countable can be crafted using diagonal counting: Write the $A_j$ in rows to get an infinite table, now label the finite diagonals consisting of $a_{ij}, i+j=m+1$ as $D_m$.
$D_m$ is a finite set of cardinality at most (duplicates are to be ignored) $m$. Now start the enumeration with $a_{11}$, the only element of $D_1$, append the elements of $D_2$ wich are not yet enumerated and continue...
If all elements are unique (i.e. the $A_j$ are disjoint), the enumeration will be defined by the sequence $$a_{11}\ a_{12}\ a_{21}\ a_{13}\ a_{22}\ a_{31}\ a_{14}\ a_{23}\ \ldots$$
• @YvesDaoust I was unsure if this was called diagonal argument because I think that's what is used to show that $\ell^\infty(\mathbb N)$ is uncountable, so I stuck with diagonal enumeration ^^ – AlexR Nov 12 '14 at 21:01