Consider some arbitrary statement p along with the following truth table:

p	¬p	F0	¬p → F0	(¬p → F0) → p
0	1	0	0	1
1	0	0	1	1

Because the implication (¬p → F₀) → p is always true, we can write

(¬p → F₀) ⟹ p

meaning it is a valid rule of inference, and thus represents the valid argument

Now suppose we’re trying to prove the statement p → q. What happens if we assume p = 1 and q = 0 (meaning ¬q = 1?) The implication p → q is false (meaning p → q = 0.) However, let’s look at what happens in an argument where we assume both p and ¬q as premises? We first examine a truth table:

p	q	p → q	¬q	p ∧ ¬q	F0	(p ∧ ¬q) → F0	((p ∧ ¬q) → F0) ↔ (p → q)
0	0	1	1	0	0	1	1
0	1	1	0	0	0	1	1
1	0	0	1	1	0	0	1
1	1	1	0	0	0	1	1

The last column has all ones, meaning we have that

((p ∧ ¬q) → F₀) ⟺ (p → q)

which means that the argument

is logically equivalent to the argument

Thus, in order to show that p ⟹ q, we could instead show that (p ∧ ¬q) ⟹ F₀.

This is the idea behind proof by contradiction: assume the negation of the desired conclusion as an additional premise, then show that doing so yields a contradiction.

Let’s start by once again revisiting Theorem 2.9.11, which states the following:

If n² is odd, then n is odd.

In trying to prove this statement by contradiction, we first point out what the premises will be. We know that n² being odd is one premise, but in a proof by contradiction, we also have the negation of the conclusion as a premise. Since the conclusion is the statement n is odd, the negation of the conclusion is the statement n is not odd, which we can write as n is even. Let’s emphasize these two premises:

n² is odd
n is even.

Now let’s use our definitions of even and odd as normal. We know that there is an integer a such that

n = 2a.

Since n = 2a, if we square n to get n², we get that

n2	=	(2a)2
	=	4a2
	=	2(2a2)
	=	2b

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

However, note that this directly contradicts the premise that n² is odd. Thus, assuming that n is even yields a contradiction whenever we assume that n² is odd. Hence, n can’t be even, and must therefore be odd as desired.

Over the past three sections, we’ve proven the statement

if n² is odd, then n is odd

in three different ways: directly, indirectly via the contrapositive, and indirectly via a contradiction as shown above. This is the versatility of mathematical logic: if we are ever stuck trying to prove a theorem one way with no success, we can try another tactic.

Some theorems are established in so many ways it can be hard to keep track of how many proofs exist. For example, there are entire books dedicated to proofs of the Pythagorean Theorem, as can be seen here. The author of this linked book claims that no trigonometric proof of the Pythagorean Theorem is possible. Seeing as all of trigonometry is (essentially) based of of the Pythagorean Theorem, this is what most mathematicians believed. However, a trigonometric proof was recently provided by two high school students, showing that there truly is no limit to the kinds of ways this theorem can be proven. You can read more about that spectacular feat here.

However, it should be noted that a great many theorems are not so easily established in such a variety of ways. Some theorems resist nearly all attempts to be established as fact or fiction. Perhaps most infamous is Fermat’s Last Theorem. For over 350 years, mathematicians have been trying to either establish the truth of the statement

When n > 2, there are no integers a, b, and c (a*b*c ≠ 0) that satisfy the equation aⁿ + bⁿ = cⁿ.

or to find a counter example. A proof in the affirmative was eventually given by Andrew Wiles in the mid 1990s. The proof however requires very abstract and sophisticated methods, and often requires multiple pages of densely typed text in order to coax out. There are entire graduate level math courses dedicated to studying that one proof because of how esoteric the methods are.

As you study more and more math, you will start to collect ever more tools at your disposal for either proving theorems, or providing counter-examples. Over the course of this book, more such proof techniques will be encountered, but for now, we show some more results using the contradiction method.

Notice that in some of our previous proofs, we’ve used the fact that if n is not even, then it must be odd. For example, the contrapositive method we used to prove that if n² is odd, then n is odd required us to assume that n is not odd. We took that to mean that n had to be even. However, we have not proved this is the case. Are there numbers that are both even or odd? Of course most people reading this book know that no such number exists, but now, we are able to provide a proof of that fact.

Again, we’d like to point some things out about this particular proof. First, notice that we used the letter a when assuming that n was even, and we used the letter b when assuming that n was odd. We did not use the letter a for both situations. This is because we can’t necessarily assume that the same value can be used for both situations. If n = 2a, then n certainly can’t be equal to 2a + 1. How can n be simultaneously equal to both an integer, and the next integer? It doesn’t make any sense. For example, suppose we had

n = 2a
n = 2a + 1

where a = 1, then we’d have that

n = 2a = 2(1) = 2
n = 2a + 1 = 2(1) + 1 = 3.

Obviously, n can’t be equal to both 2 and 3, because that would mean that 2 = 3, which is clearly absurd. This is why we use different letters. We used a when assuming n was even, and b when assuming n was odd.

The next thing to note is that when we reached the contradiction, we asserted that it was the assumption of n being odd that was the problem, and in order to fix the problem, we had to have that n was not odd. Couldn’t we just as easily assert that the assumption of n being even was faulty, and that assuming n being odd was fine?

Remember that the hypothesis is that n is even. This means we are only considering even integers. What we’re doing in this proof is assuming that n is even, and seeing what happens when we suppose n could be odd as well. In other words, we’re testing what happens if, in addition to n being even, n was also assumed to be odd. Once we reach the contradiction, then either n must not be even or n must not be odd. However, we know that n must be even since that is the hypothesis. Hence, that only leaves the assumption of n being odd to be a faulty assumption.

The last thing to note regards the actual contradiction produced. When we used the contradiction method of proof for Theorem 2.9.11, the contradiction was in regards to the theorem’s hypothesis. That is to say, statement n² is even contradicted the theorem’s hypothesis that n² is odd. However, the contradiction we arrived at in the proof of Theorem 2.11.1 had nothing to do with n being odd or even at all. Our contradiction was in regards to the number 1. By assuming that n is both even and odd, we arrive at the faulty conclusion that 1 is even, even though we know that 1 is odd.

When using the contradiction method, the contradiction we arrive at may be in regards to the hypothesis of the given proposition being examined, or it might be some previous knowledge acquired elsewhere that just happened to show up. In some sense, every piece of knowledge we have can be used as a premise of an argument, it’s just that we don’t necessarily need (or want) to explicitly lay out every premise being used because then the statements of theorems would be incredibly unwieldy.