2.8 Proof by contraposition

Definition of contraposition

When you need to prove a statement like "if P, then Q," sometimes a direct approach is awkward or hard to get started on. Proof by contraposition lets you prove the same thing from a different angle: instead of showing $P \implies Q$, you prove $\neg Q \implies \neg P$. These two statements are logically equivalent, so proving one automatically proves the other.

The core move is to reverse and negate both parts of the implication. You take the conclusion, negate it, and make it your new assumption. Then you show that the original hypothesis must also be false.

Logical form of contraposition

The original statement has the form $P \implies Q$. The contrapositive is $\neg Q \implies \neg P$.

• You negate both the antecedent (P) and the consequent (Q)
• You swap their positions: the negated consequent becomes the new "if" part, and the negated antecedent becomes the new "then" part
• The contrapositive always has the same truth value as the original implication

This is especially handy when assuming $\neg Q$ gives you something concrete to work with, while assuming P directly doesn't lead anywhere obvious.

Contrapositive vs. converse

These two get mixed up constantly, so it's worth being precise:

• Contrapositive of $P \implies Q$: $\neg Q \implies \neg P$ (logically equivalent to the original)
• Converse of $P \implies Q$: $Q \implies P$ (NOT necessarily equivalent to the original)

The contrapositive negates and swaps. The converse only swaps. That difference matters: proving the converse does not prove the original statement. For example, "if it's raining, the ground is wet" is true, but the converse "if the ground is wet, it's raining" is not necessarily true (someone could have used a hose). The contrapositive "if the ground is not wet, it's not raining" is always true whenever the original is.

Logical equivalence

The reason contraposition works as a proof technique is that $P \implies Q$ and $\neg Q \implies \neg P$ are logically equivalent. They're true in exactly the same situations and false in exactly the same situations.

Truth table analysis

You can verify this by building a truth table that checks every combination of truth values for P and Q:

The third and sixth columns match in every row. That's what logical equivalence means: no matter what P and Q are, the two statements agree.

Relationship to original statement

Because the truth values are identical, proving $\neg Q \implies \neg P$ is just as valid as proving $P \implies Q$ directly. You're not proving something weaker or different. You're proving the exact same logical content, just approached from the other direction.

This is what separates contraposition from other indirect techniques. You're not hunting for a contradiction or assuming something false. You're simply restating the problem in an equivalent form that might be easier to handle.

Steps for contrapositive proof

Here's the process, broken into clear steps:

1. Start with the original statement in the form $P \implies Q$
2. Negate the consequent Q to get $\neg Q$
3. Negate the antecedent P to get $\neg P$
4. Form the contrapositive: $\neg Q \implies \neg P$
5. Prove the contrapositive directly: assume $\neg Q$ is true, and use logical steps to show $\neg P$ must follow
6. Conclude that the original statement $P \implies Q$ holds, since it's logically equivalent to the contrapositive you just proved

Negating antecedent and consequent

Negation sounds simple, but it's where most errors happen. A few rules to keep in mind:

• Quantifiers flip: $\neg(\forall x)$ becomes $\exists x$, and $\neg(\exists x)$ becomes $\forall x$
• Compound statements use De Morgan's laws: $\neg(A \land B)$ becomes $\neg A \lor \neg B$, and $\neg(A \lor B)$ becomes $\neg A \land \neg B$
• Inequalities flip to their complement: $\neg(x > 5)$ is $x \leq 5$, not $x < 5$. The negation of $>$ is $\leq$, not $<$

Take your time with negations. Getting them wrong invalidates the entire proof.

Constructing the contrapositive statement

Once you have $\neg Q$ and $\neg P$, write the contrapositive $\neg Q \implies \neg P$ in clear mathematical language. Before diving into the proof, double-check that your contrapositive actually says the right thing. Read it back in plain English and make sure it's the logical flip of the original, not something subtly different.

Then prove it the way you'd prove any direct implication: assume the "if" part ($\neg Q$) and derive the "then" part ($\neg P$).

Applications in mathematics

Number theory examples

Claim: If $n^2$ is even, then $n$ is even.

Trying to prove this directly is tricky because you'd need to work backward from $n^2$ to $n$. The contrapositive is much cleaner:

Proof: Assume $n$ is odd, so $n = 2k + 1$ for some integer $k$. Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. Done.

Other examples where contraposition works well:

• "If a number is not divisible by 2, it is not divisible by 4." Contrapositive: "If a number is divisible by 4, it is divisible by 2." (This one is almost trivial to prove directly from the definition of divisibility by 4.)
• "If $n$ leaves remainder 1 when divided by 3, then $n$ is not divisible by 3." Contrapositive: "If $n$ is divisible by 3, then $n$ does not leave remainder 1 when divided by 3."

