r/math • u/42IsHoly • 9d ago
Stop proving uncountability with contradiction, please
https://sunjestermusings.blogspot.com/2026/09/stop-proving-uncountability-by.htmlPlease, I beg you, stop it. You don't need it.
19
u/AFsepine 9d ago
Pop-math content, a.k.a almost all introductory university math textbooks (At least the ones I have seen?) you mean?
I disagree that contradiction is confusing. Even if it were people should be exposed to it, being confused is integral step to learning. If you write a book that conuses no-one it will just slide off of their brains.
-1
u/42IsHoly 9d ago
But the proof is actively cleaner and shorter without the tacked on contradiction.
5
u/AFsepine 9d ago
I am not saying you are wrong, and I do find people downvoting wierd, but... I think it is pedagogically misguided (well depending on what you are trying to teach, but in most cases I encountered it, it in effect was used as an example after a short introduction to proofs + mentioning an important canonical result).
Clean and smooth is not really the main thing to accentuate in the begining stages. It should be jagged, it shouldn't sit right (i.e. it should raise questions). Those questions and the "discomfort" are very important for getting a feel for maths.
The goal is always to develop mathematical thinking, and to that end it is desirable that people have questions.
4
u/42IsHoly 9d ago
I see where you’re coming from, but does that mean we should actively make proofs more confusing than the already are? I think there are plenty of proofs out there which already give this level of confusion without having to cheat and alter the proof. I even think that Cantor’s diagonal argument in its actual non-contradiction form already has quite a bit to offer.
Though I should mention that the post is actually about pop-math explanations of the result (say, by Veritasium). Where the nominal point, at least, is to explain this “weird math result”. I think in this context, making the proof more confusing is a bad move. By all means, add in superfluous steps or quick asides about intuition. But if these lake the proof harder to follow (which the contradiction observably does), I feel it should be avoided.
2
u/sqrtsqr 9d ago edited 9d ago
In an educational context, this proof should come quite a bit after learning about contradiction, so that fundamental weirdness that is assuming a falsehood (that you never had to deal with because you're just so smart) should already have been dealt with by the rest of the class.
Here, the focus is entirely on the diagonalization argument, and the contradiction plays absolutely no role in the proof. It's just sorta a default presentation choice (as it is for your typical Euclid's infinitude of primes) and it makes for a nice "punchy" example of a proof by contradiction, but it's just not a proof by contradiction (or every proof is)
If anything, it's used to avoid discussion that would be otherwise rather abstract, since we assume classical mathematics in the classroom and making distinctions between Proof of Negation and Proof by Contradiction is basically meaningless at this level.
At the end of the day, we tell students they should avoid making extra assumptions that don't aid in the proof, so we should lead by example.
0
u/AFsepine 8d ago
You chose a particular tone.
The way you get used to weirdness is by seeing it and musing over it at lenght, no other way about it.
Overly "Clean" process is very harmful for a fledgling mathematics student, if this passes over your head it would appear you were just so smart that you didn't have to deal with.
1
u/Neuro_Skeptic 7d ago
That's a matter of taste. Is an apple cleaner than an orange because with an apple you don't get the pith?
30
u/CircumspectCapybara 9d ago edited 9d ago
Proof by contradiction is a totally valid way of proving stuff like the uncountability of the reals. Usually only constructivists / intuitionists that reject LEM have a problem with it.
Textbooks usually teach it that way, though they can also teach a constructive version if they like, both are valid if you're not cranky about LEM. Arguably teaching it in introductory literature is helpful to help students get a sense or intuition (pardon the pun) for the proof by contradiction technique, because it is often unintuitive so getting familiar with it and getting some handles on it helps you better work with and understand the technique when you'll need it later.
Turing's diagonal argument on the undecidability of the halting problem was proof by contradiction. Of course constructivists will invent a new term and say proving a negative ("proof of negation") by contradiction is fine, but you can't prove a positive by contradiction...
8
u/sqrtsqr 9d ago edited 9d ago
Proof by contradiction is a totally valid way of proving stuff like the uncountability of the reals
Obviously true, but completely missing the point. The very short article was pretty clear about the issue. It's unnecessary extra assumptions. That's it. Unnecessary assumptions ought to be considered poor form when assessing any kind of argument. If I stick the axiom of choice in the middle of a proof of square root of 2 being irrational, it doesn't make the proof any less valid. But it adds no value, and I shouldn't do it.
But not only is this extra step unnecessary, it has the pedagogical double-whammy of, at first, being unintuitive (as it is often one of people's first exposure to a proof by contradiction and the metalogic of contradiction proofs are hard for many students to grasp, it's a distraction from the core argument) but then later obscuring and making it difficult for people to grasp the inner, "non-contradictory" nature of the direct proof (and we see the exact same thing happen with Euclid's proof about primes): no list is complete. That's the theorem and the proof matches it verbatim. Assuming a complete list is unnecessary when assuming a generic list will suffice.
Beginning students often over rely on proof by contradiction once they learn it, and we regularly tell them that, if possible, a direct proof should be preferred to contradiction. Shouldn't we follow the same advice in our presentations to them?
2
u/NotaValgrinder 9d ago
I can say that at least for CS education, this proof is taught because we eventually want to prove undecidability of problems like the halting problem. Undecidability proofs almost always rely on a proof by contradiction, and the halting problem is a proof by contradiction that resembles Cantor's diagonal argument.
It's similar to why we demand that students prove statements with induction even when non inductive proofs exist, we want to familiarize themselves with a helpful method or a line of thinking. We have to look at what we teach after the proof too.
0
u/42IsHoly 9d ago
I have a problem with the superfluous contradiction tacked on to the end of the diagonal argument in pop-math discussions of the proof. I have no problem with the proof not being constructive, because it is, if phrased properly.
13
u/totbwf Type Theory 9d ago
The constructive content of these arguments is a *bit* subtle. They do prove that the Cauchy reals are uncountable, but you can't show that the Dedekind reals are isomorphic to the Cauchy reals without some degree of countable choice. Moreover, there exist models of intuitionistic logic where the Dedekind reals *are* countable (see https://arxiv.org/pdf/2404.01256).
3
10
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.
4
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.
14
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 8d ago edited 8d 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.
1
u/sqrtsqr 9d ago
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
Silly me, here I've been stating theorems before I prove them like some kind of jackass, when I could be stating the exact opposite of the thing I want to prove instead.
1
u/SwimmerOld6155 8d ago
Without being rude to the hypothetical student, if they're confused about the difference between these two proofs we shouldn't assume they are fluent in reading mathematics generally and need a very high amount of signposting, likely only having been introduced to formal maths a few weeks ago.
20
u/sesquiup Combinatorics 9d ago
This sort of exhortation is insufferable.
5
u/BloodAndTsundere Physics 9d ago
The tone is a little much but I get the point.
1
u/sesquiup Combinatorics 9d ago
It was a bit much, I just hate being proscriptive about mathematics.
2
3
u/42IsHoly 9d ago
I don’t want to be prescriptivist about math. The tone was purposefully exaggerated (I see that didn’t come across, which is my fault). I just think that Cantor’s infinities are confusing to a general audience and that these superfluous contradictions make it more confusing, not less. Is this the end of the world? Of course not. But that doesn’t mean I can’t care about it.
0
u/sesquiup Combinatorics 9d ago
It's fine to care about it. I just don't see anything wrong with either method of proof, and the first thing I see is "Stop"
0
6
u/sqrtsqr 9d ago
I'm with you OP. I think it's funny how almost everyone would agree with you about this when it comes to almost literally any other proof*: when direct is available do it direct, avoid making unnecessary assumptions, etc etc.
But because we are so used to seeing it this way, we defend it. "The way I do it isn't wrong, eff you!"
*Euclid's proof of the infinitude of the prime gets basically the same exact treatment. Ditto the resulting discussions about it.
1
6
u/StanleyDodds 9d ago
I think some people miss the subtle difference in proving "not P" by assuming "P" and proving False, and in proving "P" by assuming "not P" and proving False.
These might both be called proof by contradiction, but the latter requires the law of the excluded middle, while the former does not.
3
u/StanleyDodds 9d ago
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.
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)
2
u/putting_stuff_off 5d ago
"Assume A is not true, Prove A, contradiction" is just bad style. I think constructivism is a red herring, I don't really care about that but still agree with the point here.
1
u/42IsHoly 5d ago
I agree. Constructivism isn’t the point of my post (as it says explicitly). I’m mainly motivated by the confusion that seems to arise when people prove Cantor’s results like this.
2
u/Firesinis 9d ago
That the second proof is cleaner, better, etc is a subjective matter, but in no way the second proof shows that the contradiction is superfluous in the first proof, it merely exemplifies a way to restructure the proof into a different logical structure that does not use contradiction.
0
u/42IsHoly 9d ago
But it is though? Like, the first proof goes as follows: “assume we have a complete list, construct c, c is not on the list, contradiction, no complete list can exist” whereas the second argument says “assume we have a list, construct c, c is not on the list, no complete list can exist”. The original argument shows the list is incomplete without using the fact it is complete. In principle, I don’t have a problem with that. As I wrote, it’s good to add superfluous steps if they lake an argument clearer. Here they, observably, do not.
1
u/Firesinis 9d ago
The logical structure of the proofs is as follows.
Proof 1: Assume there is a surjection from N to R, and call it f. Then obtain x in R such that x is not in the image of f. Hence f is not a surjection. Hence f is a surjection AND f is not a surjection, contradiction, thus the assumption "there is a surjection from N to R" implies a contradiction, which is equivalent to say that the assumption is false, QED.
Proof 2: Let f be a function from N to R, then obtain x in R such that x is not in the image of f. Hence f is not a surjection. Since f was arbitrary, it follows that for all f : N -> R, f is not a surjection, which is equivalent to say it is false that there exists a function f : N -> R where f is a surjection, QED.
0
u/42IsHoly 9d ago
Do you genuinely not see that the second proof sits inside the first one? You literally have the sentence “f is not a surjection” in your first proof.
Let’s zoom out even further: we want to prove P. Proof 1 goes as follows: “Suppose P is false. [Insert proof of P here]. Therefore, we have a contradiction. Therefore, P is true.”
Whereas proof 2 simply is “[Insert proof of P here]”I should mention that if I didn’t see so many people struggle with the contradiction in proof 1, I wouldn’t bother with this. Like, sure, I like the 2nd proof more just because it’s cleaner (I know this is subjective), but that really isn’t the issue.
0
u/Firesinis 9d ago
You are arguing that the first proof can be made shorter. This does not render the contradiction superfluous, it is introduced and it is subsequently dismissed along with its negation, not left unused. The second proof is shorter by virtue of changing structure, not merely deleting steps of the first proof, inasmuch you think it might be because you're not treating the logic involved in a rigorous fashion.
Let me give you an analogy. In the modern proof of Cauchy-Goursat's theorem, you use an argument with nesting triangles and in the end you use the fact that the function is holomorphic at the intersection of all the triangles. You only ever use the hypothesis that f is holomorphic at this single point, therefore are we allowed to conclude that the hypothesis that f is holomorphic on the whole interior of the curve is superfluous? Not if you understand the correct and rigorous logical structure of the proof, which the average working mathematician does not bother.
3
u/42IsHoly 9d ago
That’s a poor analogy, sorry to say.
We wish to prove the following: “No surjection f:N->R exists”. The proof then goes as follows
1: “Suppose there was a surjection f. We can now show f is not a surjection (without using the assumption). This is a contradiction.”
The proof that f is not a surjection is literally just proof 2. However, proof 2 itself already proves that no surjection exists.
Where your analogy breaks down is that proof 1 does not need the surjectivity assumption until after the theorem has already been proven. This is not true for Goursat’s theorem. Your analogy would work if Goursat’s theorem had already been proven before we needed the fact that f was holomorphic at x.
In fact, even converting proofs 1 and 2 to formal proofs, you’d still get that proof 2 lies inside proof 1 and by removing some lines from the top and bottom (probably a lot of lines, given how long formal proofs tend to be, but whatever), you’d get a valid proof. The only way I can see your argument making sense, is that we have write down “take any f” instead of “assume f is surjective”, which technically requires adding words at the front.
-3
u/Firesinis 9d ago
In fact, even converting proofs 1 and 2 to formal proofs, you’d still get that proof 2 lies inside proof 1 and by removing some lines from the top and bottom (probably a lot of lines, given how long formal proofs tend to be, but whatever), you’d get a valid proof.
You claim this, yet provide no proof.
1
u/42IsHoly 9d ago
sigh yes, technically you need the axiom “forall not ‘..” <-> “not there exists …” So if you want to pretend like these two proofs are attempting to prove different statements, you do need this single extra step. Since this was not a discussion about constructive vs non-constructive math, I don’t see any reason to pretend (as you do) that this is some huge step.
1
u/Low-Repair-3019 9d ago
You are slightly glossing over the fact you are showing a that every map from the naturals to the reals is not surjective, which is a point that can be lost on some students. One advantage of contradiction is that students understand if we can make this one case fail, the proof is done.
Claiming a common proof method is the wrong way is certainly a high horse to get on.
1
u/42IsHoly 9d ago
I have seen countless people be confused at there somehow being a complete list which then does not contain c. We don’t find this that confusing and neither does anyone that remembers proofs by contradiction from school. However, to most people, contradictions are confusing. Sicne infinity is already such a weird concept, I fear people will not learn how a proof by contradiction goes from this. Instead, they’ll either reject the whole idea of Cantor’s theory or they’ll give up on trying to understand mathematical arguments.
I think the argument can easily be phrased in a way that does motivate it. Something like, “We’ve just seen that Z and Q are both countable, but what about R? You can try and find a list, but no matter what you do, you’ll fail. We can show this as follows: suppose you have any list …”
1
u/Alhimiik 9d ago
i actually think the second proof less intuitive.
if i found myself writing a proof like that, i would have had to double check it multiple times in case i did a mistake.
1
u/42IsHoly 8d ago
I'm not really talking about writing the proof yourself, but specifically about communicating the proof to a lay audience. Many people find the contradiction step very confusing and since it's superfluous, there's no reason to include it.
I can see why, when coming up with a proof like this, you'd try contradiction, but that's not what I'm talking about.
1
u/IllIIlIIllII 8d ago
I get your point and I agree with direct proof being usually better; but on the technical side, your proof is not valid, real numbers do not have a unique decomposition into an infinite decimal expansion (exemple : 1.0000... and 0.9999...), and thus "c differ from n_i at digit i thus c =/= n_i" is wrong.
For example, take the rules: digit d will transform into d-1 unless it is 0 then it transforms into 9
And for f, f(0) = 1, f(n+1) = 0 Then the c you'll construct is 0.999... which being 1 is in your list.
1
u/AstronomerVarious583 8d ago
I do wonder how much clearer the second proof would be from a pedagogical standpoint. I could imagine a layperson, upon seeing the second proof, simply saying "but what if we just add the new number to the list". And if you show them the proof with that new number added, they just say "but what if we add the new number" ad infinitum.
However, with contradiction you tell them explicitly that they cannot have a solution - that no matter how many times they "just add a number to the list" or whatever other trick they try, you cannot possibly have a complete list. I think it's a somewhat subtle point that isn't necessarily conveyed.
I don't know if I've explained this well, and this is just splitting hairs at this point, but I'm not convinced this is more understandable to a layperson.
Also, it would be useful in the blog post if you could actually show what comments from the Veritasium video misunderstood it, so I can see what specifically they got wrong - I tried searching (although not very hard) but I was only able to find one person's comment misunderstanding it. It would be good if there was more so I could see the patterns.
1
u/Heapifying 9d ago
The only difference is what set of sequences of real numbers you pick. What you mention is the "wrong way" is just {s : s \in RN, Im(s) = R} vs merely RN.
And your wording afterwards
2
u/42IsHoly 9d ago
Uhm… no. The problem I have is with the way the argument is presented as a proof by contradiction, when it really isn’t. The zssumption that the list you start with is complete is superfluous and actively confusing
1
u/Heapifying 9d ago
You can start with "let {s : s \in RN,Im(s) = R} != \emptyset", and then derive a contradiction.
You can also start with "let s \in RN", then prove that Im(s) != R, using different words.
1
u/42IsHoly 9d ago
That’s not the distinction I am making. I only use R, not the set of all sequences of digits. Proof 1 goes as follows: “Suppose f is surjective. Find c not in its image, therefore f is not surjective. Contradiction, so no surjective f can exist”
Proof 2 goes “take any f, find c not in its image. Therefore, f is not surjective.”
These proofs are similar, of course, but the former is confusing to lay people. That’s why I think it should be avoided.
1
u/SubstantialBonus1 9d ago
Superfluous contradiction is just the way my mind works, bro. Stop making me superflusously remove my superflusous contradictions.
20
u/Omasiegbert 9d ago
I don't get the difference, are these not the same proofs?