2.3: Techniques for Proving Conditional Propositions

Each of the theorems that we proved in Section 2.1 are examples of conditional propositions. However, some of the statements were disguised as such. For example, Theorem 2.3 states, “The sum of two consecutive integers is odd.” We can reword this theorem as, “If n ∈ Z, then n + (n + 1) is odd.”

Problem 2.47. Reword Theorem 2.7 so that it explicitly reads as a conditional proposition.

Each of the proofs that you produced in Section 2.1 had the same format, which we refer to as a direct proof.

Skeleton Proof 2.48 (Proof of A =⇒ B by direct proof). If you want to prove the implication A =⇒ B via a direct proof, then the structure of the proof is as follows.

Proof. [State any upfront assumptions.] Assume A.

... [Use definitions and known results to derive B] ...

Therefore, B.

Take a few minutes to review the proofs that you wrote in Section 2.1 and see if you can witness the structure of Skeleton Proof 2.48 in your proofs.

The upshot of Theorem 2.39 is that if you want to prove a conditional proposition, you can prove its contrapositive instead. This approach is called a proof by contraposition.

Skeleton Proof 2.49 (Proof of A =⇒ B by contraposition). If you want to prove the implication A =⇒ B by proving its contrapositive ¬B =⇒ ¬A instead, then the structure of the proof is as follows.

Proof. [State any upfront assumptions.] We will utilize a proof by contraposition.

Assume ¬B.

... [Use definitions and known results to derive ¬A] ...

Therefore, ¬A. We have proved the contrapositive, and hence if A, then B.

We have introduced the logical symbols ¬, ∧, ∨, =⇒, and ⇐⇒ since it provides a convenient way of discussing the formality of logic. However, when writing mathematical proofs, you should avoid using these symbols.

Problem 2.50. Consider the following statement:

If x ∈ Z such that x2 is odd, then x is odd.

The items below can be assembled to form a proof of this statement, but they are currently out of order. Put them in the proper order.

1. Assume that x is an even integer.
2. We will utilize a proof by contraposition.
3. Thus, x² is twice an integer.
4. Since x = 2k, we have that x² = (2k)² = 4k².
5. Since k is an integer, 2k² is also an integer.
6. By the definition of even, there is an integer k such that x = 2k.
7. We have proved the contrapositive, and hence the desired statement is true.
8. Assume x ∈ Z.
9. By the definition of even integer, x² is an even integer.
10. Notice that x2 = 2(2k² ).

Prove the next two theorems by proving the contrapositive of the given statement.

Theorem 2.51. If n ∈ Z such that n² is even, then n is even.

Theorem 2.52. If n,m ∈ Z such that nm is even, then n is even or m is even.

Suppose that we want to prove some proposition P (which might be something like A =⇒ B or even more complicated). One approach, called proof by contradiction, is to assume ¬P and then logically deduce a contradiction of the form Q∧¬Q, where Q is some proposition. Since this is absurd, the assumption ¬P must have been false, so P is true. The tricky part about a proof by contradiction is that it is not usually obvious what the statement Q should be.

Skeleton Proof 2.53 (Proof of P by contradiction). Here is what the general structure for a proof by contradiction looks like if we are trying to prove the proposition P .

Proof. [State any upfront assumptions.] For sake of a contradiction, assume ¬P .

... [Use definitions and known results to derive some Q and its negation ¬Q.] ...

This is a contradiction. Therefore, P .

Proof by contradiction can be useful for proving statements of the form A =⇒ B, where ¬B is easier to “get your hands on,” because ¬(A =⇒ B) is logically equivalent to A ∧ ¬B (see Corollary 2.41).

Skeleton Proof 2.54 (Proof of A =⇒ B by contradiction). If you want to prove the implication A =⇒ B via a proof by contradiction, then the structure of the proof is as follows.

Proof. [State any upfront assumptions.] For sake of a contradiction, assume A and ¬B.

... [Use definitions and known results to derive some Q and its negation ¬Q.] ...

This is a contradiction. Therefore, if A, then B.

Problem 2.55. Assume that x ∈ Z. Consider the following proposition: If x is odd, then 2 does not divide x.

(a) Prove the contrapositive of this statement.

(b) Prove the statement using a proof by contradiction.

Prove the following theorem via a proof by contradiction. Afterward, consider the difficulties one might encounter when trying to prove the result more directly. The given statement is not true if we replace N with Z. Do you see why?

Theorem 2.56. Assume that x,y ∈ N. If x divides y, then x ≤ y.

Oftentimes a conditional proposition can be proved via a direct proof and by using a proof by contradiction. Most mathematicians view a direct proof to be more elegant than a proof by contradiction. When approaching the proof of a conditional proposition, you should strive for a direct proof. In general, if you are attempting to prove A =⇒ B using a proof by contradiction and you end up with ¬B and B (which yields a contradiction), then this is evidence that a proof by contradiction was unnecessary. On the other hand, if

you end up with ¬Q and Q, where Q is not the same as B, then a proof by contradiction is a reasonable approach. we need to prove both

In light of Theorem 2.29, if we want to prove a biconditional of the form A ⇐⇒ B, A =⇒ B and B =⇒ A. You should always make it clear to the reader when you are proving each implication. One approach is to label each subproof with “(=⇒)” and “(⇐=)” (including the parentheses), respectively. Occasionally, you will discover that the proof of one implication is exactly the reverse of the proof of the other implication. If this happens to be the case, you may skip writing two subproofs and simply write a single proof that chains together each step using biconditionals. Such proofs will almost always be shorter, but can be challenging to write in an eloquent way. It is always a safe bet to write a separate subproof for each implication.

When proving each implication of a biconditional, you may choose to utilize a direct proof, a proof by contraposition, or a proof by contradiction. For example, you could prove the first implication using a proof by contradiction and a direct proof for the second implication.

The following theorem provides an opportunity to gain some experience with writing proofs of biconditional statements.

Theorem 2.57. Let n ∈ Z. Then n is even if and only if 4 divides n².