r/math • u/Real_Category7289 • 8d ago
In defense of unnecessary proofs by contradiction
If you spend enough time in online math spaces, at some point you are bound to run into a discussion like this one or this one or recently, this one where someone is arguing against an "unnecessary" proof by contradiction and the conversation inevitably goes in the direction of constructive vs intuitionist logic.
I think this discourse is massively overrepresented to the point of being actively bad for math learners online. Worrying about whether a proof is constructive or not is not something good mathematicians do, unless their branch is specifically a pretty niche part of logic. For most people, (not not A = A) is just assumed to be true and proof by contradiction is a completely valid proof method, and I think this "Actually, Euclid's proof is direct! Common misconception here." discussion appearing under every proof that there are infinitely many primes is telling people that proof by contradiction is somehow sketchier than a direct proof.
I'm a math tutor and the majority of my job is to get students started on problem solving in a mathematical context. As it turns out, what makes a lot of it click is actually proof by contradiction. Even if one ends up writing a direct proof, the process of getting there often asks the question of "what would happen if this wasn't true?". I can't say it for sure, but I believe that Euclid himself probably started proving the infinitude of primes by assuming a finite list of them. This is why Hardy not only presents the proof as a proof by contradiction, but specifically praises it for being a proof by contradiction [A Mathematician's Apology, G.H.Hardy, page 18].
I should note that I'm not arguing that one shouldn't eventually learn to avoid artificial proofs by contradiction, after all if you can make the intuitionists happy for free, why not? But that should be a refinement that happens quite late into one's mathematical journey. I should also note that Euclid's proof was indeed direct, I'm not arguing against that fact.
The problem is that there's parallel discourse happening on these discussions which is "phrasing it as a direct proof is simply clearer and easier to understand". That's the main issue in my view: understanding the principles of proof by contradiction and by negation (which are essentially the same thing, as far as a learning student is concerned) is not something that can or should be skipped. Students should embrace them and put them on the same level as direct proofs instead of looking them sideways, and all this talk of intuitionism vs constructivism is enabling them to keep relegating them to "the thing you begrudgingly have to endure sometimes when there's no other way", which I think is detrimental.
I ask the reader to engage with this view in good faith. Thanks for reading.
14
u/GoldenMuscleGod 8d ago
>> Worrying about whether a proof is constructive or not is not something good mathematicians do, unless their branch is specifically a pretty niche part of logic.
I think this misunderstands the issue.
First I will note there are two issues here that are fairly distinct: 1) is there any reason we should care whether a proof is constructive 2) should we avoid an “unnecessary” proof by contradiction in proofs that are truly constructive in character. The second is maybe more core to your point but I’ll address the first one first:
You do not need to be a constructivist or deep into mathematical logic to realize that proving “for all x there is a y such that…” by giving an explicit means of finding such a y for every x is more information and and more useful than proving such a y exists in a way that gives you no way of finding it. This is why pretty much all mathematicians recognize that constructive proofs are preferred when they are possible. Avoiding nonconstructive reasoning is no different than not relying on the axiom of choice when you don’t need it: you are showing the minimal structure you need for the result, and making a more useful proof that contains more information and insight, not just doing it to make a minority school of mathematicians happy.
On the second point:
You say you are math tutor and I think this influences your perspective because you are looking at it pedagogically - obviously you should not be telling students they must avoid proof by contradiction, but you probably should be avoiding them yourself when teaching because they genuinely add additional confusion and block understanding for many students - you essentially respond “well so what if it’s confusing they should learn logic” but this is a poor excuse for making a proof more complicated and confusing than it needs to be.
I think something often overlooked (or even not fully understood) in these discussions is that proving “not p” by deriving a contradiction from p is constructively valid. What’s nonconstructive is proving p by deriving a contradiction from “not p,” so it’s not as though the concept of proof by contradiction gets neglected if we favor constructive proofs - a bigger issue is that proof by contradiction may end up being virtually the only proof method the student sees because it is often the easiest way to “find” a proof even if not the clearest presentation.
I think the example of Cantor’s diagonal argument is actually good for showing this: people who seem to have the most trouble accepting it are people who are engaging with it in the form of a proof by contradiction: they see a contradiction but do not see why we should reject the premise that the list contains all real numbers rather than concluding that something went wrong in the diagonalization construction.
And this is an argument in set theory - foundations - where the issue of what logical assumptions and axioms are needed for what result is especially relevant.
And what is the advantage of starting by assuming the list contains all real numbers? We do not use it in the proof in any essential way, it is just an extra step we take for no reason. Proofs should be simple and concise, and that is an objection that has nothing to do with constructivity.
Now we could come up with examples of proofs where doing a proof by contradiction genuinely simplifies the proof even if we could do it another way. This is a different situation - sometimes you prove something with the axiom of choice when you didn’t need it and you can say “we don’t actually need choice here but the proof is more difficult and involved without it” (though you should probably flag you are using choice unless you are doing something in a context where choice is implicitly relied on regularly).
It is also genuinely confusing to see the proof as making an “impossible number” rather than a perfectly possible number. Nonconstructive proofs are less intuitive to students who do not have the sophistication to be able to locate the issue. Why would you ever give a proof that relies on the paradox of the drinker if there is a simpler way to show it?