Fact 6.4.1.
The following logical equivalence holds:
\begin{equation*}
(s_1 \lgcor s_2 \lgcor \dotsb \lgcor s_m) \lgccond t
\; \lgcequiv \;
(s_1 \lgccond t) \lgcand (s_2 \lgccond t) \lgcand \dotsb \lgcand (s_m \lgccond t)\text{.}
\end{equation*}
Section 6.4 Reduction to cases
Proof idea.
This is just an extended version of Example 2.2.6.
If
\begin{equation*}
C_1 \lgcor C_2 \lgcor \dotsb \lgcor C_m
\end{equation*}
is a tautology, then
\begin{equation*}
P
\; \lgcequiv \;
P \lgcand (C_1 \lgcor \dotsb \lgcor C_m)
\; \lgcequiv \;
(P \lgcand C_1) \lgcor \dotsb \lgcor (P \lgcand C_m)\text{.}
\end{equation*}
By substitution and Fact 6.4.1,
\begin{equation*}
P \lgccond Q \; \lgcequiv \;
(P \lgcand C_1 \lgccond Q) \lgcand \dotsb \lgcand (P \lgcand C_m \lgccond Q).
\end{equation*}
A conjunction is only true if each “factor” in the conjunction is true, so the conjunction on the right above can only be a tautology if each conditional \(P \lgcand C_1 \lgccond Q\) is a tautology. Therefore, when we have a collection of statements \(C_1,\dotsc,C_m\) so that
\begin{equation*}
C_1 \lgcor C_2 \lgcor \dotsb \lgcor C_m
\end{equation*}
is a tautology, we can prove \(P \lgccond Q \) by instead proving each of \(P \lgcand C_i \lgcimplies Q\) one at a time. This is also valid for universal statements, since \(\forall\) distributes over \(\lgcand\) (Proposition 4.2.6).
Now, having to prove many slightly more complicated statements \(P \lgcand C_i \lgcimplies Q\) seems like a lot more work than just proving the single simple statement \(P \lgccond Q\) — why would we want to go to all this extra effort?
Idea 6.4.2.
Each case statement \(C_i\) provides extra information that can be combined with the assumption that \(P\) is true to arrive at the conclusion that \(Q\) must also be true.
Procedure 6.4.3. Reduction to cases.
- To prove \(P\lgcimplies Q\text{,}\) determine a set of cases \(C_1, C_2, \dotsc, C_m\) such that \(C_1 \lgcor C_2 \lgcor \dotsb \lgcor C_m\) is true, then provide a separate proof of each logical implication \(P \lgcand C_i \lgcimplies Q\text{.}\)
- To prove \((\forall x)\bbrac{P(x)\lgcimplies Q(x)}\text{,}\) determine a set of cases \(C_1(x), C_2(x), \dotsc, C_m(x)\) such that\begin{equation*} (\forall x) \bbrac{C_1(x) \lgcor C_2(x) \lgcor \dotsb \lgcor C_m(x)} \end{equation*}is true, then provide a separate proof of each universally quantified logical implication \((\forall x)\bbrac{P(x) \lgcand C_i(x) \lgcimplies Q(x)}\text{.}\)
Worked Example 6.4.4.
Show \(n^2 - n\) is always even.
Solution.
Let \(P(n)\) represent the predicate “\(n\) is an integer” and let \(Q(n)\) represent the predicate “\(n^2 - n\) is even”, each with domain the integers. Note that \(P(n)\) is actually true for each \(n\) in the domain, since our original statement makes no extra premise on \(n\) besides its domain.
Suppose that \(n\) is an integer. Break into cases based on whether \(n\) is even or odd; in each case, proceed by direct proof.
Case \(n\) even.
If \(n\) is even, then there exists an integer \(m\) such that \(n = 2m\text{.}\) Then,
\begin{equation*}
n^2 - n = n(n-1) = 2m(2m - 1)
\end{equation*}
is also even.
Case \(n\) odd.
If \(n\) is odd, then \(n - 1\) is even, so there exists an integer \(m\) such that \(n - 1 = 2m\text{,}\) or \(n = 2m + 1\text{.}\) Then,
\begin{equation*}
n^2 - n = n(n-1) = (2m+1)(2m)
\end{equation*}
is even.
Warning 6.4.5.
Make sure your cases cover all possibilities! (Though it is not necessary that your cases by non-overlapping.)
Check your understanding.
Attempt Exercise 6.12.7.
