An improved diagonalizer for Cantor’s
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 the following sequence of numbers:
With such a sequence of numbers, I have observed that even medium-to-strong students oftentimes have trouble understanding why the diagonalizer ensures that it constructs a real number different from any other one in the list.. So let's try to improve our example. Here's a nice trick: Write down only the diagonal portion of the listing of reals:
r1=0.2xxxxxx…
r2=0.x4xxxx…
r3=0.xx2xxx…
r4=0.xxx9xx…
r5=0.xxxx0x…
r6=0.xxxxx8…
⋮⋮⋮⋮
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 r′ (r "prime") only because I would like to use r later.
r′=0.353019…
And now we will go replace all of those x's with the same-index digits of the number itself. For example, we will replace the 2nd, 3rd, 4th, 5th and 6th digit of r1 with 5, 3, 0, 1 and 9 respectively. We will also replace the 1st, 3rd, 4th, 5th and 6th digits of r2 with the relevant digits of r′, and so on and so forth:
r1=0.253019…
r2=0.343019…
r3=0.352019…
r4=0.353919…
r5=0.353009…
r6=0.353018…
⋮⋮⋮⋮
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 r′, they fail in at least one decimal digit. In fact, with this visualization of the first 6 decimal digits for every real rj, there is a difference of exactly one decimal digit. We have essentially pushed the argument to its limits: even if we had a real rk whose 1st, 2nd, 3rd, .... (k−1)th, (k+1)th, (k+2)th, .... digits are the same, rkk is guaranteed, by construction of r′, to be different from ak.
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 r in [0, 1], there is some positive integer j such that r=rj.
The way I like to proceed from that point onward is the following: Since there is some positive integer j such that every single r∈[0,1] can be written as rj, then this is also the case for our constructed real number r′ since, clearly, by the way that I have constructed r′, it is a number between 0 and 1!
Maybe this j is equal to 1. 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 j, r≠rj.
Maybe j=2. The first digit is ok, it is 3 in both r2 and r′, But the second digit gives us a difference, despite the fact that all other digits are the same!
Maybe j=3, and so on and so forth.
