Proof by contrapositive

A proof by contrapositive is an indirect proof that proves a theorem is true by showing that the negation of its conclusion implies the negation of its hypotheses. Proving the contrapositive \(\lnot q \rightarrow \lnot p\) of a conditional statement \(p \rightarrow q\) is the same as proving the conditional statement itself, because they are logically equivalent.

This kind of proof is preferred over a direct proof when the negation of the conclusion is a much simpler assumption than the hypotheses. When I say "much simpler," I mean that assuming the negation of the conclusion should provide you with either a less complicated expression to work with, or an expression to work with in the first place.

Proofs by contrapositive especially shine when dealing with irrational numbers. The statement "\(r\) is irrational" does not give you a clear expression to work with, but its negation allows you to use the definition of a rational number.

To negate the hypotheses and conclusion, you'll probably need to use De Morgan's laws.

⚠ Proofs by contrapositive can only be used on theorems that are conditional statements of the form "if ... then ..." Proofs by contradiction do not have this limitation. Really, a proof by contrapositive is a proof by contradiction where the contradiction is between the hypotheses and the negation of the hypotheses.
Contents

With multiple hypotheses

If you want to use a proof by contrapositive to prove a theorem that has multiple hypotheses, you need to show that the negation of one of the hypotheses results from assuming the other hypotheses (not their negations!) and the negation of the conclusion. Since this can quickly get complicated, it is best to write out exactly what you are assuming and what you are trying to prove.

In a direct proof with multiple hypotheses, you assume the hypotheses \(h_1 ... h_n\) and show the conclusion \(c\):

\((h_1 \land ... \land h_n) \rightarrow c\)

In a proof by contrapositive, you assume the negation of the conclusion and show the negation of the hypotheses:

\(\lnot c \rightarrow \lnot (h_1 \land ... \land h_n)\)

By De Morgan's law:

\(\lnot c \rightarrow (\lnot h_1 \lor ... \lor \lnot h_n)\)

As you can see, proving the contrapositive with multiple hypotheses means showing that the negation of the conclusion implies that at least one of the negated hypotheses are true. (Remember that just one proposition in a disjunction has to be true for the whole disjunction to be true!) In other words, you are allowed to assume all but one hypothesis is true. This statement then becomes:

\((\lnot c \land (h_2 \land ... \land h_n)) \rightarrow \lnot h_1\)

In this statement, \(h_1\) is the hypothesis you have chosen to prove the negation of. It could be any of the hypotheses. Just make sure you assume the rest are true.

Logic & Proofs
Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form
Set Theory
Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof
Functions
Function • Floor function • Ceiling function • Inverse function
Algorithms
Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm
Relations
Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class
Number Theory
Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm
Induction
Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition
Combinatorics
Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle
Graph Theory
Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm
Recursion
Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort