6.5: Statements Involving Disjunction

First, let's consider a conditional statement with a disjunction on the hypothesis side. To prove a statement of the form \((P_1 \lor P_2) \Rightarrow Q\text{,}\) we can use Fact 6.4.1 to decompose into two conditionals:

\begin{equation*} (P_1 \lor P_2) \rightarrow Q \Leftrightarrow (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \text{.} \end{equation*}

Appealing to the properties of conjunction, as in our discussion of reduction to cases, we see that we can prove \(P_1 \Rightarrow Q\) and \(P_2 \Rightarrow Q\) by separate proofs.

What about a conditional with a disjunction on the conclusion side? To prove a statement of the form \(P \Rightarrow (Q_1 \lor Q_2)\text{,}\) we can again reduce to cases, but in a sort of tricky way. For any statement, there are only two possibilities — either the statement is true or it is false. (See Basic Tautology 3 in Example 1.4.1. Apply this fact to one of the statements we are trying to prove.

Procedure \(\PageIndex{1}\): Proof of conditional involving disjunction

To prove a statement of the form \(P \Rightarrow (Q_1 \lor Q_2)\text{,}\) start by assuming that \(P\) is true and \(Q_1\) is false. Try to show that these assumptions lead to \(Q_2\) being true.

Idea \(\PageIndex{1}\)

There are only two possibilities for \(Q_1\text{:}\) either it is true or it is false. If \(Q_1\) is true, then \(Q_1 \lor Q_2\) is already true, regardless of the truth values of \(P\) and \(Q_2\text{,}\) so there is nothing to prove in this case. On the other hand, if \(Q_1\) is false, the only way \(Q_1 \lor Q_2\) could be true is if \(Q_2\) is true.

Note \(\PageIndex{1}\)

• Also see Exercise 2.5.3.
• Of course, you can swap the roles of \(Q_1\) and \(Q_2\) above: you could also start by assuming that \(P\) is true and \(Q_2\) is false, then try to show that this leads to \(Q_1\) being true.
• Another strategy is to attempt a proof by contradiction (discussed in Section 6.9 below). By DeMorgan, \(\neg(Q_1 \lor Q_2) \Leftrightarrow \neg Q_1 \land \neg Q_2\text{,}\) so for this strategy, you should start by assuming that \(P\) is true and both \(Q_1\) and \(Q_2\) are false. Then, try to arrive at a contradiction.

Example \(\PageIndex{1}\)

Prove: Every odd number is either \(1\) more or \(3\) more than a multiple of \(4\text{.}\)

Solution

Let \(P(n)\) represent the predicate “\(n\) is odd”, let \(Q_1(n)\) represent the predicate “\(n\) is \(1\) more than a multiple of \(4\)”, and let \(Q_2(n)\) represent the predicate “\(n\) is \(3\) more than a multiple of \(4\)”, each with domain the integers.

Start by assuming that \(n\) is an odd number that is not \(1\) more than a multiple of \(4\text{.}\) We must now try to show that \(n\) is \(3\) more than a multiple of \(4\text{.}\) We know that \(n\) is odd, so there exists a number \(m\) such that \(n = 2m + 1\text{.}\) However, since \(n\) is not \(1\) more than a multiple of \(4\text{,}\) \(2m\) cannot be a multiple of \(4\text{,}\) and so \(m\) cannot be a multiple of \(2\text{.}\) Therefore, \(m\) is also odd, and so there exists another number \(\ell\) such that \(m = 2\ell + 1\text{.}\) Then

\begin{equation*} n = 2m + 1 = 2(2\ell + 1) + 1 = 4\ell + 3 \text{,} \end{equation*}

which says that \(n\) is \(3\) more than a multiple of \(4\text{,}\) as desired.