Proving Implications by Contraposition

Hello. In the previous lesson, you practiced direct proof: assume the hypothesis, unpack definitions, and build the conclusion. For instance, from an odd integer $n=2k+1$, you derived that $n^2$ is odd.

Sometimes, however, the hypothesis gives an awkward starting point. This lesson introduces a logically equivalent route: rather than proving $P⟹Q$ directly, prove that failure of $Q$ forces failure of $P$. By the end, you should be able to write a complete proof by contraposition and recognize when this method is strategically useful.

---

The contrapositive: reverse and negate

Given an implication

$$P⟹Q,$$

its contrapositive is

$$\neg Q⟹\neg P.$$

To form it, do two things:

1. Reverse the order of the statements.
2. Negate both statements.

The key fact is that an implication and its contrapositive always have the same truth value.

$P$	$Q$	$P⟹Q$	$\neg Q⟹\neg P$
True	True	True	True
True	False	False	False
False	True	True	True
False	False	True	True

Both implications fail in precisely the same situation: $P$ is true while $Q$ is false. Thus, once you prove the contrapositive, you have proved the original statement.

This is not a trick or a weaker substitute for a direct proof. It is a proof of a genuinely equivalent statement.

Consider the claim:

$$\text{If }{n}^2\text{ is even, then }n\text{ is even.}$$

Let

$$P=\text{“}{n}^2\text{ is even”}$$

and

$$Q=\text{“}n\text{ is even.”}$$

The contrapositive is:

$$\text{If }n\text{ is not even, then }{n}^2\text{ is not even.}$$

Since every integer is either even or odd, but not both, this becomes the much more useful statement

$$\text{If }n\text{ is odd, then }{n}^2\text{ is odd.}$$

That is exactly the result proved directly in the previous lesson. Therefore, the original claim follows.

Notice why the direct route is unattractive. Starting with

$$n^2=2k$$

does not naturally produce an expression of the form $n=2r$. Taking square roots does not help: it introduces $\sqrt{2k}$, which has no obvious connection to the definition of evenness. The contrapositive instead begins with the usable form

$$n=2k+1.$$

The method changes the direction of reasoning to one where the definitions cooperate.

---

The proof structure

For a universally quantified statement,

$$\forall x\in D,P(x)⟹Q(x),$$

a proof by contraposition has this structure:

Proof. We prove the contrapositive. Let $x$ be arbitrary in $D$. Assume $\neg Q(x)$.
[Use definitions, hypotheses, and prior results to derive $\neg P(x)$.]
Therefore $\neg Q(x)⟹\neg P(x)$. Hence $P(x)⟹Q(x)$. $\square$

The middle of the proof is still a direct proof. You assume the antecedent of the contrapositive and derive its consequent. What makes the overall method indirect is that the statement being directly proved is the contrapositive rather than the theorem as initially stated.

A useful planning table is:

Original implication	Contrapositive proof
Assume $P$	Assume $\neg Q$
Prove $Q$	Prove $\neg P$
May be algebraically awkward	May reveal a useful definition or factorization

Before writing any calculations, state the contrapositive in complete words. This prevents a very common error: reversing an implication but forgetting to negate it.

For example, the contrapositive of

$$\text{If an integer }n\text{ is divisible by }5,\text{ then }n\text{ is odd}$$

would be

$$\text{If }n\text{ is not odd, then }n\text{ is not divisible by }5.$$

That statement happens to be false, since $10$ is not odd but is divisible by $5$. The original implication is consequently false too. Contraposition preserves truth, so it also preserves falsity.

---

Example: if a square is even, the integer is even

Let us write the earlier idea as a complete proof.

Claim. For every integer $n$, if $n^2$ is even, then $n$ is even.

Proof. We prove the contrapositive. Let $n$ be an arbitrary integer, and suppose that $n$ is not even. Since every integer is either even or odd, $n$ is odd. Therefore, for some integer $k$,

$$n=2k+1.$$

Then

$$\begin{array}{rl}{n}^2& =(2k+1{)}^2\\ & =4k^2+4k+1\\ & =2(2k^2+2k)+1.\end{array}$$

Since $2k^2+2k$ is an integer, $n^2$ is odd. Hence $n^2$ is not even.

We have proved that if $n$ is not even, then $n^2$ is not even. This is the contrapositive of the original implication. Therefore, if $n^2$ is even, then $n$ is even. $\square$

The proof relies on three precise facts:

• The negation of “$n$ is even,” for an integer $n$, is “$n$ is odd.”
• The previous direct proof established that the square of an odd integer is odd.
• The contrapositive is logically equivalent to the original implication.

You may sometimes shorten the final two sentences by writing “Thus $n^2$ is not even, proving the contrapositive.” In early proof writing, though, it is worth explicitly naming the logical equivalence until the structure becomes automatic.

---

Negating compound conclusions

Contraposition becomes especially valuable when the conclusion contains “and” or “or.” You must negate such conclusions carefully.

