The Contrapositive

What you'll get from this section. A second way to read every implication — by turning it to its "absence" side. You'll see why $P \Rightarrow Q$ says exactly the same thing as $\neg Q \Rightarrow \neg P$, where that comes from, and the new family of phrasings it brings with it.

From "necessary" to the contrapositive

Recall from Section 2 one of the ways to say $P \Rightarrow Q$: $Q$ is necessary for $P$. That is, $Q$ is a requirement of $P$ — $P$ cannot hold unless $Q$ holds too.

Now turn that requirement around. If $Q$ is genuinely required for $P$, then without $Q$, you cannot have $P$. Take away $Q$, and $P$ is impossible. Written out, "no $Q$ means no $P$" is

So $P \Rightarrow Q$ and $\neg Q \Rightarrow \neg P$ are the very same statement, looked at from two sides:

This flipped-and-negated form, $\neg Q \Rightarrow \neg P$, is called the contrapositive of $P \Rightarrow Q$. It is not a consequence of the original, nor a near-relative of it — it is the original, reworded.

Seeing it in examples

The contrapositive always sounds just as true as the statement it came from, because it is it.

• "If it is a dog, then it is a mammal" has contrapositive "if it is not a mammal, then it is not a dog." Clearly the same fact.
• "If $n$ is a multiple of $4$, then $n$ is even" has contrapositive "if $n$ is not even (i.e. $n$ is odd), then $n$ is not a multiple of $4$." An odd number can't be a multiple of $4$ — same fact again.
• "If it is raining, the ground is wet" has contrapositive "if the ground is not wet, then it is not raining."

There's a clean picture behind this. To say "every dog is a mammal" is to say the dogs all sit inside the mammals. Equivalently, everything outside the mammals must sit outside the dogs — the non-mammals are all non-dogs. One containment, viewed from the inside or from the outside.

The contrapositive family

Here's the useful part. The contrapositive $\neg Q \Rightarrow \neg P$ is itself an implication, so every phrasing from Section 2 applies to it — just with $\neg Q$ playing the old role of $P$, and $\neg P$ playing the old role of $Q$. All of the following therefore say the same thing as $P \Rightarrow Q$:

• if not $Q$, then not $P$
• not $Q$ only if not $P$
• not $Q$ is sufficient for not $P$
• not $P$ is necessary for not $Q$
• not $P$ is an inevitable consequence of not $Q$

Watch them work on a concrete statement. Let $P$ be "$n$ is a multiple of $4$" and $Q$ be "$n$ is even", so $\neg P$ is "$n$ is not a multiple of $4$" and $\neg Q$ is "$n$ is odd". The family reads:

• if $n$ is odd, then $n$ is not a multiple of $4$
• $n$ is odd only if $n$ is not a multiple of $4$
• $n$ being odd is sufficient for $n$ not being a multiple of $4$
• $n$ not being a multiple of $4$ is necessary for $n$ being odd
• $n$ not being a multiple of $4$ is an inevitable consequence of $n$ being odd

They get clunky with the double negatives, but every one is true and every one says exactly what "a multiple of $4$ is even" says.

Two families, one statement

Put this beside Section 2 and a tidy picture emerges. A single implication $P \Rightarrow Q$ can be expressed in two families of phrasings:

• the forward family (Section 2), keeping the arrow as $P \Rightarrow Q$;
• the contrapositive family (this section), flipping it to $\neg Q \Rightarrow \neg P$.

Every phrasing in both families is the same statement. Choosing between them is just a matter of which side — the presence of things, or their absence — is easier to reason about for the problem in front of you.

Common mistakes

1. Negate and flip — not one or the other. The contrapositive does both. Do only one and you get a statement that is not equivalent:

• the converse $Q \Rightarrow P$ (flipped, not negated), and

• the inverse $\neg P \Rightarrow \neg Q$ (negated, not flipped).

  "If it is a dog, it is a mammal" is true, but its converse "if it is a mammal, it is a dog" is false (a cat), and its inverse "if it is not a dog, it is not a mammal" is also false (again, a cat). Only the contrapositive "if it is not a mammal, it is not a dog" is guaranteed to match the original.

2. Negating the two parts carelessly. Forming the contrapositive means negating $P$ and $Q$ correctly — use the rules from Section 3. The contrapositive of "if $x > 3$ then …" starts "if $x \leq 3$ …", not "if $x < 3$ …".

Summary

• The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$, and the two are the same statement.
• It follows directly from "$Q$ is necessary for $P$": if $Q$ is required for $P$, then no $Q$ means no $P$.
• Applying Section 2's phrasings to $\neg Q \Rightarrow \neg P$ gives a whole second family of equivalent forms (e.g. "not $P$ is necessary for not $Q$").
• Negate-and-flip gives the equivalent contrapositive; flip-only (the converse) and negate-only (the inverse) do not.

Next: Section 5 — Proof by contradiction.