Proof by Contradiction

Precise definition

To prove a statement $P$ by contradiction, assume its negation $\neg P$ and derive a contradiction: a statement known false, such as $R\land\neg R$, or a violation of an established definition or theorem. Because $\neg P$ cannot hold consistently with the accepted premises, $P$ must be true.

Notation and mathematical language

Negation must respect quantifiers: $\neg(\forall x\,P(x))\equiv\exists x\,\neg P(x)$ and $\neg(\exists x\,P(x))\equiv\forall x\,\neg P(x)$. For an implication, $\neg(P\to Q)\equiv P\land\neg Q$, so both a true premise and false conclusion are assumed.

Conceptual picture

A contradiction proof explores what the world would have to look like if the claim failed. The argument is complete only when that hypothetical world conflicts with the theorem's other hypotheses or accepted facts. A surprising or unlikely consequence is not enough.

Conditions and key results

Classical contradiction uses the law of excluded middle. The contradictory statement must arise from the negated claim together with legitimate premises, not from an unrelated false assertion. When proving irrationality, reduce fractions to lowest terms so that the final common-factor contradiction is licensed.

A reliable strategy

1. Write the exact logical negation of the claim, including domains and quantifiers.
2. Assume that negation together with all original hypotheses.
3. Derive consequences using definitions and established results until an explicit incompatibility appears.
4. Name the contradiction and conclude that the assumed negation is false, hence the original statement true.

Fully worked example

Interpretation and application

Contradiction is powerful for impossibility, uniqueness, irrationality, and infinitude results. In applied arguments, 'the model predicts an impossible value' may instead reveal that a modelling assumption fails; it does not automatically prove a real-world claim outside the model.

Common mistakes

Verification and reasonableness

• Underline the exact pair of incompatible claims at the end.
• Check that every step depends only on accepted facts, hypotheses, or the temporary negation.
• Translate the conclusion back: the contradiction rejects the negation, not an unrelated premise.

Practice

1. Negate 'every graph is connected.'
2. Why assume $a/b$ is in lowest terms in the $\sqrt2$ proof?
3. Is 'the result seems unlikely' a contradiction?

Further deduction

A classic infinitude proof assumes finitely many primes $p_1,\ldots,p_k$ and considers $N=p_1\cdots p_k+1$. No listed prime divides $N$, since each leaves remainder 1. Yet every integer greater than 1 has a prime divisor, producing a prime absent from the supposedly complete list. The proof does not claim $N$ itself is prime; making that stronger, unnecessary claim is a common misunderstanding of the construction.

Contradiction is naturally a classical-logic method because it uses that $\neg\neg P$ yields $P$. In constructive settings, deriving a contradiction from $\neg P$ may establish only the impossibility of refutation unless additional principles are accepted; the proof system should be understood.

Related topics

• Methods of Proof
• Logical Equivalence
• Direct Proof