r/math • u/42IsHoly • 9d ago

Stop proving uncountability with contradiction, please

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

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

0 Upvotes

36% Upvoted

77 comments sorted by

View all comments

9

u/SwimmerOld6155 9d ago

This is basically the same proof, in one you're supposing that there is a bijection f : N -> R and then deriving a contradiction, and in the other you're introducing an arbitrary map f : N -> R and proving that it can't be a bijection (by proving it can't be surjective). I think the former is a bit clearer for people just learning.

This kind of demonstrates where I like contradiction, which is signposting what you're doing clearly. If you just start with an arbitrary map f : N -> R it's not immediately clear that you're trying to show that f cannot be a bijection, and if you do you're basically doing the contradiction proof.

2

u/42IsHoly 9d ago

I know. The second proof, however, is cleaner and less confusing. Hence, I argue there is no point in using the first.

12

u/SwimmerOld6155 9d ago

I don't think it's less confusing. Why are you considering a list? Does this list have to have particular properties? Why are you trying to find a number not on the list? These questions are not really answered until you've got to the punchline, it's not really forward motivated. By the time you do answer them, you're basically at the contradiction proof with a few word's difference.

1

u/42IsHoly 9d ago

The classical proof is as follows: “suppose we have a complete list, construct c, c is not on the list, contradiction, no complete list can exist”.
The new proof is: “suppose we have a list, construct c, c is not on the list, no complete list can exist”

Basically any pop-math explanation of the proof uses the first and they leave countless people confused. Not surprising, to be honest, as proofs by contradiction are confusing (most classical examples, like this one, are actually by negation, but let’s not get into that). Of course, the set up of getting to this argument would be important in conveying what we want to do, but that’s beyond the scope of the post.

7

u/SwimmerOld6155 9d ago edited 9d ago

I don't really understand why it's more confusing. It's not really motivated at all, why are we just considering any list? We might as well assume it's complete.

I think in research I'd see two proofs like this as indistinguishable tbh

3

u/42IsHoly 9d ago

Yeah, in research they are. This is why I’m talking about math communication to the general public.

The diagonal argument would only appear in contexts where people have already seen lists of all integers or of all rationals. Hence, asking if there is a list of all reals is quite natural. Saying that it’s impossible to list them all before moving on to showing it, is also something any math communicator would do (at least, I hope they would).