I’ve been teaching CMSC250: Discrete Structures in CS UMD for a while now. Essentially a more CS-friendly version of Discete Mathematics, with more logic, set theory, structural induction, countability. Countability, a rather esoteric subject, is challenging for our students. Naturally, a student that doesn’t get countability because they don’t get bijections cannot be helped until they understand bijections, but when it comes to the Cantorian diagonalizing proof that the reals are uncountable (to be precise, that the interval [0, 1]) is uncountable), one can lose many more students.
I conjecture that one possible reason for this is that the sequence of numbers that is used to create the 2D matrix is usually a bit arbitrary in both texts and slides. For example, in my own slides, I have this following sequence of numbers:
With such a sequence of numbers, I have observed that even medium-to-strong students oftentimes have trouble. So let’s try to improve our example. Here’s a nice trick: Write down only the diagonal portion of the listing of reals:
Since the diagonal values are the only ones that you need to construct the number of interest, go ahead and construct it. I call it ( “prime”) only because I would like to use later.
And now we will go replace all of those ‘s with the same-index digits of the number itself. For example, we will replace the 2nd, 3rd, 4th, 5th and 6th digit of with 5, 3, 0, 1 and 9 respectively. We will also replace the 1st, 3rd, 4th, 5th and 6th digits of with the relevant digits of , and so on and so forth:
The benefit of carefully constructing the number sequence in this way is that now the student can see that those numbers, no matter how hard they try to look like our own constructed number , they fail in at least one decimal digit. In fact, with this visualization of the first 6 decimal digits for every real , there is a difference of exactly one decimal digit. We have essentially pushed the argument to its limits: even if we had a real whose 1st, 2nd, 3rd, …. (k-1)th, (k+1)th, (k+2)th, …. digits are the same, is guaranteed, by construction of , to be different from .
The final piece of the argument can perhaps be shown as follows: The statement “[0, 1] is countable”, can be re-worded as: “For every real in [0, 1], there is some positive integer such that .
The way I like to proceed from that point onward is the following: Since there is some positive integer such that every single can be written as , then this is also the case for our constructed real number since, clearly, by the way that I have constructed , it is a number between 0 and 1!
Maybe this is equal to . But this can’t be, since we notice that the numbers differ in the first decimal digit, again by construction. And this is where the construction comes to help: all the other (visible) digits are the same. However, it suffices for there to be a difference in a single digit in order for us to say that, for a given .
Maybe . The first digit is ok, it is 3 in both and , But the second digit gives us a difference, despite the fact that all other digits are the same!
Maybe , and so on and so forth.
So the point is that this enumeration actually provides a Discrete Mathematics student with more intuition about why the proof works.