Proof by Contrapositive in Discrete Mathematics

---

---

In Discrete mathematics, we use logics to deduct and prove in several ways. Another way of proving logics is using the techniques with the proof by contrapositive. This method demonstrates the truth of an implication by proving the equivalent contrapositive statement instead. It is a useful and often simpler way to verify a claim when direct proof methods might be cumbersome or unclear.

What is Proof by Contrapositive?

To understand the concept of proof by contrapositive, we must cover the basics of implications. Let us first recall what an implication is. In logical terms, an implication is a statement of the form "if P, then Q", which we write as −

$$\mathrm{P \:\rightarrow\: Q}$$

Here, P is called the hypothesis (or premise), and Q is the conclusion.

The contrapositive of an implication reverses and negates both the hypothesis and the conclusion. So, the contrapositive of the statement P → Q is −

$$\mathrm{\neg\: Q \:\rightarrow\: \neg \:P}$$

This means that instead of proving "if P, then Q", we prove "if not Q, then not P". An important fact is that the contrapositive is logically equivalent to the original statement. In other words, if the contrapositive is true, the original implication must also be true.

Why Use Contrapositive Proofs?

Sometimes, it is difficult to prove a statement directly. The relationship between P and Q might be too complex or unclear when handling this. However, the contrapositive may offer a simpler or more intuitive way out. Giving the contrapositive can sometimes break down the problem into smaller, more manageable parts.

To get the idea clear on how a proof by contrapositive works, let us look at an example from the idea of even and odd numbers.

Example 1: Proving the Statement with Contrapositive

Consider the statement: "For all integers n, if n² is even, then n is even".

We want to prove this implication. Proving it directly would mean starting with the assumption that n² is even and trying to show that n itself is even. While possible, this approach might not feel straightforward. Instead, let us prove its contrapositive:

The contrapositive of the given statement is −

"If n is odd, then n2 is odd"

Proving this contrapositive will be enough to confirm the truth of the original implication. So, we start by assuming that n is odd and show that n² must also be odd.

Step 1: Assume the negation of the conclusion

We start with assuming that n is odd. If n is odd, we can write n in the form −

$$\mathrm{n \:=\: 2k \:+\: 1}$$

where k is an integer. This is the standard way to represent odd numbers because they differ from the nearest even number by 1.

Step 2: Square the assumption

Next, we need to find n², the square of an odd number. Using the expression for n, we calculate −

$$\mathrm{n^2\: = \:(2k \:+\: 1)^2}$$

Expanding the square −

$$\mathrm{n^2 \:=\: 4k^2 \:+\:4k \:+\: 1}$$

Step 3: Analyze the result

We can factor this expression −

$$\mathrm{n^2 \:=\: 2(2k^2 \:+\: 2k) \:+\: 1}$$

Notice that the expression 2(2k² + 2k) is clearly an even number since it is divisible by 2. Therefore, n² is of the form "even number + 1", which means that n² is odd.

Step 4: Conclusion

Thus, we have shown that if n is odd, then n² must also be odd. Since we have successfully proven the contrapositive, we can now conclude that the original statement is true −

"For all integers n, if n2, then n is even."

Let us now see another effective example of Proof by Contrapositive.

Example 2: Divisibility and Contrapositive

Let us prove the following statement −

"For all integers a and b, if a × b is odd, then both a and b are odd."

Again, a direct proof could be tricky, but the contrapositive offers a simpler approach. The contrapositive of this statement is −

"If either a or b is even, then a × b is even."

This is much easier to prove. We assume that one of the numbers, say a, is even. If a is even, then we can write a = 2k for some integer k. Now, a × b = (2k) × b = 2(k × b), which is clearly an even number because it is divisible by 2. Hence, we can conclude this is contrapositive, and by extension, the original statement is True.

Importance of Proving by Contrapositive

The following points highlight why it is sometimes becoming important to use Proof by Contraceptive −

• Logical Equivalence − Proof by contrapositive helps in that the original statement and its contrapositive are logically equivalent. Proving one is the same as proving the other.
• Simplicity − Sometimes, it is easier to prove the contrapositive because it allows us to work with negations, which can simplify the relationships between the variables.
• Versatility − Proof by contrapositive is very much useful when we are working with statements with properties like even and odd numbers, divisibility, and inequalities. It is widely applicable in number theory, logic, and discrete mathematics.

Conclusion

In this chapter, we explained the concept of proof by contrapositive, the fundamental technique in discrete mathematics.

We have started by explaining the basic idea of how the contrapositive of a statement is logically equivalent to the original statement. Then, we gave a detailed example proving that if n² is even, then n is even, using the contrapositive approach. We also looked at another example involving divisibility to further illustrate the utility of this proof method.