← mapLogic & Proof

Contrapositive & Iff Proofs

⚗ Dr. Möbius, from the lab

Sometimes the direct road to a proof is a swamp — you assume $P$ and the algebra just sits there, sneering at you. Today I hand you a perfectly legal detour: prove the contrapositive instead, and the swamp becomes a two-lane highway. Then we deal with "if and only if," the statement that is secretly two theorems wearing one coat and hoping you won't notice. Hand me half of an iff proof and I will hand it back. I will not grade it. I will stare at you.

THE BIG IDEA

Because P→Q is logically equivalent to its contrapositive ¬Q→¬P, you may prove either one; and an 'if and only if' is two separate implications that both require proof.

The contrapositive is a legal detour

Back in the Implication lesson we proved, with a truth table, that $P \to Q \ \equiv\ \neg Q \to \neg P.$ These are the same statement — identical in every row. That equivalence wasn't a curiosity; it's a proof strategy. Since proving $\neg Q \to \neg P$ establishes the very same fact as $P \to Q$ , you're allowed to prove whichever one is easier. That's proof by contrapositive.

The recipe: to prove "if $P$ then $Q$ ," instead assume $\neg Q$ and derive $\neg P$ . When you arrive at $\neg P$ , you've proven $\neg Q \to \neg P$ , which is $P \to Q$ . Same theorem, different door.

When is the contrapositive door easier? Whenever the negated hypothesis is more concrete than the original. " $n^2$ is even" is awkward as hell to unwrap — it gives you $n^2 = 2k$ , and you can't easily extract $n$ . But its negation in the contrapositive, " $n$ is odd," hands you $n = 2k+1$ directly, a clean witness you can compute with. The contrapositive trades a hard handle for an easy one. Same fucking result, better door.

Classic: if n² is even then n is even

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

The direct attempt is mud. Assume $n^2$ is even, so $n^2 = 2k$ . Now what? To conclude $n$ is even you'd need $n = \sqrt{2k}$ to be an even integer, and square roots are not something our integer definitions handle. Dead end.

The contrapositive is two lines. The contrapositive of "if $n^2$ even then $n$ even" is "if $n$ is not even then $n^2$ is not even" — i.e., "if $n$ is odd then $n^2$ is odd."

Proof (by contrapositive). Assume $n$ is odd. Then $n = 2k + 1$ for some integer $k$ . So $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.$ Since $2k^2 + 2k$ is an integer, $n^2$ has the form $2 \cdot (\text{integer}) + 1$ , so $n^2$ is odd. This proves the contrapositive, which is logically equivalent to the original. Therefore: if $n^2$ is even, then $n$ is even. $\blacksquare$

Two lines of clean algebra versus an impassable swamp. Remember this lemma — " $n^2$ even $\Rightarrow$ $n$ even" — because it is the exact tool that detonates the √2 proof in the very next lesson like a small beautiful bomb. We're sharpening the knife now; next lesson we gut the proof with it.

Iff proofs are TWO proofs

Recall from Implication: $P \leftrightarrow Q$ (" $P$ if and only if $Q$ ") means both $P \to Q$ and $Q \to P$ hold. So to prove a biconditional you must prove two implications, full stop. No shortcuts, no "well the other direction is obvious," no implicit bullshit. Two proofs:

the forward direction ( $\Rightarrow$ ): assume $P$ , prove $Q$ ;
the backward direction ( $\Leftarrow$ ): assume $Q$ , prove $P$ .

Each is its own little proof, with its own assumption and its own conclusion. Skipping one is not "mostly done" — it's half a theorem, which is worth exactly nothing. The forward direction can be true while the backward is false (that's just "converse $\ne$ original" from the Implication lesson), so proving one tells you nothing about the other. You prove both, or you prove neither.

Claim. For every integer $n$ : $n$ is even if and only if $n^2$ is even.

Proof. ( $\Rightarrow$ ) Assume $n$ is even, so $n = 2k$ . Then $n^2 = 4k^2 = 2(2k^2)$ , and $2k^2$ is an integer, so $n^2$ is even.

( $\Leftarrow$ ) Assume $n^2$ is even. We want $n$ even. This is exactly the contrapositive result above — we proved that $n^2$ even forces $n$ even. So $n$ is even.

Both directions hold, so $n$ is even $\iff$ $n^2$ is even. $\blacksquare$

See how the backward direction reused our contrapositive lemma? That's the point of building tools: you sharpen them in one proof and spend them in the next. Nothing in this lab is wasted.

Choosing your weapon

You now own three direct-style techniques — straight direct proof, and contrapositive — and you'll add contradiction next lesson. Here are the heuristics for when contrapositive beats a head-on direct proof:

The conclusion $Q$ is a "non-existence" or "not" statement. Negating it ( $\neg Q$ ) turns a slippery "there is no…" into a concrete "there is a…" you can grab a witness from.
The hypothesis $P$ is hard to unwrap but $\neg Q$ is easy. The $n^2$ -even case is the poster child: " $n$ odd" is a far better starting handle than " $n^2$ even."
$Q$ is " $x = y$ " or " $x \ne y$ ". Often the negation gives you an inequality (or equality) you can manipulate directly.

