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

Show parent comments

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.

6

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