Proof by Contradiction

Proving That Failure Is Impossible

In Proof by Contrapositive, we proved an implication by showing that failure of its conclusion forces failure of its hypothesis. Proof by contradiction uses a related idea: temporarily assume that the statement to be proved is false, and show that this assumption cannot be consistent with the hypotheses and established facts.

Proof by contradiction. To prove a statement \(S\), assume its negation \(\neg S\) and derive a contradiction by valid deductions. A contradiction is an impossibility, such as a statement \(R\) together with its negation \(\neg R\). Conclude that \(\neg S\) is false and hence that \(S\) is true.

This method is also called reductio ad absurdum. The temporary assumption is not a claim that the negation is actually true. It is an assumption whose consequences we investigate in order to rule it out.

Logical justification. In classical logic, a statement is either true or false. If \(S\) were false, then \(\neg S\) would be true. Valid deductions from that assumption and the true hypotheses would then yield true conclusions. But they cannot yield both \(R\) and \(\neg R\), since these cannot both be true. Thus \(S\) cannot be false, so it is true.

The same reasoning applies when the final impossibility is written as \(0=1\), \(a<a\), or a statement contradicting an established theorem. The essential requirement is that the impossibility follows from justified steps, not from an algebraic error or an unrelated false assumption.

Contradiction and Contraposition

For an implication \(P\Longrightarrow Q\), the negation is not \(\neg P\Longrightarrow\neg Q\). An implication fails exactly when its hypothesis is true and its conclusion is false. Thus

\neg(P\Longrightarrow Q) \quad\Longleftrightarrow\quad P\text{ and }\neg Q.

To prove an implication by contradiction, we therefore assume both \(P\) and \(\neg Q\). Domain restrictions remain in force, just as they did in a contrapositive proof.

Method for \(P\Longrightarrow Q\)	Assume	Derive
Direct proof	\(P\)	\(Q\)
Proof by contrapositive	\(\neg Q\)	\(\neg P\)
Proof by contradiction	\(P\) and \(\neg Q\)	An impossibility

All three methods may use the fixed domain restrictions and established results. In a contradiction proof, the impossibility need not be a direct denial of the original hypothesis. Any genuine contradiction is sufficient.

Worked Example: Revisiting a Positive Sum

Claim. For real \(x,y\), if \(x+y>0\), then \(x>0\) or \(y>0\).

Proof by contradiction. Let \(x,y\in\mathbb R\) satisfy \(x+y>0\). Suppose, for a contradiction, that the conclusion is false. By De Morgan’s laws, this means \(x\leq0\) and \(y\leq0\). Adding gives \(x+y\leq0\). We now have both \(x+y>0\) and \(x+y\leq0\), which are incompatible. Therefore the conclusion cannot be false: \(x>0\) or \(y>0\).

The previous tutorial proved this claim by contraposition. The calculation is the same, but its role differs. There, deriving \(x+y\leq0\) completed the contrapositive. Here, it contradicts the retained hypothesis \(x+y>0\).

Closely related, but not identical in presentation. A contrapositive proof of \(P\Longrightarrow Q\) can be turned into a contradiction proof by also assuming \(P\), then deriving \(\neg P\). When the argument naturally establishes \(\neg Q\Longrightarrow\neg P\), stating it as a contrapositive is often simpler.

Negating the Whole Claim

Before making a temporary assumption, identify exactly what is being proved. The negation rules from the previous tutorial still apply, but now we negate the target statement itself.

Target statement	Assumption for contradiction
\(\forall x\in D,\ R(x)\)	There is an \(x\in D\) with \(\neg R(x)\)
\(\exists x\in D,\ R(x)\)	For every \(x\in D\), \(\neg R(x)\)
\(\neg\exists x\in D,\ R(x)\)	There is an \(x\in D\) with \(R(x)\)
\(\forall x\in D,\ P(x)\Longrightarrow Q(x)\)	There is an \(x\in D\) with \(P(x)\) and \(\neg Q(x)\)

For a universal claim, the temporary assumption supplies a hypothetical counterexample. We do not choose a convenient numerical value for it: we must show that any object with the asserted counterexample properties would lead to an impossibility.

For a nonexistence claim, the temporary assumption instead supplies the object whose existence is being ruled out. Its defining properties become available for the argument.

There Is No Least Positive Real Number

A least positive real number would be a real number \(m>0\) satisfying \(m\leq x\) for every positive real number \(x\). “Least” does not mean merely small: it requires a comparison with every member of the specified collection.

Theorem. There is no least positive real number. In symbols,

\neg\exists m\in\mathbb R,\quad \bigl(m>0\text{ and } \forall x\in\mathbb R,\ (x>0\Longrightarrow m\leq x)\bigr).

Proof. Suppose, for a contradiction, that a least positive real number \(m\) exists. Then \(m>0\), and \(m\leq x\) for every positive real \(x\).

By the midpoint result proved in Direct Proof, applied to \(0<m\), the real number \(c=(0+m)/2=m/2\) satisfies

$$ 0<c<m. $$

Since \(c\) is positive, the assumed leastness of \(m\) gives \(m\leq c\). Combining \(m\leq c\) with \(c<m\) gives \(m<m\), which is impossible. Hence a least positive real number does not exist.

