6.4: Reduction to Cases

Fact $\PageIndex{1}$

The following logical equivalence holds:

$$\begin{equation*} (s_1 \lor s_2 \lor \cdots \lor s_m) \rightarrow t \; \Leftrightarrow \; (s_1 \rightarrow t) \land (s_2 \rightarrow t) \land \cdots \land (s_m \rightarrow t)\text{.} \end{equation*}$$

Proof idea

This is just an extended version of Example 2.2.3.

If

$$\begin{equation*} C_1 \lor C_2 \lor \cdots \lor C_m \end{equation*}$$

is a tautology, then

$$\begin{equation*} P \; \Leftrightarrow \; P \land (C_1 \lor \cdots \lor C_m) \; \Leftrightarrow \; (P \land C_1) \lor \cdots \lor (P \land C_m)\text{.} \end{equation*}$$

By substitution and Fact $\PageIndex{1}$,

$$\begin{equation*} P \rightarrow Q \; \Leftrightarrow \; (P \land C_1 \rightarrow Q) \land \cdots \land (P \land C_m \rightarrow 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 \land C_1 \rightarrow Q$ is a tautology. Therefore, when we have a collection of statements $C_1,\ldots ,C_m$ so that

$$\begin{equation*} C_1 \lor C_2 \lor \cdots \lor C_m \end{equation*}$$

is a tautology, we can prove $P \rightarrow Q$ by instead proving each of $P \land C_i \Rightarrow Q$ one at a time. This is also valid for universal statements, since $\forall$ distributes over $\land$ (Proposition 4.2.2).

Now, having to prove many slightly more complicated statements $P \land C_i \Rightarrow Q$ seems like a lot more work than just proving the single simple statement $P \rightarrow Q$ — why would we want to go to all this extra effort?

Idea $\PageIndex{1}$

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 $\PageIndex{1}$: Reduction to cases

• To prove $P\Rightarrow Q\text{,}$ determine a set of cases $C_1, C_2, \ldots , C_m$ such that $C_1 \lor C_2 \lor \cdots \lor C_m$ is true, then provide a separate proof of each logical implication $P \land C_i \Rightarrow Q\text{.}$
• To prove $(\forall x)(P(x)\Rightarrow Q(x))\text{,}$ determine a set of cases $C_1(x), C_2(x), \ldots , C_m(x)$ such that
  $$\begin{equation*} (\forall x) (C_1(x) \lor C_2(x) \lor \cdots \lor C_m(x)) \end{equation*}$$
  is true, then provide a separate proof of each universally quantified logical implication $(\forall x)(P(x) \land C_i(x) \Rightarrow Q(x))\text{.}$

Example $\PageIndex{1}$

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 $\PageIndex{1}$

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.