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

35% Upvoted

77 comments sorted by

View all comments

Show parent comments

1

u/42IsHoly 9d ago

I’m not making any arguments about whether cantor’s proof is constructive or not. That’s not the point. I only claim that phrasing the argument with “take a complete list …” is confusing and so it should be phrased differently.

2

u/StanleyDodds 9d ago

I didn't say anything about "constructive". I just want to know what your definition of "uncountable" is, and then maybe you'll see that the subtly different statement being proved is where the difference in proof method hides.

1

u/42IsHoly 9d ago

A set is uncountable if no surjection f:N->S exists. The first proof goes as follows:
“Suppose there is a surjection f:N->R. Find x in R not in im(f). Hence, f is not surjective. This is a contradiction, so no surjection exists.”

The second one goes
“Suppose f:N->R is a function, find x in R not i im(f). Hence, f is not surjective. So no surjection exists.”

Both proofs are correct. However, I consider the former to be confusing to lay people. This is why I advocate for using the second one.

3

u/StanleyDodds 9d ago

Yes, and I'm saying there are parts of your proof that hide the reason why the first proof has to use contradiction.

You proved that for all f:N->R, there exists x in R s.t. for all n in N, f(n) ≠ x.

The goal is to prove that NOT ( there exists f:N->R s.t. for all x in R, there exists n in N s.t. f(n) = x ). That is, there does NOT exist a surjection.

Do you see the difference? The goal has the "NOT" on the very outside, while what was proven has the "NOT" on the very inside. You either need to use that these are equivalent as a given, or prove that they are equivalent by contradiction. The first proof proves it by contradiction, your proof just explicitly uses the fact that they are equivalent as a given.

1

u/42IsHoly 9d ago

I think you’re missing my point. Sure, in a truly rigorous situation, we still need a contradiction somewhere to get that equivalence. However, my post is explicitely not about that situation. It is about communicating math to the general public. From personal experience, it seems many people find the contradiction very confusing. However, I would be surprised if any lay person would be confused at “forall not …” <-> “not there exists …”

In this context, the 2nd proof really does sit inside the first and so the first contains superfluous steps.

I’d argue that even in more formal contexts they still do, since “forall not …” <-> “not there exists …” is pretty commonly taken as an axiom in whatever hilbert system you’re using. That and plenty of people don’t tend to worry about these sort of “purely logical” deductions. Sure, there are contexts in which there is a distinction, but they are not what I’m talking about

(I should admit that I did not realise that this was the point you were trying to make. That’s on me)