Proof by Contradiction

The Logic of Proof by Contradiction

Unlike a direct or contrapositive proof where you have a clear starting point (the hypothesis) and a fixed destination (the conclusion), a proof by contradiction is more of an exploration. You begin by assuming the opposite of what you want to prove and then use logical steps to arrive at any statement that is patently false—a contradiction.

The following resource provides an excellent overview of the logical foundation for this method.

As the text explains, the strategy is as follows:

To Prove a Statement $P$:

1. Assume $\neg P$. Start by supposing, for the sake of argument, that the statement you wish to prove is false.
2. Deduce a contradiction. Using this assumption as your starting point, proceed with logical deductions until you arrive at a statement that is impossible. This could be a statement and its negation ($C\wedge \neg C$), or a mathematical falsehood like $1=0$.
3. Conclude $P$. Since the assumption $\neg P$ leads to an absurdity, the assumption must have been wrong. Therefore, the original statement $P$ must be true.

Example 1: A Fundamental Property of Integers

Let's begin with a very clear example that demonstrates the power and structure of this method. We will prove a statement that seems intuitively obvious but is best proven by contradiction: "No integer is both even and odd."

The following video from Dr. Trefor Bazett will walk you through this proof.

Let's formalize the argument presented in the video.

Proposition: No integer is both even and odd.

Proof.
We proceed by contradiction. Assume there exists an integer $n$ that is both even and odd.

By the definition of an even integer, there exists an integer $k_1$ such that $n=2k_1$.
By the definition of an odd integer, there exists an integer $k_2$ such that $n=2k_2+1$.

Since both expressions are equal to $n$, we can set them equal to each other:
$2k_1=2k_2+1$
Subtracting $2k_2$ from both sides gives:
$2k_1-2k_2=1$
Factoring out the 2 on the left side gives:
$2(k_1-k_2)=1$
Dividing by 2 gives:
$k_1-k_2=\frac{1}{2}$
Since $k_1$ and $k_2$ are integers, their difference, $k_1-k_2$, must also be an integer. However, we have shown that this difference is equal to $\frac{1}{2}$, which is not an integer. This is a contradiction.

Therefore, our initial assumption that there exists an integer that is both even and odd must be false. We conclude that no integer is both even and odd. □

Example 2: Proving Irrationality

Proof by contradiction is the classic method for proving that certain numbers are irrational. The strategy is to assume the number is rational and show that this assumption leads to a contradiction.

Let's prove the famous result that $\sqrt{2}$ is irrational. This proof dates back to ancient Greece and is a cornerstone of number theory.

Let's review the structure of this elegant argument:

Proposition: The number $\sqrt{2}$ is irrational.

Proof.
Suppose, for the sake of contradiction, that $\sqrt{2}$ is rational. By the definition of a rational number, there exist integers $a$ and $b$, with $b\ne 0$, such that $\sqrt{2}=\frac{a}{b}$. Furthermore, we can assume that this fraction is in lowest terms, meaning that $a$ and $b$ share no common factors other than 1.

Squaring both sides of the equation gives $2=\frac{a^2}{b^2}$, which rearranges to $a^2=2b^2$.
This shows that $a^2$ is an even integer. From our work in the previous lesson, we know that if $a^2$ is even, then $a$ must also be even.
Since $a$ is even, it can be written as $a=2k$ for some integer $k$.

Substituting $a=2k$ back into the equation $a^2=2b^2$ gives:
$(2k{)}^2=2b^2$
$4k^2=2b^2$
$2k^2=b^2$
This equation shows that $b^2$ is an even integer, which in turn implies that $b$ must also be even.

We have now concluded that both $a$ and $b$ are even. This means they share a common factor of 2. However, this contradicts our initial assumption that the fraction $\frac{a}{b}$ was in lowest terms.

Since our initial assumption leads to a contradiction, the assumption must be false. Therefore, $\sqrt{2}$ is irrational. □

Contradiction vs. Contrapositive for Conditional Statements

You now have two indirect proof methods: contrapositive and contradiction. How do they relate, and when should you choose one over the other?

For a conditional statement $P\to Q$:

• Proof by Contrapositive: You assume $\neg Q$ and must prove $\neg P$. Your start and end points are fixed.
• Proof by Contradiction: You assume $P\wedge \neg Q$ and must derive any contradiction. Your end point is flexible.

Often, a proof by contradiction of a conditional statement implicitly contains a proof by contrapositive. It is generally considered more elegant to use the most direct method that works.

The key insight is that if your proof by contradiction of $P\to Q$ starts by assuming $P\wedge \neg Q$ and ends by showing $\neg P$, you have just contradicted your assumption $P$. In this specific scenario, you have essentially just proven $\neg Q\to \neg P$, which is a proof by contrapositive. If you notice this pattern, it's often better to re-write the proof in the more direct contrapositive form.

However, if your proof ends in a different contradiction (e.g., $1=0$, or $a\ne a$), then proof by contradiction was the necessary tool.

Conclusion

You have now learned to construct proofs by contradiction, one of the most powerful tools in a mathematician's arsenal.

Here are the key takeaways:

• Proof by contradiction works by assuming the negation of a statement ($\neg P$) and deriving a logical impossibility.
• The structure is: Assume $\neg P$, perform logical deductions, arrive at a contradiction, and conclude that $P$ must be true.
• For conditional statements $P\to Q$, this means assuming $P$ and $\neg Q$ and finding a contradiction.
• This method is extremely useful for proving non-existence or irrationality, where a direct construction is often impossible.
• When proving a conditional, always consider if a simpler direct or contrapositive proof exists before resorting to contradiction.

You now have a solid foundation in the three primary methods of proof: direct, contrapositive, and contradiction. In our next lesson, we will introduce a completely new principle of proof designed specifically for statements involving natural numbers: the principle of mathematical induction. This will open the door to proving a vast new class of theorems.