1.5: Proving an Implication

Propositions of the form “If \(P\), then \(Q\)” are called implications. This implication is often rephrased as “\(P \text{ IMPLIES } Q\).”

Here are some examples:

• (Quadratic Formula) If \(ax^2 + bx + c = 0\) and \(a \neq 0\), then

\[\nonumber x = \left(-b \pm \sqrt{b^2 - 4ac}\right) / 2a. \]

• (Goldbach’s Conjecture 1.1.8 rephrased) If \(n\) is an even integer greater than 2, then \(n\) is a sum of two primes.
• If \(0 \leq x \leq 2\), then \(-x^3 + 4x + 1 > 0\).

There are a couple of standard methods for proving an implication.

Method #1

In order to prove that \(P \text{ IMPLIES } Q\):

1. Write, “Assume \(P\).”

2. Show that \(Q\) logically follows.

Example

Theorem \(\PageIndex{1}\)

If \(0 \leq x \leq 2\), then \(-x^3 + 4x + 1 > 0\).

Before we write a proof of this theorem, we have to do some scratchwork to figure out why it is true.

The inequality certainly holds for \(x = 0\); then the left side is equal to 1 and \(1 > 0\). As \(x\) grows, the \(4x\) term (which is positive) initially seems to have greater magnitude than \(-x^3\) (which is negative). For example, when \(x = 1\), we have \(4x = 4\), but \(-x^3 = -1\) only. In fact, it looks like \(-x^3\) doesn’t begin to dominate until \(x>2\). So it seems the \(-x^3 + 4x\) part should be nonnegative for all \(x\) between 0 and 2, which would imply that \(-x^3 + 4x + 1\) is positive.

So far, so good. But we still have to replace all those “seems like” phrases with solid, logical arguments. We can get a better handle on the critical \(-x^3 + 4x\) part by factoring it, which is not too hard:

\[\nonumber -x^3 + 4x = x(2 - x)(2 + x)\]

Aha! For \(x\) between 0 and 2, all of the terms on the right side are nonnegative. And a product of nonnegative terms is also nonnegative. Let’s organize this blizzard of observations into a clean proof.

Proof. Assume \(0 \leq x \leq 2\). Then \(x, 2 - x,\) and \(2 + x\) are all nonnegative. Therefore, the product of these terms is also nonnegative. Adding 1 to this product gives a positive number, so:

\[\nonumber x(2 - x)(2 + x) + 1 > 0\]

Multiplying out on the left side proves that

\[\nonumber -x^3 + 4x + 1 > 0\]

as claimed. \(\quad \blacksquare\)

There are a couple points here that apply to all proofs:

• You’ll often need to do some scratchwork while you’re trying to figure out the logical steps of a proof. Your scratchwork can be as disorganized as you like—full of dead-ends, strange diagrams, obscene words, whatever. But keep your scratchwork separate from your final proof, which should be clear and concise.
• Proofs typically begin with the word “Proof” and end with some sort of delimiter like \(\square\) or “QED.” The only purpose for these conventions is to clarify where proofs begin and end.

Method #2 - Prove the Contrapositive

An implication (“\(P \text{ IMPLIES } Q\)”) is logically equivalent to its contrapositive

\[\nonumber \text{NOT}(Q) \text{ IMPLIES } \text{NOT}(P) .\]

Proving one is as good as proving the other, and proving the contrapositive is sometimes easier than proving the original statement. If so, then you can proceed as follows:

1. Write, “We prove the contrapositive:” and then state the contrapositive.
2. Proceed as in Method #1.

Example

Theorem \(\PageIndex{2}\)

If \(r\) is irrational, then \(\sqrt{r}\) is also irrational.

A number is rational when it equals a quotient of integers — that is, if it equals \(m/n\) for some integers \(m\) and \(n\). If it’s not rational, then it’s called irrational. So we must show that if \(r\) is not a ratio of integers, then\(\sqrt{r}\) is also not a ratio of integers. That’s pretty convoluted! We can eliminate both not’s and simplify the proof by using the contrapositive instead.

Proof. We prove the contrapositive: if \(\sqrt{r}\) is rational, then \(r\) is rational.

Assume that \(\sqrt{r}\) is rational. Then there exist integers \(m\) and \(n\) such that:

\[\nonumber \sqrt{r} = \frac{m}{n}\]

Squaring both sides gives:

\[\nonumber \sqrt{r} = \frac{m^2}{n^2}\]

Since \(m^2\) and \(n^2\) are integers, r is also rational. \(\quad \blacksquare\)