Proof by contradiction (also known as indirect proof or the method of reductio ad absurdum) is a common proof technique that is based on a very simple principle: something that leads to a contradiction can not be true, and if so, the opposite must be true. It's a principle that is reminiscent of the philosophy of a certain fictional detective:
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth."
"Sherlock Holmes" in the novel The Sign of the Four (1890) by Sir Arthur Conan Doyle
To prove a statement by contradiction, start by assuming the opposite of what you would like to prove. Then show that the consequences of this premise are impossible. This means that your original statement must be true.
Prove that there is no largest number.
Suppose that a largest number does exist. Let it be If really is the largest number, then there can be no number larger than
Consider the number This number is larger than but it was just stated that there cannot be any number larger than . This is a contradiction. The premise that there existed a largest number cannot be true, because the consequence of this premise is absurd. Therefore, there is no largest number.
G. H. Hardy called proof by contradiction "one of a mathematician's finest weapons," saying, "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."
Contradiction proofs are often used when there is some binary choice between possibilities:
is either rational or irrational.
There are infinitely many primes or there are finitely many primes.
Either a line tangent to a circle is perpendicular to the radius of the circle containing the point of tangency, or it is not.
When writing a proof by contradiction, you need to have an idea about which possibility is correct.
One suspects that is irrational, because there doesn't seem to be any rational number that, when squared, equals 2.
One suspects that there are infinitely many primes, because although they are rare, one can always seem to find more.
One suspects that a line tangent to a circle is always perpendicular to the radius, because it always seems that way when it is drawn.
Proof by Contradiction Process
Negate the conclusion: Begin with the premise that whatever you are attempting to prove, the opposite is true. In the introduction example, the goal was to prove that there is no largest number, so the proof begins with the premise that there is a largest number.
Analyze the consequences of this premise: This step involves putting that premise in some mathematical form. In the introduction example, the largest numbers was given a name, It's not necessary to find a specific value for it's sufficient to show that it exists in some form.
Look for a contradiction: A contradiction is something that doesn't make sense given the negated conclusion premise. In the introduction example, a number was found that was larger than . This goes against the premise that is the largest number.
As soon as a contradiction is found, the proof is complete. You can conclude that what you were trying to prove was correct.
Proof by contradiction isn't very useful for proving formulas or equations. Proof by contradiction needs a specific alternative to whatever you are trying to prove. For example, you wouldn't use proof by contradiction to prove the quadratic formula. There isn't any specific alternative equation to the quadratic equation, so proof by contradiction doesn't help to prove it.
However, proof by contradiction can sometimes be used to prove the converse of a formula or equation. The proof of the converse of the Pythagorean theorem is an example of this.
Proof by contradiction is common in number theory because many proofs require some kind of binary choice between possibilities.
Prove that is irrational.
Suppose that is rational. If it were rational, it could be expressed as the ratio of two co-prime integers and . Since and are co-prime, both of them can not be even.
If , then . Since the left hand side is even, so is the right hand side. By Euclid's lemma, must be even.
If is even, is a multiple of . This in turn means is a multiple of In other words, is a multiple of . By the same reasoning as above, we conclude that is even.
That's a contradiction! It was stated that both and can't be even.
Assuming that is rational led to a contradiction. This means can't be rational. We've proved that is irrational.
Prove that there is no least positive rational number.
Suppose that there is a least positive rational number. Call it .
is a positive rational strictly less than . But this contradicts being the smallest positive rational number. in fact, does not exist. In other words, there is no such thing as the least positive rational.
Note: This result gives an intuition that any dense subset of cannot have a least positive element.
Prove that there are infinitely many prime numbers.
Suppose that there are finitely many prime numbers. Then it would be possible to list all of the prime numbers, in order:
Now consider the product of all of those prime numbers:
This number is divisible by all of the prime numbers. Now, add 1 to this number:
This number is not divisible by any of the prime numbers, because dividing it by any prime always results in a remainder of
This implies that this number is a prime number. However, this number is larger than This contradicts the assertion that is the largest prime number.
Therefore, there is no largest prime number. There are infinitely many prime numbers.
Prove that the sum of a rational number and an irrational number is irrational.
Suppose that the sum of a rational number and an irrational number is rational. The first rational number can be expressed as where and are co-prime integers. Let the irrational number be Their sum can be expressed as where and are co-prime integers. Then,
Subtracting from both sides of this equation gives
is an integer, and so is Therefore, is a rational number. However, was defined to be irrational. This is a contradiction.
Hence, the sum of a rational number and an irrational number is irrational.
If , and are all odd integers, prove that can't have a rational solution.
Assume that a rational number is the solution to with and co-prime. As with a previous example, this means that both of and can't be even. At least one of them has to be odd.
If is indeed a solution to the quadratic, then
Now the right hand side is even, so the left hand side has to be even too. But since , , are all odd, that can happen only if both and are even, and it was made very clear that they are not.
Therefore, a rational number can't be a solution to if , and are all odd.
Prove that the harmonic series diverges.
The harmonic series is
Suppose that the harmonic series converges, and consider the following series:
where the grouping symbols denote the ceiling function.
Each term in this sequence is positive and less than or equal to the corresponding term in the harmonic series:
Then if the harmonic series converges, this series converges as well.
However, this series does not converge. Grouping the like terms gives a repeated sum of
The fact that this series diverges is a contradiction. Therefore, the harmonic series diverges.
When contradiction proofs are used for geometry, it often leads to figures that look absurd. This is to be expected, because a proof by contradiction always begins with a premise that goes against what is believed to be true.
Prove that a line tangent to a circle is perpendicular to the radius of the circle that contains the point of tangency.
We are given circle tangent line and point of tangency
Suppose that the tangent line is not perpendicular to the radius containing the point of tangency. Then there exists some other point, on line such that
Since is the point of tangency, must be outside of the circle. Therefore,
However, is a right triangle, and is the hypotenuse of this triangle. Therefore, This contradicts the previous assertion that
Therefore, a line tangent to a circle is always perpendicular to the radius of the circle that contains the point of tangency.
Given the Pythagorean theorem, prove the converse of the Pythagorean theorem. That is, if a triangle contains side lengths and such that then the triangle is a right triangle.
Suppose that there exists a triangle with that is not a right triangle. The triangle can either be acute or obtuse.
Assume that the triangle is acute.
Let point be the point such that and
is a right triangle with side lengths and . It is given that so by the Pythagorean theorem,
Note that and are isosceles triangles. Thus, and
It is also apparent that and However, this cannot be true given the previous assertion about congruent angles.
A similar contradiction arises if one assumes that the triangle is obtuse.
Thus, if a triangle has side lengths and such that then the triangle is a right triangle.
Euclid's Elements, Book 1, Proposition 6. Prove that if two angles of a triangle are congruent, then the sides opposite them are congruent.
Note: This proof is the converse of Proposition 5 (If two sides of a triangle are congruent, then the angles opposite them are congruent), and it also follows from Proposition 4 (SAS congruence). There are other ways to prove this theorem, but this proof is notable for requiring very few prerequisite propositions.
Suppose that there exists a triangle with two congruent angles, but the sides opposite those angles are not congruent. If the sides are not congruent, then one of them must be longer.
In the triangle above, and
Since is longer than let be placed on such that
Now these congruences can be observed:
- which is given by how point was defined.
- also given.
- by the reflexive property of congruence.
These congruences suggest that by SAS triangle congruence. However, this cannot be true, because is clearly larger.
Hence, if two angles of a triangle are congruent, then the sides opposite them are congruent.
5 points are placed within a unit equilateral triangle. Prove that two of those points must be a maximum distance of from each other.
Suppose that for any pair of points among the 5, the distance between the points is greater than . Now consider the partition of the triangle into 4 smaller equilateral triangles.
Note that the maximum distance between two points within one of these smaller triangles is A point could be placed within each of the triangles (the 4 blue points) such that each point is further than from the other points. However, the point (the red one) would have to be placed within the same triangle as another point.
Thus, if 5 points are placed within a unit equilateral triangle, two of those points must be at most away from each other.
Prove that out of a party of 6 people, there exists a group of 3 mutual friends or a group of 3 mutual non-friends.
Suppose that given any group of 3 people among the 6, there are at most 2 friendships or 2 non-friendships. Let the 6 people be labeled with and The possible relationships are shown with dashed lines below.
Begin with person Suppose that is friends with at least 3 people, and suppose 3 of those people are and
Let a friendship be denoted with a blue line, and let a non-friendship be denoted with a red line. If any pair of or are friends, then they form a group of 3 mutual friends with
If and are all non-friends, then they form a group of 3 mutual non-friends.
Without loss of generality, this same contradiction arises with any combination of 4 people including
When you consider what happens when has at least 3 non-friends among the group, a similar contradiction arises. Note that must have at least 3 friends or have at least 3 non-friends.
Therefore, given any party of 6 people, there exists a group of 3 mutual friends or a group of 3 mutual non-friends.
Prove that it is impossible to traverse the following graph by traveling along each path exactly once. Any of the vertices may be selected as the starting vertex or ending vertex, and vertices may be passed more than once.
Suppose that it is possible to traverse the graph by traveling along each path exactly once. Consider how many times each vertex would be passed through. For every time a vertex is entered, it is also exited. Therefore, if each path is traveled exactly once, then each vertex should have an even number of paths coming from it. The exceptions to this are the starting vertex and ending vertex. These vertices should have an odd number of paths coming from them. There can only be one starting vertex and one ending vertex. However, the graph above has 4 vertices with an odd number of paths coming from them.
Thus, it is impossible to traverse the above graph by traveling along each path exactly once.
Hall's marriage theorem is often used in problems that require matchmaking between elements in a set. Its application in the following problem isn't entirely obvious, but consider this: in order for a domino to be placed in the figure, a white tile must be "matched" with an adjacent blue tile.
Main Article: Fermat's Method of Infinite Descent
Fermat's method of infinite descent is a special kind of proof by contradiction. It is based on the fact that there exists a smallest positive integer, . If a premise leads to infinitely many positive integer solutions such that each solution is successively smaller, then this is a contradiction.
Prove that if is a positive integer and is not an integer, then is irrational.
Suppose that is rational. Then it can be expressed as , where and are positive co-prime integers. Let be the largest integer that is less than , then is a positive number that is less than
Note that the above expression is equivalent to but the numerator and denominator are each smaller than and , respectively, because is less than
Substitute into the numerator and into the denominator:
Recall that and are integers. Also recall that the numerator of the above expression is positive and less than and likewise the denominator of the above expression is positive and less than This implies that there exist positive integers and such that
The process above could be repeated indefinitely to produce positive integers and that are successively smaller after each step. However, there exists a smallest positive integer, This is a contradiction, because one would not be able to indefinitely find smaller positive integers if a smallest positive integer exists.
Hence, if is a positive integer and is not an integer, then is irrational.