Proof by Contradiction

Proof by Contradiction

Proof by contradiction is a powerful method used in formal logic to establish the truth of a proposition. This technique relies on the principle that if assuming the negation of a statement leads to a contradiction, then the original statement must be true. In this lesson, we will explore how to use proof by contradiction effectively.

Understanding Proof by Contradiction

Proof by contradiction is based on the law of excluded middle, which states that for any proposition P, either P is true or its negation (not P) is true. The essence of proof by contradiction is as follows:

1. Assume that the statement you want to prove is false.
2. Show that this assumption leads to a contradiction.
3. Conclude that the original statement must be true.

Steps to Perform a Proof by Contradiction

To perform a proof by contradiction, follow these steps:

1. Identify the statement (proposition) you want to prove.
2. Assume the negation of that statement.
3. Use logical reasoning and previously established facts to derive a contradiction.
4. Conclude that the original statement is true.

Example 1: Proving that √2 is Irrational

We will prove that the square root of 2 is irrational using proof by contradiction.

Step 1: Identify the statement

We want to prove that √2 is irrational. A number is irrational if it cannot be expressed as a fraction of two integers.

Step 2: Assume the negation

Assume that √2 is rational. This means we can express it as a fraction of two integers a and b (where b ≠ 0) in simplest form:

√2 = a/b

Step 3: Derive a contradiction

Squaring both sides gives:

2 = a²/b²

Multiplying both sides by b² results in:

a² = 2b²

This implies that a² is even, since it is equal to 2 times another integer. If a² is even, then a must also be even (as the square of an odd number is odd). Therefore, we can write:

a = 2k, where k is an integer.

Now substitute a back into the equation:

(2k)² = 2b²

4k² = 2b²

Dividing both sides by 2 gives:

2k² = b²

This implies that b² is also even, and thus b must be even as well.

Since both a and b are even, this contradicts our original assumption that a/b is in simplest form (a and b cannot both be even). Therefore, our assumption that √2 is rational must be false.

Step 4: Conclude

Since assuming that √2 is rational leads to a contradiction, we conclude that √2 is irrational.

Example 2: Proving that There is No Largest Integer

We will prove that there is no largest integer using proof by contradiction.

Step 1: Identify the statement

We want to prove that there is no largest integer.

Step 2: Assume the negation

Assume that there is a largest integer, which we will call n.

Step 3: Derive a contradiction

If n is the largest integer, then n + 1 must also be an integer. However, n + 1 is greater than n, which contradicts our assumption that n is the largest integer.

Step 4: Conclude

Since our assumption leads to a contradiction, we conclude that there is no largest integer.

Common Mistakes in Proof by Contradiction

When using proof by contradiction, students often make several common mistakes:

• Failing to clearly state the assumption of the negation.
• Not deriving a clear contradiction.
• Assuming the conclusion instead of proving it through logical reasoning.

Comparison with Other Proof Techniques

Proof by contradiction is one of several proof techniques. Other techniques include:

• Natural Deduction: This method involves deriving conclusions directly from premises using rules of inference.
• Proof by Induction: This method is often used for proving statements about integers by establishing a base case and an inductive step.

Each technique has its strengths and is suitable for different types of statements. Proof by contradiction is especially useful when direct proof is difficult or impossible.

Practice Problems

To strengthen your understanding of proof by contradiction, try the following practice problems:

1. Prove that there is no smallest positive rational number.
2. Prove that if n is an odd integer, then n² is also odd.

Summary

• Proof by contradiction assumes the negation of the statement to be proved.
• A contradiction is derived from this assumption, leading to the conclusion that the original statement is true.
• Common mistakes include unclear assumptions and skipping steps in reasoning.

Check your understanding

1. What is the first step in a proof by contradiction?
2. How do you derive a contradiction in a proof by contradiction?
3. Give an example of a statement that can be proved using proof by contradiction.
4. What are two other proof techniques besides proof by contradiction?