Proof by contradiction

The term “contradiction” in mathematics refers to the situation when we have a proposition p that is true and it’s negation p that is also true. As an illustration, let us consider the concept of contradiction in the context of an example:

Consider the following two statements: p and q.

A coprime integer is represented by the symbol a/b in the following statement: x = a/b

The statement q: 2 divides both the letters “a” and “b.”

In this example, we must make the assumption that the assertion “p” is true” while also demonstrating that the statement “q” is correct. The result is that we have reached a contradiction because the assertion “q” implies that the negation of the statement “p” is correct.

Examples

• The square root of 2 is irrational.

The proof that the square root of 2 is irrational is a classic example of a proof by contradiction from the field of mathematics.

When expressed as a fraction a/b in lowest terms, it would be expressible as a rational fraction a/b, where a and b are both integers, at least one of which is odd. However, if a/b = 2, then a2 = 2b2 is obtained. As a result, a2 must be an even number, and because the square of an odd number is an odd number, this suggests that an is an even number — which implies that b must be an odd number because a/b is the lowest term.

If, on the other hand, an is an even number, then a2 is a multiple of four, and so on. If a2 is a multiple of 4 and a2 = 2b2, then 2b2 is a multiple of 4, and consequently, b2 must be an even number, which implies that b must be an even number as well, as shown in the example.

As a result, b is both odd and even, which is a contradiction. The first assumption—that 2 can be stated as a fraction—must thus be incorrect. 

• The hypotenuse’s length is the length of the hypotenuse.

The method of proof by contradiction has also been used to demonstrate that the length of the hypotenuse of any non-degenerate right triangle is less than the sum of the lengths of the two remaining sides.

Another way of expressing the assertion more succinctly is to assume that the hypotenuse is c in length and that the legs are a and b in length, respectively. In which case, using the Pythagorean theorem, it is possible to construct a proof by contradiction that is valid.

For starters, the assertion is refuted by assuming that a + b >c This would result in the result (a + b)2  <= c2, or more precisely, the result a2 + 2ab + b2 <= c2 after squaring both sides. An inverted triangle is non-degenerate if each of its edges has a positive length; therefore, it may be assumed that a and b are both larger than zero. Because of this, a2 + b2 2ab+b2 <c2, and the transitive connection can be simplified even further to a2 + b2 <c2 (see also the previous section).

According to the Pythagorean theorem, on the other hand, it is also known that a2 + b2 <=c2 is true. Due to the fact that rigorous inequality and equality are mutually exclusive, this would result in a contradiction. The contradiction indicates that it is impossible for both statements to be true at the same time, and it is well known that the Pythagorean theorem is correct. It follows from this that the assumption a + b c, thereby demonstrating the claim, must be true as well.

• There is no smallest positive rational number.

Let us consider the following statement, P: “There is no smallest rational integer bigger than 0.” We begin by making the erroneous assumption, P, that there is a minimum rational number, say, r. Then we proceed to prove the reverse, P.

Now, r/2 is a rational integer that is higher than 0 but less than r, as shown in the diagram. Nevertheless, this is in conflict with the hypothesis that r was the lowest rational number (if “r is the smallest rational number” were Q, then one can conclude that q from the statement “r/2 is a rational number smaller than r” that q. Clearly, the original statement (P) must be correct as a result of this contradiction. That is, “there is no smallest rational number bigger than zero,” as the saying goes.

Conclusion

The method of proof by contradiction is to first assume that what we wish to establish is false and then demonstrate that the consequences of this assumption are not possible. In other words, when the consequences of our assumptions contradict either what we have just assumed or what we already know to be true (or both), we have what is known as a contradiction.

Consider the case of Sally and her parking ticket, which serves as a basic illustration of this theory. We are aware that if Sally had failed to pay her parking penalty, she would have received a threatening letter from the city. We also know that she did not receive any threatening correspondence. Either she paid her parking ticket or she didn’t, and if she didn’t, we know she would have received a threatening letter, based on the information we had at the time of the incident. Because she did not get a threatening letter, it is safe to assume that she paid her ticket.

The assumption would be that Sally did not pay her ticket, and the conclusion would be that she should have received a threatening letter from the council if we were formalising the proof by contradiction. However, we are aware that her mail was very pleasant this week, and that there were no negative notes in it at all. This is a contradiction, and as a result, our first assumption is incorrect. In this case, it appears that we are going through unnecessary hoops to show something that should be obvious, but in more difficult examples, it is beneficial to specify exactly what we are assuming and where our contradiction is located.