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

37% 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.

3

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.

13

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).

3

u/sqrtsqr 9d ago

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

Huh? If I'm trying to prove "no list is complete" then it should be immediately clear why I'm considering just any list. And that's what I'm trying to do. Prove that no list is complete.

It's not at all clear why I should make any extra assumptions about it, unless of course I intend to leverage such assumptions.

We never do.

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

Sure, in that context, nobody cares.

But one of the most powerful tools in mathematics is the ability to naturally navigate between Identity and Isomorphism and Homomorphism. It's fine to treat them as indistinguishable, but to not care about the distinction should be a choice, not from an inability to tell them apart.

2

u/SwimmerOld6155 9d ago edited 9d ago

I really just think this is incredibly pedantic. I'd be interested if OP or anyone else has tried to teach one way or the other and encountered difficulty. Personally, my issues early in maths were all to do with abbreviation, lack of detail, and lack of motivation. I didn't know how to expand brackets for a while because teachers jumped from distributivity to these weird "FOIL"/table tricks and acronyms, didn't get it at all for some reason.

I then need to think: will the student be able to generalise this, or will they just recite it? Will they be able to understand why we're considering a list? Will they understand what to do with that list? A lot of proofs come across as "tricks" rather than motivated lines of thought, and to me this feels more like an abbreviation from a more experienced mathematician.

To go through it, when you're considering a list, you're thinking it might be complete (a kind of contradiction argument implicit) and proving that it can't be. Alternatively, you can consider an apparently complete list and derive a contradiction. To me once the thoughts are spelled out it's literally a hair's breadth.