Proof Technique: Indirect Proofs

As seen in the last section, a direct proof is a proof method where we assume the truth of the hypothesis, and then show the truth of the conclusion. However, the last example seen in the previous section shows that sometimes a direct proof can be quite tricky to devise.

If we’re ever stuck trying to show a proposition is a theorem by taking a direct approach, we can use mathematical logic to prove an equivalent implication. Since we are not proving the original implication to be a logical implication, but instead we’re showing a logically equivalent implication to be a logical implication, this is called an indirect approach.

The Underlying Argument

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

p → q

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

(p → q) ⟺ (¬q → ¬p)

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.

Revisiting a Previous Proof

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:

If n² is odd, then n is odd.

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

If n is not odd, then n² is not odd.

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:

If n is even, then n² is even.

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:

n²	=	(2k)²
	=	2²k²
	=	4k²
	=	2*2k²

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

n is even ⟹ n² is even

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

n² is odd ⟹ n is odd

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.

Theorem 2.9.11 (Revisited)

If n² is odd, then n is odd.

Proof

The contrapositive of the above implication is

n is even → n² is even.

Since n is even, we know there is some integer k such that

n = 2k.

Squaring n to get n² gives us that

n²	=	(2k)²
	=	4k²
	=	2*2k²

Since n² is double whatever integer 2k² happens to be, we know that n² must be even.

This tells us that

n is even ⟹ n² is even.

meaning we also have that

n² is odd ⟹ n is odd

as desired.

More Examples

Theorem 2.10.1

If n² is even, then n is even.

Proof

We start by assuming n is odd, thus there exists some integer k such that

n = 2k + 1.

Squaring n to get n² yields the following:

n²	=	(2k + 1)²
	=	4k² + 4k + 1
	=	2(2k² + 2k) + 1
	=	2c + 1

Since 2 and k are integers, we know that 2k² + 2k must be an integer as well, meaning c is an integer. Thus, since there exists an integer c such that

n² = 2c + 1,

we know that n² is odd by definition. This proves the contrapositive of the stated theorem, thus proving the desired result.

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.

Theorem 2.10.2

Suppose x and y are two real non-negative numbers (meaning they are greater than, or equal to 0.)

if xy > 100, then x > 10 or y > 10

Proof

Rewriting the above statement using mathematical logic notation we get

(xy > 100) → [(x > 10) ∨ (y > 10)].

The contrapositive of the above statement is

¬[(x > 10) ∨ (y > 10)] → ¬(xy > 100)	⟺	[¬(x > 10) ∧ ¬(y > 10)] → ¬(xy > 100)
	⟺	[(0 ≤ x ≤10) ∧ ¬(y > 10)] → ¬(xy > 100)
	⟺	[(0 ≤ x ≤10) ∧ (0 ≤ y ≤10)] → ¬(xy > 100)
	⟺	[(0 ≤ x ≤10) ∧ (0 ≤ y ≤10)] → (0 ≤ xy ≤100)

So, the largest value xy can have when x is between 0 and 10 inclusive, and y is between 0 and 10 inclusive is when x = 10 and y = 10:

xy ≤ 10*10 = 100

Similarly, the smallest value xy can have is when x = 0 and y = 0:

0 = 0*0 ≤ xy.

Thus, when we have 0 ≤ x ≤10 and 0 ≤ y ≤10, we have that

0 ≤ xy ≤100

This proves the contrapositive of the statement

(xy > 100) → [(x > 10) ∨ (y > 10)]

to be proven, and so the original claim is proven as desired.

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.

The Book ofFoundational Mathematics

Quick Links