mathematical proof by contradiction

Daniel Parker

3 min read

·

17-03-2025

1

0

Share

Mathematical proof by contradiction, also known as reductio ad absurdum, is a powerful and elegant method for establishing the truth of a statement. It works by assuming the opposite of what you want to prove is true, and then showing that this assumption leads to a logical contradiction. Since a contradiction cannot exist within a consistent mathematical system, the initial assumption must be false, thus proving the original statement true. This technique is surprisingly versatile and finds applications across various areas of mathematics.

Understanding the Logic Behind Proof by Contradiction

The core principle behind proof by contradiction is based on the law of excluded middle. This law states that for any statement, either the statement is true or its negation is true; there's no third option. We exploit this by:

1. Assuming the negation: We begin by assuming the opposite (negation) of the statement we want to prove is true.

2. Deriving a contradiction: Through logical deduction and mathematical manipulations, we work from this assumption to derive a contradiction. A contradiction could be something like proving 1=0, a statement violating a known axiom, or conflicting with previously established results.

3. Concluding the original statement is true: Since we've reached a contradiction, our initial assumption (the negation of the statement) must be false. By the law of excluded middle, the only remaining possibility is that the original statement is true.

Example: Proving the Square Root of 2 is Irrational

Let's illustrate with a classic example: proving that the square root of 2 (√2) is irrational (cannot be expressed as a fraction p/q where p and q are integers and q ≠ 0).

1. Assume the opposite: Let's assume, for the sake of contradiction, that √2 is rational. This means it can be written as √2 = p/q, where p and q are integers, q ≠ 0, and p and q have no common factors (the fraction is in its simplest form).

2. Derive a contradiction:

• Square both sides: 2 = p²/q²
• Rearrange: 2q² = p²
• This implies that p² is an even number (because it's equal to 2 times another integer). If p² is even, then p must also be even (an odd number squared is always odd).
• Since p is even, we can write it as p = 2k, where k is an integer.
• Substitute this into the equation: 2q² = (2k)² = 4k²
• Simplify: q² = 2k²
• This implies that q² is also an even number, and therefore q must be even.

We've now reached a contradiction. We initially assumed that p and q have no common factors. However, we've shown that both p and q are even, meaning they have a common factor of 2. This contradicts our initial assumption.

3. Conclusion: Our assumption that √2 is rational has led to a contradiction. Therefore, our initial assumption must be false. This proves that √2 is irrational.

When to Use Proof by Contradiction

Proof by contradiction is a powerful tool, but it's not always the best approach. Consider using it when:

• Direct proof is difficult: Sometimes, directly proving a statement is challenging. Contradiction can offer a more accessible path.
• Negating the statement is easier to work with: If the negation of the statement is simpler or more manageable to analyze, contradiction might be a good strategy.
• You want to show something doesn't exist: Proof by contradiction is particularly effective for proving the non-existence of something (e.g., proving that there are infinitely many prime numbers).

Limitations of Proof by Contradiction

While powerful, proof by contradiction has limitations:

• It doesn't provide a constructive proof: It shows something is true, but doesn't necessarily show how it's true. It establishes existence but not necessarily a method of construction.
• Can be less intuitive: It relies on indirect reasoning, which might feel less intuitive than direct proofs.

Proof by contradiction is a valuable tool in a mathematician's arsenal. By understanding its logic and applications, you can effectively leverage this technique to solve challenging mathematical problems and gain a deeper appreciation for the elegance of mathematical reasoning.