Proofs Involving Disjunctions

What do you do when a proof refuses to go through in one shot? You split the universe into cases that you can handle one at a time. Case analysis — the proof strategy for both proving and using disjunctions — is the universal "when in doubt, split" tactic. It turns a hard global argument into several easier local arguments, each of which only needs to handle a restricted situation. Done well, case analysis is elegant; done carelessly, it produces sprawling proofs that are correct but exhausting. This section teaches both the structural rule and the judgment of when to reach for it.

Proving a disjunction: two strategies

To prove $P \vee Q$, you have two options:

Strategy 1 — Establish one disjunct directly. Show that $P$ is true (or that $Q$ is true). One disjunct suffices.

Strategy 2 — Assume $\neg P$ and prove $Q$. This relies on the equivalence $P \vee Q \equiv \neg P \Rightarrow Q$. By adding $\neg P$ to your givens, you may get exactly the leverage needed to derive $Q$.

Strategy 2 is the workhorse. The equivalence $P \vee Q \equiv \neg P \Rightarrow Q$ is worth committing to memory: it turns "or" goals into conditional goals, which you already know how to attack.

Using a disjunctive given: proof by cases

If your givens include $P \vee Q$ and your goal is $R$, the standard strategy is proof by cases:

1. Case 1: Assume $P$. [Argue toward $R$.] Conclude $R$ in this case.
2. Case 2: Assume $Q$. [Argue toward $R$.] Conclude $R$ in this case.
3. Since $P \vee Q$ and $R$ follows in both cases, $R$ holds. $\blacksquare$

Inside Case 1 you may use $P$ (and any earlier givens). Inside Case 2 you may use $Q$. The two arguments are independent: they share givens that precede the case split but not the case-specific assumption.

Three or more cases

Case analysis is not limited to two cases. To prove something about an integer $n$, you might split:

• Even vs odd (mod 2) • $n \equiv 0, 1, 2 \pmod{3}$ • $n < 0$, $n = 0$, $n > 0$

The cases must be exhaustive — they must cover every possibility — but need not be mutually exclusive (though disjoint cases produce cleaner proofs). State the case split explicitly: "either $n \geq 0$ or $n < 0$; we handle each case."

When to reach for case analysis

Use case analysis when the goal involves a function that is defined piecewise (absolute value, max/min, floor/ceiling), when a given is naturally disjunctive ($|x| = 3$ means $x = 3 \vee x = -3$), or when a parity/sign distinction unlocks an otherwise sticky algebraic step. Avoid it when a single uniform argument works — case analysis is a tool of last resort because it bloats proofs. Two cases is fine; ten cases probably means you missed a unifying observation.

Common case splits in undergraduate proofs

1. Parity: every integer is even or odd. Used in irrationality, divisibility, and number-theory proofs.
2. Sign: $x > 0$, $x = 0$, $x < 0$. Standard for absolute-value arguments.
3. Set membership: for a fixed $A$, either $x \in A$ or $x \notin A$. Used in set-equality proofs.
4. Modular arithmetic: $n \equiv 0, 1, \ldots, m-1 \pmod m$. Used to prove divisibility identities like $n^3 - n \equiv 0 \pmod 6$.

Pause and think: To prove "for every integer $n$, $n(n+1)$ is even," the parity split is irresistible. Why? What concrete identity falls out of each case?

Try it

• Predict the case split before writing: which natural disjoint cases would you use for (a) "prove $n^2 + n$ is even for all integers $n$," (b) "prove $|x + y| \leq |x| + |y|$ for real $x, y$," (c) "prove every integer is the sum of two integers of the same parity"?
• Spot the flaw: a student writes "Case 1: $n$ is even. ... Case 2: $n$ is positive. ... Both cases handled, done." What went wrong?
• Disjunction goal: prove $\forall x \in \mathbb{R}, x \geq 0 \vee x < 0$ using Strategy 2 (assume the negation of one disjunct, derive the other).
• Skeleton-only: write the first sentence of each case for "for every integer $n$, either $n^2 \equiv 0 \pmod 4$ or $n^2 \equiv 1 \pmod 4$."
• When NOT to use cases: rewrite "prove that for all integers $a, b$, $a^2 + b^2 \geq 0$" without any case split. (Hint: a single observation suffices.)

A trap to watch for

The most insidious case-analysis error is non-exhaustive cases: splitting into Case 1 and Case 2 in a way that misses some scenarios. "Case 1: $x > 0$. Case 2: $x < 0$" forgets $x = 0$. "Case 1: $n$ is prime. Case 2: $n$ is composite" forgets $n = 0, 1$ and negative integers. Before declaring the proof complete, list your cases and verify they cover every possibility implied by the domain. A close cousin is overlapping cases that you treat as exclusive — harmless if the conclusion is the same in the overlap, but a source of subtle bugs otherwise. Best practice: aim for disjoint and exhaustive cases, and say so explicitly.

What you now know

You can prove a disjunction $P \vee Q$ by establishing one disjunct or by the equivalence-trick of assuming $\neg P$ and deriving $Q$. You can use a disjunctive given by case analysis — one sub-argument per case, with the cases exhaustive and (ideally) disjoint. You recognise common case splits (parity, sign, residue, membership) and you know when case analysis is the right tool versus when a uniform argument is cleaner. Combined with the conditional, quantifier, and biconditional strategies from earlier sections, you now have the full toolkit for the bulk of undergraduate-level proofs.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §3.5.
• Hammack, R. (2018). Book of Proof (3rd ed.). Open-source textbook, ch. 7 (Cases).
• Solow, D. (2014). How to Read and Do Proofs (6th ed.). Wiley, ch. 11 (Cases).
• Pierce, B. C. et al. (2018). Software Foundations, Vol. 1: Logical Foundations. Online textbook (Coq), ch. 'Logic' (or destruct, case tactic).
• Bloch, E. D. (2011). Proofs and Fundamentals. Springer, §3.4 (Proof by cases).