Contrapositive: A Powerful Way to Prove Statements

students, in discrete mathematics, proofs are not just about getting the right answer — they are about showing why a statement must be true. One especially useful proof method is the contrapositive. It is a smart way to prove an implication when proving it directly feels awkward or difficult. 📘

What you will learn

By the end of this lesson, you will be able to:

Explain what the contrapositive of a statement means.
Use contrapositive reasoning to prove statements in discrete mathematics.
Connect contrapositive proofs to direct proofs and proof by contradiction.
Recognize when a contrapositive proof is a strong choice.
Use examples to see how contrapositive proofs work in real mathematical situations.

What is a contrapositive?

Many mathematical statements are written as implications, such as $P \to Q$, which means “if $P$, then $Q$.” The contrapositive of this statement is $\neg Q \to \neg P$, which means “if not $Q$, then not $P$.”

This is an important idea because the statement $P \to Q$ and its contrapositive $\neg Q \to \neg P$ are logically equivalent. That means they always have the same truth value. If one is true, the other is true as well. ✅

Here is the key pattern:

Original statement: $P \to Q$
Contrapositive: $\neg Q \to \neg P$
Converse: $Q \to P$
Inverse: $\neg P \to \neg Q$

Only the original statement and its contrapositive are logically equivalent. The converse and inverse are not the same as the original statement, even though they may look similar.

Example of identifying a contrapositive

Suppose the statement is:

“If a number is divisible by $4$, then it is even.”

Let $P$ be “the number is divisible by $4$” and $Q$ be “the number is even.”

Original statement: $P \to Q$
Contrapositive: $\neg Q \to \neg P$

So the contrapositive is:

“If a number is not even, then it is not divisible by $4$.”

Because this is logically equivalent to the original statement, proving it proves the original too.

Why use contrapositive proofs?

Sometimes proving $P \to Q$ directly is hard because $P$ gives you too many possibilities. But proving $\neg Q \to \neg P$ may be much easier because the “not $Q$” condition can be more specific or easier to work with. This is one reason contrapositive proofs are a major tool in Proof Techniques I.

Think of it like this: instead of walking straight across a tricky bridge, you take a safer path from the opposite side. You still reach the same destination. 🌉

A contrapositive proof is especially helpful when:

the conclusion $Q$ is easier to negate than the hypothesis $P$,
the statement involves divisibility, parity, or inequalities,
the direct route would require many cases,
the negation of $Q$ gives strong information about $P$.

Simple real-world example

Consider the statement:

“If a student turns in every homework assignment, then the student will not be missing any homework.”

The contrapositive is:

“If a student is missing at least one homework assignment, then the student did not turn in every homework assignment.”

This version may feel more natural because missing even one homework assignment clearly shows that “every homework assignment” was not turned in.

How to write a contrapositive proof

A contrapositive proof follows a clear structure. Start by assuming the negation of the conclusion and then show that the negation of the hypothesis must follow.

For a statement $P \to Q$:

Assume $\neg Q$.
Use definitions, algebra, or logical reasoning.
Show that $\neg P$ must be true.
Conclude that $\neg Q \to \neg P$ is true.
Therefore, the original statement $P \to Q$ is true.

The proof should be organized and easy to follow. Every step should logically connect to the next. 🧠

Example 1: Even and odd integers

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

This statement is $P \to Q$ where:

$P$: $n^2$ is even
$Q$: $n$ is even

The contrapositive is:

If $n$ is odd, then $n^2$ is odd.

Now prove the contrapositive.

Assume $n$ is odd. Then $n = 2k + 1$ for some integer $k$. Squaring both sides gives

n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.

This has the form $2m + 1$ for some integer $m$, so $n^2$ is odd. Therefore, the contrapositive is true, and so the original statement is true.

This is a classic example because the direct proof from “$n^2$ is even” to “$n$ is even” is not as straightforward as proving the opposite direction.

Example 2: Divisibility

Prove: If $a$ and $b$ are integers and $a$ divides $b$, then $a$ divides $bc$ for any integer $c$.

Let $P$ be “$a$ divides $b$” and $Q$ be “$a$ divides $bc$.” The contrapositive is:

