Stop proving uncountability by contradiction, please

 If you've seen any amount of pop-math content, you've probably seen a theorem along the lines of the following:

Theorem (Cantor): There are just as many natural numbers as integers and as rational numbers, but there are more real numbers.

 

I don't have a problem with the above result, since it is true. However, I have a bone to pick with the way the proof is often represented in pop-math videos.

For the first part (that the cardinalities of N, Z and Q are all equal), the way it is usually represented is good. For the integers there is the reasonably easy bijection: 0, 1, -1, 2, -2, 3, ... which can in fact be given by the explicit formula

where ⌈x⌉ means "round x up to the nearest integer". For the rational numbers there are a few ways, the most common one using the zig-zag method. Sure, there are more elegant methods that give an immediate bijection and don't require skipping numbers that already appeared in the list. However, for the purpose of introducing Cantor's results to a wider audience, I think it's fine.

Where I think most pop-math covering of this result fail, is in proving the second part: the uncountability of R. Let's run through the standard way this argument is given. 

The Wrong Way

proof: Suppose there was a list containing all real numbers, say

    1) 0.14159265...

    2) 0.71828182...

    3) 0.33333333...

    4) 0.57721566...

    5) 0.12345678...

    6) 0.33000300...

    7) 0.12312133...

    ⋮ 

We now define a number, call it c, as follows. If the first digit of the first number is a 3, the first digit of c will be 4, else it will be 3. If the second digit of the second number is 3, the second digit of c will be 4, else it will be 3, and so on. For the above list we get c = 0.3343344...

Now c cannot be on the list, since it differs from the first number in the first digit, from the second number in the second digit, and so on. This is a contradiction, since we assumed that the list was complete. Therefore, no complete list of real numbers can exist. □

The Right Way

Looking at the above argument you might realise something: nowhere do we actually need the assumption that the list is complete. The contradiction is completely superfluous. After, we can just prove the result as follows.

proof: Take a list of real numbers, say

    1) 0.14159265...

    2) 0.71828182...

    2) 0.33333333...

    4) 0.57721566...

    5) 0.12345678...

    6) 0.33000300...

    7) 0.12312133...

    ⋮ 

We now define a number, call it c, as follows. If the first digit of the first number is a 3, the first digit of c will be 4, else it will be 3. If the second digit of the second number is 3, the second digit of c will be 4, else it will be 3, and so on. For the above list we get c = 0.3343344...

Now c cannot be on the list, since it differs from the first number in the first digit, from the second number in the second digit, and so on. Since we made no assumptions about the list, any list of real numbers will be incomplete. □

Contradictions are confusing

I think it is clear that the second argument is more elegant than the first. It gets rid of that redundant contradiction after all. This is, however, not the reason I prefer the second argument. Superfluous steps can be useful in trying to explain a proof, especially to a lay audience.

I also don't prefer the second argument for constructivist-reasons. First of, I'm not a constructivist.  Secondly, the first argument is actually constructively valid. I should probably make a post on "proofs by contradiction" vs. "proof by negation" to explain this.

The main reason I feel the first argument is bad, is because it's confusing. Take a look at the comment sections of some popular videos on this subject. Undoubtedly, you'll see people being confused at how c isn't on the list, since it is supposed to be complete. The contradiction makes the argument more confusing, rather than less. With something as unintuitive as different sizes of infinity, this really is a problem.

So please, if you wan't to explain Cantor's different sizes of infinity, use the second argument and not the first. Science communication is hard, math communication is harder and the confusion sown by unneccesary contradictions makes it harder still.

Brief epilogue

I should mention that I do think people should learn about proofs by contradiction. However, Cantor's infinities are not the right subject for that. His work is already unintuitive enough, as a lot of people view infinity as something unknowable or mystical. The proof that √2 is irrational is much better suited for this purpose.

Also, the above argument (as in, before the epilogue) holds for proofs of infinitude of the primes as well. No contradiction is needed for that proof either.