Proof by Contradiction
This method of proof is sometimes called reductio ad absurdum, which means "reduction to absurdity." The argument by contradiction is based on the fact that either a proposition is true or it is false but not both. The main line of argument is follows. Suppose we can show that assumption (supposition) that a given proposition is not true leads to an absurdity or a contradiction. Then that assumption (supposition) must be false; therefore, the given proposition must be true. Underlying the reducio ad absurdum validity is a slightly controversial law of logic, known as the law of the excluded middle, that, like syllogism, also dates back to the time of Aristotle. It is expressed in the following
Let r be a proposition. The proposition r ∨ ~r has a truth-value of T, no matter what is the truth-value of r.
The heart of the controversy is that this law is only applicable on the finite set and many statement s in mathematics involve infinitely many objects. It is easy to see that there is some validity to this objection. On of the famous example is the Goldbach conjecture, which says that every even integer is the sum of two primes and I am sure you can think of many many examples of infinite objects in mathematics such as there are infinitely many even integers, etc. Mathematicians of the intuitionist school of thought feel that a logical basis for mathematics should not rely on the unrestricted use of the "law of the excluded middle," essentially because this is a principle originating in antiquity where it was used only to apply to statements about finitely many things.
It follows from the law of excluded middle that r ∧ ~r is logically equivalent to ~(r ∨ ~r) and must always be false for any proposition r. The idea behind the proof of an implication p → q by the method of reductio ad absurdum is as follows: Show that to assume the negation of p → q leads to as statement r ∧ ~r for some satement r, and hence that this negation cannot be ture and thus p → q must be true. More precisely,
Let p, q and r be propositions. The proposition
(~(p → q) → (r ∧ ~r)) → (p → q)
is true no matter what be the truth of p, q and r.
From practical or computational point of view, we summarize the above discussion into following three steps:
Step 1. Suppose the statement to be proved is false. That is, suppose the negation of the given statement is true.
Step 2. Show that this supposition leads logically to an absurdity or a contradiction.
Step 3. Conclude that the statement to be proved is true.
Generally speaking, we apply the method of reductio ad absurdum in following situations:
1. When we want to show that there is no object with a certain property.
2. When we want to show that a certain object does not have a certain property.
Now we follow the above-mentioned three steps to prove the given statement by the method of reductio ad absurdum in situation 1. The given statement is:
There is no greatest integer.
Situation 1: Here our goal is to prove that there is no object with the property of being the greatest integer.
| Step 1. | We suppose that the given statement is false.
That is, the negation of the given statement is true. In other words, we
are supposing the negation that there is an object with the property of
being the greatest integer. Formally,
Suppose there is a greatest integer N. And this simply means that for an integer n, N ≥ n. |
| Step 2. | Now our job is to show that the supposition (in the step 1) leads logically to an absurdity i.e. to a contradiction. We approach to absurdity as follows: If we add 1 to a given greatest integer, then we get an integer that is greater still. |
| Step 3. | From the argument in Step 2, we see that if
somebody gives us a greatest integer, we can add 1 to it and get a still
greater integer. But this contradicts our supposed statement in the step
1. The only logical conclusion we can draw from this absurdity is that no
greatest integer can exist. Formally, we say: This is a contradiction.
Hence, the supposition is false and the theorem (given statement) is true.
Note that most mathematics textbooks do not write this step and end proofs at the point at which the contradiction has been obtained. |
Now using the above three steps of the method of reductio ad absurdum, let us prove the statement formally:
Given statement: There is no greatest integer.
Proof:
Suppose not. [We take the negation of the statement and suppose it to be true.] Suppose there is a greatest integer N. [We must deduce a contradiction.] Then
For every integer n, N ≥ n.
Let M = N + 1. Now M is an integer. [Since it is a sum of integers.] Also, M > N [because M = N + 1].
Therefore, M is an integer that is greater than the greatest integer, which is a contradiction. [This contradiction shows that supposition is false, and hence the given statement is true.]
And this completes the proof.
Now we follow the above-mentioned three steps to prove the given statement by the method of reductio ad absurdum in situation 2. The given statement is:
The sum of any rational number and any irrational number is irrational.
Situation 2. Here our goal is to prove that there is a number (an object) that does not have the property of being rational.
| Step 1. | We start by supposing that the negation of
the given statement is true. So, our task in this step is to negate the
given statement. The given statement can be written formally as:
∀ real number r and s, if r is rational ans s is irrational, then r + s is irrational. The nagtion of this statement is: ∃ a rational number r and an irrational number s such that r + s is not irrational. or equivalently, ∃ a rational number r and an irrational number s such that r + s is rational. [See my logic page to understand this negation.] Now that we have a negation of the statement to be proved. We are ready to suppose. So lets do it- Suppose not. That is, suppose there is a rational number r and an irrational number s such that r + s is rational. |
| Step 2. | Here, our job is to prove that the
supposition in the Step 1 leads logically to an absurdity i.e. to a
contradiction. To do so, it is very very ... important to understand what
the hell you are supposing exactly. See the statement again: We are
supposing exactly:
There are numbers r and s such that r is rational, s is irrational, and r + s is rational. This simply means [by definition of rational and irrational] that we cannot write s as a quotient of any two integers but we can certainly write r and r+s as a quotient of any two integers. Writing the same thing symbolically, we say: r = a/b for some integers a and b with b ≠ 0 ____________(1) and r + s = c/d for some integers c and d with d ≠ 0 ____________(2) Now, we substitute equation 1 into equation 2 and get: Since r + s = c/d therefore, a/b + s = c/d ____________(3) Now, we subtract a/b from both sides of equation 3. a/b + s − a/b = c/d − a/b s = c/d − a/b We write c/d and a/b as equivalent fraction. s = bc/bd − ad/bd We have the rule for subtracting fractions with the same denominator. So, s = (bc − ad)/bd |
| Step 3. | Now the conclusion. Clearly, both (bc -ad) and (bd) are integers and bd ≠ 0. [why? Because products and differences of integers are integers, and bd ≠ 0 by the zero product property.] Hence, s can be expressed as a quotient of two integers. [Which is, clearly, a stupidity. This means our supposition in Step 1 is false and the only logical conclusion we can draw from this is that the given statement is true.] |
Now let us do the above example all over again but this time formally. The theorem is:
The sum of any rational number and any irrational number is irrational.
Proof:
Suppose not. [we take the negation of the theorem and suppose it to be true.] Suppose there is a rational number r and an irrational number s such that (r + s) is rational. [We must deduce a contradiction.] By definition of rational, we have
r = a/b for some integers a and b with b ≠ 0
and r + s = c/d for some integers c and d with d ≠ 0
By substitution, we get
a/b + s = c/d
and so
s = c/d − a/b
= (bc − ad)/bd
Now (bc − ad) and (bd) are both integers [since a, b, c, d are all integers, and since products and differences of integers are integers], and bd ≠ 0 [by the zero product property].
Hence, s is a quotient of the two integers (bc − ad) and (bd) with bd ≠ 0. So, by the definition of rational, s is rational. This contradicts the supposition that s is irrational. [Hence, the supposition is false and theorem is true.]