Proof by Contradiction

Proof by Contradiction

Proof by contradiction (also called indirect proof) is a powerful and often elegant technique used to prove the truth of a statement. The basic idea is to assume that the statement you are trying to prove is false, and then show that this assumption leads to a contradiction—something that is logically impossible or contradictory. Since the assumption of falsehood leads to an illogical result, we conclude that the original statement must be true.

This method is widely used in many areas of mathematics, especially when direct proof seems difficult or when the statement involves negations.

Structure of a Proof by Contradiction

1. Assume the negation of the statement to be true.
2. Derive logical consequences from this assumption using known facts, definitions, and logical steps.
3. Reach a contradiction—find an inconsistency or a situation that cannot happen (such as a false statement, two contradictory conclusions, or a violation of a known rule).
4. Conclude that the original assumption must be false, meaning that the statement being proved is true.

General Form of a Proof by Contradiction

1. Assume the negation of the statement.
2. Deduce consequences logically from this assumption.
3. Identify a contradiction—an inconsistency with known facts, theorems, or axioms.
4. Conclude that the assumption is false and therefore the original statement must be true.

Example 1: Proving the Irrationality of $\sqrt{2}$

Statement: Prove that $\sqrt{2}$ is irrational.

Proof (by contradiction):

1. Assume the opposite: Assume that $\sqrt{2}$ is rational. This means that it can be expressed as a fraction $\frac{p}{q}$, where $p$ and $q$ are integers, and $q \neq 0$. Additionally, assume that the fraction is in its simplest form, meaning that $p$ and $q$ have no common factors (i.e., they are coprime).

2. From this assumption, we can write:

   $$\sqrt{2} = \frac{p}{q}$$

   Squaring both sides:

   $$2 = \frac{p^2}{q^2} \quad \Rightarrow \quad p^2 = 2q^2$$

   This equation tells us that $p^2$ is an even number, because it is divisible by 2.

3. Since $p^2$ is even, $p$ itself must also be even. (This is because the square of an odd number is odd, so if $p^2$ is even, $p$ must be even.) Therefore, we can write $p = 2k$, where $k$ is some integer.

4. Substituting $p = 2k$ into the equation $p^2 = 2q^2$:

   $$(2k)^2 = 2q^2 \quad \Rightarrow \quad 4k^2 = 2q^2 \quad \Rightarrow \quad 2k^2 = q^2$$

   This shows that $q^2$ is also divisible by 2, so $q$ must be even as well.

5. Now, we have reached a contradiction. We initially assumed that $p$ and $q$ were coprime (i.e., they had no common factors), but we have shown that both $p$ and $q$ are even, meaning they both share 2 as a common factor. This contradicts our assumption that $p$ and $q$ are coprime.

6. Since the assumption that $\sqrt{2}$ is rational leads to a contradiction, we conclude that the assumption is false. Therefore, $\sqrt{2}$ must be irrational.

Conclusion: $\sqrt{2}$ is irrational.

Example 2: Proving There Is No Smallest Positive Rational Number

Statement: Prove that there is no smallest positive rational number.

Proof (by contradiction):

1. Assume the opposite: Suppose there exists a smallest positive rational number. Let this number be $r$. Therefore, $r > 0$ and $r$ is a rational number.

2. Since $r$ is a rational number, we can write $r = \frac{p}{q}$, where $p$ and $q$ are positive integers, and $q \neq 0$.

3. Consider the number $\frac{r}{2} = \frac{p}{2q}$. Clearly, $\frac{r}{2}$ is a positive rational number, and it is smaller than $r$ (since $\frac{r}{2} < r$).

4. But this contradicts our assumption that $r$ is the smallest positive rational number because we have found a smaller rational number, $\frac{r}{2}$.

5. Therefore, the assumption that there is a smallest positive rational number must be false.

Conclusion: There is no smallest positive rational number.

Example 3: Proving $\sqrt{3}$ is Irrational (Another Classic Proof)

Statement: Prove that $\sqrt{3}$ is irrational.

Proof (by contradiction):

1. Assume the opposite: Suppose $\sqrt{3}$ is rational. This means $\sqrt{3} = \frac{p}{q}$, where $p$ and $q$ are integers and $q \neq 0$, with $p$ and $q$ having no common factors (i.e., the fraction is in its simplest form).

2. Square both sides:

   $$3 = \frac{p^2}{q^2} \quad \Rightarrow \quad p^2 = 3q^2$$

   This shows that $p^2$ is divisible by 3, meaning $p$ is divisible by 3 (since 3 is a prime number, if $p^2$ is divisible by 3, so is $p$).

3. Therefore, $p = 3k$ for some integer $k$.

4. Substitute $p = 3k$ into the equation $p^2 = 3q^2$:

   $$(3k)^2 = 3q^2 \quad \Rightarrow \quad 9k^2 = 3q^2 \quad \Rightarrow \quad 3k^2 = q^2$$

   This shows that $q^2$ is divisible by 3, so $q$ must also be divisible by 3.

5. But this contradicts our assumption that $p$ and $q$ have no common factors, because we have shown that both $p$ and $q$ are divisible by 3.

6. Therefore, our assumption that $\sqrt{3}$ is rational must be false.

Conclusion: $\sqrt{3}$ is irrational.

Summary of Proof by Contradiction

• Proof by contradiction is a powerful method where we assume the negation of the statement we want to prove and show that this assumption leads to an absurdity or contradiction.
• The contradiction implies that the assumption is false, and therefore, the original statement must be true.
• This method is especially useful when proving statements that are difficult to prove directly, such as the irrationality of numbers or properties involving the existence of certain objects.