Questions: Proving by Cases and Exhaustion

Question 1

A student wants to prove a statement about all real numbers using proof by cases. They split into: (i) x > 0, (ii) x < 0. Is this proof complete?

• A. Yes — positive and negative reals cover all reals
• B. No — the cases are not mutually exclusive
• C. No — the case x = 0 is missing, making the proof non-exhaustive
• D. No — you need at least four cases for a proof by cases to be valid

Answer: (C)

The cases x > 0 and x < 0 are mutually exclusive (they cannot both be true), but they are not exhaustive — they omit x = 0. Since 0 is a real number, the proof has a gap and is incomplete. A proof by cases fails the moment any element of the domain is not covered by at least one case. The requirement is exhaustiveness, not a minimum number of cases — two cases are fine if they truly cover everything.

Question 2

A proof of 'P holds for all integers' is conducted in two cases: n is even and n is odd. Within the even case, the prover writes n = 2k and uses that fact. What is the structural advantage of having the case assumption?

• A. It allows the prover to assume the conclusion P is true inside the case
• B. It supplies an additional hypothesis — the concrete form n = 2k — that would not be available in a general direct proof
• C. It eliminates the need to prove the odd case separately
• D. It converts the proof into a proof by contradiction

Answer: (B)

Within a case, you know not just the original hypothesis but also the case condition itself — here, that n is even, which means n = 2k for some integer k. That concrete algebraic form is often exactly what enables the sub-proof: it unlocks arithmetic manipulations that are unavailable when n is an arbitrary integer. This is the real power of case-splitting: each case provides extra fuel for its own sub-argument. Options A and C misstate the structure — you still prove P separately in each case, and the case assumption never lets you assume the conclusion.

Question 3

In a proof by cases, it is acceptable for the cases to overlap — i.e., some elements can belong to more than one case.

• T. True
• F. False

Answer: True

Cases must be exhaustive (collectively cover the whole domain) but need not be mutually exclusive. If an element falls under multiple cases, it just means you prove the statement for that element in two different ways — both proofs are valid and the conclusion still holds. For example, dividing integers into {n ≡ 0 mod 6}, {n ≡ 1 mod 6}, ..., {n ≡ 5 mod 6} is fine even though you could have used just even/odd. The danger is missing cases, not having too many.

Question 4

If you prove a statement for positive integers and separately prove it for even integers, you have proven the statement for most non-negative integers.

• T. True
• F. False

Answer: False

Positive integers and even integers are not an exhaustive partition of the non-negative integers. Positive integers cover {1, 2, 3, ...} and even integers cover {0, 2, 4, ...}. Together they miss only nothing... wait — actually they do cover all non-negative integers (0 is even, and all positive integers are covered). But the better point is: the cases must be explicitly shown to collectively cover the domain. Proving for positive integers and for even integers is redundant in places and the case split is not the natural exhaustive partition. More concretely, if you tried the analogous trick for all integers — proving for positive and for even — you'd miss negative odd integers entirely.

Question 5

Why does the proof-by-cases technique succeed when a direct proof would be unwieldy or impossible?

Model answer: Because within each case, you gain the case assumption as an additional hypothesis that restricts which elements you're reasoning about. A direct proof must handle all elements simultaneously without that extra information. When a statement has different 'reasons' for being true in different parts of the domain, no single chain of reasoning covers all of them — but separate proofs, each empowered by their case's specific assumption, can each succeed.

The logical mechanism is a disjunction: if you know (P₁ ∨ P₂ ∨ ... ∨ Pₙ) covers the domain, and you show Q follows from each Pᵢ separately, then Q holds everywhere. The cases create sub-problems with stronger starting assumptions, and the reassembly is guaranteed by logical disjunction. This is why integer parity proofs are so natural for this technique — every integer is either even or odd, and each form gives you a concrete substitution that drives the algebra.