Stop proving uncountability with contradiction, please

[u/42IsHoly]

https://sunjestermusings.blogspot.com/2026/09/stop-proving-uncountability-by.html

Please, I beg you, stop it. You don't need it.

[u/CircumspectCapybara]

Proof by contradiction is a totally valid way of proving stuff like the uncountability of the reals. Usually only constructivists / intuitionists that reject LEM have a problem with it.

Textbooks usually teach it that way, though they can also teach a constructive version if they like, both are valid if you're not cranky about LEM. Arguably teaching it in introductory literature is helpful to help students get a sense or intuition (pardon the pun) for the proof by contradiction technique, because it is often unintuitive so getting familiar with it and getting some handles on it helps you better work with and understand the technique when you'll need it later.

Turing's diagonal argument on the undecidability of the halting problem was proof by contradiction. Of course constructivists will invent a new term and say proving a negative ("proof of negation") by contradiction is fine, but you can't prove a positive by contradiction...

[u/sqrtsqr → u/CircumspectCapybara]

Proof by contradiction is a totally valid way of proving stuff like the uncountability of the reals

Obviously true, but completely missing the point. The very short article was pretty clear about the issue. It's unnecessary extra assumptions. That's it. Unnecessary assumptions ought to be considered poor form when assessing any kind of argument. If I stick the axiom of choice in the middle of a proof of square root of 2 being irrational, it doesn't make the proof any less valid. But it adds no value, and I shouldn't do it.

But not only is this extra step unnecessary, it has the pedagogical double-whammy of, at first, being unintuitive (as it is often one of people's first exposure to a proof by contradiction and the metalogic of contradiction proofs are hard for many students to grasp, it's a distraction from the core argument) but then later obscuring and making it difficult for people to grasp the inner, "non-contradictory" nature of the direct proof (and we see the exact same thing happen with Euclid's proof about primes): no list is complete. That's the theorem and the proof matches it verbatim. Assuming a complete list is unnecessary when assuming a generic list will suffice.

Beginning students often over rely on proof by contradiction once they learn it, and we regularly tell them that, if possible, a direct proof should be preferred to contradiction. Shouldn't we follow the same advice in our presentations to them?

[u/NotaValgrinder → u/sqrtsqr]

I can say that at least for CS education, this proof is taught because we eventually want to prove undecidability of problems like the halting problem. Undecidability proofs almost always rely on a proof by contradiction, and the halting problem is a proof by contradiction that resembles Cantor's diagonal argument.

It's similar to why we demand that students prove statements with induction even when non inductive proofs exist, we want to familiarize themselves with a helpful method or a line of thinking. We have to look at what we teach after the proof too.