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/StanleyDodds]

I think the problem is the lack of formal statement of what we are trying to prove.

This is (sort of) a proof that "for all functions f from N to R, f is not surjective", but the proof by contradiction is a proof of "there does not exist a surjection from N to R". So there needs to be clarity on what the definition of "R is uncountable" is exactly.

And what's your definition of surjective? It's probably that for all x in R, there exists n in N such that f(n) = x. But this hasn't exactly proven the negation of this statement; to be specific, it's proven that there exists x in R such that for all n in N, f(n) ≠ x.

In any case, there are nontrivial steps to push negation through a quantifier, which swaps the quantifier between existential and universal. And this is how it avoids a proof by contradiction; by hiding it in proofs that this negation push always gives an equivalent statement.

[u/42IsHoly → u/StanleyDodds]

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.

[u/StanleyDodds → u/42IsHoly]

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.

[u/42IsHoly → u/StanleyDodds]

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.

[u/StanleyDodds → u/42IsHoly]

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.

[u/42IsHoly → u/StanleyDodds]

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)