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.