Proof by Contrapositive: Simple Conditional Statements

The Logic of the Contrapositive

The foundation of this proof method rests on a simple principle of formal logic. A conditional statement of the form "If $P$, then $Q$" (symbolically, $P\to Q$) is logically equivalent to its contrapositive, which is "If not $Q$, then not $P$" (symbolically, $\neg Q\to \neg P$).

Logically equivalent means that the two statements always have the same truth value. If one is true, the other is true; if one is false, the other is false. We can verify this with a truth table.

Since $P\to Q$ and $\neg Q\to \neg P$ are logically interchangeable, proving one is the same as proving the other. This gives us a new strategy: if proving $P\to Q$ directly is difficult, we can instead prove its contrapositive, $\neg Q\to \neg P$, using a direct proof.

The Structure of a Contrapositive Proof

The procedure for a proof by contrapositive is systematic and builds directly upon the skills you developed in the last lesson. The following resource provides a concise outline of the method.

As the text explains, the steps are:

1. State the contrapositive. Clearly write down the $\neg Q\to \neg P$ version of the statement you intend to prove. This signals your strategy to the reader.
2. Assume $\neg Q$. This is the hypothesis of your new statement.
3. Use a direct proof to show that $\neg P$ logically follows from the assumption that $\neg Q$ is true.
4. Conclude. Since you have proven the contrapositive, you can conclude that the original statement $P\to Q$ is also true.

Example 1: When Direct Proof is Awkward

Let's consider the statement: "For any integer $n$, if $n^2$ is even, then $n$ is even."

Attempting a direct proof, we would assume $n^2$ is even. By definition, this means $n^2=2k$ for some integer $k$. Our goal is to show $n$ is even. The natural next step would be to take the square root: $n=\sqrt{2k}$. This expression is not immediately helpful. It's not at all obvious that $\sqrt{2k}$ must be an even integer. This is where the direct approach becomes difficult.

Let's see how proof by contrapositive makes this problem manageable. The following video explains this motivation and then walks through the proof.

Let's formalize the argument from the video.

Proposition: For any integer $n$, if $n^2$ is even, then $n$ is even.

Proof.
We will prove the contrapositive: "If $n$ is not even, then $n^2$ is not even." This is equivalent to proving: "If $n$ is odd, then $n^2$ is odd."

Assume $n$ is an odd integer. By the definition of an odd integer, there exists an integer $k$ such that $n=2k+1$.
Now, we square $n$:
$n^2=(2k+1{)}^2=4k^2+4k+1$
We want to show that $n^2$ is odd, so we must express it in the form $2j+1$ for some integer $j$. We can factor a 2 from the first two terms:
$n^2=2(2k^2+2k)+1$
Let $j=2k^2+2k$. Since $k$ is an integer, and integers are closed under multiplication and addition, $j$ must also be an integer.
Thus, we have shown that $n^2=2j+1$ for some integer $j$. By the definition of an odd integer, $n^2$ is odd.

Since we have proven the contrapositive, the original statement, "If $n^2$ is even, then $n$ is even," is true. □

Notice that the core of this proof is a direct proof of a statement you are already familiar with from our last lesson. The contrapositive method simply allowed us to transform the problem into this more convenient form.

Example 2: Proofs with "Or"

Proof by contrapositive is also extremely effective when dealing with statements involving logical disjunctions ("or"). When we negate a statement containing "or," De Morgan's laws turn it into a statement containing "and," which is often easier to work with.

The following resource from Oscar Levin's Discrete Mathematics: An Open Introduction provides an excellent series of examples. Let's focus on one.

Let's break down the logic of that proof.

Proposition: For all integers $a$ and $b$, if $a+b$ is odd, then $a$ is odd or $b$ is odd.

• Original Statement ($P\to Q$):

  • $P$: "$a+b$ is odd"
  • $Q$: "$a$ is odd or $b$ is odd"

• Contrapositive ($\neg Q\to \neg P$):

  • $\neg Q$: "It is not the case that ($a$ is odd or $b$ is odd))"
    • By De Morgan's laws, this is equivalent to: "$a$ is not odd AND $b$ is not odd," which means "$a$ is even and $b$ is even."
  • $\neg P$: "It is not the case that ($a+b$ is odd))"
    • This means "$a+b$ is even."

So, the contrapositive statement is: "If $a$ is even and $b$ is even, then $a+b$ is even." This is much more straightforward to prove directly.

Proof.
We prove the contrapositive. Assume $a$ and $b$ are both even integers.
By definition, there exist integers $k$ and $l$ such that $a=2k$ and $b=2l$.
Then their sum is:
$a+b=2k+2l=2(k+l)$
Let $j=k+l$. Since $k$ and $l$ are integers, their sum $j$ is also an integer.
Thus, $a+b=2j$ for some integer $j$, which means $a+b$ is even.
Since the contrapositive is true, the original statement is also true. □

A Note on Writing Good Proofs

As you build your repertoire of proof techniques, it's equally important to focus on clarity and structure in your writing. A proof must not only be correct, but also convincing and easy for a reader to follow. Given your goal of mastering proof-heavy mathematics, cultivating good writing habits now is essential.

Conclusion

In this lesson, you have added proof by contrapositive to your analytical toolkit. This method provides an alternative path when a direct proof is not forthcoming.

Here are the key takeaways:

• A proof by contrapositive works by proving the logically equivalent statement $\neg Q\to \neg P$.
• The structure involves stating the contrapositive, then using a direct proof to show that the assumption $\neg Q$ necessarily leads to the conclusion $\neg P$.
• This method is particularly powerful when the negation of the conclusion ($\neg Q$) provides a more concrete or algebraically simpler starting point than the original hypothesis $P$.

You are now equipped with two fundamental methods for proving conditional statements. In our next lesson, we will explore a third, and perhaps most intriguing, method of indirect proof: proof by contradiction. While related to the contrapositive, it operates on a slightly different and very powerful principle.