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.

  • $\begingroup$ Take the elements from the $A_i$ in a round-robin fashion, taking one more set at every round. $\endgroup$ – Yves Daoust Nov 12 '14 at 18:37
  • $\begingroup$ Yeah, students never seem to believe the round robin proof so that is why I thought of this. $\endgroup$ – 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$$

  • $\begingroup$ This is the round-robin stuff. $\endgroup$ – Yves Daoust Nov 12 '14 at 19:01
  • $\begingroup$ @YvesDaoust Didn't know it by that name, but it makes sense. $\endgroup$ – AlexR Nov 12 '14 at 19:13
  • $\begingroup$ This relates to a previous comment of mine; diagonalization is the common expression. $\endgroup$ – Yves Daoust Nov 12 '14 at 20:59
  • $\begingroup$ @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 ^^ $\endgroup$ – AlexR Nov 12 '14 at 21:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.