Notice that both parts of \(0<c<m\) are needed. The inequality \(c<m\) makes \(c\) smaller than the proposed least number. The inequality \(0<c\) makes it eligible for the comparison: a negative number smaller than \(m\) would not contradict leastness among positive numbers.

The domain controls the contradiction. Zero is not a positive real number, so choosing \(c=0\) would not work. Nor does the argument apply unchanged to positive integers: half of a positive integer need not be an integer.

A Contradiction from a Positive Gap

A useful pattern in inequality proofs is to suppose that two numbers have the wrong order, then use the resulting positive difference to choose a number that violates a universal hypothesis. This requires only elementary algebra and the meaning of “for every.”

Theorem. Let \(a,b\in\mathbb R\). If \(a<b+\varepsilon\) for every positive real number \(\varepsilon\), then \(a\leq b\).

Proof. Let \(a,b\in\mathbb R\) satisfy the stated hypothesis. Suppose, for a contradiction, that \(a>b\). Then \(a-b>0\), so

\varepsilon_0=\frac{a-b}{2}

is a positive real number. The hypothesis applies to every positive real number, so in particular it applies to \(\varepsilon_0\). It gives

a<b+\varepsilon_0 =b+\frac{a-b}{2} =\frac{a+b}{2}.

But the midpoint result, applied to \(b<a\), gives \((a+b)/2<a\). Consequently,

a<\frac{a+b}{2}<a,

which implies \(a<a\), a contradiction. Thus \(a>b\) is impossible, and \(a\leq b\).

The choice of \(\varepsilon_0\) depends on the hypothetical gap \(a-b\). This is legitimate because the hypothesis covers every positive real number, including this one. We checked positivity before applying the hypothesis.

Why “Every” and the Equality Case Matter

If the hypothesis held for only one positive \(\varepsilon\), the conclusion could fail. For example, \(a=2\), \(b=1\), and \(\varepsilon=2\) give \(a<b+\varepsilon\), since \(2<3\), but \(a\leq b\) is false.

The conclusion also cannot be strengthened to \(a<b\). Taking \(a=b=1\), we have \(1<1+\varepsilon\) for every \(\varepsilon>0\), although \(a<b\) is false. Equality is consistent with the full hypothesis.

We did not substitute \(\varepsilon=0\); that value is excluded by the hypothesis. We also did not need any theory of limits. The proof used one positive number chosen to expose the impossibility of \(a>b\).

A Procedure for Proof by Contradiction

Identify the target and the standing hypotheses.
Write the statement \(S\) precisely, including domains and quantifiers.

Assume the exact negation.
State “Suppose, for a contradiction, that \(\neg S\).” For an implication, retain its hypothesis and deny its conclusion.

Make justified deductions.
Use the temporary assumption, standing hypotheses, definitions, and established results. Check that every constructed object lies in the required domain.

Identify the impossibility explicitly.
Name the incompatible statements or explain which established fact has been contradicted.

Discharge the temporary assumption.
Conclude that \(\neg S\) is impossible under the hypotheses, and therefore \(S\) holds.

What Does Not Count as a Contradiction?

An unexpected conclusion is not necessarily an impossible one. Deriving \(x=0\) is a contradiction only if the assumptions or established facts also rule out \(x=0\). Likewise, obtaining a negative number is not contradictory unless that quantity is known to be nonnegative.

A calculation error cannot establish a theorem. If an argument divides by a quantity that might be zero and later obtains \(0=1\), the invalid division—not necessarily the temporary assumption—is responsible for the failure.

Nor may we introduce an arbitrary extra assumption and then reject the negation of the target when a contradiction occurs. To prove there is no least positive real number, for example, we cannot assume that the proposed least number equals \(1\). Ruling out that particular candidate would leave every other candidate untreated.

A contradiction must have the right source. Keep the hypotheses fixed, add the negation of the target, and use only valid consequences. The final impossibility then rules out that negation. Do not assume the target itself merely to contradict its negation; that would be circular reasoning.

Contradiction is especially useful when denying the claim supplies a concrete object or a positive gap. It is not automatically preferable to a direct proof. The best presentation is the one that makes the logical dependencies easiest to verify.

Check Your Understanding

For each requested proof, state the temporary assumption and identify the exact contradiction before concluding.

Write the negation of “for every real \(x\), if \(x>2\), then \(x>0\).” Use that negation to prove the statement by contradiction.
Prove by contradiction that there is no greatest negative real number. A greatest negative real number would be a real \(m<0\) with \(x\leq m\) for every negative real \(x\). Why is \(m/2\) an admissible comparison?
Let \(a,b\in\mathbb R\). Prove that if \(a\leq b+\varepsilon\) for every \(\varepsilon>0\), then \(a\leq b\). Explain why the same choice \(\varepsilon_0=(a-b)/2\) still works under the assumption \(a>b\).
An attempted proof that there is no least positive real number assumes a least positive number \(m\), then observes that \(-1<m\). Why is this not a contradiction? What additional property must the smaller comparison number have?
An argument for \(P\Longrightarrow Q\) assumes \(P\) and \(\neg Q\), then derives \(\neg P\). Explain why this is a contradiction proof. What would need to be checked before presenting its deductions as a proof by contrapositive?
For real \(x\), prove by contradiction that \(3x+2=8\) implies \(x=2\). If an attempted proof instead ends with \(x=2\) without having assumed \(x\neq2\), is it invalid, or is it a different proof method?

What You'll Learn