A * conditional proof* is a proof of an
"if-then" (conditional) statement.

Since any proof makes *some* assumptions, you might say that
every proof is a conditional proof. But there are different kinds of
assumptions you might make. Consider the following conditional
statements:

"If , then ."

"If and , then ."

There's an obvious sense in which the "if" part of the second statement has more content that the "if" part of the first statement. In the first statement, the "if" part doesn't give you much to go on. In the second statement, you would suspect that the number 7 is somehow related to the "then" part.

In this section, I'll look at proofs of conditional statements where the "if" part carries that kind of significant information.

* Example.* Prove that if and , then .

To prove the statement, you *assume* that . Now

Likewise,

If I add and , I get . 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, , so adding *this* inequality to , I obtain

Notice the *conditional* nature of the conclusion. It's
certainly not true that *for any*
real number x. (For example, it's false if .) The conclusion is true *if* the assumption
is true.

The last example shows how you write a conditional proof. In this
situation, you're trying to prove a statement of the form , 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 is true.

* Example.* (a) Prove that if x is a real number
and , then .

(b) Give a specific example to show that the converse is false.

(a) Suppose . Then

Thus, , , and x are all positive. The product of positive numbers is positive, so

(b) Take . Then

However, .

* Example.* Premises:

Prove: .

To prove the conditional statement , I *assume* the "if" part and try to prove the "then" part .

The *conclusion* was deduced on
line 8. Together with the *assumption* in line 3, this proves the conditional .

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

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

An *odd number* is an integer which can be written in the form
for some integer m. Since n is odd, for some m.

Squaring n, I get

Since is divisible by 4, leaves a remainder of 1 when it is divided by 4.

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

* Example.* (* Proving the
contrapositive*) Let n be an integer. Prove that if is not even, then n is not even.

Recall that the conditional is logically equivalent to its contrapositive . In some cases, you use this to prove a conditional statement by replacing it with its contrapositive.

In this example, the given conditional statement is kind of awkward: Both the "if" and "then" parts are negative statements. And if I try to prove this conditional statement by assuming the "if" part --- that is, assuming that is not even --- it isn't obvious how to proceed.

Instead, I replace the statement with its contrapositive: "If n is even, then is even."

Begin by assuming the "if" part: Suppose n is even. By definition, this means that , where m is an integer. Then

Now is an integer, so is even (by definition of "even"). Hence, is even.

Since I've proved the contrapositive, this proves the original statement.

If a and b are integers, a * divides* b means
that there is an integer c such that . a divides b is written for short.

For example, because , because , and since .

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

* Example.* Suppose a, b, and c are integers.
Prove that if and , then .

Suppose that and .Since , there is an integer m such that . Since , there is an integer n such that .

Substitute into to obtain , or . Since is an integer, it follows from the definition of divisibility that .

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
*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.* Prove: "If , then ."

Notice that both the "if" and "then" parts are false!

Assume that . Multiply both sides by , then do some algebra:

Hence, if , then .

Note that I can do the following as well: Start with . Differentiate both sides to obtain . is true, even though 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 *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.* An integer is *
divisible by* 3 if it can be written in the form for some integer m.

Prove that if n is divisible by 3, then is divisible by 3.

Suppose n is divisible by 3. Then for some integer m. So

The last expression is 3 times an integer. Hence, is divisible by 3.

Note that I didn't stop with " " and say "the sum of integers divisible by 3 must be divisible by 3". That's true, but I haven't proved it. Can you do it?

Copyright 2018 by Bruce Ikenaga