3
$\begingroup$

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.

sqrt(2) is irrational

$\endgroup$
5
  • 1
    $\begingroup$ Is the same concept proof of negation and prove by contradiction. Two different names for the same type of logic prove structure when you negate the thesis to find a contradiction $\endgroup$ Jan 16 at 10:33
  • $\begingroup$ "proof of negation" is not correct since we do not prove the negation. What is correct that we use the negation of the statement , we disprove it and establish that the negation cannot be true. This implies that the statement itself must be true. We could call it "prove by negation". $\endgroup$
    – Peter
    Jan 16 at 10:40
  • 1
    $\begingroup$ See this post. $\endgroup$ Jan 16 at 10:41
  • 1
    $\begingroup$ According to the so-called "constructivistic" point of view, there is a difference between the two: in one case we start from an "affirmative" property and we conclude with its negation, in the other we assume a "negative" claim (there is no number such that...) and we conclude in the affermative. $\endgroup$ Jan 16 at 10:43
  • 2
    $\begingroup$ If so, the above proof is a "proof by negation" because the claim is: "there are two natural numbers $n,m$ such that $\sqrt 2 = \dfrac n m$". Having found a contradiction, the conclusion is: "there are no numbers..." that amounts to saying that $\sqrt 2$ is "not rational". $\endgroup$ Jan 16 at 10:45

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

A proof by contradiction is when you assume $\neg A$, derive a contradiction and conclude that $A$ holds.

A proof of negation is when you assume $A$, derive a contradiction, and conclude that $\neg A$ holds.

In classical mathematics, the difference is immaterial, as there is no distinction between $A$ and $\neg \neg A$. In constructive mathematics there is, however: For example, to prove that $\exists n \in \mathbb{N} \ P(n)$, you need to actually show the witness $n$. A proof of $\neg \neg \exists n \in \mathbb{N} \ P(n)$ includes no such information.

To see whether the proof of irrationality of $\sqrt{2}$ is a proof of negation or a proof of contradiction, we need to look at what "$x$ is rational" and "$x$ is irrational" mean. If $x$ is rational, we can provide concrete evidence by providing $n \in \mathbb{Z}$ and $m \in \mathbb{N}$ with $x = \frac{n}{m}$. But "$x$ is irrational" just means that $x$ is not rational.

Thus, proving that $\sqrt{2}$ is irrational is a proof of negation.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .