A Different Implication, the Same Claim
In Direct Proof, we established implications by assuming their hypotheses and deriving their conclusions. Sometimes the hypothesis is difficult to use, while the negation of the conclusion gives a convenient equation or inequality. Proof by contrapositive allows us to start with that more useful information without changing the claim being proved.
Both the direction and the statements change: we begin with the negation of the original conclusion and aim for the negation of the original hypothesis. Merely reversing the arrow does not produce a contrapositive.
Proof. By the logical meaning of implication, \(P\Longrightarrow Q\) is false exactly when \(P\) is true and \(Q\) is false. The implication \(\neg Q\Longrightarrow\neg P\) is false exactly when \(\neg Q\) is true and \(\neg P\) is false. These are precisely the same conditions: \(Q\) is false and \(P\) is true. Thus the two implications are false in exactly the same circumstances and true in all the remaining circumstances. They are therefore logically equivalent.
The argument we write for \(\neg Q\Longrightarrow\neg P\) is usually a direct proof. We assume \(\neg Q\), make justified deductions, and obtain \(\neg P\). The logical equivalence then establishes \(P\Longrightarrow Q\).
Do Not Confuse the Contrapositive with the Converse
| Statement | Form | Equivalent to the original? |
|---|---|---|
| Original implication | \(P\Longrightarrow Q\) | Yes |
| Contrapositive | \(\neg Q\Longrightarrow\neg P\) | Yes |
| Converse | \(Q\Longrightarrow P\) | Not in general |
| Inverse | \(\neg P\Longrightarrow\neg Q\) | Not in general |
For example, the theorem from Introduction to Mathematical Proof states that, for real \(x\), \(x>1\) implies \(x^2>1\). Its contrapositive is
Its converse, \(x^2>1\Longrightarrow x>1\), is false: \(x=-2\) has \(x^2=4>1\), but \(x\) is not greater than \(1\). The same input disproves the inverse, \(x\leq1\Longrightarrow x^2\leq1\).
A converse may be true for a particular theorem, but it then requires its own justification. The equivalence with the contrapositive, by contrast, holds for every implication.
Negate the Exact Statement
The main source of mistakes is often not the deduction but the translation into a contrapositive. Negation must include every way that a statement can fail.
| Statement | Its negation |
|---|---|
| \(x>a\) | \(x\leq a\) |
| \(x\leq a\) | \(x>a\) |
| \(x=a\) | \(x\neq a\) |
| \(A\) and \(B\) | \(\neg A\) or \(\neg B\) |
| \(A\) or \(B\) | \(\neg A\) and \(\neg B\) |
| \(\exists t\in D,\ R(t)\) | \(\forall t\in D,\ \neg R(t)\) |
| \(\forall t\in D,\ R(t)\) | \(\exists t\in D,\ \neg R(t)\) |
The inequality rows concern real numbers. The compound-statement rows are De Morgan’s laws, with “or” understood inclusively: one or both statements may hold. The quantifier rows keep the same domain \(D\).
For a universal claim
we prove \(\neg Q(x)\Longrightarrow\neg P(x)\) for an arbitrary \(x\in D\). The outer universal quantifier stays in place. We are replacing each implication by its contrapositive, not negating the entire universal claim.
A Complete Proof with a Compound Conclusion
The conclusion permits either input, or both inputs, to be positive. Its negation says that neither is positive, so both are nonpositive. The contrapositive is therefore
Proof. We prove the contrapositive. Let \(x,y\in\mathbb R\) be arbitrary and suppose \(x\leq0\) and \(y\leq0\). Adding \(y\) to the first inequality gives \(x+y\leq y\). Combining this with \(y\leq0\), transitivity gives \(x+y\leq0\). This proves the contrapositive, and hence the original implication.
This argument includes \(x=0\) or \(y=0\); there is no need for an extra boundary argument. If we had assumed only \(x<0\) and \(y<0\), we would not have proved the full contrapositive.
The conclusion cannot be strengthened to say that both inputs are positive. For instance, \(x=2\) and \(y=-1\) give \(x+y=1>0\), although \(y<0\). Correctly identifying the word “or” is essential both to the statement and to its proof.
Reusing an Earlier Direct Proof
Sometimes the contrapositive is already an established theorem. In that case, the work consists of identifying it accurately and checking its hypotheses.
Worked Example: A Sum That Is Not Even
Claim. For integers \(m,n\), if \(m+n\) is not even, then \(m\) is not even or \(n\) is not even.
Translation. The negation of the conclusion is that \(m\) and \(n\) are both even. The negation of the hypothesis is that \(m+n\) is even. Thus the contrapositive says that the sum of two even integers is even.
Proof. We prove the contrapositive. Let \(m,n\in\mathbb Z\) and suppose both are even. By the result proved in Direct Proof, the sum of two even integers is even. Hence \(m+n\) is even, which proves the contrapositive and therefore the claim.
We do not need to repeat the integer-witness calculation from the previous tutorial. The established result applies to every pair of even integers, including zero and negative inputs.
The conclusion also does not identify which integer is not even. It guarantees at least one. For example, \(m=2,n=3\) satisfy the hypothesis, but \(m\) is even. A proof cannot conclude more than the claim and its assumptions support.
Keep the Domain Restrictions
Domain restrictions specify the inputs under discussion. They remain available when we pass to the contrapositive. This is especially important for expressions such as reciprocals, which may not be defined on a larger domain.
Worked Example: Recovering the Order from Reciprocals
Claim. For positive real numbers \(a,b\), if \(1/b<1/a\), then \(a<b\).
Contrapositive. For positive real numbers \(a,b\), if \(a\geq b\), then \(1/b\geq1/a\).
Proof. We prove the contrapositive. Let \(a,b>0\) and suppose \(a\geq b\). If \(a=b\), then \(1/b=1/a\), so the required non-strict inequality holds. If \(a>b\), then \(0<b<a\). Applying the reciprocal comparison proved in Direct Proof to these ordered inputs gives \(1/a<1/b\). Again, \(1/b\geq1/a\). The cases \(a=b\) and \(a>b\) exhaust \(a\geq b\), so the contrapositive is proved.
Positivity was not discarded or negated: it describes the domain of this implication. It guarantees that both reciprocals exist and allows us to apply the earlier theorem. The equality case matters because the negation of \(a<b\) is \(a\geq b\), not merely \(a>b\).
A Contrapositive with a Quantified Statement
A hypothesis or conclusion may itself contain a quantifier. The same method applies, but forming its negation may change “every” to “some,” or “some” to “every.”
Worked Example: No Real Number Strictly Between
Claim. For real \(a,b\), if there is no real \(c\) satisfying \(a<c<b\), then \(a\geq b\).
Translation. Here the hypothesis is \(\neg\exists c\in\mathbb R,\ a<c<b\). Its negation is \(\exists c\in\mathbb R,\ a<c<b\). The negation of the conclusion \(a\geq b\) is \(a<b\). Consequently, the contrapositive is
Proof. We prove the contrapositive. Let \(a,b\in\mathbb R\) satisfy \(a<b\). By the midpoint result proved in Direct Proof, the real number \(c=(a+b)/2\) satisfies \(a<c<b\). Thus such a real number exists. This proves the contrapositive and hence the original claim.
The domain of \(c\) is essential. Replacing “real” by “integer” would produce a false claim: there is no integer strictly between \(0\) and \(1\), yet \(0\geq1\) is false. A logical transformation preserves the specified domain; it does not authorize changing it.
A Procedure for Proof by Contrapositive
Separate \(P\), \(Q\), and the restrictions on the arbitrary inputs.
Form \(\neg Q\Longrightarrow\neg P\), checking equality cases, “and” and “or,” and any quantifiers.
Assume \(\neg Q\) and derive \(\neg P\) using definitions, valid calculations, or established results.
State that the contrapositive has been proved and therefore the original implication holds.
Do not retain \(P\) as an extra assumption in step 3. The task is to derive \(\neg P\) from \(\neg Q\), together with the fixed domain restrictions and established facts. An argument that also assumes \(P\) has not directly proved the contrapositive as stated.
Check Your Understanding
For each proof, state the contrapositive before giving the argument. Preserve all domain restrictions and include boundary cases.
- For real \(x\), write the contrapositive, converse, and inverse of “if \(x>2\), then \(x>0\).” Which are true? Give counterexamples to any that are false.
- Prove by contrapositive that, for real \(x,y\), if \(x+y<0\), then \(x<0\) or \(y<0\). Why must the contrapositive allow \(x=0\) and \(y=0\)?
- Using the theorem from Direct Proof that the product of two odd integers is odd, prove that if an integer product \(mn\) is not odd, then \(m\) is not odd or \(n\) is not odd.
- Prove by contrapositive that, for real \(x\), if \((x-1)^2\leq1\), then \(x\leq2\). Use the implication \(x>2\Longrightarrow(x-1)^2>1\) proved in the previous tutorial.
- An attempted contrapositive proof of \(P\Longrightarrow Q\) assumes \(\neg P\) and derives \(\neg Q\). Which implication has actually been proved? Explain why this does not establish the original claim in general.
- For real \(a,b\), write “there is no real \(c\) with \(a<c<b\)” using a universal quantifier and a disjunction of inequalities. Explain why “every real \(c\) satisfies \(c\leq a\) and \(c\geq b\)” is not the correct translation.