Conditional Proofs

A conditional proof uses assumptions which go beyond the basic facts of mathematics. The conclusion of a conditional proof is true provided that those additional assumptions are true. Many mathematical results have the form of "if-then" statements. A proof of such a statement will often be a conditional proof.

Example. Consider the following statement:

\qquad If $x > 3$ , then $x^2 + 5x + 2 > 25$ .

To prove it, you assume that $x > 3$ . Make what you've got look like what you want:

$$x > 3, \quad\hbox{so}\quad x^2 > 9.$$

Likewise,

$$x > 3, \quad\hbox{so}\quad 5x > 15.$$

If I add $x^2 > 9$ and $5x > 15$ , I get $x^2 + 5x > 24$ . I compare this inequality to the target inequality, and I see that I'm missing a "2" on the left and a "1" on the right. Well, $2 > 1$ , so adding this inequality to $x^2 + 5x > 24$ , I obtain

$$x^2 + 5x + 2 > 25.$$

Notice the conditional nature of the conclusion. It's certainly not true that $x^2 + 5x + 2 > 25$ for any real number x. (For example, it's false if $x = 0$ .) The conclusion is true if the assumption $x > 3$ is true. The assumption $x > 3$ goes beyond the basic facts of mathematics.

The last example shows how you write a conditional proof. In this situation, you're trying to prove a statement of the form $P \ifthen Q$ , where P is the set of assumptions --- it may be one statement, or several statements --- and Q is the conclusion. You assume P and try to derive Q. If you succeed, then $P \ifthen Q$ is true.