The two De Morgan laws are:

$$\neg (A\vee B)⟺(\neg A)\wedge (\neg B),$$ $$\neg (A\wedge B)⟺(\neg A)\vee (\neg B).$$

In words:

• “Not $A$ or $B$” means “not $A$ and not $B$.”
• “Not $A$ and $B$” means “not $A$ or not $B$.”

Consider the theorem:

$$\text{If }a+b\text{ is odd, then }a\text{ is odd or }b\text{ is odd.}$$

A direct proof begins with information about the sum $a+b$, but the conclusion asks for information about the separate integers $a$ and $b$. That separation is inconvenient.

Set

$$P=\text{“}a+b\text{ is odd”}$$

and

$$Q=\text{“}a\text{ is odd or }b\text{ is odd.”}$$

The contrapositive has the form

$$\neg Q⟹\neg P.$$

Now simplify each negation. The negation of “$a$ is odd or $b$ is odd” is

$$\text{“}a\text{ is not odd and }b\text{ is not odd.”}$$

Because $a$ and $b$ are integers, that means both are even. Similarly, “$a+b$ is not odd” means that $a+b$ is even. Thus the useful contrapositive is:

$$\text{If }a\text{ and }b\text{ are even, then }a+b\text{ is even.}$$

This is now a natural direct proof.

Proof. We prove the contrapositive. Let $a$ and $b$ be arbitrary integers, and suppose that both $a$ and $b$ are even. Then there exist integers $r$ and $s$ such that

$$a=2r$$

and

$$b=2s.$$

Therefore,

$$a+b=2r+2s=2(r+s).$$

Since $r+s\in \mathbb{Z}$, the integer $a+b$ is even. We have proved the contrapositive. Hence, if $a+b$ is odd, then $a$ is odd or $b$ is odd. $\square$

The original conclusion uses an inclusive “or”: at least one of $a$ and $b$ is odd. It does not claim that exactly one is odd, although the latter is also true when their sum is odd.

---

Choosing contraposition and avoiding logical look-alikes

Contraposition is particularly promising when the negation of the conclusion gives a concrete, usable form. In elementary number theory, common signals include:

• The conclusion says an integer is even; its negation may let you write it as $2k+1$.
• The conclusion says a number is odd; its negation may let you write it as $2k$.
• The conclusion is an “or” statement; its negation gives an “and” statement, which may supply two usable assumptions.
• The conclusion is a divisibility statement, and its failure can be interpreted through remainders or prime factors.

It is less useful to apply contraposition mechanically. First ask whether $\neg Q$ offers better raw material than $P$.

Three ideas that are often confused should remain distinct:

Name	Starting assumption	Target	Relation to $P⟹Q$
Direct proof	$P$	$Q$	Proves the original implication
Contrapositive proof	$\neg Q$	$\neg P$	Proves an equivalent implication
Converse	$Q$	$P$	A different statement; may be false

For example, from

$$n^2\text{ even}⟹n\text{ even},$$

the contrapositive is

$$n\text{ odd}⟹n^2\text{ odd}.$$

The converse, by contrast, is

$$n\text{ even}⟹n^2\text{ even}.$$

The converse is true, and it has a simple direct proof, but it is not the reason the original theorem is true. A theorem and its converse must always be assessed independently.

One further distinction will matter in the next lesson. In contraposition, you assume only $\neg Q$ and aim to prove $\neg P$. You do not also assume $P$. Assuming both $P$ and $\neg Q$ and deriving an impossibility is a proof by contradiction, a related but differently organized method.

---

A concise writing checklist

When you use contraposition, audit your proof in this order:

1. Identify the original $P$ and $Q$.
2. Write $\neg Q⟹\neg P$ before beginning calculations.
3. Simplify negations correctly, using parity facts or De Morgan’s laws where appropriate.
4. Keep the same domain. If the theorem concerns integers, your parity simplifications depend on that fact.
5. Prove the contrapositive directly from its assumed antecedent.
6. State the final logical step: the original statement holds because it is equivalent to its contrapositive.

A proof by contraposition should still read forward. Its special feature is not mysterious backward reasoning; it is the deliberate choice of a more workable, logically equivalent starting point.

---

Key takeaways

To prove

$$P⟹Q$$

by contraposition, prove instead

$$\neg Q⟹\neg P.$$

This works because the two implications have exactly the same truth value. The method is especially effective when the negation of the conclusion has a clean algebraic or definitional description.

In the parity examples:

$$n^2\text{ even}⟹n\text{ even}$$

is proved by showing

$$n\text{ odd}⟹n^2\text{ odd},$$

and

$$a+b\text{ odd}⟹(a\text{ odd}\vee b\text{ odd})$$

is proved by showing

$$(a\text{ even}\wedge b\text{ even})⟹a+b\text{ even}.$$

Next, you will study proof by contradiction. It also uses negation, but instead of proving a contrapositive directly, it assumes a statement fails and derives an impossibility.