If $a$ does not divide $bc$, then $a$ does not divide $b$.

A direct proof is actually easy here, but this example helps show the idea of contrapositive. If $a \mid b$, then there exists an integer $k$ such that $b = ak$. Multiplying both sides by $c$ gives

$ bc = a(kc).$

Since $kc$ is an integer, $a \mid bc$.

Although this proof is direct, you can still compare it to the contrapositive form to understand how the logic is structured.

Contrapositive and negation

To use contrapositive correctly, you must understand negation. The statement “not $Q$” is not always just a word like “no.” It must be the logical opposite of $Q$.

Here are some common negations:

The negation of “$x > 5$” is $x \le 5$.
The negation of “$x$ is even” is “$x$ is odd,” if $x$ is an integer.
The negation of “all students passed” is “at least one student did not pass.”
The negation of “there exists a prime number greater than $10$” is “there does not exist a prime number greater than $10$.”

Getting the negation right is essential. If you negate incorrectly, the whole proof can fail.

Example 3: Inequalities

Prove: If $x > 3$, then $x^2 > 9$ for real numbers $x$.

The contrapositive is:

If $x^2 \le 9$, then $x \le 3$.

Assume $x^2 \le 9$. Then $|x| \le 3$, which means $-3 \le x \le 3$. In particular, $x \le 3$. So the contrapositive is true, and therefore the original statement is true.

Notice that working with the negation of $x^2 > 9$ gave us the useful inequality $x^2 \le 9$, which led to a clean conclusion.

Contrapositive in the bigger picture of proof techniques

Contrapositive is one of the main proof techniques in discrete mathematics, along with direct proof and proof by contradiction.

Direct proof starts with $P$ and shows $Q$.
Contrapositive proof starts with $\neg Q$ and shows $\neg P$.
Proof by contradiction assumes $P$ and $\neg Q$ together and shows this leads to a contradiction.

These methods are closely related. In fact, a contrapositive proof can sometimes feel similar to contradiction because both often begin with a negation. The difference is important:

In a contrapositive proof, you prove $\neg Q \to \neg P$ directly.
In a contradiction proof, you assume $P \land \neg Q$ and derive an impossible result.

Understanding these differences helps you choose the best strategy for a problem. 📚

When contrapositive is a good choice

A contrapositive proof is often useful when the negation of the conclusion is easy to analyze. For example:

If a number is not divisible by $2$, then it is odd.
If a graph does not have a Hamiltonian cycle, then certain properties fail.
If a function is not one-to-one, then there exist distinct inputs with the same output.

In each case, proving the opposite direction can be simpler than proving the original claim directly.

Common mistakes to avoid

students, when writing contrapositive proofs, watch out for these common errors:

Mixing up the contrapositive with the converse or inverse.
Negating statements incorrectly.
Forgetting to clearly state the assumption $\neg Q$.
Leaving steps unexplained, especially when using definitions.
Proving a related statement instead of the exact contrapositive.

A strong proof is precise, logical, and complete.

Conclusion

The contrapositive is a central proof technique in discrete mathematics. It works because $P \to Q$ and $\neg Q \to \neg P$ are logically equivalent. This means proving the contrapositive is enough to prove the original statement. Contrapositive proofs are especially useful when the negation of the conclusion is easier to handle than the original hypothesis. students, by learning this method, you gain a flexible tool that connects directly to direct proof and proof by contradiction and strengthens your understanding of Proof Techniques I. ✅

Study Notes

A statement of the form $P \to Q$ has contrapositive $\neg Q \to \neg P$.
The original statement and its contrapositive are logically equivalent.
The converse is $Q \to P$, and the inverse is $\neg P \to \neg Q$.
In a contrapositive proof, assume $\neg Q$ and prove $\neg P$.
Correct negation is essential for a valid proof.
Contrapositive proofs are useful when proving the original statement directly is difficult.
This method is a major part of Proof Techniques I, alongside direct proof and contradiction.
Example pattern: if $n$ is odd, then $n = 2k + 1$ for some integer $k$.
Always write proofs in a clear step-by-step structure.