Geometry proofs using contraposition

• Claim: If two lines do not intersect (in Euclidean geometry, in the same plane), they are parallel. Contrapositive: If two lines are not parallel (and lie in the same plane), they intersect. This follows directly from the definition of parallel lines in Euclidean geometry.
• Claim: If a quadrilateral has diagonals that bisect each other, it is a parallelogram. Contrapositive: If a quadrilateral is not a parallelogram, its diagonals do not bisect each other.
• Claim: If a triangle has two equal angles, it is isosceles. Contrapositive: If a triangle is not isosceles, it does not have two equal angles.

Common mistakes

Confusion with contradiction

Contraposition and proof by contradiction are both indirect, but they work differently:

• Contraposition: You rewrite $P \implies Q$ as $\neg Q \implies \neg P$ and prove that equivalent statement directly.
• Contradiction: You assume $P$ is true and $Q$ is false, then derive a logical impossibility.

In contraposition, you never reach a contradiction. You just prove a different (but equivalent) implication. Mixing up the two techniques can lead to proofs that are structurally confused, even if the math inside happens to be correct.

Incorrect negation of statements

This is the most common source of errors. Watch out for:

• Quantifier mistakes: The negation of "all dogs are friendly" is "there exists a dog that is not friendly," not "no dogs are friendly"
• Compound statement mistakes: The negation of "$x > 0$ and $x < 10$" is "$x \leq 0$ or $x \geq 10$" (De Morgan's), not "$x \leq 0$ and $x \geq 10$"
• Inequality mistakes: $\neg(x > 5)$ is $x \leq 5$, not $x < 5$. The boundary case matters.

If your negation is wrong, your contrapositive is wrong, and your entire proof falls apart.

Advantages of contraposition

Simplifying complex proofs

Sometimes the direct route from $P$ to $Q$ involves working with a complicated hypothesis or an abstract conclusion. Contraposition can flip the problem so you're starting from something more concrete.

A good rule of thumb: if the negation of the conclusion gives you a specific, usable assumption (like "$n$ is odd" instead of "$n^2$ is even"), contraposition is probably the way to go.

Alternative approach to direct proof

Not every implication has an obvious direct proof. When you're stuck, forming the contrapositive is always worth trying. Even if you don't end up using it, the process of negating and reversing the statement can clarify what the original statement is really saying and suggest a path forward.

Practice problems

Identifying contrapositive statements

Try forming the contrapositive of each statement before checking the answers:

• Given: "If a number is prime, it has exactly two factors."
  • Contrapositive: "If a number does not have exactly two factors, it is not prime."
• Given: "If a function is differentiable, it is continuous."
  • Contrapositive: "If a function is not continuous, it is not differentiable."
• Given: "If a triangle is equilateral, all its angles are 60°."
  • Contrapositive: "If not all angles of a triangle are 60°, it is not equilateral."

Constructing contrapositive proofs

For each of these, try writing the contrapositive and then proving it:

• Prove: "If a number is divisible by 6, it is divisible by 2 and 3."
  • Contrapositive: "If a number is not divisible by 2 or not divisible by 3, it is not divisible by 6." (Note the "or" here, from De Morgan's law applied to "divisible by 2 and 3.")
• Prove: "If a quadrilateral is a rhombus, its diagonals are perpendicular."
  • Contrapositive: "If the diagonals of a quadrilateral are not perpendicular, it is not a rhombus."
• Prove: "If a function is one-to-one, it has an inverse."
  • Contrapositive: "If a function does not have an inverse, it is not one-to-one."

Historical context

Origins in classical logic

Contraposition has roots in ancient Greek logic. Aristotle's work on syllogistic reasoning included related ideas about how implications could be transformed. The Stoic logicians later formalized it as a valid argument form, alongside principles like modus ponens ("if P then Q; P; therefore Q") and modus tollens ("if P then Q; not Q; therefore not P"). Modus tollens is closely related to contraposition: it's essentially applying the contrapositive in a single argument step.

Development in modern mathematics

In the late 19th and early 20th centuries, mathematicians like Frege, Russell, and Hilbert formalized symbolic logic and placed proof techniques on rigorous foundations. Contraposition became a standard tool in this framework, integrated into the formal study of mathematical logic and set theory. Today it's taught as one of the core proof techniques alongside direct proof, proof by contradiction, and mathematical induction.