I am just learning about proofs in an introductory course. I came across an example of "proof by contradiction" (see attachment) about $ֿ\sqrt{2}$ being irrational. Some online sources have said that this is in fact a proof of negation. Is this correct? If so, how can you spot the difference between the two?
Thank you.
Best Answer
tl;dr The distinction is real. Nonetheless, you can safely call this a proof by contradiction in most introductory courses. Later on, in advanced and specialized courses, people might expect you to use more precise terminology, and distinguish between proofs of negation and proofs by contradiction.
Welcome to Math.SE!
I. To prove that the negation $\neg P$ of a proposition $P$ holds, we can use the following strategy: we tentatively assume that the proposition $P$ holds, and using this tentative assumption, we derive a contradiction.
For example, to prove that the negation of the proposition "there is a rational number $x$ such that $x^2 = 2$" holds, we tentatively assume that such an $x$ exists, and using this tentative assumption we show that there is an integer (the denominator of the same $x$, written in lowest terms) that is both even and odd, a contradiction.
Since assuming that "there is a rational number $x$ such that $x^2 = 2$" leads to a contradiction, we can conclude that the negation of this statement, "there is no rational number $x$ such that $x^2 = 2$" must in fact hold.
Common mathematical parlance calls this sort of reasoning a proof by contradiction (or reductio ad absurdum). It is perfectly appropriate to use the term "proof by contradiction" to refer to this sort of argument in an introductory course. Your instructors will understand what you mean.
II. Now, the sort of reasoning demonstrated above is often combined with a different logical principle, the so-called law of double negation, i.e. the fact that every proposition is equivalent to the negation of its negation.
To prove that a proposition $Q$ holds, we can tentatively assume that its negation $\neg Q$ holds, then use this assumption to reach a contradiction. By the principle above, this proves that the negation of $\neg Q$, i.e. $\neg\neg Q$, must hold.
But by the law of double negation, $\neg \neg Q$ is logically equivalent to $Q$, so we have in fact managed to prove that the proposition $Q$ holds.
An example would be the following proposition: "there are at least two different digits which appear infinitely many times in the decimal expansion of $\sqrt{2}$". We can tentatively assume the negation of this statement, "there are no two different digits which appear infinitely many times in the decimal expansion of $\sqrt{2}$". If this was the case, then at most one digit would occur infinitely often in the decimal expansion: from some point onwards, $\sqrt{2}$ would consist of the repetition of that one digit. So $\sqrt{2}$ would have a recurring decimal expansion, contradicting the fact that $\sqrt{2}$ is irrational.
We have shown that "there are no two different digits that appear infinitely many times in the decimal expansion of $\sqrt{2}$" leads to a contradiction. Therefore, the negation of this statement, "it is not the case that there are no two different digits which appear infinitely often in the decimal expansion of $\sqrt{2}$" must hold.
Using the law of double-negation, we can conclude that equivalently, "there are at least two different digits that appear infinitely many times in the decimal expansion of $\sqrt{2}$".
Surprising fact: as of 2023, nobody managed to give an actual example of two digits that appear infinitely many times in the decimal expansion $\sqrt{2}$, even though (by the simple proof above) we know that there definitely exist two such digits. The simple proof above is non-constructive: while it proves that an object satisfying some property exists, it does not give an example of such an object.
III. In certain advanced branches of mathematics (among them computer science, topos theory, type theory, proof theory), and among adherents of constructivist mathematical philosophy (which forbids non-constructive existence proofs and only allows existence proofs that provide specific examples) we have to avoid appeals to double negation.
Practitioners of these fields find it important to distinguish between the proofs by contradiction that do not appeal to the law of double negation (our first example, the irrationality of $\sqrt{2}$) and the proofs by contradiction that do (our second example, about the digits).
So in the 1980s, some practitioners of these fields devised an alternative nomenclature, where they call only proofs of this second sort proof by contradiction, and instead call proofs of the first sort proof of negation.
Despite efforts to evangelize this nomenclature, it never caught on among people who are neither computer scientists, nor topos theorists, nor type theorist, nor proof theorists. (NB it didn't fully catch on among proof theorists either! Many of us think that this newer naming scheme is dumb, since it focuses on the contradiction, even though the double negation is the real culprit).
Once you start learning about topos theory, type theory or proof theory, it will be important to know the distinction between proof of negation and proof by contradiction in this alternative nomenclature. Until then, and in any other math course, don't expect your instructors to be familiar with this alternative nomenclature, and don't expect them to care about it either.