Proof by contradiction

Understanding Proof by Contradiction

Proof by contradiction is a specific strategy for proving a statement is true by assuming, temporarily, that it is false and then showing that this assumption leads to an impossibility.

In this chapter, we focus on how this technique works, why it is valid, and how to recognize when to use it. General ideas about what a proof is and other proof techniques are treated elsewhere; here we concentrate only on contradiction.

The Basic Idea

Suppose you want to prove a statement $P$ (for example, “$\sqrt{2}$ is irrational”).

A proof by contradiction follows this pattern:

1. Assume the negation of what you want to prove: assume “not $P$” is true.
2. Use this assumption, together with known facts and definitions, to reason carefully.
3. Arrive at a contradiction:
• either a statement and its negation at the same time (like $Q$ and $\lnot Q$),
• or something impossible (such as $1 = 0$ or “an integer is both even and odd”).
4. Conclude that your assumption “not $P$” must be false.
5. Therefore, $P$ must be true.

Symbolically, the structure is:

• From $\lnot P$ we derive a contradiction, written as $\bot$.
• So we know $\lnot P$ cannot hold.
• Hence $P$ is true.

The key feature: you never directly show $P$; you show that denying $P$ is impossible.

Why This Method Is Valid

The logical idea behind proof by contradiction is:

If assuming “not $P$” leads to an impossibility, then “not $P$” cannot be true, so $P$ must be true.

This relies on two logical principles:

• Non-contradiction: A statement and its negation cannot both be true at the same time.
• Excluded middle (in this context): For the kinds of statements we work with here, either $P$ is true or $\lnot P$ is true.

If we show that $\lnot P$ leads to a contradiction, then $\lnot P$ cannot be true, leaving $P$ as the only option.

You do not need to restate or prove these logical principles here; they are part of the logical background developed elsewhere.

Typical Structure of a Contradiction Proof

A written proof by contradiction usually has a recognizable shape. In words, it might look like:

1. State clearly what you want to prove.
2. Begin: “Suppose, for the sake of contradiction, that [the statement is false].”
3. Translate that assumption into a precise mathematical form.
4. Use definitions, earlier results, and algebra or other tools to derive consequences.
5. Point out the moment where you reach an impossibility.
6. Conclude: “This is a contradiction. Therefore our assumption was false, so [original statement] is true.”

The contradiction need not be something dramatic like $1=2$. Any clear impossibility—such as “$n$ is both even and odd”—is enough.

Common Types of Contradictions

When you work through a proof by contradiction, what kind of “impossibility” are you looking for? Common patterns include:

• A statement and its negation
  You derive both $Q$ and $\lnot Q$, for example:
• “$n$ is even” and “$n$ is odd”.
• “$x > 3$” and “$x \le 3$”.
• Violating a definition
  You reach a situation that contradicts the definition of a concept, such as:
• An “integer between 0 and 1”.
• A “prime number” that has more than two positive divisors.
• Contradicting a known theorem or fact
  You deduce something that contradicts a previously proved result, for example:
• Getting that “there are only finitely many primes” after using a theorem that there are infinitely many.
• Finding a “triangle” in Euclidean geometry whose angles do not satisfy the sum property that has already been proven.
• Impossible numerical equality or inequality
  Reaching something like:
• $1 = 0$,
• $5 < 2$,
• An integer strictly between two consecutive integers, e.g. “$3 < n < 4$ where $n$ is an integer”.

The important thing is to make the contradiction explicit: you should clearly show the conflict between what you have deduced and what must be true.

How Proof by Contradiction Differs from Direct Proof

In a direct proof, to show $P$ you start from given assumptions and build step by step until you reach $P$.

In a proof by contradiction, you start from $\lnot P$ and show that this leads to something impossible.

Why might you choose contradiction instead of a direct approach?

• Sometimes a direct route is unclear, but it is easier to see why denying the statement would create a problem.
• In many “existence” or “uniqueness” proofs, assuming the opposite makes contradictions easier to find.
• Some classic results in number theory and analysis are naturally approached this way.

However, in many elementary situations, a direct proof is possible and often shorter. Proof by contradiction is a tool to use when it feels natural or when other methods seem difficult.

General Template: Proving “If …, then …” by Contradiction

Many mathematical statements are of the form

$$
\text{If } P \text{, then } Q.
$$

A direct proof would assume $P$ and reason to $Q$.

A proof by contradiction starts differently. To prove “If $P$, then $Q$” by contradiction, you:

1. Assume $P$ is true.
2. Also assume that the conclusion fails: assume $\lnot Q$.
3. From $P$ and $\lnot Q$, derive a contradiction.
4. Conclude that $\lnot Q$ cannot be true when $P$ is true.
5. Therefore, if $P$ is true, $Q$ must be true.

Symbolically, you prove:
$$
P \land \lnot Q \Rightarrow \bot,
$$
and thus conclude:
$$
P \Rightarrow Q.
$$

So in this situation, your “contradiction assumption” is not simply $\lnot(P \Rightarrow Q)$ in words, but concretely: assume $P$ and assume $\lnot Q$.

