11.2. Proof by Cases

There is another proof mechanism which is called proof by cases. This is also called exhaustive proof. So if you want to prove an implication of the form p → q, where p and q are propositions, and if your proposition P can be decomposed into conjunction of various other propositions say n propositions, then p → q is logically equivalent to p → q, conjunction 1 p → q and so on.

Proof by cases, or exhaustive proof, is a technique used to prove implications, specifically of the form p → q. In this context, p is a proposition that can be broken down into multiple cases (like p1, p2, ..., pn). To prove the implication, we show that for every case of p, the conclusion q holds true. This approach allows us to exhaust all possible situations to ensure that our conclusion is valid regardless of which specific case we are in.

Think of proof by cases like planning for a picnic. You have three different weather scenarios to prepare for: sunny, rainy, and windy. For each type of weather, you have different things to pack (like sunscreen for sunny days, umbrellas for rain, and weight for windy days). If you can show that, regardless of the weather, you will have everything needed for a successful picnic, you have effectively planned for all cases.

So if I want to prove a statement that ꓯ n, if n is an integer, then n² ≥ n. This is a universally quantified statement. And now if I apply the universal generalization, you will be choosing an arbitrary n and you will be trying to prove that this property is true for that arbitrarily chosen integer. But now that arbitrarily chosen integer can be positive, it can be negative, it can be 0. You have 3 possible cases right for this arbitrarily chosen n.

When applying proof by cases to the statement 'for all n, if n is an integer, then n² ≥ n', we first note that n can take three types of values: positive, negative, and zero. Therefore, we will examine each of these cases separately:

1. Case 1: When n is 0. In this case, n² = 0, which is equal to n.
2. Case 2: When n is a positive integer. In this case, any positive integer squared is greater than or equal to itself (e.g. 1² = 1, 2² = 4).
3. Case 3: When n is a negative integer. If n is negative, the square of any negative integer is always positive, which is greater than n. Thus, in all three scenarios, the original statement holds true, confirming that n² ≥ n for any integer n.

Imagine you're testing different types of fruits: apples, oranges, and bananas. You need to confirm a statement: 'All these fruits are sweet'. You check each type of fruit: apples are sweet, oranges are sweet, and bananas are sweet. Since you found sweetness in all fruit types, just like proving each case ensures correctness for n, you've shown that the statement holds true for the entire group.

There is also something called without loss of generality, which we very often encounter while writing the proof. In short form they call it as w.l.o.g. So let me demonstrate we have what exactly I mean by without loss of generality.

The phrase 'without loss of generality' (w.l.o.g) is used in proof by cases to streamline the process when the cases are symmetric. When performing a proof, if you find that two cases are equivalent (e.g. whether x is odd or y is odd), you can simply prove one case without needing to individually prove the symmetric counterpart. This simplifies the proof while still ensuring that all cases are accounted for.

Think of cooking with two identical pots. If you want to show that either pot can hold boiling water without specifying which pot you use, you can say 'without loss of generality, let’s use pot A'. Since both pots are identical, it suffices to prove for pot A, conveying that the outcome will hold for pot B as well without additional proof.

Since these are the three possible cases for your arbitrarily chosen n and you have chosen that p → q is true p → q is true and p → q is true.

In conclusion, by proving that the implication p → q is true for all three cases of n (0, positive, and negative), we establish that the original statement is universally true. This comprehensive proof covers every possibility, ensuring the statement holds under all specified conditions. Thus, proof by cases is an effective strategy to validate universally quantified statements.

Think of a toy company trying to ensure all toys can withstand different types of play—throwing, dropping, and scratching. By testing each type of play exhaustively, they confirm that all toys are robust under every condition, just as proof by cases confirms a mathematical statement holds under all defined scenarios.

--