If the direct proof flows, use it — don't reach for the contrapositive out of goddamn habit; it's a detour, and detours are only smart when the main road is blocked. The skill isn't memorizing which to use; it's trying the direct road, noticing the swamp, and calmly switching doors. Now go pick some locks.

🔬 SPECIMENS (worked examples)

Worked example 1 — contrapositive on a divisibility claim▸

Prove: for every integer $n$ , if $n^2$ is odd then $n$ is odd.

Trying this directly is the same swamp as the even case — " $n^2 = 2k+1$ " gives no clean handle on $n$ . So take the contrapositive.

The contrapositive of "if $n^2$ odd then $n$ odd" is "if $n$ is not odd then $n^2$ is not odd" — i.e., "if $n$ is even then $n^2$ is even."

Proof (by contrapositive). Assume $n$ is even, so $n = 2k$ for some integer $k$ . Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2),$ and $2k^2$ is an integer, so $n^2$ is even. This establishes the contrapositive, which is equivalent to the claim. Therefore if $n^2$ is odd, $n$ is odd. $\blacksquare$

The negation of "odd" is "even," giving the clean witness $n = 2k$ . That's the whole trick.

Worked example 2 — a full iff proof▸

Prove: for every integer $n$ , $n$ is odd if and only if $n + 1$ is even.

A biconditional means two proofs. Label them.

( $\Rightarrow$ ) Assume $n$ is odd. Then $n = 2k + 1$ for some integer $k$ . So $n + 1 = (2k + 1) + 1 = 2k + 2 = 2(k + 1).$ Since $k + 1$ is an integer, $n + 1$ is even.

( $\Leftarrow$ ) Assume $n + 1$ is even. Then $n + 1 = 2m$ for some integer $m$ . So $n = 2m - 1 = 2(m - 1) + 1.$ Since $m - 1$ is an integer, $n$ has the form $2 \cdot (\text{integer}) + 1$ , so $n$ is odd.

Both directions hold, so $n$ is odd $\iff$ $n + 1$ is even. $\blacksquare$

Note each direction has its own assumption and its own target. Neither half could be skipped; together they pin down the equivalence.

Worked example 3 — the trap: skipping the direction that's false▸

A student claims to prove " $n$ is divisible by $6$ if and only if $n$ is divisible by $2$ ." They show the $\Rightarrow$ direction correctly. Is the biconditional true? Decide, and prove or disprove the $\Leftarrow$ direction.

First check what the student did. ( $\Rightarrow$ ) If $6 \mid n$ then $n = 6k = 2(3k)$ , so $2 \mid n$ . Correct — divisibility by $6$ does force divisibility by $2$ .

But a biconditional needs both directions, and the student stopped halfway. Test ( $\Leftarrow$ ): "if $2 \mid n$ then $6 \mid n$ ." Take $n = 4$ : it's divisible by $2$ but $4 / 6$ is not an integer, so $6 \nmid 4$ . Counterexample. The backward direction is false.

Therefore the biconditional is false — the student "proved" a theorem that isn't true by quietly skipping the direction that fails. This is exactly why half an iff is worthless: the missing half was the false half. One honest counterexample ( $n = 4$ ) demolishes the whole claim. The correct statement is only the one-way implication $6 \mid n \to 2 \mid n$ .

☠ KNOWN HAZARDS

Confusing contrapositive with converse. The contrapositive of $P \to Q$ is $\neg Q \to \neg P$ (negate both, flip order) — equivalent. The converse $Q \to P$ (flip only) is NOT, and assuming it is wrecks your proof.
Proving only one direction of an iff. $P \leftrightarrow Q$ needs both $P \to Q$ and $Q \to P$ . Half a biconditional earns zero credit — the missing direction might be outright false, as in the "divisible by 6 iff divisible by 2" trap below. Do both or do nothing.
Forgetting to actually negate $Q$ correctly. The contrapositive of "if $n^2$ even then $n$ even" assumes " $n$ is odd" (the negation of "even"), not " $n^2$ is odd". Negate the conclusion to get your new hypothesis, the hypothesis to get your new conclusion.
Reaching for the contrapositive reflexively. It's a detour for when the direct road is blocked. If assuming $P$ leads straight to $Q$ , just do that — don't negate everything for no reason.

TL;DR

▸
To prove $P \to Q$ by contrapositive, assume $\neg Q$ and derive $\neg P$ ; this is legal because $P \to Q \equiv \neg Q \to \neg P$ .
▸
The contrapositive wins when $\neg Q$ is a cleaner handle than $P$ — e.g. " $n^2$ even $\Rightarrow$ $n$ even" is mud directly, two lines via " $n$ odd $\Rightarrow$ $n^2$ odd".
▸
That lemma (" $n^2$ even $\Rightarrow$ $n$ even") is the knife that detonates the √2 proof in proof-by-contradiction.
▸
An iff ( $P \leftrightarrow Q$ ) is two proofs: forward ( $P \to Q$ ) and backward ( $Q \to P$ ). Proving one says nothing about the other.
▸
Choose contrapositive when the conclusion is a "not"/"non-existence" statement or when $\neg Q$ is easier to start from than $P$ ; otherwise prefer the direct road.

unlocks

Proof by Contradiction →