Step-by-Step Strategy for Using Contradiction

Here is a practical way to approach a new problem where you might use contradiction:

1. Identify the statement to prove
   Make sure you can name it clearly as $P$ or “If $P$, then $Q$”, or some other logical form.
2. Write down the negation
• If you want to prove a simple statement $P$, its negation is $\lnot P$.
• If you want to prove “for all $x$, $P(x)$”, its negation is “there exists an $x$ for which $\lnot P(x)$”.
• If you want to prove “there exists an $x$ with $P(x)$”, its negation is “for all $x$, $\lnot P(x)$”.
• If you want to prove “If $P$, then $Q$”, its negation is “$P$ and not $Q$”.

Writing the negation correctly is crucial to a sound proof.

3. Assume the negation is true
   Begin your proof formally with something like “Suppose, for the sake of contradiction, that …” followed by the negation.
4. Use definitions and known results
   Expand your assumption using definitions. For instance, if you mention “even”, “odd”, “rational”, or “prime”, use their precise meanings. Also use any theorems you already know.
5. Manipulate carefully
   Work through algebraic or logical steps to see what your assumption forces to be true. Often you will:
• Rearrange equations,
• Compare sizes (inequalities),
• Consider divisibility properties,
• Or relate your object to a simpler or smaller example.
6. Search for a contradiction
   As you proceed, look for clashes with:
• earlier steps of your own argument,
• definitions,
• or known theorems and basic facts.
7. Highlight the contradiction clearly
   Do not assume the contradiction is obvious; state it explicitly, such as:
• “But now we have shown that $n$ is even and odd, which is impossible.”
• “This implies $3 < 2$, which cannot happen for real numbers.”
8. Conclude properly
   Finish by explaining:
• “Thus our assumption leads to a contradiction, so it must be wrong. Therefore, [original statement] holds.”

This closing step is part of the reasoning; it should not be skipped.

Recognizing Problems Suited to Contradiction

While you can, in theory, use contradiction for many statements, some patterns especially invite it:

• Statements denying the existence of something
  Example: “There is no integer solution to this equation.”
  You assume there is such a solution and derive a contradiction.
• Statements about impossibility
  Example: “There is no smallest positive real number.”
  Assuming such a smallest number often lets you build a smaller one, contradicting the assumption.
• Uniqueness statements
  Example: “There is exactly one object with this property.”
  You suppose there are two different ones and show they must be equal, contradicting their difference.
• Statements about infinite behavior or limits
  In more advanced contexts, contradiction is often used to show that certain “bad” behaviors cannot happen beyond some point.

If a direct approach looks complicated, try writing down the negation of what you want to prove. If the negation is easy to work with and seems to force something impossible, a proof by contradiction may be natural.

Clarity and Common Pitfalls

When writing a proof by contradiction, special care is needed to avoid confusion:

• Be clear about what you are assuming
  Early in the proof, mark the assumption explicitly:
  “Assume, for the sake of contradiction, that …”
• Do not quietly switch assumptions
  All reasoning should flow logically from the contradiction assumption and the existing facts. Avoid bringing in new, unsupported assumptions mid-proof.
• The contradiction must be genuine
  It is not enough to get something “weird” or surprising; the result must actually be impossible according to your definitions or already established results.
• State where the contradiction occurs
  Readers should be able to point to two lines (or one line and a known fact) that cannot both be true.
• Do not forget the conclusion
  Ending at “This is a contradiction” is incomplete. You must explicitly state that this means the initial assumption is false and the desired statement is true.

By paying attention to these points, you keep your proof both correct and readable.

Comparing with Related Techniques

Proof by contradiction is related to, but distinct from, other techniques:

• Direct proof: Proves $P$ by starting with given assumptions and working to $P$.
• Proof by contrapositive: Proves “If $P$, then $Q$” by proving the logically equivalent statement “If not $Q$, then not $P$”.

In practice, a proof by contrapositive can sometimes resemble a proof by contradiction because you start from “not $Q$”; however, in a contrapositive proof, you do not necessarily seek a contradiction; instead, you aim directly to “not $P$”. In a proof by contradiction, your explicit goal is to produce some sort of logical impossibility.

Understanding these distinctions helps you choose the style that best fits each problem.

Summary

• Proof by contradiction is a method of showing a statement is true by assuming it is false and deriving an impossibility.
• The general pattern is: assume $\lnot P$, derive a contradiction, and conclude $P$.
• For statements of the form “If $P$, then $Q$”, you assume $P$ and $\lnot Q$, then derive a contradiction.
• The contradiction may be a statement and its negation, a violation of a definition, a conflict with a known theorem, or an impossible equality or inequality.
• This technique is especially natural for proving impossibility, nonexistence, or uniqueness, and in many situations where a direct proof is hard to see.
• Clear assumptions, explicit contradictions, and a proper final conclusion are essential for a good proof by contradiction.

Later chapters on writing proofs will build on this logical idea to help you present contradiction arguments in a polished and structured way.