Again, suppose we’re trying to show that the implication

is a logical implication, meaning p ⟹ q (a logical implication.)

Remember that an implication is logically equivalent to its contrapositive; that is, we have that

As such, we know that p → q and ¬q → ¬p are logically equivalent arguments. As such, if we ever want to prove a statement of the form p → q, we can instead prove the statement ¬q → ¬p.

This method of proof is also commonly called “Proof by Contraposition” for the above reasons.

We are not going to show a fully tabulated form of the argument because that is no longer the goal. Instead, we want to get comfortable with taking the contrapositive of a given implication, and show that the contrapositive is always true.

Recall Theorem 2.9.11 where the given proof required some tricky algebra to work out. Here, we’ll revisit that theorem, and provide a different proof. Let’s start by restating that theorem:

The hypothesis of this implication is the proposition n² is odd. The conclusion is the proposition n is odd. Since we want to provide an indirect proof by using the contrapositive, the statement we want to prove is

Of course, we may already know that if an integer is not odd, then it is even (we will provide a proof of that fact later, but the reader is probably already familiar with that fact.) So let’s rewrite that implication as follows:

So now we proceed as if we’re trying to provide a direct proof: this means we start by assuming that n is even.

Since n is even, that means there exists some integer k such that

n = 2k.

What we want to do is how that n² is even. Since we have an expression for n, we can square it to get n² like this:

n2	=	(2k)2
	=	22k2
	=	4k2
	=	2*2k2

Since k is an integer, we know that 2k² is an integer, which we’ll just call c. Thus, we just found out that there exists some integer c such that n² = 2c, meaning n² is even as desired.

So, by assuming that n is even, we can deduce that n² is even, meaning we have that

Finally, since the contrapositive is logically equivalent to the original implication, we now also have that

as desired.

Let’s do a quick recap of what we did before formally writing a proof. We can essentially break this proof technique down into three steps:

Step 1: Write the contrapositive

For an indirect proof of the the proposition p → q, we start by writing the contrapositive ¬q → ¬p.

Step 2: Proceed with a direct proof on the contrapositive

Assume ¬q is a true proposition. Using the rules of inference along with the laws of logic, any available axioms or definitions, and any previously proven theorems, deduce the truth of ¬p if possible.

Step 3: Invoke the logical equivalence of the contrapositive

Once ¬p is deduced to be true from assuming ¬q is true, we have that ¬q ⟹ ¬p. Since an implication is always logically equivalent to it’s contrapositve, we also have that p ⟹ q. It’s almost like we get two theorems for the price of one!

Now, we present a formal proof of Theorem 2.9.11 using this indirect proof technique.

Notice that in the proof of Theorem 2.10.1, we didn’t explicitly state what the contrapositive was. We just started by assuming that the conclusion was false, meaning n must have been an odd integer. We then proceeded to show that n² is odd as a result. Not all proofs will explicitly state what the contrapositive is, though it is good practice, and is something we will do frequently.

Something else worth pointing out is that we started using the letter c to refer to the quantity 2k² + 2k. It is very common to introduce new variables in a proof to refer to complicated expressions, especially if it helps improve clarity. This is a very common practice, so being able to handle multiple variables in a proof will be a vital skill in reading proofs.

Our next theorem eschews even and odd integers, and instead deals with all real numbers and inequalities.

There are a couple of things to point out about the above proof.

First, note that ¬(x > 10) was evaluated to be equal to 0 ≤ x ≤10 instead of just x ≤10 (the same is true for variable y and the product xy.) This is because the universe we’re dealing with is that of all non-negative real numbers. This means were are not considering negative numbers at all. Hence, anything less than 0 is irrelevant. This is why we gave a lower bound of 0 to x and y. We simply don’t care what happens when x and y are negative.

The next thing to notice is that we used DeMorgan’s Laws to distribute the ¬ into the parenthesized expression. DeMorgan’s Laws are so frequently used that most of the time, their use is not explicitly stated, but implicitly used. The same is true for this proof, we simply used those laws without stating what those laws were. It is usually a good idea to mention what logical laws are being used, but again, most writing does not explicitly mention them. This is something we’ll simply have to get used to.

The contrapositive is not the only indirect method we have at proving theorems. The next section will detail another very common indirect proof technique.