Dividing into cases

Proofs by cases are often found in proofs for statements of the form \(\forall x \in U, Q(x)\).

Suppose that \(\forall x \in U, P_1(x) \vee \cdots \vee P_k(x)\) holds. Then \(\forall x \in U, Q(x)\) is logically equivalent to \(\bigwedge_{i = 1}^k \forall x \in U, P_i(x) \Rightarrow Q(x)\).

Thus, to prove \(\forall x \in U, Q(x)\), one can prove instead the following \(k\) statements: \[\begin{align} & \forall x \in U, P_1(x) \Rightarrow Q(x) \\ & \vdots \\ & \forall x \in U, P_k(x) \Rightarrow Q(x) \end{align}\] Such a proof is called a proof by cases since the predicates \(P_1(x),\ldots, P_k(x)\) divide the universe of discourse into \(k\) (not necessarily disjoint) cases.

Very often, one finds that \(P_k(x) = \neg (P_1(x) \vee \cdots \vee P_{k-1}(x)\).

Examples

1. Prove that for each \(x \in \mathbb{Z}\), \(x^2 \equiv x (\text{mod } 2).\)

   Proof.

   Let \(x \in \mathbb{Z}\).

   Case 1: \(x \equiv 0 (\text{mod } 2)\).

   By Proposition A2 here, we have \(x^2 \equiv 0^2 \equiv 0 \equiv x (\text{mod } 2).\)

   Case 2: \(x \equiv 1 (\text{mod } 2)\).

   By Proposition A2 here, we have \(x^2 \equiv 1^2 \equiv 1 \equiv x (\text{mod } 2).\)

2. Prove that for each \(x \in \mathbb{R}\), \(\lvert x + 1 \rvert + \lvert x - 1 \vert \geq 2\).

   Proof.

   Case 1: \(x \geq 1\).

   Note that \(x+1\) and \(x-1\) are both nonnegative in this case. Hence, \(\lvert x + 1 \rvert + \lvert x - 1 \vert=x+1 + (x-1) = 2x \geq 2\) as \(x \geq 1\).

   Case 2: \(-1 \leq x < 1\).

   Note that \(x+1\) is nonnegative but \(x-1\) is negative. Hence, \(\lvert x + 1 \rvert + \lvert x - 1 \vert= x+1 - (x-1) = 2\).

   Case 3: \(x < -1\).

   Note that \(x < -1\) is equivalent to \(-x > 1\).

   Also, \(x+1\) and \(x-1\) are both negative in this case. Hence, \(\lvert x + 1 \rvert + \lvert x - 1 \vert=-(x+1)-(x-1) = -2x \geq 2\) as \(-x > 1\).

Exhaustion

Proof by exhaustion (casually known as proof by brute force) is an extreme form of proof by cases. It is sometimes found in proofs of combinatorial results where basically one enumerates all the possible cases and check each one in turn. The number of cases considered can sometimes be reduced through observing symmetry or other insights.

Example

Prove that \(12\) cannot be written as \(a^2 + b^2\) where \(a\) and \(b\) are positive integers.

Proof. Without loss of generality, we may assume that \(a \leq b\) since \(12 = a^2 + b^2\) if and only if \(12 = b^2 + a^2\).

We build a table listing all possible choices of \(a\) and \(b\) with \(a \leq b\) to establish the given statement. Note that there is no need to consider values \(b > 3\) since if \(12 = a^2 + b^2\), then \(b^2 = 12 -a^2 \leq 12 - 1 = 11\), implying that \(b \leq 3\).

Remark. We could have avoided using exhaustion by considering three cases: 1. \(a = 1\); 2. \(a = 2\); 3. \(a = 3\). Give the details of such a proof.

Exercises

1. Prove that if \(n\) is an integer, then \(3n^2-n+8\) is even.

2. Prove that if \(x\) is a real number, then \(x^2 + 2|x - 1| \geq 1\).