The Central Idea
Suppose we want to prove
\[ P\Longrightarrow Q. \]Its contrapositive is
\[ \neg Q\Longrightarrow\neg P. \]These two statements are logically equivalent:
\[ \boxed{P\Longrightarrow Q \quad\Longleftrightarrow\quad \neg Q\Longrightarrow\neg P.} \]Therefore, proving the contrapositive proves the original conditional.
Why the Contrapositive Is Equivalent
A conditional statement \(P\Rightarrow Q\) is false only in the case where \(P\) is true and \(Q\) is false.
The contrapositive
\[ \neg Q\Rightarrow\neg P \]is false in exactly the same situation: \(\neg Q\) is true while \(\neg P\) is false, which means \(Q\) is false while \(P\) is true.
Because their truth values agree in every case, the two statements are logically equivalent.
Conditional, Converse, Inverse, and Contrapositive
Starting with
\[ P\Longrightarrow Q, \]four related statements are commonly considered:
- conditional: \(P\Rightarrow Q\);
- converse: \(Q\Rightarrow P\);
- inverse: \(\neg P\Rightarrow\neg Q\);
- contrapositive: \(\neg Q\Rightarrow\neg P\).
Only the contrapositive is automatically equivalent to the original conditional.
A Simple Example
Consider the statement
\[ \text{If an integer }n\text{ is divisible by }4,\text{ then }n\text{ is even.} \]Let
\[ P:\;4\mid n \]and
\[ Q:\;n\text{ is even}. \]The contrapositive is
\[ \text{If }n\text{ is not even, then }4\nmid n. \]Since an integer that is not even is odd, this can be written
\[ \boxed{n\text{ odd}\Longrightarrow 4\nmid n.} \]Negation Must Be Done Carefully
Proof by contrapositive depends on constructing the correct negations.
If the conclusion is
\[ x>5, \]its negation is
\[ x\le 5, \]not merely \(x<5\).
If the conclusion is
\[ x\in A, \]its negation is
\[ x\notin A. \]The proof is only valid if the contrapositive has been formed correctly.
Negating Common Mathematical Statements
Some frequently used negations are:
\[ \neg(x>c)\quad\Longleftrightarrow\quad x\le c, \] \[ \neg(x\ge c)\quad\Longleftrightarrow\quad xWhen Contrapositive Proof Is Useful
A contrapositive proof is especially useful when the negated conclusion gives stronger or more concrete information than the original hypothesis.
Typical signals include statements involving:
- parity;
- divisibility;
- inequalities;
- set membership;
- injectivity;
- properties that are easier to characterize through failure.
The method is not inherently stronger than direct proof. It is simply a logically equivalent route that may expose a more useful starting point.
The Basic Procedure
To prove
\[ P\Longrightarrow Q \]by contrapositive:
- Identify \(P\) and \(Q\).
- Form the contrapositive \(\neg Q\Rightarrow\neg P\).
- Assume \(\neg Q\).
- Use definitions, algebra, and known results.
- Derive \(\neg P\).
- Conclude that the original statement \(P\Rightarrow Q\) is true.
Example: If \(n^2\) Is Even, Then \(n\) Is Even
Prove:
\[ n^2\text{ even}\Longrightarrow n\text{ even}. \]A direct proof begins with information about \(n^2\), but extracting the parity of \(n\) from that equation is less immediate.
The contrapositive is
\[ n\text{ odd}\Longrightarrow n^2\text{ odd}. \]Assume \(n\) is odd. Then
\[ n=2k+1 \]for some integer \(k\).
Square:
\[ n^2=(2k+1)^2. \]Expand:
\[ n^2=4k^2+4k+1. \]Factor:
\[ n^2=2(2k^2+2k)+1. \]Since \(2k^2+2k\) is an integer, \(n^2\) is odd.
Therefore the contrapositive is true, so
\[ \boxed{n^2\text{ even}\Longrightarrow n\text{ even}.} \]Why the Previous Example Favors Contrapositive
The original hypothesis says only that
\[ n^2=2m \]for some integer \(m\).
It is not immediately obvious from that form that \(n\) itself contains a factor of \(2\).
By contrast, the negation of the conclusion gives the explicit form
\[ n=2k+1, \]which can be squared directly.
Contrapositive proof often succeeds because the new hypothesis has a more usable algebraic representation.
Example: If \(n^2\) Is Odd, Then \(n\) Is Odd
Prove:
\[ n^2\text{ odd}\Longrightarrow n\text{ odd}. \]The contrapositive is
\[ n\text{ even}\Longrightarrow n^2\text{ even}. \]Assume \(n\) is even. Then
\[ n=2k \]for some integer \(k\).
Therefore,
\[ n^2=4k^2=2(2k^2). \]Since \(2k^2\in\mathbb Z\), \(n^2\) is even.
Thus the contrapositive is true, and therefore
\[ \boxed{n^2\text{ odd}\Longrightarrow n\text{ odd}.} \]Example: Divisibility by 6
Prove:
\[ 6\mid n\Longrightarrow 3\mid n. \]The contrapositive is
\[ 3\nmid n\Longrightarrow 6\nmid n. \]Assume \(3\nmid n\).
If \(6\mid n\), then \(n=6k=3(2k)\) for some integer \(k\), which would imply \(3\mid n\).
Therefore \(6\nmid n\).
Hence the contrapositive holds, so
\[ \boxed{6\mid n\Longrightarrow 3\mid n}. \]Direct Proof May Still Be Better
The previous divisibility theorem can be proved more simply by direct proof:
\[ 6\mid n \Longrightarrow n=6k \Longrightarrow n=3(2k) \Longrightarrow 3\mid n. \]This illustrates an important point: proof by contrapositive is a tool, not a rule that must be used whenever it is available.
Prefer the route that makes the logical structure clearest.
Example: A Product and Oddness
Prove that if \(ab\) is odd, then both \(a\) and \(b\) are odd integers.
The conclusion contains two claims:
\[ a\text{ is odd}\quad\text{and}\quad b\text{ is odd}. \]Its negation is
\[ a\text{ is even}\quad\text{or}\quad b\text{ is even}. \]The contrapositive is therefore:
\[ a\text{ even or }b\text{ even}\Longrightarrow ab\text{ even}. \]If \(a\) is even, then \(a=2k\) and
\[ ab=2(kb), \]so \(ab\) is even.
Likewise, if \(b\) is even, then \(ab\) is even.
Therefore,
\[ \boxed{ab\text{ odd}\Longrightarrow a\text{ and }b\text{ odd}.} \]De Morgan's Laws Matter
When a conclusion contains “and” or “or,” its negation must follow De Morgan's laws:
\[ \neg(P\land Q)\Longleftrightarrow(\neg P\lor\neg Q), \] \[ \neg(P\lor Q)\Longleftrightarrow(\neg P\land\neg Q). \]This is why the negation of
\[ a\text{ odd and }b\text{ odd} \]is
\[ a\text{ even or }b\text{ even}. \]Correct negation is one of the most important technical skills in contrapositive proof.
Example: An Inequality
Let \(x\in\mathbb R\). Prove:
\[ x^2>4\Longrightarrow |x|>2. \]The contrapositive is
\[ |x|\le2\Longrightarrow x^2\le4. \]Assume
\[ |x|\le2. \]Then
\[ -2\le x\le2. \]Equivalently,
\[ 0\le |x|\le2. \]Squaring preserves order for these nonnegative quantities:
\[ |x|^2\le4. \]Since \(|x|^2=x^2\),
\[ x^2\le4. \]Therefore the contrapositive holds, and
\[ \boxed{x^2>4\Longrightarrow |x|>2}. \]Negating Inequalities Correctly
The negation of a strict inequality includes equality:
\[ \neg(x>c)\Longleftrightarrow x\le c. \]Likewise,
\[ \neg(xExample: Set Membership
Suppose \(A\subseteq B\). Prove:
\[ x\notin B\Longrightarrow x\notin A. \]This is the contrapositive form of
\[ x\in A\Longrightarrow x\in B. \]Assume \(x\notin B\).
If \(x\) were in \(A\), then because \(A\subseteq B\), we would have \(x\in B\).
Therefore \(x\notin A\).
Hence
\[ \boxed{x\notin B\Longrightarrow x\notin A}. \]Contrapositive and Function Injectivity
A function \(f\) is injective when
\[ f(a)=f(b)\Longrightarrow a=b. \]Its contrapositive is
\[ a\ne b\Longrightarrow f(a)\ne f(b). \]Depending on the function, either form may be easier to prove.
The two formulations express the same logical requirement.
Example: An Injective Linear Function
Let
\[ f(x)=3x+1. \]To show \(f\) is injective using the contrapositive form, assume
\[ a\ne b. \]Then
\[ 3a\ne3b \]because multiplication by the nonzero number \(3\) preserves inequality.
Adding \(1\) to both sides gives
\[ 3a+1\ne3b+1. \]Thus
\[ f(a)\ne f(b). \]Therefore \(f\) is injective.
Example: A Square-Divisibility Result
Prove:
\[ 3\mid n^2\Longrightarrow 3\mid n. \]The contrapositive is
\[ 3\nmid n\Longrightarrow 3\nmid n^2. \]If \(3\nmid n\), then \(n\) has remainder \(1\) or \(2\) when divided by \(3\). Thus
\[ n=3k+1 \]or
\[ n=3k+2. \]In the first case,
\[ n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1. \]In the second case,
\[ n^2=(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1. \]In either case, \(n^2\) leaves remainder \(1\) upon division by \(3\), so \(3\nmid n^2\).
Therefore,
\[ \boxed{3\mid n^2\Longrightarrow 3\mid n}. \]Contrapositive Can Require Case Analysis
A proof by contrapositive describes the overall logical strategy, but the internal argument may still use other techniques.
In the previous example, the contrapositive proof required two cases:
\[ n\equiv1\pmod 3 \]or
\[ n\equiv2\pmod 3. \]Proof methods can therefore be nested. A contrapositive argument may contain direct reasoning, algebra, divisibility, or case analysis.
Contrapositive Is Not Contradiction
Proof by contrapositive and proof by contradiction can look similar because both may involve negation, but their structures are different.
Contrapositive:
\[ \text{assume }\neg Q\quad\text{and prove }\neg P. \]Contradiction:
\[ \text{assume a statement you want to rule out and derive an impossibility.} \]A contrapositive proof does not need to end in a contradiction. It ends by establishing the negation of the original hypothesis.
Example: Distinguishing the Two Methods
Suppose the goal is
\[ n^2\text{ even}\Longrightarrow n\text{ even}. \]A contrapositive proof assumes
\[ n\text{ odd} \]and proves
\[ n^2\text{ odd}. \]A contradiction proof could instead assume that \(n^2\) is even and \(n\) is odd, then derive an inconsistency.
The destination of the argument distinguishes the methods.
Contrapositive Is Not the Converse
If the original theorem is
\[ P\Longrightarrow Q, \]its contrapositive is
\[ \neg Q\Longrightarrow\neg P. \]Its converse is
\[ Q\Longrightarrow P. \]Proving the converse does not prove the original theorem.
Example: The Converse Can Fail
The statement
\[ 4\mid n\Longrightarrow 2\mid n \]is true.
Its contrapositive
\[ 2\nmid n\Longrightarrow 4\nmid n \]is also true.
But its converse
\[ 2\mid n\Longrightarrow 4\mid n \]is false. For example, \(n=6\) is divisible by \(2\) but not by \(4\).
Contrapositive Is Not the Inverse
The inverse of
\[ P\Longrightarrow Q \]is
\[ \neg P\Longrightarrow\neg Q. \]The inverse is logically equivalent to the converse, not to the original conditional.
In general,
\[ P\Rightarrow Q \]does not justify
\[ \neg P\Rightarrow\neg Q. \]Choosing between Direct Proof and Contrapositive
Before beginning a conditional proof, compare both possible starting points.
Direct proof starts with
\[ P. \]Contrapositive proof starts with
\[ \neg Q. \]Ask which one provides more usable mathematical structure.
If \(P\) immediately supplies an equation, factorization, set relation, or other useful form, direct proof may be best. If \(\neg Q\) supplies the clearer structure, contrapositive may be better.
Translate Before You Calculate
A reliable habit is to write the logical form before beginning algebra.
For example:
\[ P:\;n^2\text{ is even} \] \[ Q:\;n\text{ is even} \]Then:
\[ \neg Q:\;n\text{ is odd} \] \[ \neg P:\;n^2\text{ is odd}. \]Only after the contrapositive is correct should the algebraic proof begin.
Quantifiers Also Need Correct Negation
Negating quantified statements requires reversing the quantifier:
\[ \neg(\forall x\,P(x)) \Longleftrightarrow \exists x\,\neg P(x), \] \[ \neg(\exists x\,P(x)) \Longleftrightarrow \forall x\,\neg P(x). \]Thus the negation of
\[ \text{every element has property }P \]is
\[ \text{there exists an element that does not have property }P. \]This becomes increasingly important in more advanced contrapositive arguments.
Common Error: Negating Only Part of the Conclusion
Suppose the conclusion is
\[ x>0\text{ and }y>0. \]Its negation is not
\[ x\le0\text{ and }y\le0. \]By De Morgan's law, the correct negation is
\[ \boxed{x\le0\text{ or }y\le0.} \]Negating a compound statement requires negating its entire logical structure.
Common Error: Proving the Converse
Suppose the theorem is
\[ n^2\text{ even}\Longrightarrow n\text{ even}. \]Proving
\[ n\text{ even}\Longrightarrow n^2\text{ even} \]proves the converse, not the contrapositive.
The correct contrapositive is
\[ \boxed{n\text{ odd}\Longrightarrow n^2\text{ odd}.} \]Common Error: Negating \(>\) as \(<\)
If
\[ Q:\;x>7, \]then
\[ \neg Q:\;x\le7. \]Writing \(x<7\) omits the case \(x=7\), so it is not the complete negation.
Common Error: Assuming Both the Original and Contrapositive Hypotheses
In a contrapositive proof of
\[ P\Longrightarrow Q, \]the working assumption is \(\neg Q\).
We do not normally assume \(P\) as well. The goal is to derive \(\neg P\) from \(\neg Q\).
Mixing the hypotheses can obscure the logic or quietly turn the argument into a different proof method.
Common Error: Ending without Returning to the Original Statement
After proving
\[ \neg Q\Longrightarrow\neg P, \]explicitly state why this completes the proof:
Since the contrapositive is logically equivalent to the original conditional, \(P\Rightarrow Q\) follows.
That final sentence makes the proof strategy transparent.
A Reliable Contrapositive Workflow
- Write the original statement as \(P\Rightarrow Q\).
- Negate the conclusion carefully to obtain \(\neg Q\).
- Negate the hypothesis carefully to obtain \(\neg P\).
- Write the contrapositive \(\neg Q\Rightarrow\neg P\).
- Check that you did not accidentally write the converse or inverse.
- Assume \(\neg Q\).
- Translate definitions into mathematical structure.
- Derive \(\neg P\) using valid reasoning.
- State that the contrapositive has been proved.
- Conclude that the original conditional follows by logical equivalence.
Example: Full Contrapositive Workflow
Prove:
\[ n^2\text{ divisible by }2\Longrightarrow n\text{ divisible by }2. \]Step 1: Identify the statements.
\[ P:\;2\mid n^2 \] \[ Q:\;2\mid n. \]Step 2: Form the contrapositive.
\[ 2\nmid n\Longrightarrow 2\nmid n^2. \]For integers, \(2\nmid n\) means \(n\) is odd.
Step 3: Assume the contrapositive hypothesis.
\[ n=2k+1 \]for some integer \(k\).
Step 4: Derive the required conclusion.
\[ n^2=(2k+1)^2 \] \[ =4k^2+4k+1 \] \[ =2(2k^2+2k)+1. \]Therefore \(n^2\) is odd, so \(2\nmid n^2\).
Step 5: Return to the original theorem.
The contrapositive is true. Hence
\[ \boxed{2\mid n^2\Longrightarrow2\mid n}. \]Practice 1: Form the Contrapositive
Write the contrapositive of:
\[ n\text{ divisible by }8\Longrightarrow n\text{ even}. \]Practice 2: Parity
Prove by contrapositive:
\[ n^2\text{ even}\Longrightarrow n\text{ even}. \]Practice 3: Odd Squares
Prove by contrapositive:
\[ n^2\text{ odd}\Longrightarrow n\text{ odd}. \]Practice 4: Divisibility
Prove by contrapositive:
\[ 10\mid n\Longrightarrow 5\mid n. \]Practice 5: Product Parity
Prove by contrapositive that if \(ab\) is odd, then both \(a\) and \(b\) are odd integers.
Practice 6: Inequality
For \(x\in\mathbb R\), prove by contrapositive:
\[ x^2>9\Longrightarrow |x|>3. \]Practice 7: Set Inclusion
Suppose \(A\subseteq B\). Prove:
\[ x\notin B\Longrightarrow x\notin A. \]Practice 8: Identify the Correct Negation
Negate the statement
\[ x>2\text{ and }y<5. \]Practice 9: Converse or Contrapositive?
The original statement is
\[ 6\mid n\Longrightarrow 3\mid n. \]Classify
\[ 3\nmid n\Longrightarrow 6\nmid n. \]Practice 10: Identify the Error
A student wants to prove
\[ n^2\text{ even}\Longrightarrow n\text{ even} \]by contrapositive but begins with “Assume \(n\) is even.”
Explain the error and state the correct starting assumption.
Practice Answers
Practice 1
The contrapositive is
\[ \boxed{n\text{ odd}\Longrightarrow 8\nmid n}. \]Practice 2
The contrapositive is
\[ n\text{ odd}\Longrightarrow n^2\text{ odd}. \]Write \(n=2k+1\). Then
\[ n^2=2(2k^2+2k)+1, \]so \(n^2\) is odd. Therefore the original statement holds.
Practice 3
The contrapositive is
\[ n\text{ even}\Longrightarrow n^2\text{ even}. \]Write \(n=2k\). Then
\[ n^2=4k^2=2(2k^2), \]so \(n^2\) is even.
Practice 4
The contrapositive is
\[ 5\nmid n\Longrightarrow10\nmid n. \]If \(10\mid n\), then \(n=10k=5(2k)\), which would imply \(5\mid n\). Therefore, if \(5\nmid n\), then \(10\nmid n\).
Practice 5
The contrapositive is:
\[ a\text{ even or }b\text{ even}\Longrightarrow ab\text{ even}. \]If \(a=2k\), then \(ab=2(kb)\). If instead \(b=2r\), then \(ab=2(ar)\). In either case \(ab\) is even. Therefore if \(ab\) is odd, both factors must be odd.
Practice 6
The contrapositive is
\[ |x|\le3\Longrightarrow x^2\le9. \]Since \(0\le|x|\le3\), squaring gives
\[ |x|^2\le9. \]Therefore \(x^2\le9\), proving the contrapositive.
Practice 7
Assume \(x\notin B\). If \(x\in A\), then \(A\subseteq B\) would imply \(x\in B\). Therefore \(x\notin A\), so
\[ \boxed{x\notin B\Longrightarrow x\notin A}. \]Practice 8
By De Morgan's law,
\[ \boxed{x\le2\text{ or }y\ge5}. \]Practice 9
It is the contrapositive.
The original statement has the form \(P\Rightarrow Q\), and the given statement has the form
\[ \neg Q\Rightarrow\neg P. \]Practice 10
Assuming \(n\) is even begins the converse
\[ n\text{ even}\Longrightarrow n^2\text{ even}. \]For the contrapositive, the correct starting assumption is
\[ \boxed{n\text{ is odd}.} \]The goal is then to prove that \(n^2\) is odd.
What to Remember
A conditional and its contrapositive are logically equivalent:
\[ \boxed{P\Longrightarrow Q \quad\Longleftrightarrow\quad \neg Q\Longrightarrow\neg P.} \]- negate the conclusion to create the new hypothesis;
- negate the original hypothesis to create the new conclusion;
- handle inequalities, conjunctions, disjunctions, and quantifiers carefully;
- do not confuse the contrapositive with the converse or inverse;
- use the contrapositive when \(\neg Q\) gives a more useful starting point;
- finish by connecting the proved contrapositive back to the original theorem.
The strategic question is: If proving \(Q\) from \(P\) is awkward, is proving \(\neg P\) from \(\neg Q\) easier?
Where We Go Next
Proof by contrapositive establishes a theorem by proving a logically equivalent conditional. Another major proof strategy begins differently: it assumes that a desired claim fails and then shows that this assumption leads to an impossibility.
The next lesson, Proof by Contradiction, develops that method and explains how contradictions can rule out impossible assumptions.