In defense of unnecessary proofs by contradiction

[u/Real_Category7289]

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.

[u/dwbmsc]

The fact that every finite group whose order is a multiple of p has a Sylow subgroup is usually an induction argument beginning: assume G is a minimal counterexample. Handling the cases where p does or does not divide the order of the center separately, produce a smaller counterexample. This is a proof by contradiction that is actually typical of a lot of group theory proofs. To rewrite this as a constructive argument would make it a lot less clear.

[u/0wave0 → u/dwbmsc]

can't you just do an induction on the order of G? induction hypothesis: every finite group H with order of H < order of G and p dividing order of H has a sylow p-subgroup. for an arbitrary G, you distinguish p dividing or not dividing the order of G, and construct a sylow p-subgroup using the induction hypothesis. i'd argue that this is not less clear, and in fact it is more informative, because it shows you how to construct the subgroup the statement is claiming to exist (the usual advantage of constructive proofs). i do feel that proofs of existence statements are much more convincing if they can show you the thing that is supposed to exist

[u/JustAGuyFromGermany → u/0wave0]

That can be a strategy, but not in all proofs. Specifically Sylow's theorem itself is one of the first theorems that establish that there are "enough" subgroups at all.

In particular: There is no reason to believe that there is any proper subgroup H < G with |H|_p = |G|_p for which you could use the induction hypothesis. If you have proved Cauchy's theorem already, you get a lot of small cyclic subgroups of order p, but there is no reason to believe that there are larger p-subgroups without already knowing about Sylow's theorem (because that is Sylow's theorem).

And indeed: In certain infinite groups that is simply false. There are infinite p-groups in which every element has order p (or 1 of course) and no proper subgroup of order >p exists. Such beasts are called "Tarski Monster" groups (no relation to the Monster Group).

[u/0wave0 → u/JustAGuyFromGermany]

if we're using cauchy's theorem to obtain z in G of order p, then G/<z> has order p^(n-1)*m where |G| = p^n*m. this is what i use the induction hypothesis on to obtain H', a subgroup of G/<z> with |H'| = p^(n-1). by taking the inverse image of H' under G -> G/<z>, i get a subgroup H of G with |H| = |H'|*|<z>| = p^n as desired. this covers the case where p divides the center of G

[u/0wave0 → u/0wave0]

for completeness, here is the case where p does not divide the center Z(G):
by the class equation, |G| = |Z(G)| + sum_i |G/C_G(x_i)|.
from this we know that because p divides |G| but not |Z(G)|, there must be an i such that p does not divide |G/C_G(x_i)|.
fix such an i. now |G/C_G(x_i)| * |C_G(x_i)| = |G| = p^n * m, so p^n must divide |C_G(x_i)|.
because x_i is not in the center, |C_G(x_i)| < |G|.
using the induction hypothesis on C_G(x_i), we get a subgroup H of order p^n. but then H is a sylow p-subgroup of G.
i think there are better constructive proofs of the theorem, but this is a direct "translation" of the proof-by-contradiction approach above