Example. Premises: $\left\{\matrix{A \land \lnot D \cr B \ifthen (C \ifthen D) \cr}\right.$

Prove: $(A \ifthen B) \ifthen\, \lnot C$ .

To prove the conditional statement $(A \ifthen B) \ifthen\,\lnot C$ , I assume the antecedent $A \ifthen B$ and try to deduce the consequent $\lnot C$ .

$$\matrix{ \hfill 1. & A \land \lnot D \hfill & \hbox{Premise} \hfill \cr \hfill 2. & B \ifthen (C \ifthen D) \hfill & \hbox{Premise} \hfill \cr \hfill 3. & A \ifthen B \hfill & \hbox{Premise for conditional proof} \hfill \cr \hfill 4. & A \hfill & \hbox{Decomposing a conjunction (1)} \hfill \cr \hfill 5. & B \hfill & \hbox{Modus ponens (1,3)} \hfill \cr \hfill 6. & C \ifthen D \hfill & \hbox{Modus ponens (2,5)} \hfill \cr \hfill 7. & \lnot D \hfill & \hbox{Decomposing a conjunction (1)} \hfill \cr \hfill 8. & \lnot C \hfill & \hbox{Modus tollens (6,7)} \hfill \cr \hfill 9. & (A \ifthen B)\ifthen\, \lnot C \hfill & \hbox{Conditional proof (3,8)} \hfill \cr }$$

The conclusion $\lnot C$ was deduced on line 8. Together with the assumption $A \ifthen B$ in line 3, this proves the conditional $(A \ifthen B) \ifthen\,\lnot C$ .

Example. Prove that if n is odd, then $n^2$ leaves a remainder of 1 when it is divided by 4.

I assume that n is an odd number. I want to prove that $n^2$ leaves a remainder of 1 when it is divided by 4.

An odd number is an integer which can be written in the form $2m + 1$ for some integer m. Since n is odd, $n = 2m + 1$ for some m.

Squaring n, I get

$$n^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 4(m^2 + m) + 1.$$

Since $4(m^2 + m)$ is divisible by 4, $n^2$ leaves a remainder of 1 when it is divided by 4.

This proves the conditional statement that if n is odd, then $n^2$ leaves a remainder of 1 when it is divided by 4.

Example. If a and b are integers, a divides b means that there is an integer c such that $ac = b$ . a divides b is written $a \mid b$ for short.

For example, $6 \mid 18$ because $6\cdot 3 = 18$ , $10 \mid 0$ because $10\cdot 0 = 0$ , and $-6 \mid 6$ since $(-6)\cdot (-1) = 6$ .

On the other hand, 3 does not divide 5, since there is no integer c such that $3\cdot c = 5$ . "3 does not divide 5" is written $3 \notdiv 5$ .

Suppose a, b, and c are integers. I'll prove that if $a \mid b$ and $b \mid c$ , then $a \mid c$ .

Suppose that $a \mid b$ and $b \mid c$ .Since $a \mid b$ , there is an integer m such that $am = b$ . Since $b \mid c$ , there is an integer n such that $bn = c$ .

Substitute $am = b$ into $bn = c$ to obtain $(am)n = c$ , or $a(mn) = c$ . Since $mn$ is an integer, it follows from the definition of divisibility that $a \mid c$ .

Note that when I introduced m and n, I was careful to use different letters than the a, b, and c that were already in use. Note also that after stating my assumptions, I translated those assumptions using the definition of divisibility. I asked myself: "What does it {\it mean} for a to divide b? What does it mean for b to divide c?"

When a proof involves a concept (like divisibility in this proof), you must have a clear idea of what it means. You should be able to write down a clear, correct definition before proceeding; if you can't remember the definition, look it up in your book or notes and write it down. Just having a vague idea of what something means is not enough when you're writing proofs.

Example. You know that $P \ifthen Q$ is always true if P is false: Anything follows from a false assumption. For example, I'll prove:

\qquad If $0 = 1$ , then $\pi = 100$ .

(Notice that both the antecedent and the consequent are false!)

Assume that $0 = 1$ . Multiply both sides by $\pi - 100$ to obtain

$$0\cdot(\pi - 100) = 1\cdot(\pi - 100), \quad\hbox{or}\quad 0 = \pi - 100.$$

Adding 100 to both sides, I obtain $\pi = 100$ . Hence, if $0 = 1$ , then $\pi = 100$ .

But note that I can do the following as well: Start with $0 = 1$ . Differentiate both sides to obtain $0 = 0$ . $0 = 0$ is true, even though $0 = 1$ is false.

People sometimes erroneously suppose that they can prove something by starting with what they want to prove, and working until they get a true statement --- which they suppose provides "confirmation" that the original statement is true. This example shows that the procedure is invalid, since a true conclusion may come from a false assumption.

Assuming what you want to prove is the most fundamental logical fallacy. It's called begging the question. In a formal debate, the {\it question} was the issue or statement being debated. Thus, begging the question referred to arguing for the truth of the statement by assuming that it was true. It's also called circular reasoning. Another way to see that this procedure is nonsensical is to observe that if you're trying to prove that P is true and you assume that P is true, then you're done: There's no need for an argument at all!

Example. Consider the following example from basic algebra. I'm going to solve the equation

$$x + 3 = \sqrt{x + 5}.$$

All the steps that follow are legitimate:

$$\eqalign{(x + 3)^2 &= (\sqrt{x + 5})^2 \cr x^2 + 6x + 9 &= x + 5 \cr x^2 + 5x + 4 &= 0 \cr (x + 1)(x + 4) &= 0 \cr}$$

The possible solutions are $x = -1$ and $x = -4$ . You can check that $x = -1$ works. However, if $x = -4$ ,

$$x + 3 = -1, \quad\hbox{while}\quad \sqrt{x + 5} = 1.$$

So $x = -4$ doesn't work. You may have been told that $x = -4$ is an "extraneous solution". But if you think about this, you might wonder how it is that a sequence of valid algebraic steps can lead to an incorrect solution.

To understand this, think about what I just proved. I assumed that $x + 3 = \sqrt{x + 5}$ , and from this I deduced that $x = -1$ or $x = -4$ . In other words, this is a conditional proof of the if-then statement

$$\hbox{``If $x + 3 = \sqrt{x + 5}$, then $x = -1$ or $x = -4$.''}$$

However, you know that a conditional statement $P \ifthen Q$ and its converse $Q \ifthen P$ aren't logically equivalent. Therefore, there is no reason that the following statement should be true:

$$\hbox{``If $x = -1$ or $x = -4$, then $x + 3 = \sqrt{x + 5}$.''}$$

And in fact, as I noted above, it's false!

In other words, when you "solve an equation" in algebra, you're really finding a set of solution candidates. This will not be exactly the set of solutions unless the steps in your derivation are reversible.

One of the steps in the derivation above is not reversible, and that is what leads to the "extraneous solution". Can you tell which step it is?

Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2009 by Bruce Ikenaga