Proof by Contradiction in Discrete Mathematics: A Step-by-Step Guide

Learn the technique of proof by contradiction, a powerful indirect method of proving mathematical statements. This tutorial explains the underlying logic, provides illustrative examples, and demonstrates how to construct a sound proof by contradiction, showing how an assumption leads to a logical impossibility.

Proof by Contradiction in Discrete Mathematics

What is Proof by Contradiction?

Proof by contradiction is an indirect method of proving a statement. Instead of directly showing the statement is true, we assume it's false and then show that this assumption leads to a contradiction (something logically impossible). Because the assumption leads to a contradiction, we conclude that the original statement must be true.

Steps in a Proof by Contradiction

  1. Assume the Opposite: Start by assuming the opposite (negation) of what you want to prove.
  2. Deduce Consequences: Use logical reasoning and the assumption to derive new consequences.
  3. Find a Contradiction: Show that the consequences lead to a contradiction – either a contradiction with the initial assumption, a known fact, or both.
  4. Conclude: Since the assumption led to a contradiction, the assumption must be false, and therefore, the original statement is true.

Why Does Proof by Contradiction Work?

Proof by contradiction essentially proves the contrapositive of the original statement ("If not Y, then not X"). Since a statement and its contrapositive are logically equivalent, proving the contrapositive proves the original statement. The contradiction forces us to reject the initial assumption because all subsequent steps are logically sound; the only possible flaw is the initial assumption itself.

Example: The "Potter and his Parking Ticket" Analogy

Imagine Potter received a parking ticket. If he didn't pay, the council would send a nasty letter. He didn't get a nasty letter. Therefore, he must have paid. This uses contradiction because we explored the consequence of "not paying" and showed it contradicts the fact that he didn't receive a letter.

Examples of Proof by Contradiction

Example 1: Proving the Product of an Irrational Number and a Non-Zero Rational Number is Irrational

(A step-by-step proof by contradiction would be included here. The steps should clearly show the assumption, the logical deductions, and the point where the contradiction arises.)

Example 2: A Simpler Example with Two Statements

(This example involving statements p and q, showing how assuming p is true leads to a contradiction with q, demonstrating the use of proof by contradiction, would be included here.)

Conclusion

Proof by contradiction is a powerful technique for proving mathematical statements, especially when a direct proof is difficult. By systematically exploring the consequences of a false assumption and arriving at a contradiction, we can confidently conclude that the original statement is true.